Description

我曾在弦歌之中聽(tīng)過(guò)你，

檀板聲碎，半出折子戲。

舞榭歌臺(tái)被風(fēng)吹去，

歲月深處尚有余音一縷……

Gty神(xian)犇(chong)從來(lái)不缺妹子……

他來(lái)到了一棵妹子樹(shù)下，發(fā)現(xiàn)每個(gè)妹子有一個(gè)美麗度……

由于Gty很哲♂學(xué)，他只對(duì)美麗度大于某個(gè)值的妹子感興趣。

他想知道某個(gè)子樹(shù)中美麗度大于k的妹子個(gè)數(shù)。

某個(gè)妹子的美麗度可能發(fā)生變化……

樹(shù)上可能會(huì)出現(xiàn)一只新的妹子……

維護(hù)一棵初始有n個(gè)節(jié)點(diǎn)的有根樹(shù)(根節(jié)點(diǎn)為1)，樹(shù)上節(jié)點(diǎn)編號(hào)為1-n，每個(gè)點(diǎn)有一個(gè)權(quán)值wi。

支持以下操作：

0 u x 詢問(wèn)以u(píng)為根的子樹(shù)中，嚴(yán)格大于x的值的個(gè)數(shù)。(u^=lastans,x^=lastans)

1 u x 把u節(jié)點(diǎn)的權(quán)值改成x。(u^=lastans,x^=lastans)

2 u x 添加一個(gè)編號(hào)為"當(dāng)前樹(shù)中節(jié)點(diǎn)數(shù)+1"的節(jié)點(diǎn)，其父節(jié)點(diǎn)為u，其權(quán)值為x。(u^=lastans,x^=lastans)

最開(kāi)始時(shí)lastans=0。

Input

輸入第一行包括一個(gè)正整數(shù)n(1<=n<=30000)，代表樹(shù)上的初始節(jié)點(diǎn)數(shù)。

接下來(lái)n-1行，每行2個(gè)整數(shù)u,v，為樹(shù)上的一條無(wú)向邊。

任何時(shí)刻，樹(shù)上的任何權(quán)值大于等于0，且兩兩不同。

接下來(lái)1行，包括n個(gè)整數(shù)wi，表示初始時(shí)每個(gè)節(jié)點(diǎn)的權(quán)值。

接下來(lái)1行，包括1個(gè)整數(shù)m(1<=m<=30000)，表示操作總數(shù)。

接下來(lái)m行，每行包括三個(gè)整數(shù) op,u,v：

op,u,v的含義見(jiàn)題目描述。

保證題目涉及的所有數(shù)在int內(nèi)。

Output

對(duì)每個(gè)op=0，輸出一行，包括一個(gè)整數(shù)，意義見(jiàn)題目描述。

Sample Input

2

1 2

10 20

1

0 1 5

Sample Output

2

Solution

• 大家多用的是樹(shù)分塊的方法，這里我用的歸并樹(shù)+定期重構(gòu)。

• 具體怎樣呢？關(guān)鍵是我們考慮每個(gè)修改對(duì)之后詢問(wèn)的影響。

• 如果沒(méi)有修改（靜態(tài)詢問(wèn)），我們對(duì)dfs序建歸并樹(shù)，直接區(qū)間查詢即可。

• （歸并樹(shù)就是一種線段樹(shù)，區(qū)間內(nèi)存的是這個(gè)區(qū)間權(quán)值排序后的序列，查詢時(shí)在上面二分）

• 有了修改，我們就要判斷修改對(duì)詢問(wèn)有影響，其中修改點(diǎn)要在詢問(wèn)點(diǎn)的子樹(shù)內(nèi)。

• 如何判斷是否在子樹(shù)內(nèi)：倍增跳。加點(diǎn)時(shí)處理出其 $2^i$ 級(jí)父親。

• 于是我們得到這樣一個(gè)算法：我們?cè)跉w并樹(shù)中查詢后，針對(duì)若干修改操作暴力判斷影響。

• 那我們就可以定期重構(gòu)啦！

• 如果我們?cè)诓樵冎暗男薷牟怀^(guò) $\sqrt{m}$ 次時(shí)，就在歸并樹(shù)上查詢后暴力掃描修改計(jì)算貢獻(xiàn)；

• 如果修改超過(guò)了 $\sqrt{m}$ 次時(shí)，我們只要根據(jù)修改重建一下歸并樹(shù)就可以清除掉這些修改，

• 可以發(fā)現(xiàn)歸并樹(shù)的重建不會(huì)超過(guò) $\sqrt{m}$ 次。

• 那么我們來(lái)分析一下復(fù)雜度：（假設(shè) $n,m$ 同階）

