BZOJ 2243 染色 树链剖分 线段树
题
解
树剖裸题。
用了一点线段树的小trick，就是处理信息区间加法是直接用operator+来连结，这样在函数里操作起来简单点（个人觉得），只不过写好这个operator+不简单……（因此WA若干次的DEL桑真是……）
总之傻逼数据结构题都能写5k赛场上还是只能狗带……
码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
template<class T>
inline void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T>
inline void read(T& x, T& y){read(x), read(y);}
template<class T>
inline void read(T& x, T& y, T& z){read(x), read(y), read(z);}
const int maxn = 1e6;
int n;
struct Edge
{
int to;
Edge* next;
} pool[maxn * 4], *header[maxn];
int pcnt = 0;
void add_edge(int u, int v)
{
Edge *newedge = &pool[pcnt++];
newedge -> to = v;
newedge -> next = header[u];
header[u] = newedge;
}
int size[maxn] = {0}, hson[maxn] = {0}, fa[maxn] = {0}, depth[maxn] = {0};
int dfs(int i = 1)
{
size[i] = 1, hson[i] = 0;
for(Edge *e = header[i]; e; e = e -> next)
{
if(e -> to != fa[i])
{
fa[e -> to] = i;
depth[e -> to] = depth[i] + 1;
dfs(e -> to);
size[i] += size[e -> to];
if(size[e -> to] > size[hson[i]])
hson[i] = e -> to;
}
}
}
int number[maxn] = {0}, ncnt = 1, top[maxn] = {0};
int build_tree(int i = 1, int tp = 1)
{
number[i] = ncnt++, top[i] = tp;
if(hson[i])
build_tree(hson[i], tp);
for(Edge *e = header[i]; e; e = e -> next)
if(e -> to != hson[i] && e -> to != fa[i])
build_tree(e -> to, e -> to);
}
namespace SegTree
{
struct Info
{
int color;
int lc, rc;
int blocks;
Info(int x = -1, int n = 0) : color(x), lc(x), rc(x), blocks(n){}
Info(int x, int l, int r, int b) : color(x), lc(l), rc(r), blocks(b){}
Info operator+(Info& a)
{
if(lc == -1)
return Info(-1, a.lc, a.rc, a.blocks);
if(a.rc == -1)
return Info(-1, lc, rc, blocks);
if(color != -1)
lc = rc = color, blocks = 1;
if(a.color != -1)
a.lc = a.rc = a.color, a.blocks = 1;
int t = rc == a.lc ? 1 : 0;
return Info(-1, lc, a.rc, blocks + a.blocks - t);
}
} I[maxn * 4];
void maintain(int o, int L, int R)
{
if(L < R)
{
int c = I[o].color;
I[o] = I[o << 1] + I[(o << 1) + 1];
I[o].color = c;
}
}
int x, y, c;
void change(int o = 1, int L = 1, int R = n)
{
if(x <= L && R <= y)
I[o] = Info(c, 1);
else
{
if(I[o].color != -1)
I[o << 1] = I[(o << 1) + 1] = Info(I[o].color, 1), I[o].color = -1;
int M = (L + R) / 2;
if(x <= M) change(o << 1, L, M); else maintain(o << 1, L, M);
if(M < y) change((o << 1) + 1, M + 1, R); else maintain((o << 1) + 1, M + 1, R);
maintain(o, L, R);
}
}
Info ans;
void query(int o = 1, int L = 1, int R = n)
{
if(I[o].color != -1)
ans = ans + I[o];
else if(x <= L && R <= y)
ans = ans + I[o];
else
{
int M = (L + R) / 2;
if(x <= M) query(o << 1, L, M);
if(M < y) query((o << 1) + 1, M + 1, R);
}
}
}
int change(int a, int b, int co)
{
using namespace SegTree;
x = a, y = b, c = co;
change();
}
SegTree::Info que(int u, int v)
{
using namespace SegTree;
x = u, y = v; ans = Info();
query();
return ans;
}
int modify(int u, int v, int c)
{
int tu = top[u], tv = top[v];
while(tu != tv)
{
if(depth[tu] < depth[tv])
swap(u, v), swap(tu, tv);
change(number[top[u]], number[u], c);
u = fa[tu], tu = top[u];
}
if(u == v)
change(number[u], number[u], c);
else
{
if(depth[u] < depth[v])
swap(u, v);
change(number[v], number[u], c);
}
}
int query(int u, int v)
{
int tu = top[u], tv = top[v];
int ans = 0;
int uc = -1, vc = -1;
SegTree::Info i;
while(tu != tv)
{
if(depth[tu] < depth[tv])
swap(u, v), swap(tu, tv), swap(uc, vc);
i = que(number[top[u]], number[u]);
ans += i.blocks;
if(uc == i.rc)
ans--;
uc = i.lc;
u = fa[tu], tu = top[u];
}
if(u == v)
{
i = que(number[u], number[u]);
ans += i.blocks;
if(i.lc == uc)
ans--;
if(i.rc == vc)
ans--;
}
else
{
if(depth[u] < depth[v])
swap(u, v), swap(uc, vc);
i = que(number[v], number[u]);
ans += i.blocks;
if(vc == i.lc)
ans--;
if(uc == i.rc)
ans--;
}
return ans;
}
int color[maxn] = {0};
int main()
{
int m;
read(n, m);
for(int i = 1; i <= n; i++)
read(color[i]);
for(int i = 1, x, y; i < n; i++)
{
read(x, y);
add_edge(x, y);
add_edge(y, x);
}
dfs();
build_tree();
for(int i = 1; i <= n; i++)
{
change(number[i], number[i], color[i]);
}
while(m--)
{
char com[2];
scanf("%s", &com);
int a, b, c;
if(com[0] == 'C')
{
read(a, b, c);
modify(a, b, c);
}
else
{
read(a, b);
printf("%d\n", query(a, b));
}
}
return 0;
}