Lvat_s Blog

两个都是可持久化线段树，相当于复习一下算法。。

第一个程序我没加路径压缩，第二个加了

第二个读入的操作编号不要异或lastans……在这里卡了一下

#include<cstdio>
#include<algorithm>
using namespace std;

struct SegTree{
int l,r,ls,rs,v;
}tree[2000005];

int root[20005],cnt,deep[200005],n,m;

void Build(int &rt,int l,int r){
if(!rt)rt=++cnt;
if(l==r){tree[rt].v=l;return;}
int mid=l+r>>1;
tree[rt].l=l;
tree[rt].r=r;
Build(tree[rt].ls,l,mid);
Build(tree[rt].rs,mid+1,r);
}

void Change(int x,int &y,int pos,int val){
y=++cnt;
tree[y].l=tree[x].l;
tree[y].r=tree[x].r;
if(tree[x].l==tree[x].r){tree[y].v=val;deep[y]=deep[x];return;}
tree[y].ls=tree[x].ls;
tree[y].rs=tree[x].rs;
int mid=tree[x].l+tree[x].r>>1;
if(pos<=mid)Change(tree[x].ls,tree[y].ls,pos,val);
if(pos>mid)Change(tree[x].rs,tree[y].rs,pos,val);
}

int Query(int rt,int pos){
if(tree[rt].l==tree[rt].r)return rt;
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)return Query(tree[rt].ls,pos);
if(pos>mid)return Query(tree[rt].rs,pos);
}

void Add(int rt,int pos){
if(tree[rt].l==tree[rt].r){deep[rt]++;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)Add(tree[rt].ls,pos);
if(pos>mid)Add(tree[rt].rs,pos);
}

int Find(int rt,int x){
int tp=Query(rt,x);
if(x==tree[tp].v)return tp;
return Find(rt,tree[tp].v);
}

int main(){
freopen("3673.in","r",stdin);
freopen("3673.out","w",stdout);
scanf("%d %d",&n,&m);
Build(root[0],1,n);
for(int i=1;i<=m;i++){
    int opt;
    scanf("%d",&opt);
    if(opt==1){
		int x,y,px,py;
        scanf("%d %d",&x,&y);
        root[i]=root[i-1];
        px=Find(root[i],x);py=Find(root[i],y);
        if(tree[px].v==tree[py].v)continue;
        if(deep[px]>deep[py])swap(px,py);
        Change(root[i-1],root[i],tree[px].v,tree[py].v);
        if(deep[px]==deep[py])Add(root[i],tree[py].v);
    }
    if(opt==2){
		int k;
		scanf("%d",&k);
		root[i]=root[k];
    }
    if(opt==3){
		int x,y;
		root[i]=root[i-1];
		scanf("%d %d",&x,&y);
		if(tree[Find(root[i],x)].v!=tree[Find(root[i],y)].v)puts("0");
		else puts("1");
    }
}
return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,cnt,lastans=0,deep[10000005],root[200005];

struct SegTree{
int l,r,ls,rs,v;
}tree[10000005];

void Build(int &rt,int l,int r){
if(!rt)rt=++cnt;
tree[rt].l=l;
tree[rt].r=r;
if(l==r){tree[rt].v=l;return;}
int mid=l+r>>1;
Build(tree[rt].ls,l,mid);
Build(tree[rt].rs,mid+1,r);
}

void Change(int x,int &y,int pos,int val){
y=++cnt;
tree[y].l=tree[x].l;
tree[y].r=tree[x].r;
if(tree[x].l==tree[x].r){tree[y].v=val;deep[y]=deep[x];return;}
tree[y].ls=tree[x].ls;
tree[y].rs=tree[x].rs;
int mid=tree[x].l+tree[x].r>>1;
if(pos<=mid)Change(tree[x].ls,tree[y].ls,pos,val);
if(pos>mid)Change(tree[x].rs,tree[y].rs,pos,val);
}

void Add(int rt,int pos){
if(tree[rt].l==tree[rt].r){deep[rt]++;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)Add(tree[rt].ls,pos);
if(pos>mid)Add(tree[rt].rs,pos);
}

int Query(int rt,int pos){
if(tree[rt].l==tree[rt].r){return rt;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)return Query(tree[rt].ls,pos);
if(pos>mid)return Query(tree[rt].rs,pos);
}

int Find(int rt,int x){
int p=Query(rt,x);
if(x==tree[p].v){return p;}
int tp=Find(rt,tree[p].v);
Change(rt,rt,tree[p].v,tp);
return tp;
}

int main(){
freopen("3674.in","r",stdin);
freopen("3674.out","w",stdout);
scanf("%d %d",&n,&m);
Build(root[0],1,n);
for(int i=1;i<=m;i++){
    int opt;
    scanf("%d",&opt);
    if(opt==1){
		int x,y,p,q;
		scanf("%d %d",&x,&y);
		x^=lastans;y^=lastans;
        root[i]=root[i-1];
        p=Find(root[i],x);
        q=Find(root[i],y);
        if(tree[p].v==tree[q].v)continue;
        if(deep[p]>deep[q])swap(p,q);
        Change(root[i-1],root[i],tree[p].v,tree[q].v);
        if(deep[p]==deep[q])Add(root[i],tree[q].v);
    }
    if(opt==2){
		int k;
		scanf("%d",&k);
		k^=lastans;
        root[i]=root[k];
    }
    if(opt==3){
		int x,y;
		scanf("%d %d",&x,&y);
		x^=lastans;y^=lastans;
		root[i]=root[i-1];
        if(tree[Find(root[i],x)].v==tree[Find(root[i],y)].v){puts("1");lastans=1;}
        else {puts("0");lastans=0;}
	}
}
return 0;
}

Splay模版题

调试两天总算A啦！

2016/2/21 *1

2016/3/20 *1

#include<cstdio>
#include<algorithm>
using namespace std;

int n,a[1000005],m;

struct Node{
int v,mx,sum,lx,rx,siz,tag,rev;
Node *ch[2],*fa;
Node(int val,Node *fat);
void Pushdown();
void Pushup();
}*root,*Null;

Node::Node(int val=0,Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
v=sum=mx=val;
tag=rev=0;
siz=1;
if(v>=0)lx=rx=v;
else lx=rx=0;
}

void Node::Pushdown(){
if(tag){
	tag=rev=0;
	if(ch[0]!=Null){ch[0]->tag=1;ch[0]->sum=ch[0]->siz*v;ch[0]->v=v;}
	if(ch[1]!=Null){ch[1]->tag=1;ch[1]->sum=ch[1]->siz*v;ch[1]->v=v;}
	if(v>=0){
        if(ch[0]!=Null){ch[0]->lx=ch[0]->mx=ch[0]->rx=v*ch[0]->siz;}
        if(ch[1]!=Null){ch[1]->lx=ch[1]->mx=ch[1]->rx=v*ch[1]->siz;}
	}
	else {
		if(ch[0]!=Null){ch[0]->mx=v;ch[0]->lx=ch[0]->rx=0;}
        if(ch[1]!=Null){ch[1]->mx=v;ch[1]->lx=ch[1]->rx=0;}
	}
}
if(rev){
	rev=0;
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0]->ch[0],ch[0]->ch[1]);
	swap(ch[1]->ch[0],ch[1]->ch[1]);
	swap(ch[0]->lx,ch[0]->rx);
	swap(ch[1]->lx,ch[1]->rx);
}
}

