网站建设的价值,石狮app网站开发哪家好,网址推广主要做些什么内容,企业做网站 乐云seoDescription
一个 n 个结点的有根树#xff0c;每个结点 x 有一个值 txt_xtx#xff0c;和一个颜色 (黑/白)。 m 次操作#xff1a;
翻转某点颜色。询问有多少点 x 满足#xff1a;x 为黑色#xff0c;x 的白色后代数 tx。 n, m ≤ 10510^5105
Solution
令 wi …Description
一个 n 个结点的有根树每个结点 x 有一个值 txt_xtx和一个颜色 (黑/白)。 m 次操作
翻转某点颜色。询问有多少点 x 满足x 为黑色x 的白色后代数 tx。 n, m ≤ 10510^5105
Solution
令 wi ti− 子树内白点数那么询问就是 wi 0 的黑点数修改就是翻转颜色并将至根路径的w值1/ − 1。思来想去好像没有什么奇妙的数据结构能在O(nlogn)O(nlogn)O(nlogn)或O(nlog2n)O(nlog^2n)O(nlog2n)内解决这样的问题于是想到分块。考虑对询问分块。使用对询问分块的算法的条件是
现在处理的询问块 之前的询问的影响 可以在O(n)O(n)O(n)时间内求出。显然可以满足处理好每一块的询问后作好标记处理下一块询问前把整张图再扫一遍即可。处理单独一个块内询问的复杂度应该为均摊一次O(B)O(B)O(B)其中B为块大小。
对于第二个条件因为受询问影响的点只有询问点到根的链并所以先构建块内所有询问点到根的链并实际上就是一棵虚树只不过1号点一定要存在在虚树中因为是链并显然构建的复杂度是O(BlogB)O(BlogB)O(BlogB)。虚树中同一条边上的点(原树上 处于虚树上相邻两点之间的 那些点)在所有的操作中它们的wi的变化量都是相同的那么我们可以将它们放到一起处理。具体来说对虚树上每条边建一个vectorvector中存处在这条边上的原树上的点把点按w值排好序把w值相同的合并到一起维护一个指针指向最后一个小于0的位置。每次操作后指针最多平移一位就可以维护这条边上的点对答案的贡献了。排序可以用桶排或基数排序优化。时间复杂度为O(n2BnB)O(\frac {n^2}BnB)O(Bn2nB)显然当BnB\sqrt nBn 时时间复杂度取最优为O(nn)O(n\sqrt n)O(nn)。
Code
#includeiostream
#includecstdio
#includecstring
#includealgorithm
#includevector
#includecmath
using namespace std;
int read(){int x0,f1;char chgetchar();while (ch0||ch9){if(ch-)f-1;chgetchar();}while (ch0ch9){xx*10ch-0;chgetchar();}return x*f;
}
const int N100005;
struct Edge{int v,nxt;}edge[N*2];
int n,m,cnt,head[N],t[N],ans[N];
int siz[N],top[N],dep[N],fa[N],ind,dfn[N],mx[N];
int tot,a[N],que[N],stack[N];
bool ins[N],col[N];
//col:颜色
//ins:是否为虚树上点
int b[N*2],c[N],bel[N];
//b[in]记录i的t值个数
//c[i]表示按t值排序后的第i位
//bel:对于虚树上每个点把它在实树里到虚树父亲的路径上的点全部提出来,标记成它的编号
vectorint stk,vec[N];
//vec:记录虚树上每个点在实树里到虚树父亲的路径
int p1[N],p2[N];
//p1:vec中的t值(已去重) p2[i]:vec中t值p1[i]且为白点的点个数
void addedge(int u,int v){edge[cnt].vv;edge[cnt].nxthead[u];head[u]cnt;
}
void dfs1(int x){dep[x]dep[fa[x]]1;dfn[x]ind;siz[x]1;for (int ihead[x];i;iedge[i].nxt)dfs1(edge[i].v),siz[x]siz[edge[i].v];mx[x]ind;
}
void dfs2(int x,int tp){top[x]tp;int k0;for(int ihead[x];i;iedge[i].nxt)if(siz[edge[i].v]siz[k]) kedge[i].v;if(k) dfs2(k,tp);for(int ihead[x];i;iedge[i].nxt)if (edge[i].v!k) dfs2(edge[i].v,edge[i].v);
}
int get_lca(int x,int y){while (top[x]!top[y]){if (dep[top[x]]dep[top[y]]) swap(x,y);xfa[top[x]];}return dep[x]dep[y]?x:y;
}
bool cmp(int x,int y){return dfn[x]dfn[y];
}
void build(){sort(a1,atot1,cmp);int top0;stack[top]1;stk.push_back(1);for(int i1;itot;i){if(a[i]stack[top]) continue;int lcaget_lca(a[i],stack[top]);if(lcastack[top]) {stack[top]a[i];stk.push_back(a[i]);continue;}while (dep[stack[top-1]]dep[lca]) top--;if(dep[stack[top]]dep[lca]) top--;if(stack[top]!lca) stack[top]lca,stk.push_back(lca);stack[top]a[i];stk.push_back(a[i]);}while(top1) top--;
}void work(int l,int r){for(int i1;in*2;i) b[i]0;for(int i1;in;i) b[t[i]n],bel[i]0;for(int i1;in*2;i) b[i]b[i-1];for(int i1;in;i) c[b[t[i]n]--]i;ins[0]1;for(int i0;istk.size();i) ins[stk[i]]1;for(int i0;istk.size();i)for(int jfa[stk[i]];!ins[j];jfa[j])bel[j]stk[i];int w0;for(int i1;in;i)if(bel[c[i]]) vec[bel[c[i]]].push_back(c[i]);//这样存到vec中就已经按t值排好序了 else w(!col[c[i]]t[c[i]]0!ins[c[i]]!bel[c[i]]);//这波修改是不会对不在虚树边上的点造成影响的 //处理不在虚树边上的点 for(int il;ir;i) ans[i]w;//逐一处理虚树中同一条边上的点 for(int i0;istk.size();i){int sz0,xstk[i];for(int j0;jvec[x].size();j)if(szp1[sz]t[vec[x][j]]) p2[sz](!col[vec[x][j]]);else p1[sz]t[vec[x][j]],p2[sz](!col[vec[x][j]]);int pts0,now0,tag0;//now:vec中对答案有贡献的点的个数 while(ptsszp1[pts1]0) pts,nowp2[pts];for(int jl;jr;j){col[que[j]]^1;if(dfn[que[j]]dfn[x]dfn[que[j]]dfn[x]siz[x]-1){t[x](!col[que[j]])?1:-1;tag(!col[que[j]])?1:-1;}while(ptsszp1[pts1]tag0) pts,nowp2[pts];while(ptsp1[pts]tag0) now-p2[pts],pts--;//两句while分别针对两种情况一句都不能少 ans[j]now;if(t[x]0!col[x]) ans[j];}for(int jl;jr;j) col[que[j]]^1;//复原 for(int j0;jvec[x].size();j) t[vec[x][j]]tag;//更新 }for(int il;ir;i) col[que[i]]^1;//更新
}
void clear(){for(int i0;istk.size();i){int xstk[i];vec[x].clear();ins[x]0;}stk.clear();
}
int main(){nread();mread();for(int i2;in;i) fa[i]read(),addedge(fa[i],i);for(int i1;in;i) t[i]read();for(int i1;im;i) que[i]abs(read());dfs1(1);dfs2(1,1);int Bsqrt(m);for (int i1;im;iB){int tmpcnt;tot0;for (int j0;jBijm;j) a[tot]que[ij];//que必须保持输入顺序只能拿a[]排序建虚树 build();work(i,min(m,iB-1));cnttmp;clear();}for(int i1;im;i) printf(%d ,ans[i]);return 0;
}参考文章 https://blog.csdn.net/qq_33229466/article/details/80331803 https://blog.csdn.net/Maxwei_wzj/article/details/81950058
