CF1137F Matches Are Not a Child‘s Play(树上数据结构问题、树链剖分+ODT)
生活随笔
收集整理的這篇文章主要介紹了
CF1137F Matches Are Not a Child‘s Play(树上数据结构问题、树链剖分+ODT)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
Description
一棵 n 個點的樹,點權最初為 1 ~ n 的排列。
定義一個刪點過程:每次找到權值最小的葉子,刪去它以及連接的邊,重復這個過程直到剩下一個點,然后刪去最后的點。
處理 q 個詢問:
- 將一個點 x 的權值賦為當前最大權值 +1。
- 查詢在刪點過程中,x 會是第幾個被刪除的。
n, q ≤ 2×1052 \times 10^52×105
Solution
- 觀察到刪除序列的一些性質:
- 不難分析,一次賦值操作,不會影響非 y → x 路徑上的點的變葉子過程,所以造成的影響就是將 y → x 路徑提到序列最后,其他點的順序不變。(設給y賦值,x為原權值最大的點)
- 所以,不妨先把初始序列模擬出來,然后維護它。
- 轉化一下模型:修改權值變為將 y → x 的路徑染上一種新的顏色。
- 那么詢問 z 就變成了;多少點的顏色出現早于 z 顏色,以及與 z 同色的點優先于 z 的個數。
- 維護顏色/同色的優先級可以用樹鏈剖分 + 線段樹 或 樹鏈剖分 + ODT,每種顏色的點數可以直接樹狀數組。
- 具體講ODT做法:先樹剖,對于每一條重鏈,維護一個set,set里維護這條重鏈上的顏色區間。那么一次區間覆蓋只要把舊的區間刪去,并加入新的區間就行了。
Code
#include<iostream> #include<cstdio> #include<queue> #include<set> using namespace std; const int N=200035; const int M=400035; struct Edge{int v,nxt; }edge[M]; int n,q,cnt,head[N],tim,root[N*2]; int deg[N],fa[N],dep[N],siz[N],son[N],top[N],dfn[N],ind; char opt[20]; struct node{//ODTint l,r,val;node(int a=0,int b=0,int c=0):l(a),r(b),val(c) {}bool operator < (node b) const {return l<b.l;} }; set<node> s[N]; typedef set<node>::iterator itr; priority_queue<int,vector<int>,greater<int> > que; namespace BIT{int c[N*2];void add(int i,int x){for(i+=5;i<=n+q+5;i+=i&-i) c[i]+=x;}int sum(int i){int res=0;for(i+=5;i;i-=i&-i) res+=c[i];return res;} }; void add(int u,int v){edge[++cnt].v=v;edge[cnt].nxt=head[u];head[u]=cnt; } void dfs1(int u,int f){fa[u]=f;dep[u]=dep[f]+1;top[u]=son[u]=-1;siz[u]=1;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(v==f) continue;dfs1(v,u);siz[u]+=siz[v];if(son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;} } void dfs2(int u,int tp){if(u==tp){s[u].insert(node(n+1,n+1,0));}dfn[u]=++ind;top[u]=tp;if(son[u]==-1) return;dfs2(son[u],tp);for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(v!=fa[u]&&v!=son[u]) dfs2(v,v);} } itr split(int i,int pos){itr loc=s[i].lower_bound(node(pos));if(loc!=s[i].end()&&loc->l==pos) return loc;int l=(--loc)->l,r=loc->r,val=loc->val;s[i].erase(loc);s[i].insert(node(l,pos-1,val));return s[i].insert(node(pos,r,val)).first; } void insert(int i,int l,int r,int c){itr rpos=split(i,r+1),lpos=split(i,l);for (itr it=lpos;it!=rpos;++it)BIT::add(it->val,-(it->r-it->l+1));//遍歷清除歷史顏色s[i].erase(lpos,rpos);BIT::add(c,r-l+1);s[i].insert(node(l,r,c)); } int LCA(int u,int v){while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]) v=fa[top[v]];else u=fa[top[u]];}if(dep[u]<dep[v]) return u;return v; } int dist(int u,int v){int lca=LCA(u,v);return dep[u]+dep[v]-(dep[lca]<<1); } void ChainModify(int u,int v){while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]) swap(u,v);insert(top[u],dfn[top[u]],dfn[u],tim);u=fa[top[u]];}if(dep[u]<dep[v]) swap(u,v);insert(top[v],dfn[v],dfn[u],tim); } int query(int u){int c=split(top[u],dfn[u])->val;return BIT::sum(c-1)+dist(u,root[c-1])+1;//root[c-1]是指上一個歷史版本節點編號最大的一個元素 } int main(){scanf("%d%d",&n,&q);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);deg[x]++;deg[y]++;}dfs1(1,0);dfs2(1,1);//先搞出初始序列: for(int i=1;i<=n;i++) if(deg[i]==1) que.push(i);for(int i=1;i<=n;i++){int u=que.top();que.pop();root[i-1]=root[i]=u;//寫成root[i-1]=root[i]=u是因為對于初始序列,查詢時候要保持dist(u,root[c-1])=0;但是對于之后修改的詢問root[n]應該為nBIT::add(i,1);deg[u]=0;s[top[u]].insert(node(dfn[u],dfn[u],++tim));//node不加括號啊啊啊,為這個調了我一天 for(int i=head[u];i;i=edge[i].nxt)if((--deg[edge[i].v])==1) que.push(edge[i].v); }//不斷修改、查詢序列: for(int i=1;i<=q;i++){//用while(q--)就錯?why? int u,v;scanf("%s",opt);if(opt[0]=='u'){scanf("%d",&u);root[++tim]=u;ChainModify(u,root[tim-1]);}else if(opt[0]=='w'){scanf("%d",&u);printf("%d\n",query(u));}else{scanf("%d%d",&u,&v);printf("%d\n",(query(u)<query(v))?u:v);}}return 0; }參考文章:
https://www.cnblogs.com/bztMinamoto/p/10537308.html
https://www.cnblogs.com/antiquality/p/10660122.html
總結
以上是生活随笔為你收集整理的CF1137F Matches Are Not a Child‘s Play(树上数据结构问题、树链剖分+ODT)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 光遇圣岛季先祖任务位置在哪 光遇圣岛季先
- 下一篇: 求人原谅说什么 求女朋友原谅的话