void Node::Pushup(){
siz=ch[0]->siz+ch[1]->siz+1;
sum=ch[0]->sum+ch[1]->sum+v;
mx=max(ch[0]->mx,ch[1]->mx);
mx=max(mx,ch[0]->rx+v+ch[1]->lx);
lx=max(ch[0]->lx,ch[0]->sum+v+ch[1]->lx);
rx=max(ch[1]->rx,ch[1]->sum+v+ch[0]->rx);
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x,Node *place){
while(x->fa!=place){
	Node *y=x->fa,*z=y->fa;
	if(z==Null || z==place)Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
if(place==Null)root=x;
}

Node *Find(Node *splay,int k){
splay->Pushdown();
if(splay->ch[0]->siz+1==k)return splay;
if(splay->ch[0]->siz>=k)return Find(splay->ch[0],k);
return Find(splay->ch[1],k-1-splay->ch[0]->siz);
}

Node *Split(int pos,int tot){
Node *x=Find(root,pos);
Splay(x,Null);
Node *y=Find(root,pos+tot+1);
Splay(y,root);
return y->ch[0];
}

Node *Build(int l,int r){
if(l>r)return Null;
int mid=l+r>>1;
Node *splay=new Node(a[mid],Null);
splay->ch[0]=Build(l,mid-1);
if(splay->ch[0]!=Null)splay->ch[0]->fa=splay;
splay->ch[1]=Build(mid+1,r);
if(splay->ch[1]!=Null)splay->ch[1]->fa=splay;
splay->Pushup();
return splay;
}

void Insert(int pos,int tot){
Node *x=Find(root,pos+1),*y=Find(root,pos+2);
Splay(x,Null);Splay(y,root);
y->ch[0]=Build(1,tot);
if(y->ch[0]!=Null)y->ch[0]->fa=y;
y->Pushup();
x->Pushup();
}

Node *GetNull(){
Node *p=new Node(0,Null);
p->fa=p->ch[0]=p->ch[1]=p;
p->mx=p->v=-1000000000;
p->rev=p->tag=p->siz=p->sum=p->lx=p->rx=0;
return p;
}

void Build_First(){
Null=GetNull();
a[1]=-1000000000;
a[n+2]=-1000000000;
root=Build(1,n+2);
}

void Del_Tree(Node *splay){
if(splay==Null)return;
splay->Pushdown();
Del_Tree(splay->ch[0]);
Del_Tree(splay->ch[1]);
if(splay->ch[0]!=Null)delete splay->ch[0];
if(splay->ch[1]!=Null)delete splay->ch[1];
splay->ch[0]=Null;
splay->ch[1]=Null;
splay->Pushup();
}

void Delete(int pos,int val){
Node *seq=Split(pos,val),*fat=seq->fa;
Del_Tree(seq);
if(seq!=Null)delete seq;
fat->ch[0]=Null;
fat->Pushup();
fat->fa->Pushup();
}

void MakeSame(int pos,int tot,int val){
Node *seq=Split(pos,tot),*fat=seq->fa;
seq->tag=1;
seq->sum=seq->siz*val;
seq->v=val;
if(val>=0)seq->lx=seq->rx=seq->mx=seq->siz*val;
else seq->lx=seq->rx=0,seq->mx=val;
fat->Pushup();
fat->fa->Pushup();
}

void Reverse(int pos,int tot){
Node *seq=Split(pos,tot),*fat=seq->fa;
if(!seq->tag){
	seq->rev^=1;
	swap(seq->ch[0],seq->ch[1]);
	swap(seq->lx,seq->rx);
	fat->Pushup();
	fat->fa->Pushup();
}
}

int GetSum(int pos,int tot){
Node *seq=Split(pos,tot);
return seq->sum;
}

int main(){
freopen("1500.in","r",stdin);
freopen("1500.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=2;i<=n+1;i++)scanf("%d",&a[i]);
Build_First();
for(int i=1;i<=m;i++){
	char s[10];
    scanf("%s",s);
    if(s[0]=='I'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		for(int i=1;i<=tot;i++)scanf("%d",&a[i]);
		Insert(pos,tot);
	}
	if(s[0]=='D'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		Delete(pos,tot);
	}
	if(s[0]=='M' && s[2]=='K'){
		int pos,tot,val;
		scanf("%d %d %d",&pos,&tot,&val);
        MakeSame(pos,tot,val);
	}
	if(s[0]=='M' && s[2]=='X'){
		printf("%d\n",root->mx);
	}
	if(s[0]=='R'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		Reverse(pos,tot);
	}
	if(s[0]=='G'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		printf("%d\n",GetSum(pos,tot));
	}
}
return 0;
}

无语了……

参考hzwer的题解，我自己没想出来……

具体就是先搞一遍LCA，再分三种情况判断

详见hzwer题解：传送门

判定ROOT时居然写了if(ROOT=x)简直爆炸

没救了

#include<cstdio>
#include<algorithm>
using namespace std;
 
int h[100005],en,fa[100005][18],data[100005],dfn,L[100005],R[100005],pre[100005],ROOT=1,bits[20],dep[100005],n,q;
 
struct Edge{
int b,next;
}e[200005];
 
struct SegTree{
int l,r,mn;
}tree[400005];
 
void Pushup(int root){
tree[root].mn=min(tree[root*2].mn,tree[root*2+1].mn);
}
 
void Build(int root,int l,int r){
tree[root].l=l;
tree[root].r=r;
if(l==r){
    tree[root].mn=data[pre[l]];
    return;
}
int mid=l+r>>1;
Build(root*2,l,mid);
Build(root*2+1,mid+1,r);
Pushup(root);
}
 
void Change(int root,int pos,int val){
if(tree[root].l==tree[root].r){
    tree[root].mn=val;
    return;
}
int mid=tree[root].l+tree[root].r>>1;
if(pos<=mid)Change(root*2,pos,val);
if(pos>mid)Change(root*2+1,pos,val);
Pushup(root);
}
 
int GtMn(int root,int l,int r){
if(l>r)return 2100000000;
if(tree[root].l>=l && tree[root].r<=r){
    return tree[root].mn;
}
int mid=tree[root].l+tree[root].r>>1,ans=2100000000;
if(l<=mid)ans=min(ans,GtMn(root*2,l,r));
if(r>mid)ans=min(ans,GtMn(root*2+1,l,r));
return ans;
}
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
void dfs(int u){
L[u]=++dfn;
pre[dfn]=u;
for(int i=1;i<=18;i++){
    if(bits[i]<=dep[u])fa[u][i]=fa[fa[u][i-1]][i-1];
    else break;
}
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    dep[v]=dep[u]+1;
    fa[v][0]=u;
    dfs(v);
}
R[u]=dfn;
}
 
int main(){
freopen("3306.in","r",stdin);
freopen("3306.out","w",stdout);
bits[0]=1;
for(int i=1;i<=18;i++)bits[i]=bits[i-1]<<1;
scanf("%d %d",&n,&q);
//printf("%d %d\n",n,q);
for(int i=1;i<=n;i++){
    int u;
    scanf("%d %d",&u,&data[i]);
    //printf("%d %d\n",u,data[i]);
    if(u)AddEdge(u,i);
}
dfs(ROOT=1);
Build(1,1,n);
for(int i=1;i<=q;i++){
    char s[5];
    int x,y;
    scanf("%s",s);
    if(s[0]=='V'){
        scanf("%d %d",&x,&y);
        Change(1,L[x],y);
    }
    if(s[0]=='E'){
        scanf("%d",&x);
        ROOT=x;
    }
    if(s[0]=='Q'){
        scanf("%d",&x);
        if(ROOT==x){printf("%d\n",tree[1].mn);continue;}
        if(L[x]<=L[ROOT] && R[x]>=R[ROOT]){
            y=ROOT;
            int deep=dep[y]-dep[x]-1;
            for(int i=0;i<=18;i++){
                if(bits[i]&deep)y=fa[y][i];
            }
            printf("%d\n",min(GtMn(1,1,L[y]-1),GtMn(1,R[y]+1,n)));
            continue;
        }
        printf("%d\n",GtMn(1,L[x],R[x]));
    }
}
return 0;
}

因为一棵树的子树一定在dfs序上是连续的

所以直接修改就行了

#include<cstdio>
#include<algorithm>
using namespace std;

struct Edge{
int b,next;
}e[1000005];

struct SegTree{
int l,r;
long long tag,sum;
}tree[1000005];

int n,q,en,cnt,top[400005],id[400005],pre[400005],dep[400005],son[400005],h[400005],siz[400005],fa[400005];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void Pushdown(int root){
if(tree[root].tag){
	tree[root*2].tag+=tree[root].tag;
	tree[root*2].sum+=tree[root].tag*(tree[root*2].r-tree[root*2].l+1);
	tree[root*2+1].tag+=tree[root].tag;
	tree[root*2+1].sum+=tree[root].tag*(tree[root*2+1].r-tree[root*2+1].l+1);
	tree[root].tag=0;
}
}

void Pushup(int root){
tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}

void Build(int root,int l,int r){
tree[root].l=l;
tree[root].r=r;
if(l==r){
    tree[root].sum=0;
    return;
}
int mid=(l+r)/2;
Build(root*2,l,mid);
Build(root*2+1,mid+1,r);
tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}

void Add(int root,int l,int r,long long v){
if(tree[root].l>=l && tree[root].r<=r){
	tree[root].tag+=v;
	tree[root].sum+=v*(tree[root].r-tree[root].l+1);
	return;
}
Pushdown(root);
int mid=tree[root].l+tree[root].r>>1;
if(l<=mid)Add(root*2,l,r,v);
if(r>mid)Add(root*2+1,l,r,v);
Pushup(root);
}

long long Sum(int root,int l,int r){
if(tree[root].l>=l && tree[root].r<=r){
	return tree[root].sum;
}
Pushdown(root);
int mid=tree[root].l+tree[root].r>>1;
long long ans=0;
if(l<=mid)ans+=Sum(root*2,l,r);
if(r>mid)ans+=Sum(root*2+1,l,r);
return ans;
}

void dfs1(int u,int father,int deep){
fa[u]=father;
dep[u]=deep;
siz[u]=1;
son[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==father)continue;
    dfs1(v,u,deep+1);
    siz[u]+=siz[v];
    if(siz[v]>siz[son[u]]){
        son[u]=v;
    }
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++cnt;
pre[cnt]=u;
if(son[u])dfs2(son[u],ux);
else return;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=son[u] && v!=fa[u]){dfs2(v,v);}
}
}

