本文共 1382 字，大约阅读时间需要 4 分钟。
题目大意：将某个节点的颜色变为x，查询i,j路径上多少个颜色为x的点...
其实最开始一看就是主席树+树状数组+DFS序...但是过不去...MLE+TLE BY FCWWW
其实树剖裸的一批...只是在树剖上套一个动态开点的线段树就可以了...很显然的...就是注意一下细节问题，还有Map这种东西，还是不要乱用的说...
附上代码：
#include #include #include #include #include #include #include #include using namespace std;#define N 100005#define lson l,m,tr[rt].ls#define rson m+1,r,tr[rt].rsstruct edge{int to,next;}e[N<<1];struct node{int ls,rs,siz;}tr[N*40];int rot[N],n,Q,cnt,a[N],head[N],son[N],fa[N],dep[N],siz[N],anc[N],idx[N],tims;void add(int x,int y){e[cnt]=(edge){y,head[x]};head[x]=cnt++;}void Update(int x,int c,int l,int r,int &rt){ if(!rt)rt=++cnt;tr[rt].siz+=c;if(l==r)return ;int m=(l+r)>>1; if(m>=x)Update(x,c,lson);else Update(x,c,rson);}void dfs1(int x,int from){ fa[x]=from,dep[x]=dep[from]+1,siz[x]=1; for(int i=head[x];i!=-1;i=e[i].next) { int to1=e[i].to; if(to1!=from) { dfs1(to1,x);siz[x]+=siz[to1]; if(siz[son[x]] >1,ret=0; if(L<=m)ret+=query(L,R,lson);if(m dep[y])swap(x,y); return ret+query(idx[x],idx[y],1,n,rot[c]);}map mp;int tot=0,S[N],top,b[N];char s[2];int main(){ scanf("%d%d",&n,&Q);memset(head,-1,sizeof(head)); for(int i=1,x;i<=n;i++) { scanf("%d",&x);b[i]=x; if(mp.find(x)==mp.end())mp[x]=++tot; a[i]=mp[x]; }for(int i=1,x,y;i
转载于:https://www.cnblogs.com/Winniechen/p/9241850.html