平衡树板子

Achen大佬说不要沉迷数据结构否则智商会降低的。

从省选考完后就开始学treap，首先是自己yy了一个打了两百多行，然后debug了2个月还是3个月记不清了。

最后弃疗，去找了网上别人的代码抄了一遍。

noip考完后补常规的一段时间，羡慕Achen能20分钟打出一个treap模板，于是自己也开始走上打板子的不归路。

到了后来可以10分钟左右打出一个结构体版的treap，看了Achen的数组版treap，觉得自己结构体版的太不优秀啦，于是就换成数组版的。

然后现在有几周没有碰过treap，感觉又不会打了。。。。不过还好，大概看一下又想起来了。

先放板子，还不会打题。

结构体版：

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<ctime>
using namespace std;
const int maxn=100000+10;
int n,tot=0,ans1,ans2,root;

int aa,ff;char cc;
int read() {
    aa=0;ff=1;cc=getchar();
    while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
    if(cc=='-') ff=-1,cc=getchar();
    while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
    return aa*ff;
}

struct Node{
    int num,rnd,son[2],sum,x;
}node[maxn];

void rotate(int &pos,int p) {
    int s=node[pos].son[p];
    node[s].sum=node[pos].sum;
    node[pos].son[p]=node[s].son[!p];
    node[s].son[!p]=pos;
    node[pos].sum=node[pos].x+node[node[pos].son[0]].sum+node[node[pos].son[1]].sum;
    pos=s;
}

void add(int &pos,int x) {
    if(!pos) {
        pos=++tot;node[pos].num=x;node[pos].rnd=rand();
        node[pos].sum=node[pos].x=1;
        return ;
    }
    node[pos].sum++;
    if(node[pos].num==x) {
        node[pos].x++; return;
    }
    int p=x>node[pos].num;
    add(node[pos].son[p],x);
    if(node[node[pos].son[p]].rnd<node[pos].rnd) rotate(pos,p);
}

void del(int &pos,int x) {
    if(!pos) return;
    if(node[pos].num==x) {
        if(node[pos].x>1) {
            node[pos].x--;node[pos].sum--;return;
        }
        if(node[pos].son[0]*node[pos].son[1]==0) {
            pos=node[pos].son[0]+node[pos].son[1]; return;
        }
        int p= node[node[pos].son[1]].rnd<node[node[pos].son[0]].rnd;
        rotate(pos,p);
        node[pos].sum--;
        del(node[pos].son[!p],x);
    }
    else {
        node[pos].sum--;
        if(node[pos].num>x) del(node[pos].son[0],x);
        else del(node[pos].son[1],x);
    }
}

int qrank(int pos,int x) {
    if(node[pos].num==x) return node[node[pos].son[0]].sum+1;
    if(node[pos].num>x) return qrank(node[pos].son[0],x);
    return node[node[pos].son[0]].sum+node[pos].x+qrank(node[pos].son[1],x);
}

int qnum(int pos,int x) {
    if(x>node[node[pos].son[0]].sum&&x<=node[node[pos].son[0]].sum+node[pos].x) return node[pos].num;
    if(x<=node[node[pos].son[0]].sum) return qnum(node[pos].son[0],x);
    return qnum(node[pos].son[1],x-node[pos].x-node[node[pos].son[0]].sum);
}

void q1(int pos,int x) {
    if(!pos) return;
    if(x>node[pos].num) {
        ans1=node[pos].num;
        q1(node[pos].son[1],x);
    }
    else q1(node[pos].son[0],x);
}

void q2(int pos,int x) {
    if(!pos) return;
    if(x<node[pos].num) {
        ans2=node[pos].num;
        q2(node[pos].son[0],x);
    }
    else q2(node[pos].son[1],x);
}

