Description

Input

Output

Sample Input

10 10
0 1
1 2
2 4
3 12
2 6
2 15
3 5
3 10
7 7
9 16
2 3
1 10 9
2 6
2 5
1 1 8
1 4 13
1 3 11
2 8
2 12
2 14

Sample Output

4
15
6
10
8
11

Data Constraint

Solution

• 這題的話用兩棵 LCT 維護(hù)就可以了。

• 一棵是形態(tài) LCT ，另一棵是權(quán)值 LCT （Splay），實(shí)際上權(quán)值 LCT 是依據(jù)形態(tài) LCT 改變的。

• 每一塊中形態(tài)和權(quán)值 LCT 的點(diǎn)是深度一一對應(yīng)的。

• 那么加點(diǎn)的話，就將其父親 $xaccess$ （到根路徑上的權(quán)值已經(jīng)是單調(diào)的了），二分出合適的位置添加即可。

• 具體來講就是形態(tài) LCT 中 $x$ 后加一個(gè)點(diǎn)，權(quán)值 LCT 中二分出合適位置加上權(quán)值 $val$。

• 可以發(fā)現(xiàn)這樣點(diǎn)與點(diǎn)間仍能一一對應(yīng)。

• 那么詢問就很好詢問了，找到 $x$ 在權(quán)值 LCT 上對應(yīng)的值即可（kth）。

• 時(shí)間復(fù)雜度 $O(nlogn)$ 。

Code

#include<cstdio> #include<cctype> using namespace std; const int N=1e6+5; inline int max(int x,int y) {return x>y?x:y; } struct value {int mx[N],key[N],s[N][2],fa[N],size[N];inline bool pd(int x){return x==s[fa[x]][1];}inline void update(int x){mx[x]=max(max(mx[s[x][0]],mx[s[x][1]]),key[x]);size[x]=size[s[x][0]]+size[s[x][1]]+1;}inline void rotate(int x){int y=fa[x],w=pd(x);if(fa[x]=fa[y]) s[fa[y]][pd(y)]=x;if(s[y][w]=s[x][w^1]) fa[s[y][w]]=y;s[fa[y]=x][w^1]=y;update(y);}inline void splay(int x){for(int y;y=fa[x];rotate(x))if(fa[y]) rotate(pd(x)==pd(y)?y:x);update(x);}inline int kth(int x,int k){if(size[s[x][0]]+1==k) return x;if(size[s[x][0]]+1>k) return kth(s[x][0],k);return kth(s[x][1],k-size[s[x][0]]-1);}inline int root(int x){while(fa[x]) x=fa[x];return x;} }v; struct shape {int s[N][2],fa[N],size[N],nex[N];inline bool pd(int x){return x==s[fa[x]][1];}inline bool isroot(int x){return s[fa[x]][0]^x && s[fa[x]][1]^x;}inline void update(int x){size[x]=size[s[x][0]]+size[s[x][1]]+1;}inline void rotate(int x){int y=fa[x],w=pd(x);if((fa[x]=fa[y]) && !isroot(y)) s[fa[y]][pd(y)]=x;if(s[y][w]=s[x][w^1]) fa[s[y][w]]=y;nex[x]=nex[y],nex[y]=0;s[fa[y]=x][w^1]=y;update(y);}inline void splay(int x){for(int y;!isroot(x);rotate(x))if(!isroot(y=fa[x])) rotate(pd(x)==pd(y)?y:x);update(x);}inline void access(int x){for(int y=0;x;x=fa[y=x]){splay(x);int xx=v.root(nex[x]);xx=v.kth(xx,size[s[x][0]]+1);v.splay(nex[x]=xx);if(s[x][1]){nex[s[x][1]]=v.s[xx][1];v.fa[v.s[xx][1]]=0;v.s[xx][1]=s[x][1]=0;}if(y){s[x][1]=y;v.s[xx][1]=v.root(nex[y]);if(v.s[xx][1]) v.fa[v.s[xx][1]]=xx;}v.update(xx);update(x);}} }s; 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'); } int main() {freopen("heap.in","r",stdin);freopen("heap.out","w",stdout);int n=read(),q=read();for(int i=1;i<=n;i++){s.fa[i]=read();v.mx[i]=v.key[i]=read();v.size[i]=s.size[i]=1;s.nex[i]=i;}while(q--){int op=read();if(op==1){int x=read(),y=read();s.splay(x);int xx=s.nex[x];v.splay(xx);xx=v.kth(xx,s.size[s.s[x][0]]+1);s.access(x);v.splay(xx);if(v.key[xx]<y){v.fa[++n]=xx;v.key[n]=y;v.size[n]=1;v.s[xx][1]=n;v.update(xx);s.fa[n]=x;s.size[n]=1;s.s[x][1]=n;while(x) s.size[x]++,x=s.fa[x];continue;}int pos=xx;while(true){if(v.s[pos][0] && v.key[v.s[pos][0]]>y){pos=v.s[pos][0];continue;}if(v.s[pos][0] && v.mx[v.s[v.s[pos][0]][1]]>y){int p1=v.s[v.s[pos][0]][1];while(v.key[p1]<y) p1=v.s[p1][1];pos=p1;continue;}else break;}v.splay(pos);v.fa[++n]=pos;v.key[n]=y;v.size[n]=1;if(v.s[pos][0]){v.fa[v.s[pos][0]]=n;v.s[n][0]=v.s[pos][0];}v.s[pos][0]=n;pos=n;while(pos) v.update(pos),pos=v.fa[pos];v.splay(n);s.fa[n]=x;s.size[n]=1;s.s[x][1]=n;while(x) s.size[x]++,x=s.fa[x];}else{int x=read();s.splay(x);int xx=s.nex[x];v.splay(xx);xx=v.kth(xx,s.size[s.s[x][0]]+1);write(v.key[xx]),putchar('\n');}}return 0; } 與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5977. 【清华2019冬令营模拟12.15】堆的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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