## 【BZOJ 4771】七彩树

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;
const int M = 1e7;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

class Segment_Tree_Sum{
int cnt,AnsTmp,root[N],ch[M][2],sum[M];
public:
inline void modify(int w, int p, int delta) {
modify(root[w], 1, n, p, delta);
}
inline void merge(int a, int b) {
root[a] = Merge(root[a], root[b]);
}
inline int query(int w, int d) {
AnsTmp = 0;
query(root[w], 1, n, 1, d);
return AnsTmp;
}
inline void init() {
memset(root,0,sizeof(int)*(n+5));
memset(ch,0,sizeof(int)*(cnt+5)*2);
memset(sum,0,sizeof(int)*(cnt+5));
cnt = 0;
}
private:
void modify(int &w, int l, int r, int p, int delta) {
w = cpy(w); sum[w] += delta;
if (l < r) {
int mid = l + r + 1 >> 1;
if (p < mid) modify(ch[w][0], l, mid-1, p, delta);
else modify(ch[w][1], mid, r, p, delta);
}
}
int Merge(int a, int b) {
a = a? cpy(a): 0; b = b? cpy(b): 0;
if (!b || !a) return a + b;
else {
if (ch[a][0] || ch[a][1]) {
ch[a][0] = Merge(ch[a][0], ch[b][0]);
ch[a][1] = Merge(ch[a][1], ch[b][1]);
}
return sum[a] += sum[b], a;
}
}
void query(int w, int l, int r, int L, int R) {
if (L <= l && r <= R) AnsTmp += sum[w];
else {
int mid = l + r + 1 >> 1;
if (L < mid) query(ch[w][0], l, mid-1, L, R);
if (mid <= R) query(ch[w][1], mid, r, L, R);
}
}
inline int cpy(int b) {
memcpy(ch[++cnt], ch[b], 8);
sum[cnt] = sum[b]; return cnt;
}
}STS;

class Segment_Tree_Col{
int cnt,root[N],ch[M][2],mn[M];
public:
inline void insert(int w, int c) {
insert(root[w], 1, n, c, dep[w]);
STS.modify(w, dep[w], 1);
}
inline void merge(int a, int b) {
STS.merge(a, b);
root[a] = merge(root[a], root[b], a);
}
inline void init() {
memset(root,0,sizeof(int)*(n+5));
memset(ch,0,sizeof(int)*(cnt+5)*2);
memset(mn,0,sizeof(int)*(cnt+5));
cnt = 0;
}
private:
void insert(int &w, int l, int r, int p, int v) {
if (!w) w = ++cnt; if (l == r) mn[w] = v;
else {
int mid = l + r + 1 >> 1;
if (p < mid) insert(ch[w][0], l, mid-1, p, v);
else insert(ch[w][1], mid, r, p, v);
}
}
int merge(int a, int b, int w) {
if (!a || !b) return a + b;
else if (ch[a][0] || ch[a][1]) {
ch[a][0] = merge(ch[a][0], ch[b][0], w);
ch[a][1] = merge(ch[a][1], ch[b][1], w);
} else {
STS.modify(w, max(mn[a], mn[b]), -1);
mn[a] = min(mn[a], mn[b]);
} return a;
}
}STC;

int main() {
STS.init(); STC.init(); dep[1] = 1;
for (int i=1;i<=n;i++) col[i] = read();
for (int i=2;i<=n;i++) dep[i] = dep[fa[i]=read()] + 1;
for (int i=1;i<=n;i++) STC.insert(i, col[i]);
for (int i=n;i>1;i--) STC.merge(fa[i], i);
for (int i=1,x,d,last=0;i<=m;i++) {
printf("%d\n",last=STS.query(x, dep[x]+d));
}
}
return 0;
}


—————————— UPD 2017.4.11 ——————————

http://www.cnblogs.com/clrs97/p/5538804.html

## 【UOJ 218】[UNR #1] 火车管理

™我的自定义测试，那么大的数据都没有wa

std的做法是：

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 500000+9;

