列表

详情

NC20818. 小K种妹妹

描述

众所周知，小K有一个可耐的骨科限定妹妹，所以小K很擅长打表，但是本题与打表无关

小K加入了某客组织，在这里他学会了种妹妹的方法，通过这种方式，小K可以获得更多的妹妹。

小K很希望可以获得更多的妹妹来关照，所以小K种下了一棵妹妹树，善于观察的他发现了每个妹妹都有一个可爱度……

由于小K的精力有限，他只能照顾可爱度大于某个值的妹妹。

他想知道某个子树中可爱度大于x的妹妹个数。

某个妹妹的可爱度可能发生变化……

树上可能会出现一只新的妹妹……

但是……树枝可能会断裂，于是，小K惊讶地发现，他的面前变成了一片妹妹树组成的森林……
初始你有一个有n个节点的有根妹妹树（根妹妹（节点）为1），妹妹（节点）编号为1-n，每个妹妹有一个可爱度，她有可能会变成森林。、
受某客组织神秘力量的影响，所以妹妹树支持以下几种操作：

0 u x 询问以u为根的子妹妹树中，可爱度严格大于x的妹妹的个数。

1 u x 把第u个妹妹的可爱度改成x。

2 u x 添加一个编号为"当前树中妹妹数+1"的妹妹，其父节点为u，其可爱度为x。

3 u 删除妹妹u与其父节点之间的路径。此时u的父节点变成叶子节点，u变成分裂出的树的根。


输入描述

输入第一行包括一个正整数n(1<=n<=100000)，代表树上的初始妹妹数。
接下来n-1行，每行2个整数u,v，为树上的一条无向边。
任何时刻，树上的任何妹妹的可爱度大于等于0，且两两不同。
接下来1行，包括n个整数wi，表示初始时每个妹妹的可爱度。
接下来1行，包括1个整数m(1<=m<=100000)，表示操作总数。
接下来m行，每行最开始包括一个整数op,
若op=3，该行还会有一个整数u；
若op不等于3，该行还会有两个整数u,x；

输出描述

对每个op=0，输出一行，包括一个整数，表示某个子树中可爱度大于x的妹妹个数。

示例1

输入: 

2
1 2
10 20
1
0 1 5

输出: 

2

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 844ms, 内存消耗: 16232K, 提交时间: 2018-11-02 19:25:05 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define N 200006
#define M 400006

using namespace std;
inline int read(){
    int ret=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while ('0'<=ch&&ch<='9'){
        ret=ret*10-48+ch;
        ch=getchar();
    }
    return ret;
}

const int KK=400;
vector<int> seq[N];

struct edge{
    int adj,next;
    edge(){}
    edge(int _adj,int _next):adj(_adj),next(_next){}
} e[M];
int n,g[N],m;
void AddEdge(int u,int v){
    e[++m]=edge(v,g[u]);g[u]=m;
    e[++m]=edge(u,g[v]);g[v]=m;
}
int w[N];

vector<int> nxt[N];
int fa[N],bl[N],sz[N],cnt,top[N];
void refresh(int u,int p){
    for (;p>0&&seq[u][p]<seq[u][p-1];--p)swap(seq[u][p],seq[u][p-1]);
    for (;p<sz[u]-1&&seq[u][p]>seq[u][p+1];++p)swap(seq[u][p],seq[u][p+1]);
}
void newnode(int u){
    if (sz[bl[fa[u]]]==KK){
        sz[bl[u]=++cnt]=0;
        top[cnt]=u;
    }
    else bl[u]=bl[fa[u]];
    ++sz[bl[u]];
}
void dfs(int u){
    newnode(u);
    for (int i=g[u];i;i=e[i].next){
        int v=e[i].adj;
        if (v==fa[u]) continue;
        fa[v]=u;
        dfs(v);
    }
}
void dfs_pre(int u){
    seq[bl[u]].push_back(w[u]);++sz[bl[u]];
    for (int i=g[u];i;i=e[i].next)if (fa[e[i].adj]==u){
        int v=e[i].adj;
        if (bl[v]==bl[u]) dfs_pre(v);
        else nxt[bl[u]].push_back(bl[v]);
    }
}
void prepare(int id){
    seq[id].clear();vector<int>(seq[id]).swap(seq[id]);
    nxt[id].clear();vector<int>(nxt[id]).swap(nxt[id]);
    sz[id]=0;
    dfs_pre(top[id]);
    sort(seq[id].begin(),seq[id].end());
}

int solve(int u,int lmt){
    int l=-1,r=sz[u],mid;
    while (l+1<r){
        mid=l+r>>1;
        if (seq[u][mid]<=lmt) l=mid;
        else r=mid;
    }
    int ret=sz[u]-l-1;
    for (int j=nxt[u].size()-1;j>=0;--j) ret+=solve(nxt[u][j],lmt);
    return ret;
}
int query(int u,int lmt){
    if (bl[u]!=bl[fa[u]]) return solve(bl[u],lmt);
    int ret=w[u]>lmt;
    for (int i=g[u];i;i=e[i].next)if (fa[e[i].adj]==u)ret+=query(e[i].adj,lmt);
    return ret;
}

void modify(int u,int x){
    int p;
    for (int i=0;i<sz[bl[u]];++i)
        if (seq[bl[u]][i]==w[u]){p=i;break;}
    w[u]=x;seq[bl[u]][p]=x;
    refresh(bl[u],p);
}

void create(int u,int x){
    AddEdge(u,++n);fa[n]=u;w[n]=x;
    int tmp=cnt;
    newnode(n);
    seq[bl[n]].push_back(w[n]);
    refresh(bl[n],sz[bl[n]]-1);
    if (tmp<cnt) nxt[bl[u]].push_back(cnt);
}

