本文共 3802 字，大约阅读时间需要 12 分钟。
对于每个询问操作，输出一行答案。
数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。
一道很有思维含量且细节挺多的题。首先想如何求序列上一个区间有几个颜色段？线段树每个点维护这个点所代表区间的左右端点颜色及这个区间的颜色段数就好了。在树上操作就直接dfs出树剖序然后架在线段树上。但要注意一点，每次查询时两点在跳lca的过程中每次跳的是一条重链，两条重链的相接的两个点颜色如果相同就要把答案数减1，所以还要维护每次跳的链头的颜色。当最后两个点跳到同一个重链上时这两点间的链的两头要分别判断一下。
#include #include #include #include #include #include #include #include #include #include using namespace std;int n,m;int tot;int num;int x,y,z;char ch[2];int s[100010];int d[100010];int a[800010];int f[100010];int v[100010];int q[100010];int ls[800010];int rs[800010];int to[200010];int sum[800010];int son[100010];int top[100010];int size[100010];int head[100010];int next[200010];void add(int x,int y){ tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y;}void dfs(int x,int fa){ size[x]=1; f[x]=fa; d[x]=d[fa]+1; for(int i=head[x];i;i=next[i]) { if(to[i]!=fa) { dfs(to[i],x); size[x]+=size[to[i]]; if(size[to[i]]>size[son[x]]) { son[x]=to[i]; } } }}void dfs2(int x,int tp){ s[x]=++num; q[num]=x; top[x]=tp; if(son[x]) { dfs2(son[x],tp); } for(int i=head[x];i;i=next[i]) { if(to[i]!=f[x]&&to[i]!=son[x]) { dfs2(to[i],to[i]); } }}void pushup(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; if(rs[rt<<1]==ls[rt<<1|1]) { sum[rt]--; } ls[rt]=ls[rt<<1]; rs[rt]=rs[rt<<1|1];}void pushdown(int rt){ if(a[rt]!=-1) { a[rt<<1]=a[rt]; a[rt<<1|1]=a[rt]; ls[rt<<1]=a[rt]; rs[rt<<1]=a[rt]; ls[rt<<1|1]=a[rt]; rs[rt<<1|1]=a[rt]; sum[rt<<1]=1; sum[rt<<1|1]=1; a[rt]=-1; }}void build(int rt,int l,int r){ a[rt]=-1; if(l==r) { ls[rt]=rs[rt]=v[q[l]]; sum[rt]=1; return ; } int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); pushup(rt);}void change(int rt,int l,int r,int L,int R,int v){ if(L<=l&&r<=R) { sum[rt]=1; ls[rt]=v; rs[rt]=v; a[rt]=v; return ; } pushdown(rt); int mid=(l+r)>>1; if(L<=mid) { change(rt<<1,l,mid,L,R,v); } if(R>mid) { change(rt<<1|1,mid+1,r,L,R,v); } pushup(rt);}int query(int rt,int l,int r,int L,int R){ if(L<=l&&r<=R) { return sum[rt]; } pushdown(rt); int mid=(l+r)>>1; if(R<=mid) { return query(rt<<1,l,mid,L,R); } else if(L>mid) { return query(rt<<1|1,mid+1,r,L,R); } if(rs[rt<<1]==ls[rt<<1|1]) { return query(rt<<1,l,mid,L,R)+query(rt<<1|1,mid+1,r,L,R)-1; } else { return query(rt<<1,l,mid,L,R)+query(rt<<1|1,mid+1,r,L,R); }}int find(int rt,int l,int r,int k){ if(l==r) { return ls[rt]; } pushdown(rt); int mid=(l+r)>>1; if(k<=mid) { return find(rt<<1,l,mid,k); } else { return find(rt<<1|1,mid+1,r,k); }}void color(int x,int y,int v){ while(top[x]!=top[y]) { if(d[top[x]] d[y]) { swap(x,y); } change(1,1,n,s[x],s[y],v);}int ask(int x,int y){ int t1=-1; int s1=-1; int res=0; while(top[x]!=top[y]) { if(d[top[x]]>d[top[y]]) { res+=query(1,1,n,s[top[x]],s[x]); if(s1==find(1,1,n,s[x])) { res--; } s1=find(1,1,n,s[top[x]]); x=f[top[x]]; } else { res+=query(1,1,n,s[top[y]],s[y]); if(t1==find(1,1,n,s[y])) { res--; } t1=find(1,1,n,s[top[y]]); y=f[top[y]]; } } if(x==y) { res++; int miku=find(1,1,n,s[x]); if(miku==t1) { res--; } if(miku==s1) { res--; } } else { if(d[x]>d[y]) { res+=query(1,1,n,s[y],s[x]); } else { res+=query(1,1,n,s[x],s[y]); } if(find(1,1,n,s[x])==s1) { res--; } if(find(1,1,n,s[y])==t1) { res--; } } return res;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&v[i]); } for(int i=1;i
转载于:https://www.cnblogs.com/Khada-Jhin/p/9561998.html