时间戳

首页 > 技术文章 > Luogu P2042维护数列 splay区间操作

Luogu P2042维护数列 splay区间操作

lzqlalala 2019-06-04 20:02 原文

题意

就是用splay完成一堆区间操作，空间卡的比较紧，要回收无用节点编号

做题过程

从周六下午做到周二晚上。。。。细节贼多，我快要疯了
最后还是搞不懂pushdown操作的原理。。

40分代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f;
using namespace std;
typedef long long LL;
const int N=1e6+17;

int ch[N][2],par[N],siz[N],sum[N],val[N],la[N],ra[N],sa[N],rev[N],tag[N];
int a[N],id[N],tot,n,m,root;
char s[10];
queue<int> Q;
void output(int);

int read()
{
    int x=0,p=1; char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') p=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*p;
}

void recycle(int x)
{
	if(ch[x][0]) recycle(ch[x][0]),ch[x][0]=0;
	if(ch[x][1]) recycle(ch[x][1]),ch[x][1]=0;
	Q.push(x); 
}

int chk(int x) { return ch[par[x]][1]==x; }

void pushup(int x)
{
    int l=ch[x][0],r=ch[x][1];
    siz[x]=siz[l]+siz[r]+1;
    sum[x]=sum[l]+sum[r]+val[x];
    la[x]=max(sum[l]+la[r]+val[x],la[l]);
    ra[x]=max(sum[r]+ra[l]+val[x],ra[r]);
    sa[x]=max(ra[l]+la[r]+val[x],max(sa[l],sa[r]));
}

void pushdown(int x)
{
    int l=ch[x][0],r=ch[x][1];
    if(tag[x])
    {
        val[x]=tag[x]; 
        sum[x]=tag[x]*siz[x];
        la[x]=ra[x]=max(sum[x],0);
        sa[x]=max(sum[x],val[x]);
        if(l) tag[l]=tag[x],rev[l]=0;
        if(r) tag[r]=tag[x],rev[r]=0;
        tag[x]=rev[x]=0;
    }
    if(rev[x])
    {
        swap(la[x],ra[x]);
        swap(ch[x][0],ch[x][1]);
        rev[l]^=1,rev[r]^=1;
        rev[x]=0;
    }
}

void Push(int x)
{
	int l=ch[x][0],r=ch[x][1];
	pushdown(x);
	if(l) pushdown(l);
	if(r) pushdown(r);
}

void rotate(int x)
{
    int y=par[x],z=par[y],k=chk(x),w=ch[x][k^1];
    ch[y][k]=w,par[w]=y;
    ch[z][chk(y)]=x,par[x]=z;
    ch[x][k^1]=y,par[y]=x;
    pushup(y),pushup(x);
}

void splay(int x,int goal)
{
    int y,z;
    while(par[x]!=goal)
    {
        y=par[x],z=par[y];
        if(z!=goal)
            chk(x)==chk(y) ? rotate(y):rotate(x);
        rotate(x);
    }
    if(!goal) root=x;
}

int kth(int k)
{
    int x=root;
    if(k>siz[x]) return 0;
    while(1)
    {
        Push(x);//cout<<x<<" "<<ch[x][0]<<" "<<ch[x][1]<<endl; getchar(); 
        if(ch[x][1] && k>siz[ch[x][0]]+1) k-=siz[ch[x][0]]+1,x=ch[x][1];
        else if(ch[x][0] && k<=siz[ch[x][0]]) x=ch[x][0];
        else return x;
    }
}

int split(int L,int R)
{
    int x=kth(L),y=kth(R+2);
    splay(x,0),splay(y,x);//cout<<"finished"<<endl;
    return ch[y][0];
}

void remove()
{
    int L=read(),R=L+read()-1,x=split(L,R),y=par[x];
    recycle(ch[y][0]); ch[y][0]=0; 
    pushup(y); pushup(par[y]);
    //output(root); puts("");
}

void makesame()
{
    int L=read(),R=L+read()-1,c=read(),x=split(L,R),y=par[x];
	tag[x]=c; Push(x);
    pushup(y); pushup(par[y]);
}

void reverse()
{
    int L=read(),R=L+read()-1,x=split(L,R),y=par[x];//cout<<"finished"<<endl;
    rev[x]^=1; Push(x);
    pushup(y); pushup(par[y]);
}

void Getsum()
{
    int L=read(),R=L+read()-1,x=split(L,R);
    printf("%d\n",sum[x]);
}

void Maxsum()
{
	int x=split(1,tot-Q.size()-2);
    printf("%d\n",sa[x]);
}