void AddLine(int u,int v,long long val){
int f1=top[u],f2=top[v];
while(f1!=f2){
	if(dep[f1]<dep[f2]){swap(u,v);swap(f1,f2);}
	Add(1,id[f1],id[u],val);
	u=fa[f1];
	f1=top[u];
}
if(dep[u]>dep[v])swap(u,v);
//printf("%d %d\n",id[u],id[v]);
Add(1,id[u],id[v],val);
}

int main(){
freopen("2836.in","r",stdin);
freopen("2836.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++){
	int u,v;
	scanf("%d %d",&u,&v);
	AddEdge(u+1,v+1);
	AddEdge(v+1,u+1);
}
Build(1,1,n);
dfs1(1,0,1);
dfs2(1,1);
scanf("%d",&q);
while(q--){
	int u,v;
	long long val;
	char s[3];
	scanf("%s",s);
	if(s[0]=='A'){
		scanf("%d %d %lld",&u,&v,&val);
		AddLine(u+1,v+1,val);
	}
	if(s[0]=='Q'){
		scanf("%d",&u);
		//printf("IS:%d %d %d\n",id[u+1],siz[u+1],u+1);
		printf("%lld\n",Sum(1,id[u+1],id[u+1]+siz[u+1]-1));
	}
}
return 0;
}