int n,m,ty,last_ans,arr[MAXN];

char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return (buf*f+last_ans*ty) % n + 1;
}

namespace Segment_Tree{
#define SEG Segment_Tree
const int N = MAXN*4;
int tag[N],sum[N],tm[N],ans_tmp,L,R,DEL;

inline void push_down(int w, int l, int r, int mid){
tag[w*2] = tag[w*2+1] = tag[w];
sum[w*2] = (mid-l)*arr[tag[w]];
sum[w*2+1] = (r-mid+1)*arr[tag[w]];
tag[w] = 0;
}

void query(int w, int l, int r){
if (L <= l && r <= R) ans_tmp += sum[w];
else {
int mid = (l + r + 1) / 2;
if (tag[w]) push_down(w,l,r,mid);
if (L < mid) query(w*2,l,mid-1);
if (R >= mid) query(w*2+1,mid,r);
}
}inline int query(int l, int r){ans_tmp=0;L=l,R=r;query(1,1,n);return ans_tmp;}

void Modify(int w, int l, int r){
if (L <= l && r <= R) tag[w] = DEL, sum[w] = (r-l+1)*arr[DEL];
else {
int mid = (l + r + 1) / 2;
if (tag[w]) push_down(w,l,r,mid);
if (L < mid) Modify(w*2,l,mid-1);
if (R >= mid) Modify(w*2+1,mid,r);
sum[w] = sum[w*2] + sum[w*2+1];
}
}inline void modify(int l, int r, int del){L=l,R=r,DEL=del;Modify(1,1,n);}

inline int index(int pos){
int w = 1, l = 1, r = n, mid;
while (l < r) {
if (tag[w]) return tag[w];
else {
mid = (l + r + 1) / 2;
if (pos < mid) w = w*2, r = mid-1;
else w = w*2+1, l = mid;
}
}
return tag[w];
}
};

namespace Persistent_Segment_Tree{
#define PST Persistent_Segment_Tree
const int N = 20000000;
int tag[N],root[N],ch[N][2],tot,cnt,L,R,DEL;

inline int query(int tm, int pos) {
if (tm < 1) return 0;
else {
int w = root[tm], l=1, r=n, mid;
while (l < r) {
if (tag[w]) return tag[w];
else {
mid = (l + r + 1) / 2;
if (pos < mid) w = ch[w][0], r = mid-1;
else w = ch[w][1], l = mid;
}
}
return tag[w];
}
}

inline void push_down(int w){
for (int i=0;i<=1;i++) if (!ch[w][i]) ch[w][i] = ++cnt;
for (int i=0;i<=1;i++) tag[ch[w][i]] = tag[w];
tag[w] = 0;
}

void Modify(int pre, int &w, int l, int r, int tg){
w = ++cnt; ch[w][1] = ch[pre][1];
ch[w][0] = ch[pre][0]; tag[w] = tg?tg:tag[pre];
if (L <= l && r <= R) tag[w] = DEL;
else {
int mid = (l + r + 1) / 2;
if (L < mid) Modify(ch[pre][0],ch[w][0],l,mid-1,tag[w]);
else if (tag[w]) ch[w][0] = ++cnt, tag[cnt] = tag[w];
if (mid <= R) Modify(ch[pre][1],ch[w][1],mid,r,tag[w]);
else if (tag[w]) ch[w][1] = ++cnt, tag[cnt] = tag[w];
tag[w] = 0;
}
}

inline int modify(int l, int r, int val, bool type){
L = l, R = r, DEL = val;
Modify(root[tot], root[(tot+type)], 1, n, 0);
}
};

int main(){
scanf("%d%d%d",&n,&m,&ty);
for (int i=1,type,l,r,del;i<=m;i++){
scanf("%d",&type);
if (type == 1) {
if (l > r) swap(l, r);
printf("%d\n",last_ans=SEG::query(l,r));
} else if (type == 2) {
int tmp = SEG::index(l);
int nv = PST::query(tmp-1,l);
PST::modify(l,l,nv,0);
SEG::modify(l,l,nv);
} else {