## 【模板库】线段树合并

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

const int N = 200009;
const int M = N * 21;

int n, m, vis[N], head[N], nxt[N], to[N];
int dep[N], beg[N], out[N], sz[N], fa[N];
struct Data{
int t, x, y;
inline Data() {
}
inline Data(bool a, int b, int c):t(a), x(b), y(c) {
}
}opt[N];

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

inline void AddEdge(int u, int v) {
static int E = 1;
}

inline void DFS(int w, int f) {
static int D = 0;
vis[w] = 1;
beg[w] = ++D;
dep[w] = dep[f] + 1;
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] != f) {
DFS(to[i], w);
}
}
out[w] = D;
}

inline int find(int x) {
return fa[x] == x? x: fa[x] = find(fa[x]);
}

class SegmentTree{
int cnt, ch[M][2], sum[M], root[N];
public:
inline void insert(int p, int v) {
insert(root[p], 1, n, v);
}
inline void merge(int a, int b) {
root[a] = Merge(root[a], root[b]);
}
inline int query(int p, int l, int r) {
return query(root[p], 1, n, l, r);
}
private:
inline int Merge(int a, int b) {
if (!a || !b) {
return a + b;
} else {
sum[a] += sum[b];
ch[a][0] = Merge(ch[a][0], ch[b][0]);
ch[a][1] = Merge(ch[a][1], ch[b][1]);
return a;
}
}
inline void insert(int &w, int l, int r, int p) {
sum[w = ++cnt] = 1;
if (l < r) {
int mid = l + r + 1 >> 1;
if (p < mid) {
insert(ch[w][0], l, mid - 1, p);
} else {
insert(ch[w][1], mid, r, p);
}
}
}
inline int query(int w, int l, int r, int L, int R) {
if (!w) {
return 0;
} else if (L <= l && r <= R) {
return sum[w];
} else {
int mid = l + r + 1 >> 1, ret = 0;
ret += L < mid? query(ch[w][0], l, mid - 1, L, R): 0;
ret += mid <= R? query(ch[w][1], mid, r, L, R): 0;
return ret;
}
}
}SGT;

int main() {
for (int i = 1; i <= m; i++) {
char cmd[3];
scanf("%s", cmd);
if (cmd[0] == 'A') {
}
opt[i] = Data(cmd[0] == 'A', u, v);
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
DFS(i, i);
}
}
for (int i = 1; i <= n; i++) {
sz[i] = 1;
fa[i] = i;
SGT.insert(i, beg[i]);
}
for (int i = 1; i <= m; i++) {
int u = opt[i].x, v = opt[i].y;
if (opt[i].t == 1) {
SGT.merge(find(u), find(v));
sz[find(u)] += sz[find(v)];
fa[find(v)] = find(u);
} else {
if (dep[u] < dep[v]) {
swap(u, v);
}
int p1 = SGT.query(find(u), beg[u], out[u]);
int p2 = sz[find(u)] - p1;
printf("%lld\n", (LL)p1 * p2);
}
}
return 0;
}


## 【BZOJ 4530】[BJOI2014] 大融合

### Code

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

const int N = 200009;
const int M = N * 21;

int n, m, vis[N], head[N], nxt[N], to[N];
int dep[N], beg[N], out[N], sz[N], fa[N];
struct Data{
int t, x, y;
inline Data() {
}
inline Data(bool a, int b, int c):t(a), x(b), y(c) {
}
}opt[N];

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

inline void AddEdge(int u, int v) {
static int E = 1;
}

inline void DFS(int w, int f) {
static int D = 0;
vis[w] = 1;
beg[w] = ++D;
dep[w] = dep[f] + 1;
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] != f) {
DFS(to[i], w);
}
}
out[w] = D;
}

inline int find(int x) {
return fa[x] == x? x: fa[x] = find(fa[x]);
}

