BruceJay's Blog

BZOJ1500 维修数列

| Comments

To start with

据说如果看到这道题1h能打完AC,就说明掌握了Splay

Problem

Solution

很经典的区间处理问题,不过更难了。
求全局最大子序列可以对每个节点维护lx和rx,表示最大前缀和、最大后缀和。
特别注意翻转区间时lx和rx需要swap(Bruce因此WA得不知所措)。
具体见代码。

Code

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 500100;
const int INF = 0x3f3f3f3f;
int a[N]; int id[N]; int v[N];
int tr[N][2]; int fa[N]; int sz[N];
int tag[N]; int rev[N]; int sum[N];
int lx[N]; int rx[N]; int mx[N];
queue<int> q;
int n,m,cnt,root=0;

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

void Pushup(int &k)
{
    int l=tr[k][0],r=tr[k][1];
    sz[k]=sz[l]+sz[r]+1;
    sum[k]=sum[l]+sum[r]+v[k];
    mx[k]=max(mx[l],mx[r]);
    mx[k]=max(mx[k],rx[l]+v[k]+lx[r]);
    lx[k]=max(lx[l],sum[l]+v[k]+lx[r]);
    rx[k]=max(rx[r],sum[r]+v[k]+rx[l]);
}

void Pushdown(int &k)
{
    int l=tr[k][0],r=tr[k][1];
    if(tag[k]){
        tag[k]=rev[k]=0;
        if(l) tag[l]=1,v[l]=v[k],sum[l]=sz[l]*v[k];
        if(r) tag[r]=1,v[r]=v[k],sum[r]=sz[r]*v[k];
        if(v[k]>=0){
            if(l) lx[l]=rx[l]=mx[l]=sum[l];
            if(r) lx[r]=rx[r]=mx[r]=sum[r];
        }
        else{
            if(l) lx[l]=rx[l]=0,mx[l]=v[l];
            if(r) lx[r]=rx[r]=0,mx[r]=v[r];
        }
    }
    if(rev[k]){
        rev[k]=0; rev[l]^=1; rev[r]^=1;
        if(l) swap(tr[l][0],tr[l][1]),swap(lx[l],rx[l]);
        if(r) swap(tr[r][0],tr[r][1]),swap(lx[r],rx[r]);
    }
}

void Rotate(int x,int &k)
{
    int y=fa[x],z=fa[y];
    int t=tr[y][0]==x?0:1;
    if(y==k) k=x;
    else{
        if(tr[z][0]==y) tr[z][0]=x;
        else tr[z][1]=x;
    }
    fa[x]=z; fa[y]=x; fa[tr[x][t^1]]=y;
    tr[y][t]=tr[x][t^1]; tr[x][t^1]=y;
    Pushup(y); Pushup(x);
}

void Splay(int x,int &k)
{
    while(x!=k){
        int y=fa[x];
        if(y!=k){
            int z=fa[y];
            if(tr[z][0]==y^tr[y][0]==x) Rotate(x,k);
            else Rotate(y,k);
        }
        Rotate(x,k);
    }
}

int Find(int x,int &k)
{
    Pushdown(k);
    int t=sz[tr[k][0]]+1;
    if(t==x) return k;
    else if(t<x) return Find(x-t,tr[k][1]);
    else return Find(x,tr[k][0]);
}

void Build(int &k,int l,int r,int p)
{
    int mid=(l+r)>>1;
    k=id[mid]; tag[k]=rev[k]=0;
    fa[k]=p; v[k]=a[mid];
    if(l<mid) Build(tr[k][0],l,mid-1,k);
    if(mid<r) Build(tr[k][1],mid+1,r,k);
    Pushup(k);
}

void Insert()
{
    int pos,x;
    pos=read(); x=read();
    for(int i=1;i<=x;i++) a[i]=read();
    for(int i=1;i<=x;i++){
        if(!q.empty()) id[i]=q.front(),q.pop();
        else id[i]=++cnt;
    }
    int l=Find(pos+1,root),r=Find(pos+2,root);
    Splay(l,root); Splay(r,tr[l][1]);
    Build(tr[r][0],1,x,r);
    Pushup(r); Pushup(l);
}

void Record(int &k)
{
    q.push(k);
    if(tr[k][0]) Record(tr[k][0]);
    if(tr[k][1]) Record(tr[k][1]);
    tr[k][0]=tr[k][1]=0;
}

void Delete()
{
    int pos,x;
    pos=read(); x=read();
    int l=Find(pos,root),r=Find(pos+x+1,root);
    Splay(l,root); Splay(r,tr[l][1]);
    int z=tr[r][0]; tr[r][0]=0;
    Pushup(r); Pushup(l); Record(z);
}

void Make_Same()
{
    int pos,x,val;
    pos=read(); x=read(); val=read();
    int l=Find(pos,root),r=Find(pos+x+1,root);
    Splay(l,root); Splay(r,tr[l][1]);
    int z=tr[r][0];
    tag[z]=1; v[z]=val; sum[z]=sz[z]*v[z];
    if(val>=0) lx[z]=rx[z]=mx[z]=sum[z];
    else lx[z]=rx[z]=0,mx[z]=v[z];
    Pushup(r); Pushup(l);
}

void Reverse()
{
    int pos,x;
    pos=read(); x=read();
    int l=Find(pos,root),r=Find(pos+x+1,root);
    Splay(l,root); Splay(r,tr[l][1]);
    int z=tr[r][0];
    if(!tag[z]){
        rev[z]^=1; swap(lx[z],rx[z]);
        swap(tr[z][0],tr[z][1]);
        Pushup(r); Pushup(l);
    }
}

void Get_Sum()
{
    int pos,x;
    pos=read(); x=read();
    int l=Find(pos,root),r=Find(pos+x+1,root);
    Splay(l,root); Splay(r,tr[l][1]);
    int z=tr[r][0]; printf("%d\n",sum[z]);
}

void Max_Sum()
{
    printf("%d\n",mx[root]);
}

void print(int &k)
{
    Pushdown(k);
    if(tr[k][0]) print(tr[k][0]);
    if(v[k]!=-INF) printf("%d ",v[k]);
    if(tr[k][1]) print(tr[k][1]);
}

int main()
{
    char s[15];
    freopen("1500.in","r",stdin);
    freopen("1500.out","w",stdout);
    n=read(); m=read(); cnt=n+2;
    mx[0]=a[1]=a[n+2]=-INF;
    for(int i=2;i<=n+1;i++) a[i]=read();
    for(int i=1;i<=n+2;i++) id[i]=i;
    Build(root,1,n+2,0);
    for(int i=1;i<=m;i++){
        scanf("%s",s);
        if(s[0]=='I') Insert();
        else if(s[0]=='D') Delete();
        else if(s[0]=='M' && s[2]=='K') Make_Same();
        else if(s[0]=='R') Reverse();
        else if(s[0]=='G') Get_Sum();
        else Max_Sum();
    }
    //print(root);
 return 0;
}

Last but not least

感觉打了这题,就不会被Splay旋晕了。

Comments

comments powered by Disqus