LCT

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;

int n,m,c,t,have[10005][105];
map<int,int> Mp[1000005];

struct Node{
int rev;
Node *ch[2],*fa;
Node(Node *fat);
void Pushdown();
}*root[1000005],*Null;

Node::Node(Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
rev=0;
}

Node *GetNull(){
Node *re=new Node(re);
re->rev=0;
re->ch[0]=re->fa=re->ch[1]=re;
return re;
}

void Node::Pushdown(){
if(rev){
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0],ch[1]);
	rev=0;
}
}

int Notroot(Node *x){
return (x->fa->ch[0]==x)||(x->fa->ch[1]==x);
}

void Prepare(Node *x){
if(Notroot(x))Prepare(x->fa);
x->Pushdown();
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
}

void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;}
}

void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
}

void Link(Node *u,Node *v){
Makeroot(u);
u->fa=v;
}

void Cut(Node *u,Node *v){
Makeroot(u);
Access(v);
Splay(v);
if(v->ch[0]==u){v->ch[0]=Null;u->fa=Null;}
}

Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}

int GetPoint(int x,int y){
return x+(y-1)*n;
}

Node *ToLct(int x,int c){
return root[GetPoint(x,c)];
}

void Change(int x,int y,int z){
int Tok=Mp[x][y];
if(Tok==0){puts("No such cable.");return;}
if(Tok==z){puts("Already owned.");return;}
//printf("%d %d\n",have[x][z],have[y][z]);
if(have[x][z]==2 || have[y][z]==2){puts("Forbidden: monopoly.");return;}
Node *u1=ToLct(x,Tok),*u2=ToLct(x,z),*v1=ToLct(y,Tok),*v2=ToLct(y,z);
//printf("%d %d\n",Find(u2),Find(v2));
if(Find(u2)==Find(v2)){puts("Forbidden: redundant.");return;}
Cut(u1,v1);
have[x][Tok]--;
have[y][Tok]--;
have[x][z]++;
have[y][z]++;
Mp[x][y]=z;
Link(u2,v2);
puts("Sold.");
}

