splay树序列终结者

4655 序列终结者

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

网上有许多题，就是给定一个序列，要你支持几种操作：A、B、C、D。一看另一道题，又是一个序列要支持几种操作：D、C、B、A。尤其是我们这里的某人，出模拟试题，居然还出了一道这样的，真是没技术含量……这样我也出一道题，我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠，没有什么其他的意思。这道题目就叫序列终结者吧。

给定一个长度为N的序列，每个序列的元素是一个整数（废话）。要支持以下三种操作： 1. 将[L,R]这个区间内的所有数加上V。 2. 将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1。 3. 求[L,R]这个区间中的最大值。最开始所有元素都是0。

输入描述 Input Description

第一行两个整数N，M。M为操作个数。以下M行，每行最多四个整数，依次为K，L，R，V。K表示是第几种操作，如果不是第1种操作则K后面只有两个数。

输出描述 Output Description

对于每个第3种操作，给出正确的回答。*/

//splay树第一次知道spaly树还可以这么玩，好开心。。。

//不过因为一个小错误调了半天。

#include<cstdio>
#include<iostream>
using namespace std;
int n,v[50005],shu[50005][2],fa[50005],m,size,sz[50005],mx[50005],root;
int he[50005],bi[50005];
void geng(int a1)
{
sz[a1]=sz[shu[a1][0]]+sz[shu[a1][1]]+1;
    mx[a1]=max(mx[shu[a1][0]],mx[shu[a1][1]]);
    mx[a1]=max(mx[a1],v[a1]);
    return;
}
void roate(int a1,int &k)
{
int y=fa[a1],z=fa[y],l,r;
if(shu[y][0]==a1)
   l=0;
else
   l=1;
r=l^1;
if(y==k)
   k=a1;
else
   if(shu[z][0]==y)
     shu[z][0]=a1;
   else
     shu[z][1]=a1;
fa[a1]=z;
shu[y][l]=shu[a1][r];
fa[shu[a1][r]]=y;
shu[a1][r]=y;
fa[y]=a1;
geng(a1);
geng(y);
return;
}
void splay(int &k,int a1)
{
for(;a1!=k;)
   {
   int y=fa[a1],z=fa[y];
   if(y!=k)
      if(shu[z][0]==y^shu[y][0]==a1)
       roate(a1,k);
     else
          roate(y,k);
  roate(a1,k);
   }
}
void geng1(int a1)
{
int l=shu[a1][0],r=shu[a1][1];
if(he[a1])
      {
      if(l){mx[l]+=he[a1];v[l]+=he[a1];he[l]+=he[a1];}
      if(r){mx[r]+=he[a1];v[r]+=he[a1];he[r]+=he[a1];}
      he[a1]=0;
   }
if(bi[a1])
   {
   bi[l]^=1;
   bi[r]^=1;
   bi[a1]=0;
   swap(shu[a1][0],shu[a1][1]);
   }
}
void jian(int a1,int a2,int a3)
{
if(a1>a2)
   return;
if(a1==a2)
   {
   fa[a1]=a3;
   if(a1<a3)
      shu[a3][0]=a1;
   else
      shu[a3][1]=a1;
   sz[a1]=1;
     return;
   }
int mid=(a1+a2)>>1;
fa[mid]=a3;
if(mid<a3)
   shu[a3][0]=mid;
else
   shu[a3][1]=mid;
    jian(a1,mid-1,mid);
    jian(mid+1,a2,mid);
    geng(mid);
}
int find(int a1,int a2)
{
if(he[a1]||bi[a1])geng1(a1);
if(sz[shu[a1][0]]==a2-1)
   return a1;
if(sz[shu[a1][0]]>=a2)
   return(find(shu[a1][0],a2));
return(find(shu[a1][1],a2-sz[shu[a1][0]]-1));
}
void jia(int a1,int a2,int a3)
{
int x=find(root,a1);
int y=find(root,a2+2);
splay(root,x);
splay(shu[x][1],y);
int z=shu[y][0];
v[z]+=a3;
mx[z]+=a3;
he[z]+=a3;
return;
}
void fan(int a1,int a2)
{
int x=find(root,a1),y=find(root,a2+2);
splay(root,x);
splay(shu[x][1],y);
int z=shu[y][0];
bi[z]^=1;
return;
}
int zhao(int a1,int a2)
{
int x=find(root,a1),y=find(root,a2+2);
splay(root,x);
splay(shu[x][1],y);
int z=shu[y][0];
return mx[z];
}
int main()
{
mx[0]=-999999999;
scanf("%d%d",&n,&m);
jian(1,n+2,0);
root=(n+3)>>1;
for(int i=0;i<m;i++)
   {
   int a1,a2,a3,a4;
   scanf("%d%d%d",&a1,&a2,&a3);
   if(a1==1)
      {
      scanf("%d",&a4);
      jia(a2,a3,a4);
   }
  if(a1==2)
    fan(a2,a3);
  if(a1==3)
    printf("%d\n",zhao(a2,a3));
   }
}

巴特西

splay树序列终结者

4655 序列终结者

最新文章

热门文章

巴特西

splay树 序列终结者

4655 序列终结者

最新文章

热门文章

splay树序列终结者