void dfs_update(int u,int last,int now){
    bl[u]=now;
    for (int i=g[u];i;i=e[i].next)if (fa[e[i].adj]==u)
        if (bl[e[i].adj]==last) dfs_update(e[i].adj,last,now);
}

void cut(int u){
    int lst=bl[u];
    if (bl[fa[u]]!=bl[u]){
        int f=bl[fa[u]];
        for (vector<int>::iterator it=nxt[f].begin();it!=nxt[f].end();++it)
            if ((*it)==lst){nxt[f].erase(it);break;}
        fa[u]=0;return;
    }
    top[++cnt]=u;
    fa[u]=0;
    dfs_update(u,lst,cnt);
    prepare(lst);
    prepare(cnt);
}

int main(){
    n=read();
    memset(g,0,sizeof(g));m=1;
    for (int i=1;i<n;++i) AddEdge(read(),read());
    for (int i=1;i<=n;++i) w[i]=read();
    fa[1]=0;bl[0]=0;sz[0]=KK;cnt=0;
    dfs(1);
    int lastans=0;
    for (int i=1;i<=cnt;++i) prepare(i);
    for (int Q=read();Q;Q--){
        int op=read(),u=read()^lastans,x;
        if(op<3) x=read()^lastans;
        else cut(u);
        if(op==0)printf("%d\n",lastans=query(u,x));
        if(op==1)modify(u,x);
        if(op==2)create(u,x);
    }
}

C++14(g++5.4) 解法, 执行用时: 1319ms, 内存消耗: 11744K, 提交时间: 2018-11-08 13:52:36 

#include<bits/stdc++.h>
#define ll  long long
//#define int long long
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define pa pair<int,int>
#define mkp(a,b) make_pair(a,b)
const int N=1e5+10;
const int mod=998244353;
using namespace std;

struct block
{
	vector<int> v;
	void clear(){v.clear();}
	void insert(int x){v.insert(lower_bound(v.begin(),v.end(),x+1),x);}
	void erase(int x){v.erase(lower_bound(v.begin(),v.end(),x));}
	void modify(int x,int y){erase(x),insert(y);}
	int query(int x){return v.end()-upper_bound(v.begin(),v.end(),x);}
	int size(){return v.size();}
}blo[N];
int tot,ver[N<<2],head[N],nxt[N<<2],first[N];
inline void add(int u,int v){ver[++tot]=v,nxt[tot]=head[u],head[u]=tot;}
inline void addb(int u,int v){ver[++tot]=v,nxt[tot]=first[u],first[u]=tot;}
int n,B,a[N],fa[N],belong[N],bat[N],cnt;
void dfs(int u,int f)
{
	fa[u]=f;
	if(u==1||blo[belong[f]].size()==B) blo[belong[u]=++cnt].insert(a[u]),addb(belong[f],belong[u]),bat[cnt]=belong[f];
 	else blo[belong[u]=belong[f]].insert(a[u]);
 	for(int i=head[u];i;i=nxt[i]) if(ver[i]!=f) dfs(ver[i],u);
}
int Y,ans;
void block_dfs(int u)
{
	ans+=blo[u].query(Y);
	for(int i=first[u];i;i=nxt[i]) if(bat[ver[i]]==u) block_dfs(ver[i]);
}
void find(int u,int f)
{
	if(a[u]>Y) ans++;
	for(int i=head[u];i;i=nxt[i])if(ver[i]!=f&&fa[ver[i]]==u)
	{
		if(belong[ver[i]]==belong[u]) find(ver[i],u);
		else block_dfs(belong[ver[i]]);
	}
}
int c[N],d[N];
void cont(int u,int f)
{
	c[++*c]=u;
	for(int i=head[u];i;i=nxt[i]) if(ver[i]!=f&&fa[ver[i]]==u)
	{
		if(belong[ver[i]]==belong[u]) cont(ver[i],u);
		else d[++*d]=belong[ver[i]];
	}
}
int main()
{
	scanf("%d",&n); B=sqrt(n);
	for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	dfs(1,0);
	int q; scanf("%d",&q);
	int lastans=0;
	while(q--)
	{
		int op,u,v; scanf("%d",&op);
		if(op==0)
		{
			scanf("%d%d",&u,&v); u^=lastans,v^=lastans;
			Y=v,ans=0;
			find(u,fa[u]);
			printf("%d\n",lastans=ans);
		}
		else if(op==1)
		{
			scanf("%d%d",&u,&v); u^=lastans,v^=lastans;
			blo[belong[u]].modify(a[u],v); a[u]=v;
		}
		else if(op==2)
		{
			scanf("%d%d",&u,&v); u^=lastans,v^=lastans;
			a[++n]=v;
			add(u,n),add(n,u);
			fa[n]=u;
			if(blo[belong[u]].size()==B) blo[belong[n]=++cnt].insert(a[n]),addb(belong[u],belong[n]),bat[cnt]=belong[u];
			else blo[belong[n]=belong[u]].insert(a[n]);
		}
		else
		{
			scanf("%d",&u); u^=lastans;
			if(belong[u]!=belong[fa[u]]) {fa[u]=0,bat[belong[u]]=0;continue; }
			cont(u,fa[u]);
			belong[u]=++cnt;
			for(int i=1;i<=*c;i++)
			{
				blo[belong[fa[u]]].erase(a[c[i]]);
				blo[cnt].insert(a[c[i]]);
				belong[c[i]]=cnt;
			}
			for(int i=1;i<=*d;i++)
			{
				addb(cnt,d[i]),bat[d[i]]=cnt;
			}
			fa[u]=0,*c=*d=0;
		}
	}    
return 0;
}
/*

*/

上一题

© 2024 nowcoder.com