int main(){
freopen("3651.in","r",stdin);
freopen("3651.out","w",stdout);
scanf("%d %d %d %d",&n,&m,&c,&t);
Null=GetNull();
for(int i=1;i<=n*c;i++){root[i]=new Node(Null);}
//printf("%d %d %d %d\n",Null,Null->ch[0],Null->ch[1],Null->fa);
for(int i=1;i<=m;i++){
	int s1,s2,k;
	scanf("%d %d %d",&s1,&s2,&k);
	if(s1>s2)swap(s1,s2);
	have[s1][k]++;
	have[s2][k]++;
	Mp[s1][s2]=k;
	//printf("%d %d %d | %d %d N*C:%d\n",s1,s2,k,GetPoint(s1,k),GetPoint(s2,k),n*c);
	Node *x=ToLct(s1,k),*y=ToLct(s2,k);
	Link(x,y);
}
for(int i=1;i<=t;i++){
	int s1,s2,k;
	scanf("%d %d %d",&s1,&s2,&k);
	if(s1>s2)swap(s1,s2);
    Change(s1,s2,k);
}
return 0;
}

LCT直接上

记录子树的大小

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,Next[200005];

struct Node{
int siz,rev;
Node *ch[2],*fa;
Node(Node *fat);
void Pushup();
void Pushdown();
}*root[200005],*Null;

Node::Node(Node *fat){
ch[0]=ch[1]=Null;
fa=fat;
siz=1;
rev=0;
}

void Node::Pushup(){
siz=1;
if(ch[0]!=Null)siz+=ch[0]->siz;
if(ch[1]!=Null)siz+=ch[1]->siz;
}

void Node::Pushdown(){
if(rev){
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0],ch[1]);
	rev=0;
}
}

int Notroot(Node *x){
return (x->fa->ch[0]==x)||(x->fa->ch[1]==x);
}

void Prepare(Node *x){
if(Notroot(x))Prepare(x->fa);
x->Pushdown();
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y)){Rotate(x,y->ch[0]==x);}
	else {
		if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else {Rotate(x,1);Rotate(x,0);}
	}
}
}

void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}
}

void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
}

void Link(Node *x,Node *y){
Makeroot(x);
x->fa=y;
}

void Cut(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
if(y->ch[0]==x){y->ch[0]=Null;x->fa=Null;}
}

Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}

Node *ToLct(int x){
return root[x];
}

Node *GetNull(){
Node *u=new Node(Null);
u->fa=u->ch[0]=u->ch[1]=u;
u->siz=0;
u->rev=0;
return u;
}

int Jump(int x){
Node *u=ToLct(x);
Makeroot(ToLct(n+1));
Access(u);
Splay(u);
return u->ch[0]->siz;
}

void Change(int x,int y){
//Node *u=ToLct(x),*v=ToLct(Next[x]);
//printf("Tp%d\n",Next[x]);
int t=min(x+y,n+1);
//printf("Tpt%d\n",t);
Cut(ToLct(x),ToLct(Next[x]));
Link(ToLct(x),ToLct(t));
Next[x]=t;
}