class SegmentTree{
int cnt, ch[M][2], sum[M], root[N];
public:
inline void insert(int p, int v) {
insert(root[p], 1, n, v);
}
inline void merge(int a, int b) {
root[a] = Merge(root[a], root[b]);
}
inline int query(int p, int l, int r) {
return query(root[p], 1, n, l, r);
}
private:
inline int Merge(int a, int b) {
if (!a || !b) {
return a + b;
} else {
sum[a] += sum[b];
ch[a][0] = Merge(ch[a][0], ch[b][0]);
ch[a][1] = Merge(ch[a][1], ch[b][1]);
return a;
}
}
inline void insert(int &w, int l, int r, int p) {
sum[w = ++cnt] = 1;
if (l < r) {
int mid = l + r + 1 >> 1;
if (p < mid) {
insert(ch[w][0], l, mid - 1, p);
} else {
insert(ch[w][1], mid, r, p);
}
}
}
inline int query(int w, int l, int r, int L, int R) {
if (!w) {
return 0;
} else if (L <= l && r <= R) {
return sum[w];
} else {
int mid = l + r + 1 >> 1, ret = 0;
ret += L < mid? query(ch[w][0], l, mid - 1, L, R): 0;
ret += mid <= R? query(ch[w][1], mid, r, L, R): 0;
return ret;
}
}
}SGT;

int main() {
for (int i = 1; i <= m; i++) {
char cmd[3];
scanf("%s", cmd);
if (cmd[0] == 'A') {
}
opt[i] = Data(cmd[0] == 'A', u, v);
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
DFS(i, i);
}
}
for (int i = 1; i <= n; i++) {
sz[i] = 1;
fa[i] = i;
SGT.insert(i, beg[i]);
}
for (int i = 1; i <= m; i++) {
int u = opt[i].x, v = opt[i].y;
if (opt[i].t == 1) {
SGT.merge(find(u), find(v));
sz[find(u)] += sz[find(v)];
fa[find(v)] = find(u);
} else {
if (dep[u] < dep[v]) {
swap(u, v);
}
int p1 = SGT.query(find(u), beg[u], out[u]);
int p2 = sz[find(u)] - p1;
printf("%lld\n", (LL)p1 * p2);
}
}
return 0;
}


## 【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

## 【日常小测】最大值

### Code

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

const int N = 100009;
const int M = N * 30;

int fa[N][20],dis[N],dep[N],val[N],HASH[N];

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{
int root[N],cnt;
struct Node{int ch[2],lca,sz,id; LL ans,sum;}p[M];
public:
inline void insert(int v, int w) {
insert(root[w], 1, n, v, w);
}
inline void Merge(int a, int b) {
root[a] = merge(root[a], root[b]);
}
inline int query(int w) {
return p[root[w]].id;
}
inline Segment_Tree() {
p[0].ans = -1;
}
private:
void insert(int &w, int l, int r, int pos, int lca) {
if (w=++cnt, l==r) {
p[w].lca = lca; p[w].sz = 1;
} else {
int mid = l + r + 1 >> 1;
if (pos < mid) insert(p[w].ch[0], l, mid-1, pos, lca);
else insert(p[w].ch[1], mid, r, pos, lca);
} p[w].id = pos; p[w].ans = 0;
}
int merge(int a, int b) {
if (!a || !b) return a + b;
if (p[a].ch[0] || p[a].ch[1]) {
p[a].ch[0] = merge(p[a].ch[0], p[b].ch[0]);
p[a].ch[1] = merge(p[a].ch[1], p[b].ch[1]);
int ls = p[a].ch[0], rs = p[a].ch[1];
if (p[ls].ans >= p[rs].ans) p[a].ans = p[ls].ans, p[a].id = p[ls].id;
else p[a].ans = p[rs].ans, p[a].id = p[rs].id;
} else {
int lca = LCA(p[a].lca, p[b].lca);
LL delta = (dis[p[a].lca] + dis[p[b].lca] - dis[lca] * 2ll) * p[a].sz * p[b].sz;
delta += p[a].sum * p[b].sz + p[b].sum * p[a].sz;
p[a].ans = p[a].ans + p[b].ans + delta;
p[a].sum = p[a].sum + ((LL)dis[p[a].lca] - dis[lca]) * p[a].sz ;
p[a].sum += p[b].sum + ((LL)dis[p[b].lca] - dis[lca]) * p[b].sz;
p[a].sz += p[b].sz; p[a].lca = lca;
} return a;
}
inline int LCA(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i=19;~i;i--) if (dep[fa[u][i]]>=dep[v]) u=fa[u][i];
if (u == v) return u;
for (int i=19;~i;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
}SGT;

inline void AddEdge(int u, int v, int c) {
static int E = 1; cost[E+1] = cost[E+2] = c;
}

void DFS(int w, int f) {
dep[w] = dep[f] + 1; fa[w][0] = f;
if (to[i] != f) {
dis[to[i]] = dis[w] + cost[i];
DFS(to[i], w);
}
}
}