void build(int L,int R,int p)
{//cout<<"?";
    int mid=(L+R)>>1,x=id[mid],fa=id[p];
    if(L>R) return ;
    if(L==R)
    {
        sum[x]=a[L];
        la[x]=ra[x]=sa[x]=max(a[L],0);
        siz[x]=1;
    }
    if(L<mid) build(L,mid-1,mid);
    if(mid<R) build(mid+1,R,mid);
    tag[x]=rev[x]=0; val[x]=a[mid]; 
    pushup(x);
    ch[fa][mid>=p]=x; par[x]=fa;
}

void insert()
{
    int pos=read(),num=read();
    for(int i=1;i<=num;i++) 
    {
        a[i]=read();
        if(Q.empty()) id[i]=++tot;
        else id[i]=Q.front(),Q.pop();
    }
	//cout<<"finished"<<endl;
	build(1,num,0);
    int x=kth(pos+1),y=kth(pos+2),g=id[(1+num)>>1];
    splay(x,0),splay(y,x);

    ch[y][0]=g,par[g]=y; 
    pushup(y); pushup(par[y]);
    //output(root); puts("");
}

void output(int x)
{
    if(ch[x][0]) output(ch[x][0]);
    //if(x!=1 && x!=n+2) 
    printf("%d ",val[x]);
    if(ch[x][1]) output(ch[x][1]);
}

int main()      
{
	//freopen("my.out","w",stdout);
	//ios::sync_with_stdio(false);
    n=read(),m=read();
    sa[0]=a[1]=a[n+1]=-INF;
    for(int i=2;i<=n+1;i++) a[i]=read();
    for(int i=1;i<=n+2;i++) id[i]=i;
    build(1,n+2,0);
    root=(n+3)>>1; tot=n+2;
    //output(root); return 0;
    while(m--)
    {
        scanf("%s",s);
        if(1)
        {
            if(s[0]=='I') insert(); 
            else if(s[0]=='D') remove();
            else if(s[0]=='M' && s[2]=='K') makesame(); 
            else if(s[0]=='R') reverse();
            else if(s[0]=='G') Getsum();
            else if(s[0]=='M') Maxsum(); 
        }
    }

    return 0;
}
/*
tips:
1.splay和线段树不一样，线段树只有叶子节点有权值，splay每个点都有，
所以在维护信息时要把val[x]算上;

*/

AC代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f;
using namespace std;
typedef long long LL;
const int N=1e6+17;

int ch[N][2],par[N],siz[N],sum[N],val[N],la[N],ra[N],sa[N],rev[N],tag[N];
int a[N],id[N],tot,n,m,root;
char s[10];
queue<int> Q;
void output(int);

int read()
{
    int x=0,p=1; char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') p=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*p;
}

void recycle(int x)
{
	if(ch[x][0]) recycle(ch[x][0]),ch[x][0]=0;
	if(ch[x][1]) recycle(ch[x][1]),ch[x][1]=0;
	Q.push(x); 
}

int chk(int x) { return ch[par[x]][1]==x; }

void pushup(int x)
{
    int l=ch[x][0],r=ch[x][1];
    siz[x]=siz[l]+siz[r]+1;
    sum[x]=sum[l]+sum[r]+val[x];
    la[x]=max(sum[l]+la[r]+val[x],la[l]);
    ra[x]=max(sum[r]+ra[l]+val[x],ra[r]);
    sa[x]=max(ra[l]+la[r]+val[x],max(sa[l],sa[r]));
}

void cg(int l,int c)
{
	tag[l]=1; val[l]=c;
    sum[l]=c*siz[l];
    la[l]=ra[l]=max(sum[l],0);
    sa[l]=max(c,sum[l]);
}

void pushdown(int x)
{
    int l=ch[x][0],r=ch[x][1];
    if(tag[x])
    {
        tag[x]=rev[x]=0;
        if(l) cg(l,val[x]);
        if(r) cg(r,val[x]);
    }
    if(rev[x])
    {
        rev[x]=0; rev[l]^=1,rev[r]^=1;
        swap(la[l],ra[l]),swap(la[r],ra[r]);
        swap(ch[l][0],ch[l][1]);
		swap(ch[r][0],ch[r][1]);
    }
}

void Push(int x)
{
	int l=ch[x][0],r=ch[x][1];
	pushdown(x);
	if(l) pushdown(l);
	if(r) pushdown(r);
}

void rotate(int x)
{
    int y=par[x],z=par[y],k=chk(x),w=ch[x][k^1];
    ch[y][k]=w,par[w]=y;
    ch[z][chk(y)]=x,par[x]=z;
    ch[x][k^1]=y,par[y]=x;
    pushup(y),pushup(x);
}