int main(){
freopen("2002.in","r",stdin);
freopen("2002.out","w",stdout);
Null=GetNull();
scanf("%d",&n);
root[n+1]=new Node(Null);
for(int i=1;i<=n;i++){
	int tp;
	scanf("%d",&tp);
	root[i]=new Node(Null);
	Next[i]=min(n+1,tp+i);
}
for(int i=1;i<=n;i++){
	Link(ToLct(i),ToLct(Next[i]));
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
	int opt,x,y;
	scanf("%d",&opt);
	if(opt==1){scanf("%d",&x);printf("%d\n",Jump(x+1));}
	if(opt==2){scanf("%d %d",&x,&y);Change(x+1,y);}
}
return 0;
}

Link-Cut Tree直接上……

但是因为智商原因2天才能理解+写会这个东西。

因为BZOJ爆了所以测不了。但是和hzwer的程序对拍了没拍出什么错误。。。在BZOJ上AC了

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m;

struct Node{
int v,ans,rev;
Node *ch[2],*fa;
Node(int val,Node *fat);
void Pushdown();
void Pushup();
}*root[300005],*Null;

Node::Node(int val=0,Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
v=ans=val;
rev=0;
}

void Node::Pushdown(){
if(rev){
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0],ch[1]);
	rev=0;
}
}

void Node::Pushup(){
ans=v;
if(ch[0]!=Null)ans^=ch[0]->ans;
if(ch[1]!=Null)ans^=ch[1]->ans;
}

int Notroot(Node *x){
return (x->fa->ch[0]==x)||(x->fa->ch[1]==x);
}

void Prepare(Node *x){
if(Notroot(x))Prepare(x->fa);
x->Pushdown();
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y)){Rotate(x,y->ch[0]==x);}
	else {
		if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else {Rotate(x,1);Rotate(x,0);}
	}
}
}

void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}
}

void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
}

void Link(Node *x,Node *y){
Makeroot(x);
x->fa=y;
}

void Cut(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
if(y->ch[0]==x){y->ch[0]=Null;x->fa=Null;}
}

Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}

Node *ToLct(int x){
return root[x];
}

int Xor(int x,int y){
Node *u=ToLct(x),*v=ToLct(y);
Makeroot(u);
Access(v);
Splay(v);
return v->ans;
}

void Add(int x,int y){
Node *u=ToLct(x),*v=ToLct(y);
Link(u,v);
}

void Delete(int x,int y){
Node *u=ToLct(x),*v=ToLct(y);
Cut(u,v);
}

void Change(int x,int y){
Node *u=ToLct(x);
Access(u);
Splay(u);
u->v=y;
u->Pushup();
}

Node *GetNull(){
Node *re=new Node(0,re);
re->v=re->ans=re->rev=0;
re->ch[0]=re->fa=re->ch[1]=re;
return re;
}

int main(){
freopen("3282.in","r",stdin);
freopen("3282.out","w",stdout);
scanf("%d %d",&n,&m);
Null=GetNull();
for(int i=1;i<=n;i++){
	int tp;
	scanf("%d",&tp);
	root[i]=new Node(tp,Null);
}
for(int i=1;i<=m;i++){
	int opt,x,y;
    scanf("%d %d %d",&opt,&x,&y);
    if(opt==0){printf("%d\n",Xor(x,y));}
    if(opt==1 && Find(ToLct(x))!=Find(ToLct(y)) && x!=y){Add(x,y);}
    if(opt==2 && Find(ToLct(x))==Find(ToLct(y)) && x!=y){Delete(x,y);}
    if(opt==3){Change(x,y);}
}
return 0;
}

疯狂的块状链表……

我写个半成品程序放这儿坑着……不知道哪天会填坑……

感觉写到快崩溃了……

jcvb写的完整版也就我这么长……但我只写了一半……orzorz

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

struct List{
long long cur[1105],cover,rev,tag,sum,mx,mn,siz;
List *prev,*next;
List(List *pre,List *nex){
siz=0;
mx=-21000000000ll;
mn=21000000000ll;
sum=0;
rev=0;
tag=0;
cover=-21000000000ll;
prev=pre;
next=nex;
}
void Renew(long long k){
mx=max(mx,k);
mn=min(mn,k);
sum+=k;
}
void Fix(){
prev->next=this;
next->prev=this;
}
}*root,*Null=new List(Null,Null);

int m,n,block_size;
long long a[100005],tmp[1105];

