bzoj3720 gty的妹子树

Description

维护一棵初始有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，输出一行，包括一个整数，意义见题目描述。

块状树

设定每个块的大小上限为sqrt(n)，

块内维护块内结点权值的升序排列，并记录由块组成的树

将根结点加入第一个块，对其它结点若父结点所在的块未满就加入其中，否则另开新块

查询时对子树完整包含的块二分查找，不完整的块暴力查找

时间复杂度O(n^1.5logn)

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int mxsz=200;
vector<int> tr[60005];
vector<int> tr0[60005];
int tp;
int v[60005];
int b[60005];
struct block{
    int vs[200],vp;
    vector<int>ss;
    int id;
    block(){
        vp=0;
    }
    void insert(int w);
    void change(int a,int b);
    int getans(int m);
};
bool isr[60005];
block bs[10005];
int bp=2;
void block::insert(int w){
    if(vp<mxsz){
        vs[vp++]=v[w];
        sort(vs,vs+vp);
        b[w]=id;
        isr[w]=(vp==1?1:0);
    }else{
        ss.push_back(bp);
        bs[bp++].insert(w);
        isr[w]=1;
    }
}
void block::change(int a,int b){
    for(int i=0;i<vp;i++){
        if(vs[i]==a){
            vs[i]=b;
            break;
        }
    }
    sort(vs,vs+vp);
}
int block::getans(int m){
    int ans=vp-(upper_bound(vs,vs+vp,m)-vs);
    for(int i=ss.size()-1;i>=0;i--)ans+=bs[ss[i]].getans(m);
    return ans;
}
int dfs(int m,int w){
    if(isr[w])return bs[b[w]].getans(m);
    int ans=0;
    if(v[w]>m)ans++;
    for(int i=tr[w].size()-1;i>=0;i--)ans+=dfs(m,tr[w][i]);
    return ans;
}
void build(int w,int pa){
    if(pa==-1)bs[1].insert(w);
    else bs[b[pa]].insert(w);
    for(int i=tr0[w].size()-1;i>=0;i--){
        int u=tr0[w][i];
        if(u!=pa)tr[w].push_back(u);
        else continue;
        build(u,w);
    }
}
int n,m,op,p1,p2,la=0;
int main(){
    for(int i=0;i<10005;i++)bs[i].id=i;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d",&p1,&p2);
        tr0[p1].push_back(p2);
        tr0[p2].push_back(p1);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&p1);
        v[i]=p1;
    }
    build(1,-1);
    tp=n+1;
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&op,&p1,&p2);
        p1^=la;p2^=la;
        if(op==0){
            printf("%d
",la=dfs(p2,p1));
        }else if(op==1){
            bs[b[p1]].change(v[p1],p2);
            v[p1]=p2;
        }else{
            tr[p1].push_back(tp);
            v[tp]=p2;
            bs[b[p1]].insert(tp);
            tp++;
        }
    }
    return 0;
}