这道题感觉非常简单，（其实用树链剖分写的话肯定快多了），一个区间染色问题，需要记录一下最左段，最右端的颜色，还有就是有几段，这样才能维护起来，在一个傻逼地方wa了好多遍，翻转的时候，左端的颜色变成了右端的颜色，右端的颜色变成了左端的颜色。下面是代码：
#include#include #include #include #include #define LL long long#define INF 0x3fffffff#define FOR(i,x,y) for(int i = x;i < y;i ++)#define IFOR(i,x,y) for(int i = x;i > y;i --)#define MAXN 110000using namespace std;int n,m;vector mat[MAXN];struct LCT{ int pre[MAXN],ch[MAXN][2],key[MAXN],flip[MAXN]; int ans[MAXN],l[MAXN],r[MAXN],lazy[MAXN]; bool rt[MAXN]; void Update_Lazy(int x,int w){ if(!x) return; lazy[x] = w; key[x] = w; l[x] = w; r[x] = w; ans[x] = 1; } void Update_Flip(int x){ if(!x) return; swap(l[x],r[x]); swap(ch[x][0],ch[x][1]); flip[x] ^= 1; } void Init(){ memset(ch,0,sizeof(ch)); memset(flip,0,sizeof(flip)); memset(rt,true,sizeof(rt)); FOR(i,1,n+1){ l[i] = r[i] = key[i]; ans[i] = 1; lazy[i] = -1; } } void PushUp(int x){ ans[x] = 1; l[x] = r[x] = key[x]; if(ch[x][0]){ ans[x] += ans[ch[x][0]]; if(r[ch[x][0]] == key[x]) ans[x] --; l[x] = l[ch[x][0]]; } if(ch[x][1]){ ans[x] += ans[ch[x][1]]; if(l[ch[x][1]] == key[x]) ans[x] --; r[x] = r[ch[x][1]]; } } void PushDown(int x){ if(lazy[x] != -1){ Update_Lazy(ch[x][0],lazy[x]); Update_Lazy(ch[x][1],lazy[x]); lazy[x] = -1; } if(flip[x]){ Update_Flip(ch[x][0]); Update_Flip(ch[x][1]); flip[x] = 0; } } void Rotate(int x,int kind){ int y = pre[x]; PushDown(y); PushDown(x); ch[y][!kind] = ch[x][kind]; if(ch[x][kind]) pre[ch[x][kind]] = y; if(rt[y]){ rt[x] = true; rt[y] = false; } else{ if(ch[pre[y]][1] == y) ch[pre[y]][1] = x; if(ch[pre[y]][0] == y) ch[pre[y]][0] = x; } pre[x] = pre[y]; pre[y] = x; ch[x][kind] = y; PushUp(y); } void Splay(int x){ PushDown(x); while(!rt[x]){ int y = pre[x]; int z = pre[y]; if(rt[y]){ PushDown(y); PushDown(x); Rotate(x,ch[y][0] == x); } else{ PushDown(z); PushDown(y); PushDown(x); int kind = ch[z][0] == y; if(ch[y][kind] == x){ Rotate(x,!kind); Rotate(x,kind); } else{ Rotate(y,kind); Rotate(x,kind); } } } PushUp(x); } void Access(int x){ int fa = 0; for(;x;x = pre[fa = x]){ Splay(x); rt[ch[x][1]] = true; rt[ch[x][1] = fa] = false; PushUp(x); } } int GetRoot(int x){ Access(x); Splay(x); while(ch[x][0]) x = ch[x][0]; return x; } void MakeRoot(int x){ Access(x); Splay(x); Update_Flip(x); } void Modify(int u,int v,int w){ MakeRoot(u); Access(v); Splay(v); Update_Lazy(v,w); } int Query(int u,int v){ MakeRoot(u); Access(v); Splay(v); return ans[v]; }}lct;void dfs(int u,int fa){ lct.pre[u] = fa; for(int i = 0;i < mat[u].size();i ++){ int v = mat[u][i]; if(v == fa) continue; dfs(v,u); }}int main(){ //freopen("test.in","r",stdin); while(~scanf("%d%d",&n,&m)){ FOR(i,1,n+1) mat[i].clear(); FOR(i,1,n+1) scanf("%d",&lct.key[i]); FOR(i,1,n){ int u,v; scanf("%d%d",&u,&v); mat[u].push_back(v); mat[v].push_back(u); } dfs(1,0); lct.Init(); char op[10]; FOR(i,0,m){ scanf("%s",op); if(op[0] == 'Q'){ int u,v; scanf("%d%d",&u,&v); printf("%d\n",lct.Query(u,v)); } else{ int u,v,w; scanf("%d%d%d",&u,&v,&w); lct.Modify(u,v,w); } } } return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。