void Read(long long &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

void PushTag(List *p){
if(p->tag){
	for(int i=0;i<p->siz;i++)p->cur[i]+=p->tag;
	p->tag=0;
}
}

void PushCover(List *p){
if(p->cover!=-21000000000ll){
	for(int i=0;i<p->siz;i++)p->cur[i]=p->cover;
	p->cover=-21000000000ll;
}
}

void PushRev(List *p){
if(p->rev){
	for(int i=0;i<p->siz/2;i++)swap(p->cur[i],p->cur[p->siz-i-1]);
	p->rev=0;
}
}

void Pushdown(List *p){
PushTag(p);
PushCover(p);
PushRev(p);
}

void CopyTags(List *p,List *q){
p->cover=q->cover;
p->tag=q->tag;
p->rev=q->rev;
}

List* Split(List *lis,int k){
List *p=new List(lis,lis->next);
lis->next=p;
lis->Fix();
p->Fix();
PushRev(lis);
CopyTags(p,lis);
lis->mx=-21000000000ll;
lis->mn=21000000000ll;
lis->sum=0;
for(int i=0;i<=k;i++){
	lis->Renew(lis->cur[i]);
}
lis->siz=k+1;
if(p->cover)return p;
for(int i=k+1;i<lis->siz;i++){
	p->cur[p->siz++]=lis->cur[i];
	p->Renew(lis->cur[i]);
}
return p;
}

List* Merge(List *p,List *q){
p->next=q;
q->prev=p;
p->Fix();
q->Fix();
Pushdown(p);
Pushdown(q);
for(int i=0;i<q->siz;i++){
	p->cur[p->siz++]=q->cur[i];
	p->Renew(q->cur[i]);
}
return p;
}

void Swap(List *p,List *q){
p->prev->next=q;
q->next->prev=p;
p->next->prev=q;
q->prev->next=p;
swap(p->next,q->next);
swap(p->prev,q->prev);
}

pair<List*,int> Location(int pos){
List *i;
for(i=root;i!=Null && pos>i->siz;pos-=i->siz,i=i->next);
return make_pair(i,pos-1);
}
///Wo Mei You You Hua block_size;
void Insert(int pos,long long val){
pair<List*,int> Real=Location(pos);
Real.second++;
Pushdown(Real.first);
for(int i=Real.first->siz;i>Real.second;i--){
	Real.first->cur[i]=Real.first->cur[i-1];
}
Real.first->siz++;
Real.first->cur[Real.second]=val;
Real.first->Renew(val);
if(Real.first->siz>2*block_size){Split(Real.first,Real.first->siz/2);}
}

void Delete(int pos){
pair<List*,int> Real=Location(pos);
Pushdown(Real.first);
Real.first->mx=-2100000000ll;
Real.first->mn=21000000000ll;
Real.first->sum=0;
for(int i=0;i<Real.second;i++)Real.first->Renew(Real.first->cur[i]);
for(int i=Real.second+1;i<Real.first->siz;i++){
	Real.first->Renew(Real.first->cur[i]);
	Real.first->cur[i-1]=Real.first->cur[i];
}
Real.first->siz--;
if(Real.first->siz<block_size/2){
	if(Real.first->next!=Null){Merge(Real.first,Real.first->next);}
	else {
		if(Real.first->prev!=Null){Merge(Real.first->prev,Real.first);}
	}
}
}

void Reverse(int l,int r){
pair<List*,int> R1=Location(l),R2=Location(r);
Pushdown(R1.first);
Pushdown(R2.first);
List *p=Split(R1.first,R1.second),*q=Split(R2.first,R2.second)->prev;
int flag=0;
for(List *i=p;i!=q;i=i->next){i->rev^=1;}
for(;p!=q && p!=q->next;p=p->next,q=q->prev)Swap(p,q);
}

void True_rotate(List *lis,int k){
int cnt=0,Circle=lis->siz;
for(int i=0;i<Circle;i++){
	tmp[(++cnt+k-1)%Circle+1]=lis->cur[i];
}
for(int i=0;i<Circle;i++){
	lis->cur[i]=tmp[i-k+1];
}
}

void Rotate(int l,int r,int k){
pair<List*,int> R1=Location(l),R2=Location(r);
if(R1.first==R2.first){
	List *p=Split(R1.first,R1.second-1),*q=Split(R1.first->next,R2.second-R1.second+1)->prev;
	p=Merge(p,q);
	True_rotate(p,k);
	return;
}
if(R1.first->next==R2.first){
    List *p=Split(R1.first,R1.second-1),*q=Split(R2.first,R2.second)->prev;
	p=Merge(p,q);
	True_rotate(p,k);
	return;
}

}

void Add(int l,int r,long long v){

}

void Cover(int l,int r,long long val){

}

long long Sum(int l,int r){}

long long MinAbs(int l,int r){}

long long PrevNext(int l,int r,long long val){}

long long Kth(int l,int r,int k){}

int Rank(int l,int r,long long val){}

int main(){
freopen("3337.in","r",stdin);
freopen("3337.out","w",stdout);
Read(n);
for(int i=1;i<=n;i++){
	Read(a[i]);
}
block_size=(int)sqrt((double)n);
root=new List(Null,Null);
List *p=root;
int Count=0;
for(int i=1;i<=n;i++){
if((i-1)%block_size==0 && i!=1){
	p->next=new List(p,Null);
	p->siz=Count;
	p=p->next;
	Count=0;
}
p->Renew(a[i]);
p->cur[Count++]=a[i];
}
p->siz=Count;
Read(m);
while(m--){
	int opt,l,r,k;
	long long v;
	Read(opt);
	if(opt==1){
		Read(k);Read(v);
		Insert(k,v);
	}
	if(opt==2){
		Read(k);
		Delete(k);
	}
	if(opt==3){
		Read(l);Read(r);
		Reverse(l,r);
	}
	if(opt==4){
		Read(l);Read(r);Read(k);
		Rotate(l,r,k);
	}
	if(opt==5){
		Read(l);Read(r);Read(v);
		Add(l,r,v);
	}
	if(opt==6){
		Read(l);Read(r);Read(v);
		Cover(l,r,v);
	}
	if(opt==7){
		Read(l);Read(r);
		printf("%lld\n",Sum(l,r));
	}
	if(opt==8){
		Read(l);Read(r);
		printf("%lld\n",MinAbs(l,r));
	}
	if(opt==9){
		Read(l);Read(r);Read(v);
		printf("%lld\n",PrevNext(l,r,v));
	}
	if(opt==10){
		Read(l);Read(r);Read(k);
		printf("%lld\n",Kth(l,r,k));
	}
	if(opt==11){
		Read(l);Read(r);Read(v);
		printf("%d\n",Rank(l,r,v));
	}
}
return 0;
}

Splay模版题。

虽然最近学习了fhqTreap但是还是先写个splay吧，补一补以前的漏洞……

Splay

#include<cstdio>
#include<algorithm>
using namespace std;

struct Node{
Node *ch[2],*fa;
int v,mx,tag,rev,siz;
Node(int val,Node* fa);
void Pushup();
void Pushdown();
}*root,*Null=new Node(-2100000000,Null);

int n,m;

Node::Node(int val=0,Node* fat=Null){
siz=1;
fa=fat;
ch[0]=ch[1]=Null;
v=mx=val;
tag=0;
}

void Node::Pushdown(){
if(rev){
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0],ch[1]);
	rev=0;
}
if(tag){
	if(ch[0]!=Null){ch[0]->tag+=tag;ch[0]->v+=tag;ch[0]->mx+=tag;}
	if(ch[1]!=Null){ch[1]->tag+=tag;ch[1]->v+=tag;ch[1]->mx+=tag;}
	tag=0;
}
}