int main() {
    srand((unsigned)time(NULL));
    n=read();
    int opt,x,y;
    for(int i=1;i<=n;++i) {
        opt=read();x=read();
        if(opt==1) add(root,x);
        else if(opt==2) del(root,x);
        else if(opt==3) printf("%d
",qrank(root,x));
        else if(opt==4) printf("%d
",qnum(root,x));
        else if(opt==5) q1(root,x),printf("%d
",ans1);
        else q2(root,x),printf("%d
",ans2);
    }
    return 0;
}

数组版：

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1e5+10;
int n,tot,root,ans;
int sum[maxn],num[maxn],rnd[maxn],fx[maxn],son[maxn][2];

int aa,ff;char cc;
int read() {
    aa=0;cc=getchar();ff=1;
    while(cc<'0'||cc>'9') {
        if(cc=='-') ff=-1;
        cc=getchar();
    }
    while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
    return aa*ff;
}

void rotate(int &pos,int p) {
    int s=son[pos][p];
    sum[s]=sum[pos];
    son[pos][p]=son[s][!p];
    son[s][!p]=pos;
    sum[pos]=sum[son[pos][0]]+sum[son[pos][1]]+fx[pos];
    pos=s;
}

void add(int &pos,int x) {
    if(!pos) {
        pos=++tot;
        num[pos]=x;
        rnd[pos]=rand();
    }
    sum[pos]++;
    if(num[pos]==x) {
        fx[pos]++;
        return;
    }
    int p=x>num[pos];
    add(son[pos][p],x);
    if(rnd[son[pos][p]]<rnd[pos]) rotate(pos,p);
}

void del(int &pos,int x) {
    if(!pos) return;
    if(num[pos]==x) {
        if(fx[pos]>1) {
            fx[pos]--;
            sum[pos]--;
            return;
        }
        if(son[pos][0]*son[pos][1]==0) {
            pos=son[pos][0]+son[pos][1];
            return;
        }
        int p=rnd[son[pos][1]]<rnd[son[pos][0]];
        rotate(pos,p);sum[pos]--;
        del(son[pos][!p],x);
    }
    else {
        sum[pos]--;
        del(son[pos][x>num[pos]],x);
    }
}

int qnum(int pos,int x) {
    if(x>sum[son[pos][0]]&&x<=sum[son[pos][0]]+fx[pos]) return num[pos];
    if(x<=sum[son[pos][0]]) return qnum(son[pos][0],x);
    return qnum(son[pos][1],x-sum[son[pos][0]]-fx[pos]);
}

int qrank(int pos,int x) {
    if(x==num[pos]) return sum[son[pos][0]]+1;
    if(x<num[pos]) return qrank(son[pos][0],x);
    return sum[son[pos][0]]+fx[pos]+qrank(son[pos][1],x);
}

void q1(int pos,int x) {
    if(!pos) return;
    if(num[pos]<x) ans=num[pos],q1(son[pos][1],x);
    else q1(son[pos][0],x);
}

void q2(int pos,int x) {
    if(!pos) return;
    if(num[pos]>x) ans=num[pos],q2(son[pos][0],x);
    else q2(son[pos][1],x);
}
int main() {
    srand(1031);
    n=read();
    int op,x;
    for(int i=1;i<=n;++i) {
        op=read();x=read();
        switch(op) {
            case 1:add(root,x);break;
            case 2:del(root,x);break;
            case 3:printf("%d
",qrank(root,x));break;
            case 4:printf("%d
",qnum(root,x));break;
            case 5:q1(root,x);printf("%d
",ans);break;
            case 6:q2(root,x);printf("%d
",ans);break;
        }
    }
    return 0;
}

而非旋treap支持split和merge很是有趣，这次直接照着Achen的板子学，感受到Achen大佬的数据结构多么优秀。

merge的时候不想用pair然后就乱搞了一搞，调了一阵子，最后强制把代码改成自己的码风。感觉不是很难打。

普通平衡树版：

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=1e5+10,base=28;
int n,root,tot,ans;
int son[maxn][2],num[maxn],sum[maxn],rnd[maxn];

int aa,ff;char cc;
int read() {
	aa=0;ff=1;cc=getchar();
	while(cc!='-'&&(cc<'0'||cc>'9')) cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	return aa*ff;
}

void ud(int pos){sum[pos]=sum[lc]+sum[rc]+1;}
ll pr(int x,int y) {return ((ll)x<<base)+(ll)y;}//第一个ll要套在里面 
int fi(ll x){return x>>base;}
int se(ll x){return x-((ll)fi(x)<<base);}

int merge(int x,int y) {
	if((ll)x*y==0) return x^y;
	if(rnd[x]<rnd[y]) return son[x][1]=merge(son[x][1],y),ud(x),x;
	else return son[y][0]=merge(x,son[y][0]),ud(y),y;
}

ll split(int pos,int x) {
	if(!pos) return 0;
	ll rs;
	if(sum[lc]>=x) {
		rs=split(lc,x);
		lc=se(rs);
		rs=pr(fi(rs),pos);
	}
	else {
		rs=split(rc,x-sum[lc]-1);
		rc=fi(rs);
		rs=pr(pos,se(rs));
	}
	return ud(pos),rs;
}

int qrank(int pos,int x) {
	if(!pos) return 1;
	if(num[pos]<x) return sum[lc]+1+qrank(rc,x);
	return qrank(lc,x);
}

int qnum(int pos,int x) {
	if(x==sum[lc]+1) return num[pos];
	if(x<=sum[lc]) return qnum(lc,x);
	return qnum(rc,x-sum[lc]-1);
}

void q1(int pos,int x) {
    if(!pos) return;
    if(num[pos]<x) ans=num[pos],q1(son[pos][1],x);
    else q1(son[pos][0],x);
}
 
void q2(int pos,int x) {
    if(!pos) return;
    if(num[pos]>x) ans=num[pos],q2(son[pos][0],x);
    else q2(son[pos][1],x);
}

void add(int &pos,int x) {
	int k=qrank(pos,x); ++tot;
	num[tot]=x;sum[tot]=1;rnd[tot]=rand();
	ll p=split(pos,k-1);
	pos=merge(fi(p),tot);
	pos=merge(pos,se(p));
}

void del(int &pos,int x) {
	int k=qrank(pos,x);
	ll p=split(pos,k-1);
	ll q=split(se(p),1);
	pos=merge(fi(p),se(q));
}

int main() {
	srand(1031);n=read();
	int op,x;
	while(n--) {
		op=read(); x=read();
		switch(op) {
			case 1:add(root,x);break;
			case 2:del(root,x);break;
			case 3:printf("%d
",qrank(root,x));break;
			case 4:printf("%d
",qnum(root,x));break;
			case 5:q1(root,x);printf("%d
",ans);break;
            case 6:q2(root,x);printf("%d
",ans);break;
		}
	}
	return 0;
}

文艺平衡树版：

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=1e5+10,base=28;
int n,m,root,tot;
int son[maxn][2],num[maxn],sum[maxn],rnd[maxn],laz[maxn];

int aa;char cc;
int read() {
	aa=0;cc=getchar();
	while(cc<'0'||cc>'9') cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	return aa;
}

void ud(int pos){sum[pos]=sum[lc]+sum[rc]+1;}
void pd(int pos){if(!laz[pos])return;swap(lc,rc);laz[lc]^=1;laz[rc]^=1;laz[pos]=0;}
ll pr(int x,int y) {return ((ll)x<<base)+(ll)y;}
int fi(ll x){return x>>base;}
int se(ll x){return x-((ll)fi(x)<<base);}

int bld(int l,int r) {
	if(l>r) return 0;
	int mid=(l+r)>>1,pos=++tot;
	num[pos]=mid;sum[pos]=1;rnd[pos]=rand();
	lc=bld(l,mid-1);rc=bld(mid+1,r);
	return ud(pos),pos;
}

int merge(int x,int y) {
	if((ll)x*y==0) return x^y; pd(x); pd(y);
	if(rnd[x]<rnd[y]) return son[x][1]=merge(son[x][1],y),ud(x),x;
	else return son[y][0]=merge(x,son[y][0]),ud(y),y;
}

ll split(int pos,int x) {
	if(!pos) return 0;
	ll rs; pd(pos);
	if(sum[lc]>=x) {
		rs=split(lc,x);
		lc=se(rs);
		rs=pr(fi(rs),pos);
	}
	else {
		rs=split(rc,x-sum[lc]-1);
		rc=fi(rs);
		rs=pr(pos,se(rs));
	}
	return ud(pos),rs;
}

void rever() {
	int l=read(),r=read();
	ll p=split(root,l-1);
	ll q=split(se(p),r-l+1);
	laz[fi(q)]^=1;
	root=merge(fi(p),fi(q));
	root=merge(root,se(q));
}

void print_ans(int pos) {
	if(!pos) return; pd(pos);
	print_ans(lc);
	printf("%d ",num[pos]);
	print_ans(rc);
}

int main() {
	srand(1031);
	n=read(); m=read();
	root=bld(1,n);
	while(m--) rever();
	print_ans(root);
	return 0;
}

Achen说我的Splay不是正常人的打法，我也觉得，但是主要原因是我打Splay的时候有打treap的感觉，然后函数都是递归的不优秀。

特别烦rotate函数感觉贼难受。还需要多多练习才能熟悉啊。

普通平衡树版：

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=1e5+10;
int n,root,tot,ans;
int sum[maxn],fx[maxn],num[maxn],son[maxn][2],fa[maxn];

int aa,ff;char cc;
int read() {
	aa=0;ff=1;cc=getchar();
	while(cc<'0'||cc>'9') {
		if(cc=='-') ff=-1;
		cc=getchar();
	}
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	return aa*ff;
}

void ud(int pos){sum[pos]=sum[lc]+sum[rc]+fx[pos];}
void rotate(int pos) {
	int x,y,p; y=fa[x=fa[pos]]; p=son[x][1]==pos;
	fa[son[pos][!p]]=x;son[x][p]=son[pos][!p];
	fa[x]=pos;         son[pos][!p]=x;
	fa[pos]=y;         son[y][son[y][1]==x]=pos;
	ud(x);ud(pos);
	if(root==x) root=pos; fa[root]=fa[0]=0;
}

void splay(int pos,int &to) {
	int x,y;
	for(;pos!=to;rotate(pos)) {
		y=fa[x=fa[pos]];
		if(x!=to) (son[x][1]==pos ^ son[y][1]==x)? rotate(pos):rotate(x);
	}
}

void add(int &pos,int x,int f) {
	if(!pos) {
		pos=++tot;
		fa[pos]=f;
		num[pos]=x;
	}
	++sum[pos];
	if(num[pos]==x) {
		++fx[pos];
		return;
	}
	add(son[pos][x>num[pos]],x,pos);
} 

void q1(int pos,int x) {
	if(!pos) return;
	if(num[pos]<x) ans=pos,q1(rc,x);
	else q1(lc,x);
}

void q2(int pos,int x) {
	if(!pos) return;
	if(num[pos]>x) ans=pos,q2(lc,x);
	else q2(rc,x);
}

int qnum(int pos,int x) {
	if(x>sum[lc]&&x<=sum[lc]+fx[pos]) return ans=pos,num[pos];
	if(x<=sum[lc]) return qnum(lc,x);
	return qnum(rc,x-sum[lc]-fx[pos]);
}

int qrank(int pos,int x) {
	if(x==num[pos]) return ans=pos,sum[lc]+1;
	if(x<num[pos]) return qrank(lc,x);
	return sum[lc]+fx[pos]+qrank(rc,x);
}

void del(int x) {
	int a,b; a=b=qrank(root,x);
	splay(ans,root); --sum[root];
	if((--fx[root])!=0) return;
	if(!son[root][0]) fa[root=son[root][1]]=0;
	else if(!son[root][1]) fa[root=son[root][0]]=0;
	else {
		qnum(root,a-1);a=ans;
		qnum(root,b);  b=ans;
		splay(b,root); splay(a,son[b][0]);
		fa[son[a][1]]=0;
		son[a][1]=0;
	}
}

int main() {
	 n=read(); int op,x;
    for(int i=1;i<=n;++i) {
        op=read(); x=read(); fa[ans=0]=sum[0]=fx[0]=0;
        switch(op) {
        	case 1:add(root,x,0);break;
            case 2:del(x);break;
            case 3:printf("%d
",qrank(root,x));break;
            case 4:printf("%d
",qnum(root,x)); break;
            case 5:q1(root,x);printf("%d
",num[ans]);break;
            case 6:q2(root,x);printf("%d
",num[ans]);break;
        }
        if(op!=2&&ans&&ans<=tot) splay(ans,root);
    }
	return 0;
}　　

文艺平衡树版：

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=1e5+10;
int n,m,tot,root,ans;
int sum[maxn],num[maxn],son[maxn][2],fa[maxn],laz[maxn],zz[maxn];

int aa;char cc;
int read() {
	aa=0;cc=getchar();
	while(cc<'0'||cc>'9') cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	return aa;
}

void ud(int pos) {sum[pos]=sum[lc]+sum[rc]+1;}
void pd(int pos) {if(!laz[pos])return;swap(lc,rc);laz[lc]^=1;laz[rc]^=1;laz[pos]=0;}

void rotate(int pos) {
	int x,y,p; y=fa[x=fa[pos]]; p=son[x][1]==pos;
	fa[son[pos][!p]]=x;son[x][p]=son[pos][!p];
	fa[x]=pos;         son[pos][!p]=x;
	fa[pos]=y;         son[y][son[y][1]==x]=pos;
	ud(x); ud(pos);
	if(root==x) root=pos;fa[root]=fa[0]=0;
}

void splay(int pos,int &to) {
	int x,y,t=0;
	for(int p=pos;p!=to;p=fa[p]) zz[++t]=p;
	zz[++t]=to;
	while(t) pd(zz[t--]);
	for(;pos!=to;rotate(pos)) {
		y=fa[x=fa[pos]];
		if(x!=to) (son[x][1]==pos ^ son[y][1]==x)? rotate(pos):rotate(x);
	}
}

int bld(int l,int r,int f) {
	if(l>r) return 0;
	int pos=++tot,mid=(l+r)>>1;
	num[pos]=mid; sum[pos]=1; fa[pos]=f;
	lc=bld(l,mid-1,pos); rc=bld(mid+1,r,pos);
	return ud(pos),pos;
}

int qnum(int pos,int x) {
	pd(pos);if(x<1||x>sum[pos]) return ans=-1;
	if(x==sum[lc]+1) return num[ans=pos];
	if(x<=sum[lc]) return qnum(lc,x);
	return qnum(rc,x-sum[lc]-1);
}

void rever() {
	int l=read(),r=read(),a,b; ans=0;
	qnum(root,l-1); a=ans;
	qnum(root,r+1); b=ans;
	if(l==1&&r==n) laz[root]^=1;
	else if(l==1) splay(b,root),laz[son[b][0]]^=1;
	else if(r==n) splay(a,root),laz[son[a][1]]^=1;
	else {
		splay(b,root);
		splay(a,son[b][0]);
		laz[son[a][1]]^=1;
	}
}

void print_ans(int pos) {
    if(!pos) return; pd(pos);
    print_ans(lc);
    printf("%d ",num[pos]);
    print_ans(rc);
}

int main() {
	n=read(); m=read();
	root=bld(1,n,0);
	while(m--) rever();
	print_ans(root);
	return 0;
}

　　

bzoj1503郁闷的出纳员

没有什么好说的，就是一个模板题，treap、非旋treap、splay都可以。

一个技巧：对于所有员工工资上涨下降可以直接改变工资的最低值，但是注意加入一个员工时对员工工资的处理，还有查询第k大输出-1的情况。

普通treap：

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=1e5+10;
int n,slry,now,tot,root,ans,delans;
char s[23];
int sum[maxn],num[maxn],fx[maxn],son[maxn][2],rnd[maxn];

int aa;char cc;
int read() {
	aa=0;cc=getchar();
	while(cc<'0'||cc>'9') cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	return aa;
}

void rotate(int& pos,int p) {
	int s=son[pos][p];
	sum[s]=sum[pos];
	son[pos][p]=son[s][!p];
	son[s][!p]=pos;
	sum[pos]=sum[lc]+sum[rc]+fx[pos];
	pos=s;
}

void add(int& pos,int x) {
	if(!pos) {
		pos=++tot;
		num[pos]=x;
		rnd[pos]=rand();
	}
	++sum[pos];
	if(num[pos]==x) {
		++fx[pos];
		return;
	}
	int p=x>num[pos];
	add(son[pos][p],x);
	if(rnd[son[pos][p]]<rnd[pos]) rotate(pos,p); 
}

void del(int &pos,int x) {
	if(!pos) return;
	if(num[pos]==x) {
		if(fx[pos]>1) {
			--sum[pos];
			--fx[pos];
			return;
		}
		if((ll)son[pos][0]*son[pos][1]==0) {
			pos=son[pos][0]^son[pos][1];
			return;
		}
		int p=rnd[rc] < rnd[lc];
		rotate(pos,p); --sum[pos];
		del(son[pos][!p],x);
	}
	else {
		--sum[pos];
		del(son[pos][x>num[pos]],x);
	}
}

int qnum(int pos,int x) {
	if(x<=0) return -1+now-slry;
	if(x>sum[lc]&&x<=sum[lc]+fx[pos]) return num[pos];
	if(x<=sum[lc]) return qnum(lc,x);
	return qnum(rc,x-sum[lc]-fx[pos]);
}

int q(int pos) {
	if(lc) return q(lc);
	return num[pos];
}

void getadd(int x) {
	if(x<slry) return;
	add(root,x+now-slry);
}

void getdel(int x) {
	int num;
	while(root&&(num=q(root))<x) {
		++delans;
		del(root,num);
	}
}

int main() {
	srand(1031);
	n=read(); now=slry=read();
	for(int i=1;i<=n;++i) {
		scanf("%s",s+1);
		switch(s[1]) {
			case 'I':getadd(read());break;
			case 'A':now-=read(); break;
			case 'S':now+=read();getdel(now);break;
			case 'F':printf("%d
",qnum(root,sum[root]-read()+1)-now+slry);break;
		}
	}
	printf("%d",delans);
	return 0;
}

非旋treap：

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=1e5+10,base=25;
int n,slry,now,tot,root,ans,delans;
char s[23];
int sum[maxn],num[maxn],son[maxn][2],rnd[maxn];

int aa;char cc;
int read() {
	aa=0;cc=getchar();
	while(cc<'0'||cc>'9') cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	return aa;
}

void ud(int pos) {sum[pos]=sum[lc]+sum[rc]+1;}
ll pr(int x,int y) {return ((ll)x<<base)+(ll)y;}
int fi(ll x) {return x>>base;}
int se(ll x) {return x-((ll)fi(x)<<base);}

int merge(int x,int y) {
	if((ll)x*y==0) return x^y;
	if(rnd[x]<rnd[y]) return son[x][1]=merge(son[x][1],y),ud(x),x;
	return son[y][0]=merge(x,son[y][0]),ud(y),y;
}

ll split(int pos,int x) {
	if(!pos) return 0;
	ll rs;
	if(sum[lc]>=x) {
		rs=split(lc,x);
		lc=se(rs);
		rs=pr(fi(rs),pos);
	}
	else {
		rs=split(rc,x-sum[lc]-1);
		rc=fi(rs);
		rs=pr(pos,se(rs));
	}
	return ud(pos),rs;
}

int qrank(int pos,int x) {
	if(!pos) return 1;
	if(num[pos]<x) return sum[lc]+1+qrank(rc,x);
	return qrank(lc,x);
}

int qnum(int pos,int x) {
	if(x<=0) return -1+now-slry;
	if(x>sum[lc]&&x<=sum[lc]+1) return num[pos];
	if(x<=sum[lc]) return qnum(lc,x);
	return qnum(rc,x-sum[lc]-1);
}

void getadd(int &pos,int x) {
	if(x<slry) return;
	x+=now-slry;
    int k=qrank(pos,x); ++tot;
    num[tot]=x;sum[tot]=1;rnd[tot]=rand();
    ll p=split(pos,k-1);
    pos=merge(fi(p),tot);
    pos=merge(pos,se(p));
}

void getdel(int &pos,int x) {
	int k=qrank(pos,x);
	delans+=k-1;
	if(k==1) return;
	ll p=split(root,k-1);
	pos=se(p);
}

int main() {
	srand(1031);
	n=read(); now=slry=read();
	for(int i=1;i<=n;++i) {
		scanf("%s",s+1);
		switch(s[1]) {
			case 'I':getadd(root,read());break;
			case 'A':now-=read(); break;
			case 'S':now+=read();getdel(root,now);break;
			case 'F':printf("%d
",qnum(root,sum[root]-read()+1)-now+slry);break;
		}
	}
	printf("%d",delans);
	return 0;
}

　　

LCT

只要会Splay，LCT就很好打，第一次打是12月18日，因为直接是抄的板，所以1A，

昨天打SAM+LCT的时候发现有点快忘了LCT怎么打，就重新打了LCT，

然后link那里写成了newroot(y),fa[x]=y，所以死WA

然后用二分拼接代码法很快找到了bug

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=3e5+10;
int n,m,tot;
int fa[maxn],son[maxn][2],zz[maxn],sum[maxn],num[maxn],laz[maxn];

char cc;ll ff;
template<typename T>void read(T& aa) {
	aa=0;ff=1; cc=getchar();
	while(cc!='-'&&(cc<'0'||cc>'9')) cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

bool isroot(int pos) {return son[fa[pos]][0]!=pos&&son[fa[pos]][1]!=pos;}
void ud(int pos) {sum[pos]=sum[lc]^sum[rc]^num[pos];}
void pd(int pos) {
	if(!laz[pos]) return;
	laz[pos]=0; swap(lc,rc);
	if(lc) laz[lc]^=1;
	if(rc) laz[rc]^=1;
}

void rotate(int pos) {
	int x,y,p;y=fa[x=fa[pos]];
	p=son[x][1]==pos;
	if(!isroot(x)) son[y][son[y][1]==x]=pos;fa[pos]=y;
	son[x][p]=son[pos][!p]; fa[son[pos][!p]]=x;
	son[pos][!p]=x; fa[x]=pos;
	ud(x); ud(pos);
}

void splay(int pos) {
	int x,y,t=0;
	for(x=pos;!isroot(x);x=fa[x]) zz[++t]=x; zz[++t]=x;
	while(t) pd(zz[t--]);
	for(;!isroot(pos);rotate(pos)) {
		y=fa[x=fa[pos]];
		if(!isroot(x)) 
			(son[x][1]==pos)^(son[y][1]==x)? rotate(pos):rotate(x);
	}
}

void access(int pos) {
	for(int t=0;pos;pos=fa[t=pos]) {
		splay(pos); rc=t; ud(pos);
	}
}

int findroot(int pos) {
	access(pos);
	splay(pos);
	while(lc) pos=lc;
	return pos;
}

void newroot(int pos) {
	access(pos);
	splay(pos);
	laz[pos]^=1;
}

void lk(int x,int y) {
	if(findroot(x)==findroot(y)) return ;
	newroot(x);
	fa[x]=y;
}

void del(int x,int y) {
	newroot(x);
	access(y);
	splay(y);
	if(son[y][0]==x) fa[x]=son[y][0]=0;
}

int Yth(int x,int y) {
	newroot(x);
	access(y);
	splay(y);
	return sum[y];
}

void mdf(int x,int y) {
	splay(x);
	num[x]=y;
	ud(x);
}

int main() {
	read(n); read(m);
	int op,x,y;
	for(int i=1;i<=n;++i) read(num[i]);
	for(int i=1;i<=m;++i) {
		read(op); read(x); read(y);
		switch(op) {
			case 0:printf("%d
",Yth(x,y)); break;
			case 1:lk(x,y); break;
			case 2:del(x,y); break;
			case 3:mdf(x,y); break;
		}
	}
	return 0;
}

可持久化treap

就是在merge和split的时候新开一下节点就可以了

克服了心理障碍就没什么难打的

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define lc son[pos][0]
#define rc son[pos][1]
const ll maxn=1e6+7,base=25,INF=2147483647;
int n,tot,root[maxn];
int num[25*maxn],sum[25*maxn],rnd[25*maxn],son[25*maxn][2];

char cc;ll ff;
template<typename T>void read(T& aa) {
    aa=0;ff=1; cc=getchar();
    while(cc!='-'&&(cc<'0'||cc>'9')) cc=getchar();
    if(cc=='-') ff=-1,cc=getchar();
    while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
    aa*=ff;
}

ll pr(ll x,ll y) {return (x<<base)+y;}
ll fi(ll x) {return x>>base;}
ll se(ll x) {return x-(fi(x)<<base);}
void ud(int pos) {sum[pos]=sum[lc]+sum[rc]+1;}

void copy(int pos,int x) {
    num[pos]=num[x];
    sum[pos]=sum[x];
    rnd[pos]=rnd[x];
    lc=son[x][0]; rc=son[x][1];
}

bool exit(int pos,int x) {
    while(num[pos]!=x&&pos) {
        if(x<num[pos]) pos=lc;
        else pos=rc;
    }
    return pos;
}

int merge(int x,int y) {
    if((ll)x*y==0) return x^y;
    int pos=++tot;
    if(rnd[x]<rnd[y]) copy(pos,x),rc=merge(rc,y);
    else copy(pos,y),lc=merge(x,lc);
    return ud(pos),pos;
}

ll split(int p,int x) {
    if(!p) return 0;
    int pos=++tot; copy(pos,p);
    ll rs;
    if(sum[lc]>=x) {
        rs=split(lc,x);
        lc=se(rs);
        rs=pr(fi(rs),pos);
    }
    else {
        rs=split(rc,x-sum[lc]-1);
        rc=fi(rs);
        rs=pr(pos,se(rs));
    }
    return ud(pos),rs;
}

int qrank(int pos,int x) {
    if(!pos) return 1;
    if(num[pos]<x) return sum[lc]+1+qrank(rc,x);
    return qrank(lc,x);
}

int qnum(int pos,int x) {
    if(x==sum[lc]+1) return num[pos];
    if(x<=sum[lc]) return qnum(lc,x);
    return qnum(rc,x-sum[lc]-1);
}

void add(int &pos,int x) {
    int k=qrank(pos,x);
    ll p=split(pos,k-1);
    num[++tot]=x;sum[tot]=1;rnd[tot]=rand();
    pos=merge(fi(p),tot);
    pos=merge(pos,se(p));
}

void del(int &pos,int x) {
    if(!exit(pos,x)) return;
    int k=qrank(pos,x);
    ll p=split(pos,k-1);
    ll q=split(se(p),1);
    pos=merge(fi(p),se(q));
}

int q1(int pos,int x) {
    if(!pos) return -INF;
    if(num[pos]<x) return max(q1(rc,x),num[pos]);
    else return q1(lc,x);
}

int q2(int pos,int x) {
    if(!pos) return INF;
    if(num[pos]>x) return min(q2(lc,x),num[pos]);
    else return q2(rc,x);
}

int main() {
    srand(1031);
    read(n);int op,x,p;
    for(int i=1;i<=n;++i) {
        read(p); read(op); read(x);
        root[i]=root[p];
        switch(op) {
            case 1:add(root[i],x);break;
            case 2:del(root[i],x); break;
            case 3:printf("%d
",qrank(root[i],x));break;
            case 4:printf("%d
",qnum(root[i],x));break;
            case 5:printf("%d
",q1(root[i],x));break;
            case 6:printf("%d
",q2(root[i],x));break;
        }
        if(!root[i]) root[i]=merge(son[root[i]][0],son[root[i]][1]);
    }
    return 0;
}
/*
10
0 1 9
1 1 3
1 1 10
2 4 2
3 3 9
3 1 2
6 4 1
6 2 9
8 6 3
4 5 8
*/ 

树上莫队(uoj58糖果公园)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
const int maxn=1e5+7,maxs=21;
int n,m,q,size;
ll nowans,v[maxn],w[maxn],c[maxn],ans[maxn];

char cc;ll ff;
template<typename T>void read(T& aa) {
	aa=0;ff=1; cc=getchar();
	while(cc!='-'&&(cc<'0'||cc>'9')) cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

int dep[maxn],fa[maxn][maxs],dfn[maxn],dfsclock;
int bel[maxn],totb;
int zz[maxn],top;

struct Ask{
	int x,y,id,t;
	Ask(){}
	Ask(int x,int y,int id,int t):x(x),y(y),id(id),t(t){}
}ask[maxn];
int totask;
bool cmp(const Ask& a,const Ask& b) {
	return bel[a.x]==bel[b.x]? 
			(bel[a.y]==bel[b.y]? a.t<b.t:bel[a.y]<bel[b.y])
		:	bel[a.x]<bel[b.x];
}

struct Mdf{
	int pos,now,last;
	Mdf(){}
	Mdf(int pos,int now,int last):pos(pos),now(now),last(last){	}
}mdf[maxn];
int totmdf;

int fir[maxn],nxt[2*maxn],to[2*maxn],e=0;
void add(int x,int y) {
	to[++e]=y;nxt[e]=fir[x];fir[x]=e;
	to[++e]=x;nxt[e]=fir[y];fir[y]=e;
}

void together(int l,int &r) {
	++totb;  while(r>l) bel[zz[r--]]=totb;
}

void dfs(int pos,int d) {
	int bot=top,y,z;
	dfn[pos]=++dfsclock;
	dep[pos]=d;
	for(int i=1;i<20;++i) fa[pos][i]=fa[fa[pos][i-1]][i-1];
	for(y=fir[pos];y;y=nxt[y]) {
		if((z=to[y])==fa[pos][0]) continue;
		fa[z][0]=pos; dfs(z,d+1);
		if(top-bot>=size) together(bot,top);
	}
	zz[++top]=pos;
}

int get_lca(int x,int y) {
	if(dep[x]!=dep[y]) {
		if(dep[x]<dep[y]) swap(x,y);
		for(int i=19;(~i)&&dep[x]>dep[y];--i) 
			if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	}
	if(x==y) return x;
	for(int i=19;~i;--i) if(fa[x][i]!=fa[y][i]) {
		x=fa[x][i];y=fa[y][i];
	}
	return fa[x][0];
}

bool vis[maxn];int sum[maxn];
void chge(int pos,int p) {
	if(p) {
		sum[c[pos]]++;
		nowans+=(ll)w[sum[c[pos]]]*v[c[pos]];
	}
	else {
		nowans-=(ll)w[sum[c[pos]]]*v[c[pos]];
		sum[c[pos]]--;
	}
}

void fz(int x,int y) {
	int lca=get_lca(x,y);
	for(int i=x;i!=lca;i=fa[i][0]) chge(i,vis[i]^=1);
	for(int i=y;i!=lca;i=fa[i][0]) chge(i,vis[i]^=1);
}

int main() {
	read(n); read(m); read(q);
	size=0.5*pow(n,2.0/3);
	int op,x,y;
	for(int i=1;i<=m;++i) read(v[i]);
	for(int i=1;i<=n;++i) read(w[i]);
	for(int i=1;i<n;++i) {
		read(x); read(y);
		add(x,y);
	}
	dfs(1,1);
	while(top) bel[zz[top--]]=totb;
	for(int i=1;i<=n;++i) read(c[i]);
	for(int i=1;i<=q;++i) {
		read(op); read(x); read(y);
		if(!op) {mdf[++totmdf]=Mdf(x,y,c[x]);c[x]=y;}
		else {
			if(dfn[x]>dfn[y]) swap(x,y);
			++totask;
			ask[totask]=Ask(x,y,totask,totmdf);
		}
	}
	for(int i=totmdf;i;--i) c[mdf[i].pos]=mdf[i].last;
	
	sort(ask+1,ask+totask+1,cmp); 
	int nowt=0,pos,lastx=ask[1].x,lasty=ask[1].y;
	fz(lastx,lasty);
	for(int i=1;i<=totask;++i) {
		x=ask[i].x; y=ask[i].y;
		while(nowt>ask[i].t) {
			pos=mdf[nowt].pos;
			if(vis[pos]) chge(pos,0);
			c[pos]=mdf[nowt--].last;
			if(vis[pos]) chge(pos,1);
		}
		while(nowt<ask[i].t) {
			pos=mdf[++nowt].pos;
			if(vis[pos]) chge(pos,0);
			c[pos]=mdf[nowt].now;
			if(vis[pos]) chge(pos,1);
		}
		fz(lastx,x); fz(lasty,y);
		pos=get_lca(x,y);
		chge(pos,vis[pos]^=1);
		ans[ask[i].id]=nowans;
		chge(pos,vis[pos]^=1);
		lastx=x; lasty=y;
	}
	for(int i=1;i<=totask;++i) 	printf("%lld
",ans[i]);
	return 0;
}
/*
4 3 5
1 9 2
7 6 5 1
2 3
3 1
3 4
1 2 3 2
1 1 2
1 4 2
0 2 1
1 1 2
1 4 2
*/

一些Achen几万年前就A过的模板题：

bzoj1208宠物收养所

treap/splay随便维护一下即可

注意bz上交不能有srand，为此debug2h

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=1e5+7;
const ll mod=1000000;
int n,root,now=-1,tot; ll ans,INF=1e14;
int son[maxn][2],rnd[maxn];ll num[maxn];

char cc; ll ff;
template<typename T>void read(T& aa) {
	aa=0;cc=getchar();ff=1;
	while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

void rotate(int &pos,int p) {
	int s=son[pos][p];
	son[pos][p]=son[s][!p];
	son[s][!p]=pos;
	pos=s;
}

void add(int &pos,ll x) {
	if(!pos) {
		pos=++tot;
		num[pos]=x;
		rnd[pos]=rand()*rand();
		return;
	}
	int p=x>num[pos];
	add(son[pos][p],x);
	if(rnd[son[pos][p]]<rnd[pos]) rotate(pos,p);
}

void del(int &pos,ll x) {
	if(!pos) return;
	if(num[pos]==x) {
		if((ll)lc*rc==0) {
			pos=lc^rc;
			return;
		}
		int p=rnd[rc]<rnd[lc];
		rotate(pos,p);
		del(son[pos][!p],x);
	}
	else del(son[pos][x>num[pos]],x);
}

ll q1(int pos,ll x) {
	if(!pos) return -INF;
	if(num[pos]<=x) return max(q1(rc,x),num[pos]);
	return q1(lc,x);
}

ll q2(int pos,ll x) {
	if(!pos) return INF;
	if(num[pos]>=x) return min(q2(lc,x),num[pos]);
	return q2(rc,x);
}

int main() {
	read(n); ll x,y,p1,p2;
	For(i,1,n) {
		read(x); read(y);
		if(x==now||(!root)) {
			add(root,y); now=x;
		}
		else {
			p1=q1(root,y); p2=q2(root,y);
			if(y-p1<=p2-y) del(root,p1),ans+=(y-p1);
			else del(root,p2),ans+=(p2-y);
			ans%=mod;
		}
	}
	printf("%lld",ans);
	return 0;
}

bzoj2733永无乡

splay+启发式合并

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=1e5+7;
int n,m;
char s[maxn];
int num[maxn],sum[maxn],fa[maxn],son[maxn][2];

char cc; ll ff;
template<typename T>void read(T& aa) {
	aa=0;cc=getchar();ff=1;
	while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

int f[maxn];
int find(int x){return x==f[x]? x:f[x]=find(f[x]);}

void rotate(int pos) {
	int x,y,p; y=fa[x=fa[pos]]; p= son[x][1]==pos;
	fa[son[pos][!p]]=x; son[x][p]=son[pos][!p];
	fa[x]=pos; son[pos][!p]=x;
	fa[pos]=y; son[y][son[y][1]==x]=pos;
	sum[pos]=sum[x];
	sum[x]=sum[son[x][0]]+sum[son[x][1]]+1;
} 

void add(int &pos,int x,int f) {
	if(!pos) {
		pos=x;
		fa[pos]=f;
		return;
	}
	sum[pos]+=sum[x];
	add(son[pos][num[x]>num[pos]],x,pos);
}

void splay(int pos) {
	int x,y;
	for(;fa[pos];rotate(pos)) {
		y=fa[x=fa[pos]];
		if(y) (son[x][1]==pos ^ son[y][1]==x)? rotate(pos):rotate(x);
	}
}

void insert(int root,int pos) {
	if(!pos) return;
	int lson=lc,rson=rc;
	fa[lc]=fa[rc]=0; lc=rc=0;
	sum[pos]=1; add(root,pos,0);
	insert(root,lson); insert(root,rson);
}

void lik(int x,int y) {
	if(find(x)==find(y)) return;
	f[find(x)]=find(y);
	splay(x);splay(y);
	if(sum[x]<sum[y]) swap(x,y);
	insert(x,y);
}

int qnum(int pos,int x) {
	if(x==sum[lc]+1) return pos;
	if(x<=sum[lc]) return qnum(lc,x);
	return qnum(rc,x-sum[lc]-1);
}

int q(int pos,int x) {
	splay(pos);
	if(x>sum[pos]) return -1;
	return qnum(pos,x);
}

int main() {
	read(n); read(m);
	int x,y;
	For(i,1,n) f[i]=i,read(num[i]=i),sum[i]=1;
	For(i,1,m) {
		read(x); read(y);
		lik(x,y);
	}
	read(m);
	For(i,1,m) {
		scanf("%s",s+1); read(x); read(y);
		if(s[1]=='B') lik(x,y);
		else printf("%d
",q(x,y));
	}
	return 0;
}
/*
5 1           
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3
*/

bzoj2843极地旅行社

LCT

一开始1e5+7打+的时候按成了Backspace，结果打成1e7然后MLE了

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=1e5+7;
int n,m,f[maxn]; char s[maxn];
int fa[maxn],sum[maxn],son[maxn][2],num[maxn],laz[maxn];

char cc; ll ff;
template<typename T>void read(T& aa) {
	aa=0;cc=getchar();ff=1;
	while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

int find(int x){return x==f[x]? x:f[x]=find(f[x]);}

bool isroot(int pos){return son[fa[pos]][0]!=pos&&son[fa[pos]][1]!=pos;}
void ud(int pos) {sum[pos]=sum[lc]+sum[rc]+num[pos];}
void pd(int pos) {
	if(!laz[pos]) return;
	swap(lc,rc); laz[pos]=0;
	if(lc) laz[lc]^=1;
	if(rc) laz[rc]^=1;
}

void rotate(int pos) {
	int x,y,p; y=fa[x=fa[pos]]; p=son[x][1]==pos;
	if(!isroot(x)) son[y][son[y][1]==x]=pos; fa[pos]=y;
	son[x][p]=son[pos][!p]; fa[son[x][p]]=x;
	son[pos][!p]=x; fa[x]=pos;
	ud(x); ud(pos);
}

int zz[maxn];
void splay(int pos) {
	int x,y,t=0;
	for(x=pos;!isroot(x);x=fa[x]) zz[++t]=x; zz[++t]=x;
	while(t) pd(zz[t--]);
	for(;!isroot(pos);rotate(pos)) {
		y=fa[x=fa[pos]];
		if(!isroot(x)) (son[x][1]==pos ^ son[y][1]==x)? rotate(pos):rotate(x);
	}
}

void access(int pos) {
	for(int t=0;pos;pos=fa[t=pos]) {
		splay(pos); rc=t; ud(pos);
	}
}

void newroot(int pos) {
	access(pos);
	splay(pos);
	laz[pos]^=1;
}

void lik(int x,int y) {
	if(find(x)==find(y)) {
		printf("no
"); return;
	}
	printf("yes
");
	newroot(x); fa[x]=y; f[find(x)]=find(y);
}

void chge(int pos,int y) {
	splay(pos); 
	num[pos]=y; 
	ud(pos);
}

int q(int x,int y) {
	if(find(x)!=find(y)) return -1;
	newroot(x); access(y); splay(y);
	return sum[y];
}

int main() {
	read(n); int x,y,ans;
	For(i,1,n) read(num[i]),f[i]=i;
	read(m); 
	For(i,1,m) {
		scanf("%s",s+1); read(x); read(y);
		if(s[1]=='b') lik(x,y);
		else if(s[1]=='p') chge(x,y);
		else {
			ans=q(x,y);
			if(ans==-1) printf("impossible
");
			else printf("%d
",ans);
		}
	}
	return 0;
}
/*
5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5
*/

bzoj2002 弹飞绵羊

LCT：

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=2e5+7;
int n,m,sum[maxn],fa[maxn],son[maxn][2];

char cc; ll ff;
template<typename T>void read(T& aa) {
	aa=0;cc=getchar();ff=1;
	while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

void ud(int pos) {sum[pos]=sum[lc]+sum[rc]+1;}
bool isroot(int pos){return son[fa[pos]][0]!=pos&&son[fa[pos]][1]!=pos;}

void rotate(int pos) {
	int x,y,p; y=fa[x=fa[pos]]; p=son[x][1]==pos;
	if(!isroot(x)) son[y][son[y][1]==x]=pos; fa[pos]=y;
	son[x][p]=son[pos][!p]; fa[son[pos][!p]]=x;
	son[pos][!p]=x; fa[x]=pos;
	ud(x); ud(pos);
}

void splay(int pos) {
	int x,y;
	for(;!isroot(pos);rotate(pos)) {
		y=fa[x=fa[pos]];
		if(!isroot(x)) (son[x][1]==pos^son[y][1]==x)? rotate(pos):rotate(x);
	}
}

void access(int pos) {
	for(int t=0;pos;pos=fa[t=pos]) {
		splay(pos);
		rc=t;
		ud(pos);
	}
}

void cut(int x) {
	access(x); splay(x);
	fa[son[x][0]]=0; son[x][0]=0;
	ud(x);
}

int main() {
	read(n); int op,x,y;
	For(i,1,n+1) sum[i]=1;
	For(i,1,n) {
		read(x);
		fa[i]=min(i+x,n+1);
	}
	read(m);
	For(i,1,m) {
		read(op); read(x); x++;
		if(op==1) {
			access(x); 
			splay(x);
			printf("%d
",sum[son[x][0]]);
		}
		else {
			read(y);
			y=min(y+x,n+1);
			cut(x); 
			fa[x]=y;
		}
	}
	return 0;
}

Splay维护括号序列：

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=4e5+7;
int n,m,root,num[maxn],sum[maxn],fa[maxn],son[maxn][2];

char cc; ll ff;
template<typename T>void read(T& aa) {
	aa=0;cc=getchar();ff=1;
	while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

int fir[maxn],nxt[maxn],to[maxn],e=0;
void add(int x,int y) {
	to[++e]=y;nxt[e]=fir[x];fir[x]=e;
}

int dfn[maxn],end[maxn],dfn_clock;
void dfs(int pos) {
	num[dfn[pos]=++dfn_clock]=1;
	for(int y=fir[pos];y;y=nxt[y]) dfs(to[y]);
	num[end[pos]=++dfn_clock]=-1;
}

void ud(int pos) {sum[pos]=num[pos]+sum[lc]+sum[rc];}

void bld(int &pos,int l,int r,int f) {
	if(l>r) {pos=0;return;}
	pos=(l+r)>>1; fa[pos]=f;
	bld(lc,l,pos-1,pos);
	bld(rc,pos+1,r,pos);
	ud(pos);
}

void rotate(int pos) {
	int x,y,p; y=fa[x=fa[pos]]; p=son[x][1]==pos;
	if(y) son[y][son[y][1]==x]=pos; else root=pos; fa[pos]=y;
	son[x][p]=son[pos][!p]; fa[son[pos][!p]]=x;
	son[pos][!p]=x; fa[x]=pos;
	ud(x); ud(pos);
}

void splay(int pos) {
	int x,y;
	for(;fa[pos];rotate(pos)) {
		y=fa[x=fa[pos]];
		if(y) (son[x][1]==pos^son[y][1]==x)? rotate(pos):rotate(x);
	}
}

int split(int pos) {
	splay(pos); int rs;
	fa[rs=rc]=0; rc=0;
	ud(pos); 
	return rs;
}

void merge(int x,int y) {
	splay(x); splay(y);
	while(son[x][1]) x=son[x][1];
	splay(x); fa[y]=x; son[x][1]=y;
	ud(x);
}

int q(int pos) {
	splay(pos);
	pos=lc;
	while(rc) pos=rc;
	return pos;
}

int main() {
	read(n); int op,x,y,l,r;
	For(i,1,n) {
		read(x);
		x=min(i+x,n+1);
		add(x,i);
	}
	dfs(n+1);
	bld(root,1,dfn_clock,0);
	
	son[2*n+3][0]=root; fa[root]=2*n+3;
	ud(2*n+3); root=2*n+3;
	son[2*n+4][1]=root; fa[root]=2*n+4;
	ud(2*n+4); root=2*n+4;
	
	read(m);
	For(i,1,m) {
		read(op); read(x); ++x;
		if(op==1) {
			splay(x=dfn[x]);
			printf("%d
",sum[son[x][0]]);
		}
		else {
			read(y); y=min(y+x,n+1);
			l=q(dfn[x]);
			split(l);
			r=split(end[x]);
			merge(l,r);
			split(dfn[y]);
			merge(dfn[y],end[x]);
			merge(end[x],end[y]);
		}
	}
	return 0;
}

bzoj3786 星系探索

splay维护括号序列(下面是一份还T着的代码)

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=2e5+7;
int n,m,root;
char s[13];
ll w[maxn],d[maxn],tot[maxn],sum[maxn],num[maxn],laz[maxn];
int son[maxn][2],fa[maxn];

char cc; ll ff;
template<typename T>void read(T& aa) {
	aa=0;cc=getchar();ff=1;
	while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

int fir[maxn],nxt[maxn],to[maxn],e=0;
void add(int x,int y) {
	to[++e]=y;nxt[e]=fir[x];fir[x]=e;
}

int dfn[maxn],end[maxn],dfn_clock;
void dfs(int pos) {
	num[dfn[pos]=++dfn_clock]=w[pos]; d[dfn_clock]=1;
	for(int y=fir[pos];y;y=nxt[y]) dfs(to[y]);
	num[end[pos]=++dfn_clock]=-w[pos]; d[dfn_clock]=-1;
}

void ud(int pos) {sum[pos]=num[pos]+sum[lc]+sum[rc];tot[pos]=d[pos]+tot[lc]+tot[rc];}
void add_tag(int pos,ll x) {
	sum[pos]+=tot[pos]*x;
	num[pos]+=d[pos]*x;//
	laz[pos]+=x;
}
void pd(int pos) {
	if(!laz[pos]) return;
	if(lc) add_tag(lc,laz[pos]);
	if(rc) add_tag(rc,laz[pos]);
	laz[pos]=0;
}

void bld(int &pos,int l,int r,int f) {
	if(l>r) {pos=0;return;}
	pos=(l+r)>>1; fa[pos]=f;
	bld(lc,l,pos-1,pos);
	bld(rc,pos+1,r,pos);
	ud(pos);
}

void rotate(int pos) {
	int x,y,p; y=fa[x=fa[pos]]; p=son[x][1]==pos;
	if(y) son[y][son[y][1]==x]=pos; else root=pos; fa[pos]=y;
	son[x][p]=son[pos][!p]; fa[son[pos][!p]]=x;
	son[pos][!p]=x; fa[x]=pos;
	ud(x); ud(pos);
}

int zz[maxn];
void splay(int pos) {
	int t=0,x,y;
	for(int p=pos;p;p=fa[p]) zz[++t]=p;
	while(t) pd(zz[t--]);
	for(;fa[pos];rotate(pos)) {
		y=fa[x=fa[pos]];
		if(y) (son[x][1]==pos^son[y][1]==x)? rotate(pos):rotate(x);
	}
}

int split(int pos) {
	splay(pos); int rs;
	fa[rs=rc]=0; rc=0;
	ud(pos); return rs;
}

void merge(int x,int y) {
	splay(x); splay(y);//
	while(son[x][1]) pd(x),x=son[x][1];
	splay(x); fa[y]=x; son[x][1]=y;
	ud(x);
}

int q(int pos) {
	splay(pos); pos=lc;
	while(rc) pd(pos),pos=rc;
	return pos;
}

int main() {
	read(n); ll x,y,l,r;
	For(i,2,n) {
		read(x);
		add(x,i);
	}
	For(i,1,n) read(w[i]);
	dfs(1);
	bld(root,1,dfn_clock,0);
	
	son[2*n+3][0]=root; fa[root]=2*n+3;
	ud(2*n+3); root=2*n+3;
	son[2*n+4][1]=root; fa[root]=2*n+4;
	ud(2*n+4); root=2*n+4;
	
	read(m);
	For(i,1,m) {
		scanf("%s",s+1); read(x);
		if(s[1]=='Q') {
			splay(x=dfn[x]);
			printf("%lld
",sum[son[x][0]]+num[x]);
		}
		else if(s[1]=='C') {
			read(y);
			l=q(dfn[x]);
			split(l);
			r=split(end[x]);
			split(dfn[y]);
			merge(dfn[y],dfn[x]);
			merge(dfn[x],end[y]);
		}
		else {
			read(y);
			l=q(dfn[x]);
			split(l);
			r=split(end[x]);
			splay(dfn[x]);
			add_tag(dfn[x],y);
			merge(l,dfn[x]);
			merge(dfn[x],r);
		}
	}
	return 0;
}
/*
3
1
1
4 5 7
5
Q 2
F 1 3
Q 2
C 2 3
Q 2
*/

bzoj4530 大融合

LCT维护子树信息，又把rotate的p和!p写错了，debug真烦

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=1e5+7;
int n,m,fa[maxn],sum[maxn],tot[maxn],son[maxn][2],laz[maxn];
char s[13];

char cc; ll ff;
template<typename T>void read(T& aa) {
	aa=0;cc=getchar();ff=1;
	while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

bool isroot(int pos) {return son[fa[pos]][0]!=pos&&son[fa[pos]][1]!=pos;}
void ud(int pos){sum[pos]=sum[lc]+sum[rc]+tot[pos]+1;}
void pd(int pos) {
	if(!laz[pos]) return;
	swap(lc,rc);
	laz[lc]^=1;
	laz[rc]^=1;
	laz[pos]=0;
}

void rotate(int pos) {
	int x,y,p; y=fa[x=fa[pos]]; p=son[x][1]==pos;
	if(!isroot(x)) son[y][son[y][1]==x]=pos; fa[pos]=y;
	son[x][p]=son[pos][!p]; fa[son[pos][!p]]=x;
	son[pos][!p]=x; fa[x]=pos;
	ud(x); ud(pos);
}

int zz[maxn];
void splay(int pos) {
	int x,y,p,t=0;
	for(p=pos;!isroot(p);p=fa[p]) zz[++t]=p;
	zz[++t]=p;
	while(t) pd(zz[t--]);
	for(;!isroot(pos);rotate(pos)) {
		y=fa[x=fa[pos]];
		if(!isroot(x)) (son[x][1]==pos^son[y][1]==x)? rotate(pos):rotate(x);
	}
}

void access(int pos) {
	for(int t=0;pos;pos=fa[t=pos]) {
		splay(pos);
		tot[pos]+=sum[rc]-sum[t];
		rc=t; ud(pos);
	}
}

void newroot(int pos) {
	access(pos);
	splay(pos);
	laz[pos]^=1;
}

void lk(int x,int y) {
	newroot(x); newroot(y);
	fa[y]=x; tot[x]+=sum[y];
	ud(x);
}

int main() {
	read(n); read(m); int x,y;
	For(i,1,n) sum[i]=1;
	For(i,1,m) {
		scanf("%s",s+1);
		read(x); read(y);
		if(s[1]=='A') lk(x,y);
		else {
			newroot(x); newroot(y);
			printf("%lld
",(ll)(sum[y]-sum[x])*sum[x]);
		}
	}
	return 0;
}

UOJ207 共价大爷游长沙

LCT维护子树信息

num和sum没分清

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=3e5+7;
int n,m,son[maxn][2],fa[maxn],laz[maxn];
ll now,sum[maxn],num[maxn];

char cc; ll ff;
template<typename T>void read(T& aa) {
	aa=0;cc=getchar();ff=1;
	while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

struct Node{
	int x,y;ll num;
	Node(){}
	Node(int x,int y,ll num):x(x),y(y),num(num){}
}node[maxn];
int tot;

bool isroot(int pos){return son[fa[pos]][0]!=pos&&son[fa[pos]][1]!=pos;}
void ud(int pos){sum[pos]=sum[lc]^sum[rc]^num[pos];}
void pd(int pos) {
	if(!laz[pos]) return;
	swap(lc,rc);
	if(lc) laz[lc]^=1;
	if(rc) laz[rc]^=1;
	laz[pos]=0;
}

void rotate(int pos) {
	int x,y,p; y=fa[x=fa[pos]]; p=son[x][1]==pos;
	if(!isroot(x)) son[y][son[y][1]==x]=pos; fa[pos]=y;
	son[x][p]=son[pos][!p]; fa[son[pos][!p]]=x;
	son[pos][!p]=x; fa[x]=pos;
	ud(x); ud(pos);
}

int zz[maxn];
void splay(int pos) {
	int x,y,p,t=0;
	for(p=pos;!isroot(p);p=fa[p]) zz[++t]=p;
	zz[++t]=p;
	while(t) pd(zz[t--]);
	for(;!isroot(pos);rotate(pos)) {
		y=fa[x=fa[pos]];
		if(!isroot(x)) (son[x][1]==pos^son[y][1]==x)? rotate(pos):rotate(x);
	}
}

void access(int pos) {
	for(int t=0;pos;pos=fa[t=pos]) {
		splay(pos);
		num[pos]^=(sum[rc]^sum[t]);//
		rc=t;
		ud(pos);
	}
}

void newroot(int pos) {
	access(pos);
	splay(pos);
	laz[pos]^=1;
}

void lk(int x,int y) {
	newroot(x); newroot(y);//
	fa[y]=x; num[x]^=sum[y];
	ud(x);
}

void del(int x,int y) {
	newroot(x); access(y); splay(y);
	son[y][0]=fa[x]=0;
	ud(y);
}

int main() {
	srand(1031);
	read(n); int op,x,y; ll r;
	read(n); read(m);
	For(i,1,n-1) {
		read(x); read(y);
		lk(x,y);
	}
	For(i,1,m) {
		read(op);
		if(op==1) {
			read(x); read(y);
			del(x,y);
			read(x); read(y);
			lk(x,y);
		}
		else if(op==2) {
			read(x); read(y);
			node[++tot]=Node(x,y,r=rand()*rand());
			newroot(x); num[x]^=r; ud(x);
			newroot(y); num[y]^=r; ud(y);
			now^=r;
		}
		else if(op==3) {
			read(r);
			x=node[r].x; y=node[r].y;
			r=node[r].num;
			newroot(x); num[x]^=r; ud(x);
			newroot(y); num[y]^=r; ud(y);
			now^=r;
		}
		else {
			read(x); read(y);
			newroot(x); newroot(y);
			printf(sum[x]==now?"YES
":"NO
");
		}
	}
	return 0;
}
/*
0
5 7
1 2
1 3
2 4
1 5
2 1 5
1 1 5 2 5
4 2 5
2 1 4
4 2 5
3 1
4 2 4
*/

bzoj4573大森林

感觉是一道非常有意思的题

当时看到这道题也觉得这种题肯定是把所有树的共同点一起维护了，然后对于不同的树的查询修改些地方

对于每次换生长节点就建一个虚点(权为0)

然后生长就在上一个建的虚点上长实点(权为1)

先把虚点串起来，考虑离线后，按照区间从左到右做

一个虚点会在一段时间有用，就把他连到对于实点的下面

否则他的父亲就是上一个虚点。

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=3e5+7;
int n,m,ans[maxn];
int son[maxn][2],fa[maxn],sum[maxn],num[maxn];
int L[maxn],R[maxn],id[maxn],tid,tot,last;

char cc; ll ff;
template<typename T>void read(T& aa) {
	aa=0;cc=getchar();ff=1;
	while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

struct Ask{
	int pos,t,x,y;
	Ask(){}
	Ask(int pos,int t,int x,int y):pos(pos),t(t),x(x),y(y){}
	bool operator < (const Ask& b) const{return pos==b.pos? t<b.t:pos<b.pos;}
}ask[2*maxn];
int totask,totq;

void ud(int pos){sum[pos]=sum[lc]+sum[rc]+num[pos];}
int newnode(int x) {num[++tot]=x; ud(tot); return tot;}
bool isroot(int pos) {return son[fa[pos]][0]!=pos&&son[fa[pos]][1]!=pos;}

void rotate(int pos) {
	int x,y,p; y=fa[x=fa[pos]]; p=son[x][1]==pos;
	if(!isroot(x)) son[y][son[y][1]==x]=pos; fa[pos]=y;
	son[x][p]=son[pos][!p]; fa[son[pos][!p]]=x;
	son[pos][!p]=x; fa[x]=pos;
	ud(x); ud(pos);
}

void splay(int pos) {
	for(int x,y;!isroot(pos);rotate(pos)) {
		y=fa[x=fa[pos]];
		if(!isroot(x)) (son[x][1]==pos^son[y][1]==x)? rotate(pos):rotate(x);
	}
}

int access(int pos) {
	int t=0;
	for(;pos;pos=fa[t=pos]) {
		splay(pos);
		rc=t;
		ud(pos);
	}
	return t;
}

void lk(int x,int y) {
	splay(x);
	fa[x]=y;
}

void cut(int pos) {
	access(pos);
	splay(pos);
	fa[lc]=0; lc=0;
	ud(pos);
}

int Yth(int x,int y) {
	int rs=0,lca;
	access(x); splay(x); rs+=sum[x];
	lca=access(y); splay(y); rs+=sum[y];
	access(lca); splay(lca); rs-=2*sum[lca];
	return rs;
}

int main() {
	read(n); read(m);
	id[++tid]=newnode(1);L[1]=1;R[1]=n;
	newnode(0);lk(2,1);last=2;
	int op,l,r,x;
	For(i,1,m) {
		read(op);
		if(op==0) {
			read(l); read(r);
			id[++tid]=newnode(1);
			L[tot]=l; R[tot]=r;
			lk(tot,last);
		}
		else if(op==1) {
			read(l); read(r); read(x);
			l=max(l,L[id[x]]); r=min(r,R[id[x]]);
			if(l>r) continue;
			lk(newnode(0),last);
			ask[++totask]=Ask(l,i-m,tot,id[x]);
			ask[++totask]=Ask(r+1,i-m,tot,last);
			last=tot;
		}
		else {
			read(x); read(l); read(r);
			ask[++totask]=Ask(x,++totq,id[l],id[r]);
		}
	}
	sort(ask+1,ask+totask+1);
	For(i,1,totask) {
		if(ask[i].t<=0) {
			cut(ask[i].x);
			lk(ask[i].x,ask[i].y);
		}
		else ans[ask[i].t]=Yth(ask[i].x,ask[i].y);
	}
	For(i,1,totq) printf("%d
",ans[i]);
	return 0;
}
/*
5 5
0 1 5
1 2 4 2
0 1 4
2 1 1 3
2 2 1 3
*/

bzoj3669魔法森林

没有删除操作的动态MST问题

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=2e5+7,INF=0x3f3f3f3f;
int n,m,f[maxn],ans=INF;
int num[maxn],maxnum[maxn],son[maxn][2],fa[maxn],laz[maxn],tot;

char cc; ll ff;
template<typename T>void read(T& aa) {
	aa=0;cc=getchar();ff=1;
	while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

int find(int x) {return x==f[x]? x:f[x]=find(f[x]);}

struct Node{
	int x,y,a,b;
	bool operator < (const Node& r) const{return a==r.a? b<r.b:a<r.a;}
}node[maxn];

void ud(int pos){
	maxnum[pos]=num[maxnum[lc]]>num[maxnum[rc]]? maxnum[lc]:maxnum[rc];
	if(num[pos]>num[maxnum[pos]]) maxnum[pos]=pos;
}
bool isroot(int pos) {return son[fa[pos]][0]!=pos&&son[fa[pos]][1]!=pos;}
int newnode(int r) {num[++tot]=r; ud(tot); return tot;}
void pd(int pos) {
	if(!laz[pos]) return ;
	swap(lc,rc);
	if(lc) laz[lc]^=1;
	if(rc) laz[rc]^=1;
	laz[pos]=0;
}

void rotate(int pos) {
	int x,y,p; y=fa[x=fa[pos]]; p=son[x][1]==pos;
	if(!isroot(x)) son[y][son[y][1]==x]=pos; fa[pos]=y;
	son[x][p]=son[pos][!p]; fa[son[pos][!p]]=x;
	son[pos][!p]=x; fa[x]=pos;
	ud(x); ud(pos);
}

int zz[maxn];
void splay(int pos) {
	int x,y,t=0,p;
	for(p=pos;!isroot(p);p=fa[p]) zz[++t]=p; zz[++t]=p;
	while(t) pd(zz[t--]);
	for(;!isroot(pos);rotate(pos)) {
		y=fa[x=fa[pos]];
		if(!isroot(x)) (son[x][1]==pos^son[y][1]==x)? rotate(pos):rotate(x);
	}
}

void access(int pos) {
	for(int t=0;pos;pos=fa[t=pos]) {
		splay(pos);
		rc=t;
		ud(pos);
	}
}

void newroot(int pos) {
	access(pos);
	splay(pos);
	laz[pos]^=1;
}

void lk(int x,int y,int r) {
	int p=newnode(r);
	newroot(x); newroot(y);
	fa[x]=fa[y]=p;
}

void cut(int pos) {
	newroot(pos);
	splay(pos);
	fa[lc]=fa[rc]=0;
}

int Yth(int x,int y) {
	if(find(x)!=find(y)) return -1;
	newroot(x); 
	access(y); splay(y);
	return maxnum[y];
}

int main() {
	read(n); read(m);
	For(i,1,n) newnode(0),f[i]=i;
	For(i,1,m) {
		read(node[i].x);
		read(node[i].y);
		read(node[i].a);
		read(node[i].b);
	}
	sort(node+1,node+m+1);
	int x,y,pos;
	For(i,1,m) {
		x=node[i].x;
		y=node[i].y;
		if(find(x)!=find(y)) {
			f[find(x)]=find(y);
			lk(x,y,node[i].b);
		}
		else {
			pos=Yth(x,y);
			if(num[pos]>node[i].b) {
				cut(pos);
				lk(x,y,node[i].b);
			}
		}
		pos=Yth(1,n);
		if(~pos) ans=min(ans,num[pos]+node[i].a);
	}
	if(ans!=INF) printf("%d",ans);
	else printf("-1");
	return 0;
}
/*
4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17
*/

bzoj3595方伯伯的OJ

只要不卡常，什么都好，map+set+splay

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=6e5+7;
const ll Bs=1e7;
int n,m,tot,root;
int L[maxn],R[maxn],sum[maxn],num[maxn],fa[maxn],son[maxn][2];
map<int,int> G,H;

struct Node{
	int l,r,id;
	Node(int l,int r,int id):l(l),r(r),id(id){}
	bool operator < (const Node& b) const{return l==b.l? r<b.r : l<b.l;}
};

set<Node> P;
set<Node>::iterator it;

char cc; ll ff;
template<typename T>void read(T& aa) {
	aa=0;cc=getchar();ff=1;
	while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

ll pr(ll x,ll y) {return x*Bs+y;}
ll fi(ll x){return x/Bs;}
ll se(ll x){return x%Bs;}

void ud(int pos) {num[pos]=R[pos]-L[pos]+1; sum[pos]=num[pos]+sum[lc]+sum[rc];}
int newnode(int l,int r,int f) {
	fa[++tot]=f;
	L[tot]=l; R[tot]=r;
	P.insert(Node(l,r,tot));
	ud(tot); 
	if(f) ud(f);
	return tot;
}
void del(int pos) {
	Node o=Node(L[pos],R[pos],pos);
	it=P.lower_bound(o);
	P.erase(it);
	lc=rc=fa[pos]=0;
	num[pos]=sum[pos]=0;
}
int get_id(int x) {
	Node o=Node(x,x+1,0);
	it=P.lower_bound(o);
	if(it->l>x) --it;
	return it->id;
}

void rotate(int pos) {
	int x,y,p; y=fa[x=fa[pos]]; p=son[x][1]==pos;
	if(y) son[y][son[y][1]==x]=pos; 
	if(x==root) root=pos;
	fa[pos]=y;
	son[x][p]=son[pos][!p]; fa[son[pos][!p]]=x;
	son[pos][!p]=x; fa[x]=pos;
	ud(x); ud(pos);
}

void splay(int pos) {
	for(int x,y;fa[pos];rotate(pos)) {
		y=fa[x=fa[pos]];
		if(y) (son[x][1]==pos^son[y][1]==x)? rotate(pos):rotate(x);
	}
}

int merge(int x,int y) {
	if((ll)x*y==0) return x+y;
	splay(x); splay(y);
	while(son[x][1]) x=son[x][1];
	splay(x);
	son[x][1]=y; fa[y]=x;
	ud(y); ud(x);
	return x;
}

ll split(int pos,int x) {
	splay(pos);
	int ld=lc,rd=rc,l,r;
	del(pos);
	l=newnode(L[pos],x,0);
	r=newnode(x+1,R[pos],0);
	son[l][0]=ld; fa[ld]=l;
	son[r][1]=rd; fa[rd]=r;
	ud(l); ud(r);
	root=merge(l,r);
	return pr(l,r);
}

void cut(int pos) {
	splay(pos);
	fa[lc]=fa[rc]=0;
	root=merge(lc,rc);
	lc=rc=0;
}

int sep(int pos,int x) {
	if(L[pos]==x&&R[pos]==x) return pos;
	if(L[pos]!=x) pos=se(split(pos,x-1));
	if(R[pos]!=x) pos=fi(split(pos,x));
	return pos;
}

int qrank(int x) {
	int pos=get_id(x);
	splay(pos);
	return sum[lc]+(x-L[pos]+1);
}

int qnum(int pos,int &x) {
	if(x>sum[lc]&&x<=sum[lc]+num[pos]) return x-=sum[lc],pos;
	if(x<=sum[lc]) return qnum(lc,x);
	x-=sum[lc]+num[pos]; return qnum(rc,x);
}

int main() {
	read(n); read(m);
	newnode(1,n,0); root=1;
	son[1][0]=newnode(1,0,1);
	son[1][1]=newnode(n+1,n,1);
	int op,x,y,pos,p,last=0;
	For(i,1,m) {
		read(op); read(x); x-=last;
		if(op==1) {
			read(y); y-=last;
			G[y]=G[x]? G[x]:x; G[x]=0;
			H[G[y]]=y;
			last=qrank(G[y]);
		}
		else {
			if(op!=4&&G[x]) x=G[x];
			if(op==2) {
				pos=get_id(x);
				last=qrank(x);
				pos=sep(pos,x);
				cut(pos); cut(2);
				root=merge(pos,root);
				root=merge(2,pos);
			}
			else if(op==3) {
				pos=get_id(x);
				last=qrank(x);
				pos=sep(pos,x);
				cut(pos); cut(3);
				root=merge(root,pos);
				root=merge(root,3);
			}
			else {
				pos=qnum(root,x);
				x=x+L[pos]-1;
				last=H[x]? H[x]:x;
			}
		}
		printf("%d
",last);
	}
	return 0;
}
/*
10 10
1 2 11
3 13
2 5
3 7
2 8
2 10
2 11
3 14
2 18
4 9
*/