【BZOJ1500】维修数列（splay）

题意：

输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。

思路：集大成的splay模板，写完就去学LCT了

注意可能会爆INT64，改了好久，我也不知道c++为什么不开long long能过

这题卡内存，需要数组垃圾回收

 const oo=;

 var t:array[..,..]of longint;

     sum,lx,rx,mx:array[..]of int64;

     tag,rev,a,b,fa,id,d,size:array[..]of longint;

     q:array[..]of longint;

     n,m,i,j,k,x,f,root,cnt,head,tail,s:longint;

     ch:ansistring;

 function max(x,y:int64):int64;

 begin

  if x>y then exit(x);

  exit(y);

 end;

 procedure swap(var x,y:int64);

 var t:int64;

 begin

  t:=x; x:=y; y:=t;

 end;

 procedure pushup(x:longint);

 var l,r:longint;

 begin

  l:=t[x,]; r:=t[x,];

  sum[x]:=sum[l]+sum[r]+b[x];

  size[x]:=size[l]+size[r]+;

  mx[x]:=max(mx[l],mx[r]);

  mx[x]:=max(mx[x],rx[l]+lx[r]+b[x]);

  lx[x]:=max(lx[l],sum[l]+b[x]+lx[r]);

  rx[x]:=max(rx[r],sum[r]+b[x]+rx[l]);

 end;

 procedure pushdown(x:longint);

 var l,r,tmp:longint;

 begin

  l:=t[x,]; r:=t[x,];

  if tag[x]> then

  begin

   rev[x]:=; tag[x]:=;

   if l> then

   begin

    tag[l]:=; b[l]:=b[x]; sum[l]:=b[x]*size[l];

   end;

   if r> then

   begin

    tag[r]:=; b[r]:=b[x]; sum[r]:=b[x]*size[r];

   end;

   if b[x]>= then

   begin

    if l> then

    begin

     lx[l]:=sum[l]; rx[l]:=sum[l]; mx[l]:=sum[l];

    end;

    if r> then

    begin

     lx[r]:=sum[r]; rx[r]:=sum[r]; mx[r]:=sum[r];

    end;

   end

   else

   begin

    if l> then

    begin

     lx[l]:=; rx[l]:=; mx[l]:=b[x];

    end;

    if r> then

    begin

     lx[r]:=; rx[r]:=; mx[r]:=b[x];

    end;

   end;

  end;

  if rev[x]> then

  begin

   rev[x]:=rev[x] xor ; rev[l]:=rev[l] xor ; rev[r]:=rev[r] xor ;

   //tmp:=lx[l]; lx[l]:=rx[l]; rx[l]:=tmp;

   //tmp:=lx[r]; lx[r]:=rx[r]; rx[r]:=tmp;

   tmp:=t[l,]; t[l,]:=t[l,]; t[l,]:=tmp;

   tmp:=t[r,]; t[r,]:=t[r,]; t[r,]:=tmp;

   swap(lx[l],rx[l]); swap(lx[r],rx[r]);

  // swap(t[l,],t[l,]); swap(t[r,],t[r,]);

  end;

 end;

 procedure rotate(x:longint;var k:longint);

 var y,z,l,r:longint;

 begin

  y:=fa[x]; z:=fa[y];

  if t[y,]=x then l:=

   else l:=;

  r:=l xor ;

  if y<>k then

  begin

   if t[z,]=y then t[z,]:=x

    else t[z,]:=x;

  end

   else k:=x;

  fa[t[x,r]]:=y; fa[x]:=z; fa[y]:=x;

  t[y,l]:=t[x,r]; t[x,r]:=y;

  pushup(y);

  pushup(x);

 end;

 procedure splay(x:longint;var k:longint);

 var y,z:longint;

 begin

  while x<>k do

  begin

   y:=fa[x]; z:=fa[y];

   if y<>k then

   begin

    if (t[y,]=x)xor(t[z,]=y) then rotate(x,k)

     else rotate(y,k);

   end

    else k:=x;

   rotate(x,k);

  end;

 end;

 procedure build(l,r,x:longint);

 var mid,now,last:longint;

 begin

  if l>r then exit;

  mid:=(l+r)>>; now:=id[mid]; last:=id[x];

  if l=r then

  begin

   sum[now]:=a[l]; size[now]:=;

   tag[now]:=; rev[now]:=;

   if a[l]>= then

   begin

    lx[now]:=a[l]; rx[now]:=a[l]; mx[now]:=a[l];

   end

    else

    begin

     lx[now]:=; rx[now]:=; mx[now]:=a[l];

    end;

  end

   else

   begin

    build(l,mid-,mid);

    build(mid+,r,mid);

   end;

  b[now]:=a[mid]; fa[now]:=last;

  pushup(now);

  if mid>=x then t[last,]:=now

   else t[last,]:=now;

 end;

 function find(x,k:longint):longint;

 var l,r:longint;

 begin

  pushdown(x);

  l:=t[x,]; r:=t[x,];

  if size[l]+=k then exit(x);

  if size[l]+>k then exit(find(l,k))

   else exit(find(r,k-size[l]-));

 end;

 procedure clear(x:longint);

 var l,r:longint;

 begin

  if x= then exit;

  l:=t[x,]; r:=t[x,];

  clear(l); clear(r);

  inc(tail); q[tail mod ]:=x; //队列，记录以前用过但现在已经被删除，可以使用的编号

  fa[x]:=; t[x,]:=; t[x,]:=;

  tag[x]:=; rev[x]:=;

 end;

 function split(k,tot:longint):longint;

 var x,y:longint;

 begin

  x:=find(root,k); y:=find(root,k+tot+);

  splay(x,root); splay(y,t[x,]);

  exit(t[y,]);

 end;

 procedure query(k,tot:longint);

 var x:longint;

 begin

  x:=split(k,tot);

  writeln(sum[x]);

 end;

 procedure del(k,tot:longint);

 var x,y:longint;

 begin

  x:=split(k,tot); y:=fa[x];

  clear(x); t[y,]:=;

  pushup(y);

  pushup(fa[y]);

 end;

 procedure change(k,tot,v:longint);

 var x,y:longint;

 begin

  x:=split(k,tot); y:=fa[x];

  b[x]:=v; tag[x]:=; sum[x]:=size[x]*v;

  if v>= then

  begin

   lx[x]:=sum[x]; rx[x]:=sum[x]; mx[x]:=sum[x];

  end

   else

   begin

    lx[x]:=; rx[x]:=; mx[x]:=v;

   end;

  pushup(y);

  pushup(fa[y]);

 end;

 procedure rever(k,tot:longint);

 var x,y,tmp:longint;

 begin

  x:=split(k,tot); y:=fa[x];

  if tag[x]= then

  begin

   rev[x]:=rev[x] xor ;

   tmp:=t[x,]; t[x,]:=t[x,]; t[x,]:=tmp;

  // swap(t[x,],t[x,]);

   swap(lx[x],rx[x]);

   pushup(y);

   pushup(fa[y]);

  end;

 end;

 procedure ins(k,tot:longint);

 var x,y,z,i:longint;

 begin

  for i:= to tot do

   if tail>=head then begin id[i]:=q[head mod ]; inc(head); end //垃圾回收

    else begin inc(cnt); id[i]:=cnt; end;

  build(,tot,); z:=id[(tot+)>>];

  x:=find(root,k+); y:=find(root,k+);

  splay(x,root); splay(y,t[x,]);

  fa[z]:=y; t[y,]:=z;

  pushup(y);

  pushup(x);

 end;

 begin

  readln(n,m);

  head:=; tail:=;

  mx[]:=-oo; a[]:=-oo; a[n+]:=-oo;

  for i:= to n+ do read(a[i]);

  readln;

  for i:= to n+ do id[i]:=i;

  build(,n+,);

  root:=(n+)>>; cnt:=n+;

  for i:= to m do

  begin

   for j:= to  do d[j]:=;

   readln(ch); s:=;

   k:=length(ch); f:=; x:=;

   for j:= to k do

   begin

    if (ch[j]>='A')and(ch[j]<='Z')or((ch[j]='-')and(s=)) then continue;

    if ch[j]=' ' then

    begin

     if s> then d[s]:=f*x;

     inc(s);

     x:=; f:=;

     continue;

    end;

    if ch[j]='-' then

    begin

     f:=-; continue;

    end;

    x:=x*+ord(ch[j])-ord('');

   end;

   d[s]:=f*x;

   ch:=copy(ch,,);

   if ch='INS' then

   begin

    for j:= to d[] do a[j]:=d[j+];

    ins(d[],d[]);

   end;

   if ch='DEL' then del(d[],d[]);

   if ch='MAK' then change(d[],d[],d[]);

   if ch='REV' then rever(d[],d[]);

   if ch='GET' then

    if d[]= then writeln()

     else query(d[],d[]);

   if ch='MAX' then writeln(mx[root]);

  end;

 end.