void splay(int x,int goal)
{
    int y,z;
    while(par[x]!=goal)
    {
        y=par[x],z=par[y];
        if(z!=goal)
            chk(x)==chk(y) ? rotate(y):rotate(x);
        rotate(x);
    }
    if(!goal) root=x;
}

int kth(int k)
{
    int x=root;
    if(k>siz[x]) return 0;
    while(1)
    {
        pushdown(x);//cout<<x<<" "<<ch[x][0]<<" "<<ch[x][1]<<endl; getchar(); 
        if(ch[x][1] && k>siz[ch[x][0]]+1) k-=siz[ch[x][0]]+1,x=ch[x][1];
        else if(ch[x][0] && k<=siz[ch[x][0]]) x=ch[x][0];
        else return x;
    }
}

int split(int L,int R)
{
    int x=kth(L),y=kth(R+2);
    splay(x,0),splay(y,x);//cout<<"finished"<<endl;
    return ch[y][0];
}

void remove()
{
    int L=read(),R=L+read()-1,x=split(L,R),y=par[x];
    recycle(ch[y][0]); ch[y][0]=0; 
    pushup(y); pushup(par[y]);
    //output(root); puts("");
}

void makesame()
{
    int L=read(),R=L+read()-1,c=read(),x=split(L,R),y=par[x];
	cg(x,c);
    pushup(y); pushup(par[y]);
}

void reverse()
{
    int L=read(),R=L+read()-1,x=split(L,R),y=par[x];//cout<<"finished"<<endl;
    if(!tag[x])
    {
    	rev[x]^=1;
    	swap(ch[x][0],ch[x][1]);
    	swap(la[x],ra[x]);
    	pushup(y); pushup(par[y]);
    }
}

void Getsum()
{
    int L=read(),R=L+read()-1,x=split(L,R);
    printf("%d\n",sum[x]);
}

void Maxsum()
{
	int x=split(1,tot-Q.size()-2);
    printf("%d\n",sa[x]);
}

void build(int L,int R,int p)
{//cout<<"?";
    int mid=(L+R)>>1,x=id[mid],fa=id[p];
    if(L>R) return ;
    if(L==R)
    {
        sum[x]=a[L];
        la[x]=ra[x]=sa[x]=max(a[L],0);
        siz[x]=1;
    }
    if(L<mid) build(L,mid-1,mid);
    if(mid<R) build(mid+1,R,mid);
    tag[x]=rev[x]=0; val[x]=a[mid]; 
    pushup(x);
    ch[fa][mid>=p]=x; par[x]=fa;
}

void insert()
{
    int pos=read(),num=read();
    for(int i=1;i<=num;i++) 
    {
        a[i]=read();
        if(Q.empty()) id[i]=++tot;
        else id[i]=Q.front(),Q.pop();
    }
	//cout<<"finished"<<endl;
	build(1,num,0);
    int x=kth(pos+1),y=kth(pos+2),g=id[(1+num)>>1];
    splay(x,0),splay(y,x);

    ch[y][0]=g,par[g]=y; 
    pushup(y); pushup(par[y]);
    //output(root); puts("");
}

void output(int x)
{
    if(ch[x][0]) output(ch[x][0]);
    //if(x!=1 && x!=n+2) 
    printf("%d ",val[x]);
    if(ch[x][1]) output(ch[x][1]);
}

int main()      
{
	//freopen("my.out","w",stdout);
	//ios::sync_with_stdio(false);
    n=read(),m=read();
    sa[0]=a[1]=a[n+1]=-INF;
    for(int i=2;i<=n+1;i++) a[i]=read();
    for(int i=1;i<=n+2;i++) id[i]=i;
    build(1,n+2,0);
    root=(n+3)>>1; tot=n+2;
    //output(root); return 0;
    while(m--)
    {
        scanf("%s",s);
        if(1)
        {
            if(s[0]=='I') insert(); 
            else if(s[0]=='D') remove();
            else if(s[0]=='M' && s[2]=='K') makesame(); 
            else if(s[0]=='R') reverse();
            else if(s[0]=='G') Getsum();
            else if(s[0]=='M') Maxsum(); 
        }
    }

    return 0;
}
/*
tips:
1.splay和线段树不一样，线段树只有叶子节点有权值，splay每个点都有，
所以在维护信息时要把val[x]算上;

*/

可以看到两份代码只有pushdown不同。。。

哦，我好像知道了，如果要区间赋值为0时，我的tag会炸。。。

推荐阅读