void solve(int w, int f) {
if (to[i] != f) {
solve(to[i], w);
SGT.Merge(w, to[i]);
}
} vout[w] = SGT.query(w);
}

int main() {
for (int i=1,u,v;i<n;i++) {
}
for (int i=1;i<=n;i++) HASH[i] = val[i] = read();
sort(HASH+1, HASH+1+n);
tot = unique(HASH+1, HASH+1+n) - HASH - 1;
for (int i=1;i<=n;i++) val[i] = lower_bound(HASH+1, HASH+1+tot, val[i]) - HASH;
for (int i=1;i<=n;i++) SGT.insert(val[i], i);
DFS(1, 1);
for (int j=1;j<=19;j++) for (int i=1;i<=n;i++)
fa[i][j] = fa[fa[i][j-1]][j-1];
solve(1, 1);
for (int i=1;i<=n;i++) printf("%d\n",HASH[vout[i]]);
return 0;
}


## 【BZOJ 3307】雨天的尾巴

### Code

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

const int N = 100009;
const int M = N << 1;
const int G = 7000000;
const int INF = 1e9;

int n,m,dep[N],ans[N],fa[N][20];

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;
}

inline void AddEdge(int u, int v) {
static int E = 1;
}

void DFS(int w, int f) {
fa[w][0] = f; dep[w] = dep[f] + 1;
if (to[i] != f) {
DFS(to[i], w);
}
}
}

inline int LCA(int u, int v) {
if (dep[u]<dep[v]) swap(u, v);
for (int j=19;~j;j--) if (dep[fa[u][j]]>=dep[v]) u = fa[u][j];
if (u == v) return u;
for (int j=19;~j;j--) if (fa[u][j]!=fa[v][j]) u=fa[u][j],v=fa[v][j];
return fa[u][0];
}

class Segment_Tree{
int cnt,ch[G][2],mx[G],id[G],root[N];
public:
inline void merge(int x, int y) {
root[x] = Merge(root[x], root[y]);
}
inline void insert(int w, int p, int t) {
insert(root[w], 1, INF, p, t);
}
inline int query(int w) {
return mx[root[w]]? id[root[w]]: 0;
}
private:
int Merge(int x, int y) {
if (!x || !y) return x + y;
if (!ch[x][0] && !ch[x][1]) {
mx[x] += mx[y];
return x;
} else {
ch[x][0] = Merge(ch[x][0], ch[y][0]);
ch[x][1] = Merge(ch[x][1], ch[y][1]);
if (mx[ch[x][0]] >= mx[ch[x][1]]) id[x] = id[ch[x][0]], mx[x] = mx[ch[x][0]];
else id[x] = id[ch[x][1]], mx[x] = mx[ch[x][1]];
return x;
}
}
void insert(int &w, int l, int r, int p, int delta) {
if (!w) w = ++cnt;
if (l == r) {
mx[w] += delta; id[w] = l;
} else {
int mid = l + r + 1 >> 1;
if (p < mid) insert(ch[w][0], l, mid-1, p, delta);
else insert(ch[w][1], mid, r, p, delta);
if (mx[ch[w][0]] >= mx[ch[w][1]]) id[w] = id[ch[w][0]], mx[w] = mx[ch[w][0]];
else id[w] = id[ch[w][1]], mx[w] = mx[ch[w][1]];
}
}
}ST;

void solve(int w, int f) {
if (to[i] != f) {
solve(to[i], w);
ST.merge(w, to[i]);
}
}
ans[w] = ST.query(w);
}

int main() {
DFS(1, 1);
for (int j=1;j<20;j++) {
for (int i=1;i<=n;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
for (int i=1,u,v,lca,c;i<=m;i++) {
lca = LCA(u, v);
ST.insert(u, c, 1);
ST.insert(v, c, 1);
ST.insert(lca, c, -1);
if (lca-1) ST.insert(fa[lca][0], c, -1);
}
solve(1, 1);
for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}