UPD（2018.9.17）：C++

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second

 #define MP make_pair

 #define N   1100000

 #define MOD 1000000007

 #define eps 1e-8

 #define pi acos(-1)

 #define oo 1e9

 int a[N],id[N],fa[N],t[N][],sum[N],size[N],v[N],mx[N],lx[N],rx[N],

     tag[N],rev[N],n,m,root,cnt;

 queue<int> q;

 int read()

 {

    int v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 void pushup(int x)

 {

     int l=t[x][];

     int r=t[x][];

     sum[x]=sum[l]+sum[r]+v[x];

     size[x]=size[l]+size[r]+;

     mx[x]=max(mx[l],mx[r]);

     mx[x]=max(mx[x],rx[l]+v[x]+lx[r]);

     lx[x]=max(lx[l],sum[l]+v[x]+lx[r]);

     rx[x]=max(rx[r],sum[r]+v[x]+rx[l]);

 }

 void pushdown(int x)

 {

     int l=t[x][];

     int r=t[x][];

     if(tag[x])

     {

         rev[x]=tag[x]=;

         if(l){tag[l]=; v[l]=v[x]; sum[l]=v[x]*size[l];}

         if(r){tag[r]=; v[r]=v[x]; sum[r]=v[x]*size[r];}

         if(v[x]>=)

         {

             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]=; mx[l]=v[x];}

             if(r){lx[r]=rx[r]=; mx[r]=v[x];}

          }

     }

     if(rev[x])

     {

         rev[x]^=; rev[l]^=; rev[r]^=;

         swap(lx[l],rx[l]);

         swap(lx[r],rx[r]);

         swap(t[l][],t[l][]);

         swap(t[r][],t[r][]);

     }

 }

 void rotate(int x,int &k)

 {

     int y=fa[x];

     int z=fa[y];

     int l;

     if(t[y][]==x) l=;

      else l=;

     int r=l^;

     if(y!=k)

     {

         if(t[z][]==y) t[z][]=x;

          else t[z][]=x;

     }

      else k=x;

     fa[t[x][r]]=y; fa[x]=z; fa[y]=x;

     t[y][l]=t[x][r]; t[x][r]=y;

     pushup(y);

     pushup(x);

 }

 void splay(int x,int &k)

 {

     while(x!=k)

     {

         int y=fa[x];

         int z=fa[y];

         if(y!=k)

         {

             if(t[y][]==x^t[z][]==y) rotate(x,k);

              else rotate(y,k);

         }

          else k=x;

         rotate(x,k);

     }

 }

 int find(int x,int rank)

 {

     pushdown(x);

     int l=t[x][];

     int r=t[x][];

     if(size[l]+==rank) return x;

     if(size[l]>=rank) return find(l,rank);

     return find(r,rank-size[l]-);

 }

 void rec(int x)

 {

     if(!x) return;

     int l=t[x][];

     int r=t[x][];

     rec(l);

     rec(r);

     q.push(x);

     fa[x]=t[x][]=t[x][]=tag[x]=rev[x]=;

 }

 int split(int k,int tot)

 {

     int x=find(root,k);

     int y=find(root,k+tot+);

     splay(x,root);

     splay(y,t[x][]);

     return t[y][];

 }

 void query(int k,int tot)

 {

     int x=split(k,tot);

     printf("%d\n",sum[x]);

 }

 void update(int k,int tot,int val)

 {

     int x=split(k,tot);

     int y=fa[x];

     v[x]=val; tag[x]=; sum[x]=size[x]*val;

     if(val>=) lx[x]=rx[x]=mx[x]=sum[x];

      else{lx[x]=rx[x]=; mx[x]=val;}

     pushup(y);

     pushup(fa[y]);

 }

 void rever(int k,int tot)

 {

     int x=split(k,tot);

     int y=fa[x];

     if(!tag[x])

     {

         rev[x]^=;

         swap(t[x][],t[x][]);

         swap(lx[x],rx[x]);

         pushup(y);

         pushup(fa[y]);

     }

 }

 void Delete(int k,int tot)

 {

     int x=split(k,tot);

     int y=fa[x];

     rec(x);

     t[y][]=;

     pushup(y);

     pushup(fa[y]);

 }

 void build(int l,int r,int p)

 {

     if(l>r) return;

     int mid=(l+r)>>;

     int now=id[mid];

     int last=id[p];

     if(l==r)

     {

         sum[now]=a[l];

         size[now]=;

         tag[now]=rev[now]=;

         if(a[l]>=) lx[now]=rx[now]=mx[now]=a[l];

          else{lx[now]=rx[now]=; mx[now]=a[l];}

     }

      else

      {

         build(l,mid-,mid);

         build(mid+,r,mid);

      }

     v[now]=a[mid];

     fa[now]=last;

     pushup(now);

     t[last][mid>=p]=now;

 }

 void Insert(int k,int tot)

 {

     for(int i=;i<=tot;i++) a[i]=read();

     for(int i=;i<=tot;i++)

      if(!q.empty()){id[i]=q.front(); q.pop();}

       else id[i]=++cnt;

     build(,tot,);

     int z=id[(tot+)>>];

     int x=find(root,k+);

     int y=find(root,k+);

     splay(x,root);

     splay(y,t[x][]);

     fa[z]=y;

     t[y][]=z;

     pushup(y);

     pushup(x);

 }

 int main()

 {

     //freopen("bzoj1500.in","r",stdin);

     //freopen("bzoj1500.out","w",stdout);

     n=read();

     m=read();

     mx[]=a[]=a[n+]=-oo;

     for(int i=;i<=n+;i++) a[i]=read();

     for(int i=;i<=n+;i++) id[i]=i;

     build(,n+,);

     root=(n+)>>;

     cnt=n+;

     int x,y,z;

     char ch[];

     while(m--)

     {

         scanf("%s",ch);

         if(ch[]!='M'||ch[]!='X') scanf("%d%d",&x,&y);

         if(ch[]=='I') Insert(x,y);

         if(ch[]=='D') Delete(x,y);

         if(ch[]=='M')

         {

             if(ch[]=='X') printf("%d\n",mx[root]);

              else

              {

                 z=read();

                 update(x,y,z);

              }

         }

         if(ch[]=='R') rever(x,y);

         if(ch[]=='G') query(x,y);

     }

     return ;

 }

巴特西

【BZOJ1500】维修数列（splay）

最新文章

热门文章