HZOI2015黑树白

发表于

树链剖分、树状数组套主席树


题意

给定一棵树，每个节点有点权，要求维护以下两个操作：
1、Q u v a b 本蒟蒻施展大魔法，使得树上所有点权>=a且点权<=b的点变成白点，其余的点变成黑点，并查询u到v的简单路径上有多少个白点
2、M u v 本蒟蒻施展小魔法，将u点的点权改为v
对于每次Q和M输入的u和v，你需要令u=(u+ans)%n+1,v=(v+ans)%n+1
其中ans为上一次的答案，最开始ans=0

  • n，m<=80000

题解

  • 强制在线，树链剖分，用树状数组套主席树维护

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include<bits/stdc++.h>
using namespace std;
#define maxn 80010
int size[maxn],dep[maxn],val[maxn],id[maxn],hson[maxn],top[maxn],fa[maxn];//定义
int num,head[maxn],tot_edge,n,q;
struct Edge {
    int to, nxt;
} edge[maxn*2];
void add_edge(int u, int v) {
    tot_edge ++;
    edge[tot_edge].to = v;
    edge[tot_edge].nxt = head[u];
    head[u] = tot_edge;
}
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))  {
        if(ch=='-')  f=-1;
        ch=getchar();
    }
    while(isdigit(ch))  {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
#define MAX 20001000
int lson[MAX], rson[MAX], c[MAX], tot ,S[maxn], T[maxn];
int build(int l, int r) {
    int root = tot++;
    c[root] = 0;
    if(l != r) {
        int mid = (l+r) >> 1;
        lson[root] = build(l, mid);
        rson[root] = build(mid+1, r);
    }
    return root;
}
int Insert(int root, int pos, int val) {
    int newroot = tot++, tmp = newroot;
    int l = 0, r = n;
    c[newroot] = c[root] + val;
//    printf("**%d\n",c[newroot]);
    while(l < r) {
        int mid = (l+r)>>1;
        if(pos <= mid) {
            lson[newroot] = tot++;
            rson[newroot] = rson[root];
            newroot = lson[newroot];
            root = lson[root];
            r = mid;
        } else {
            rson[newroot] = tot++;
            lson[newroot] = lson[root];
            newroot = rson[newroot];
            root = rson[root];
            l = mid+1;
        }
        c[newroot] = c[root] + val;
    }
    return tmp;
}
int lowbit(int x) {
    return x&(-x);
}
int use[maxn],tuse[maxn],tleft,tright;
void add(int x, int pos, int d) {
    while(x <= n) {
//        printf("--%d %d %d\n",x,pos,d);
        S[x] = Insert(S[x], pos, d);
        x += lowbit(x);
    }
}
int Sum(int x) {
    int ret = 0;
    while(x > 0) {
        ret += c[use[x]];
//        printf("--%d\n",use[x]);
        x -= lowbit(x);
    }
    return ret;
}
int Query(int left,int right,int L,int R,int p,int left_root,int right_root){
    if(L==R){
        return Sum(right) - Sum(left-1) + c[right_root] - c[left_root];
    }else{
        int M=(L+R)>>1;
        for(int i = left-1; i; i -= lowbit(i)){
            tuse[i] = rson[use[i]];
            use[i] = lson[use[i]];
        }
        for(int i = right; i; i -= lowbit(i)){
            tuse[i] = rson[use[i]];
            use[i] = lson[use[i]];
        }
        tleft=rson[left_root];
        tright=rson[right_root];
        left_root = lson[left_root];
        right_root = lson[right_root];
        if(p<=M) return Query(left,right,L,M,p,left_root,right_root);
        else{
            int ans=Sum(right)-Sum(left-1)+c[right_root]-c[left_root];
//            printf("%d %d %d %d %d %d\n",left_root,right_root,c[right_root]-c[left_root],Sum(right),Sum(left-1),ans);
            for(int i = left-1; i; i -= lowbit(i)) use[i] = tuse[i];
            for(int i = right; i; i -= lowbit(i)) use[i] = tuse[i];
            left_root=tleft;right_root=tright;
            return ans+Query(left,right,M+1,R,p,left_root,right_root);
        }
    }
}
int initQuery(int left, int right, int p) {
    if(p<0) return 0;
    int left_root = T[left-1], right_root = T[right];
    for(int i = left-1; i; i -= lowbit(i)) use[i] = S[i];
    for(int i = right; i; i -= lowbit(i)) use[i] = S[i];
    return Query(left,right,0,n,p,left_root,right_root);
}
void dfs1(int d,int f,int u) { //d：深度 f:父节点 u：当前节点
    dep[u]=d;
    size[u]=1;
    hson[u]=0;
    fa[u]=f;
    for(int i = head[u]; i; i = edge[i].nxt) {
        int to = edge[i].to;
        if(to==f) continue;
        dfs1(d+1,u,to);
        size[u]+=size[to];
        if(size[hson[u]]<size[to])
            hson[u]=to;//找重儿子
    }
}
void dfs2(int u,int tp) {
    top[u]=tp;//赋值top
    id[u]=num++;//赋值id
    if(hson[u]) dfs2(hson[u],tp);//优先重儿子
    for(int i = head[u]; i; i = edge[i].nxt) {
        int to = edge[i].to;
        if(to==fa[u]||to==hson[u]) continue;
        dfs2(to,to);
    }
}
int W[maxn];
int find(int u,int v,int a,int b) {
    int t1=top[u],t2=top[v];
    int ans=0;
    while(t1!=t2) {
        if(dep[t1]<dep[t2]) {
            swap(t1,t2);
            swap(u,v);
        }
        ans+=initQuery(id[t1],id[u],b)-initQuery(id[t1],id[u],a-1);
        u=fa[t1];
        t1=top[u];
    }
    if (dep[u] > dep[v]) swap(u, v);
    ans+=initQuery(id[u],id[v],b)-initQuery(id[u],id[v],a-1);
    return ans;
}
void init(int n) {
    dfs1(1,0,1);
    dfs2(1,1);
    for(int i=1; i<=n; i++)
        val[id[i]] = W[i];
    T[0]=build(0,n);
    for(int i=1;i<=n;i++) T[i]=Insert(T[i-1],val[i],1);
}
int main() {
    freopen("D_Tree.in","r",stdin);
    freopen("D_Tree.out","w",stdout);
    n=read();q=read();
    num=1;
    int u,v;
    for(int i=1;i<=n;i++) W[i]=read();
    for(int i=1; i<n; i++){
        u=read();v=read();
        add_edge(u,v);
        add_edge(v,u);
    }
    init(n);
    char op[5];
    int a,b,ans=0;
    while(q--) {
        scanf("%s%d%d",op,&u,&v);
        u=(u+ans)%n+1;v=(v+ans)%n+1;
        if(op[0]=='M'){
            add(id[u],W[u],-1);
            add(id[u],v,1);
            W[u]=v;
        }else {
            scanf("%d%d",&a,&b);
            ans=find(u,v,a,b);
            printf("%d\n",ans);
        }
    }
    return 0;
}