• 每次掃描修改算貢獻(xiàn)，修改最多 $\sqrt{n}$ 個(gè)，每次倍增判是否在子樹(shù)要 $O(logn)$ ，復(fù)雜度為 $O(n\sqrt{n}logn)$ 。

• 每次重建歸并樹(shù)要 $O(nlogn)$ ，最多重建 $O(logn)$ 次，故復(fù)雜度同是 $O(n\sqrt{n}logn)$ 。

• 于是這題就解決了，總時(shí)間復(fù)雜度 $O(n\sqrt{n}logn)$ 。

• 有一些細(xì)節(jié)要注意：

• 由于重建歸并樹(shù)常數(shù)比較大，我們可以多幾次修改再重建一次，比如說(shuō) $5?\sqrt{n}$ 。

• 還有就是打線段樹(shù)詢問(wèn)時(shí)：$find(1,1,n)$ ，由于加點(diǎn)時(shí) $n$ 會(huì)增加，但帶進(jìn)詢問(wèn)時(shí)仍然要是之前的 $n$ ，不然就不對(duì)了，重構(gòu)時(shí)再把 $find(1,1,n)$ 的 $n$ 改成新的。

Code

#include<cstdio> #include<algorithm> #include<cmath> #include<vector> #include<cctype> using namespace std; const int N=60005; struct data {int op,x,y,z; }q[N>>1]; int n,tot,num,cnt,qx,qy,qz,last,lim; int first[N],nex[N<<1],en[N<<1]; int w[N],dfn[N],size[N],id[N],dep[N],fa[N][16]; vector<int>ss[N<<2]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline void insert(int x,int y) {nex[++tot]=first[x];first[x]=tot;en[tot]=y; } void dfs(int x) {dfn[x]=++cnt;id[cnt]=x;size[x]=1;dep[x]=dep[fa[x][0]]+1;for(int i=first[x];i;i=nex[i])if(en[i]^fa[x][0]){fa[en[i]][0]=x;dfs(en[i]);size[x]+=size[en[i]];} } void make(int v,int l,int r) {ss[v].clear();if(l==r){ss[v].push_back(w[id[l]]);return;}int mid=l+r>>1,ls=v<<1,rs=ls|1;make(ls,l,mid);make(rs,mid+1,r);int i=0,ni=ss[ls].size()-1;int j=0,nj=ss[rs].size()-1;while(i<=ni && j<=nj) ss[v].push_back(ss[ls][i]<ss[rs][j]?ss[ls][i++]:ss[rs][j++]);while(i<=ni) ss[v].push_back(ss[ls][i++]);while(j<=nj) ss[v].push_back(ss[rs][j++]); } int find(int v,int l,int r) {if(qx<=l && r<=qy) return ss[v].size()-(upper_bound(ss[v].begin(),ss[v].end()--,qz)-ss[v].begin());int mid=l+r>>1,s=0;if(qx<=mid) s=find(v<<1,l,mid);if(qy>mid) s+=find(v<<1|1,mid+1,r);return s; } void dfs1(int x) {size[x]=1;dfn[x]=++cnt;id[cnt]=x;for(int i=first[x];i;i=nex[i])if(en[i]^fa[x][0]){dfs(en[i]);size[x]+=size[en[i]];} } inline void rebuild() {cnt=num=0;dfs1(1);make(1,1,n);cnt=n; } inline bool belong(int x,int y) {if(dep[x]<dep[y]) return false;for(int i=log2(dep[x]);i>=0;i--)if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];return x==y; } int main() {n=read();for(int i=1;i<n;i++){int x=read(),y=read();insert(x,y);insert(y,x);}for(int i=1;i<=n;i++) w[i]=read();dfs(1);cnt=n;for(int j=1;j<16;j++)for(int i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];make(1,1,n);int m=read();lim=ceil(sqrt(m)*5);while(m--){int op=read(),x=read()^last,y=read()^last;if(op==0){if(x<=cnt){qx=dfn[x],qy=dfn[x]+size[x]-1,qz=y;last=find(1,1,cnt);}else last=0;for(int i=1;i<=num;i++)if(q[i].op==1){if((q[i].y<y)^(q[i].z<y) && belong(q[i].x,x)) last+=q[i].z>y?1:-1;}else{if(q[i].z>y && belong(q[i].x,x)) last++;}write(last),putchar('\n');}elseif(op==1){q[++num]=(data){1,x,w[x],y};w[x]=y;if(num==lim) rebuild();}else{q[++num]=(data){2,++n,x,y};insert(x,n);insert(n,x);fa[n][0]=x;dep[n]=dep[x]+1;w[n]=y;for(int i=1;i<16;i++) fa[n][i]=fa[fa[n][i-1]][i-1];if(num==lim) rebuild();}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ 3720 [洛谷P2137] : Gty的妹子树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。