3720: Gty的妹子树

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1440 Solved: 482
[Submit][Status][Discuss]

Description

我曾在弦歌之中听过你，

檀板声碎，半出折子戏。

舞榭歌台被风吹去，

岁月深处尚有余音一缕……

Gty神(xian)犇(chong)从来不缺妹子……

他来到了一棵妹子树下，发现每个妹子有一个美丽度……

由于Gty很哲♂学，他只对美丽度大于某个值的妹子感兴趣。

他想知道某个子树中美丽度大于k的妹子个数。

某个妹子的美丽度可能发生变化……

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

维护一棵初始有n个节点的有根树(根节点为1)，树上节点编号为1-n，每个点有一个权值wi。

支持以下操作：

0 u x          询问以u为根的子树中，严格大于x的值的个数。(u^=lastans,x^=lastans)

1 u x          把u节点的权值改成x。(u^=lastans,x^=lastans)

2 u x          添加一个编号为"当前树中节点数+1"的节点，其父节点为u，其权值为x。(u^=lastans,x^=lastans)

最开始时lastans=0。

Input

输入第一行包括一个正整数n(1<=n<=30000)，代表树上的初始节点数。

接下来n-1行，每行2个整数u,v，为树上的一条无向边。

任何时刻，树上的任何权值大于等于0，且两两不同。

接下来1行，包括n个整数wi，表示初始时每个节点的权值。

接下来1行，包括1个整数m(1<=m<=30000)，表示操作总数。

接下来m行，每行包括三个整数 op,u,v：

op,u,v的含义见题目描述。

保证题目涉及的所有数在int内。

Output

对每个op=0，输出一行，包括一个整数，意义见题目描述。

Sample Input

2
1 2
10 20
1
0 1 5

Sample Output

HINT

Source

By Autumn

分析：

这个SIZE值要注意，由于有二分操作，所以大小定为2.0*sqrt(n)*log2(n)比较好，而不是sqrt(n)，证明略。
加点的时候，分两种情况讨论，
1.如果x节点所在块的数量还没有达到最大值，那就把y节点加进去，然后对整个序列快排。
2.如果达到了最大的值，就新建一个块。
最后询问的时候，由于每一次操作之后块里存的数组都是有序的，因此查找只需要二分。
写两个递归的query函数，在不整的块中暴力查找，在整的块中二分查找
g:存储树的形态
block：储存属于root的子树，且超过SIZE，另行分块的节点
g.del[i]：i边是否已重复，保证块外往块内转移不会出错
然后看代码

luogu's #1&&cogs's #1&&bzoj's #3 (id:bbsh)

#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N=6e4+5,M=N<<1;
int n,m,last,size[N],sum,SIZE,w[N],top[N];
struct node{
    int v[M],next[M],head[M],tot;
    bool del[M];
    inline void add(int x,int y){
        v[++tot]=y;next[tot]=head[x];head[x]=tot;
    }
}g,block,linked;
vector<int>list[N];
inline void init(int u,int f){
    int root=top[u];
    list[root].push_back(w[u]);
    for(int i=g.head[u];i;i=g.next[i]){
        if(g.v[i]==f){g.del[i]=1;continue;} 
        if(size[root]<SIZE)
            size[root]++,top[g.v[i]]=root;
        else
            block.add(root,g.v[i]);
        init(g.v[i],u);
    }
}
inline void query_block(int u,int x){
    sum+=list[u].end()-upper_bound(list[u].begin(),list[u].end(),x);
    for(int i=block.head[u];i;i=block.next[i])
        query_block(block.v[i],x);
}
inline void query_out_board(int u,int x){
    if(w[u]>x) sum++;
    for(int i=g.head[u];i;i=g.next[i]){
        if(g.del[i]) continue; 
        if(top[u]==top[g.v[i]])
            query_out_board(g.v[i],x);
        else
            query_block(g.v[i],x);
    }
}
int main(){
    #ifndef online_judge
        freopen("gtygirltree.in","r",stdin);
        freopen("gtygirltree.out","w",stdout);
    #endif
    n=read();
    SIZE=(int)ceil(2.0*sqrt(n)*log2(n));
    for(int i=1,x,y;i<n;i++){
        x=read();y=read();
        g.add(x,y);g.add(y,x);
    }
    for(int i=1;i<=n;i++) w[i]=read(),top[i]=i,size[i]=1;
    init(1,0);
    for(int i=1;i<=n;i++) if(top[i]==i) sort(list[i].begin(),list[i].end());
    m=read(),last=0;
    for(int opt,u,x,tp;m--;){
        opt=read();u=read()^last;x=read()^last;
        if(!opt){
            sum=0;
            if(u==top[u])
                query_block(u,x);
            else
                query_out_board(u,x);
            printf("%d
",last=sum);
        }
        else if(opt==1){
            tp=top[u];
            list[tp].erase(lower_bound(list[tp].begin(),list[tp].end(),w[u]));
            list[tp].insert(lower_bound(list[tp].begin(),list[tp].end(),x),x);
            w[u]=x;
        }
        else{
            w[++n]=x;
            tp=top[u];
            g.add(u,n);
            if(size[tp]<SIZE){
                top[n]=tp;
                size[tp]++;
                list[tp].insert(lower_bound(list[tp].begin(),list[tp].end(),x),x);
            }
            else{
                top[n]=n;
                size[u]=1;
                list[n].push_back(x);
                block.add(tp,n);
            }
        }
    }
    return 0;
}