void Node::Pushup(){
siz=1;
if(ch[0]!=Null)siz+=ch[0]->siz;
if(ch[1]!=Null)siz+=ch[1]->siz;
mx=v;
if(ch[0]!=Null)mx=max(mx,ch[0]->mx);
if(ch[1]!=Null)mx=max(mx,ch[1]->mx);
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x,Node *place){
while(x->fa!=place){
	Node *y=x->fa,*z=y->fa;
	if(z==Null || z==place){Rotate(x,y->ch[0]==x);}
	else {
		if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else {Rotate(x,1);Rotate(x,0);}
	}
}
if(place==Null)root=x;
}

Node* Build_Tree(int l,int r){
int mid=l+r>>1;
if(l>r)return Null;
Node *splay=new Node(0,Null);
splay->ch[0]=Build_Tree(l,mid-1);
if(splay->ch[0]!=Null){splay->ch[0]->fa=splay;}
splay->ch[1]=Build_Tree(mid+1,r);
if(splay->ch[1]!=Null){splay->ch[1]->fa=splay;}
splay->Pushup();
return splay;
}

void Build(){
Null->siz=0;
root=new Node(-2100000000,Null);
root->ch[1]=new Node(-2100000000,root);
root->ch[1]->fa=root;
root->ch[1]->ch[0]=Build_Tree(1,n);
root->ch[1]->ch[0]->fa=root->ch[1];
root->ch[1]->Pushup();
root->Pushup();
}

Node *Find(Node *splay,int k){
if(splay->rev || splay->tag)splay->Pushdown();
if(k==splay->ch[0]->siz+1){return splay;}
if(k<=splay->ch[0]->siz){return Find(splay->ch[0],k);}
else {return Find(splay->ch[1],k-1-splay->ch[0]->siz);}
}

Node *GetSeq(int l,int r){
Node *L=Find(root,l);
Splay(L,Null);
Node *R=Find(root,r+2);
Splay(R,root);
return R->ch[0];
}

void Reverse(int l,int r){
Node *seq=GetSeq(l,r);
seq->rev^=1;
}

void Add(int l,int r,int val){
Node *seq=GetSeq(l,r);
seq->tag+=val;
seq->v+=val;
seq->mx+=val;
}

int GetMx(int l,int r){
Node *seq=GetSeq(l,r);
return seq->mx;
}

int main(){
freopen("1251.in","r",stdin);
freopen("1251.out","w",stdout);
scanf("%d %d",&n,&m);
Build();
while(m--){
	int opt,l,r,v;
	scanf("%d",&opt);
	if(opt==1){scanf("%d %d %d",&l,&r,&v);Add(l,r,v);}
	if(opt==2){scanf("%d %d",&l,&r);Reverse(l,r);}
	if(opt==3){scanf("%d %d",&l,&r);printf("%d\n",GetMx(l,r));}
}
return 0;
}

fhqTreap(待填坑)

在拖了很长时间后，我第一次写掉了Splay而且AC了bzoj 1251！！！

我实在太高兴了！！！