1500: [NOI2005]维修数列

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1500

题目思路：splay ,包括区间插入，区间删除，回收内存，区间反转，区间和，区间最大子段，成段更新等操作。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
#define M 501000
#define keytree ch[ch[root][1]][0]
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int p[M],ch[M][2],v[M],s[M],lm[M],rm[M],ma[M],same[M],rev[M],sum[M],vst[M],a[M];
int top1,top2,root,n,m;
void visit(int x)
{
    if(!x) return;
   // printf(" x %d p %d ch0 %d ch1 %d v %d s %d rev %d sum %d lm %d rm %d ma %d \n",
     //      x,p[x],ch[x][0],ch[x][1],v[x],s[x],rev[x],sum[x],lm[x],rm[x],ma[x]);
    vst[++top2]=x;
    visit(ch[x][0]);
    visit(ch[x][1]);
}
void up(int x)
{
    int l=ch[x][0],r=ch[x][1];
    s[x]=1+s[l]+s[r];
    sum[x]=sum[l]+v[x]+sum[r];
    lm[x]=max(lm[l],sum[l]+v[x]+max(0,lm[r]));
    rm[x]=max(rm[r],sum[r]+v[x]+max(0,rm[l]));
    ma[x]=max(0,rm[l])+v[x]+max(0,lm[r]);
    ma[x]=max(ma[x],max(ma[l],ma[r]));
}
void datasame(int x,int val)
{
    if(!x) return;
    same[x]=1;
    v[x]=val;
    sum[x]=s[x]*val;
    lm[x]=rm[x]=ma[x]=max(val,sum[x]);
}
void datarev(int x)
{
    if(!x) return;
    rev[x]^=1;
    swap(lm[x],rm[x]);
    swap(ch[x][0],ch[x][1]);
}
void down(int x)
{
    int l=ch[x][0],r=ch[x][1];
    if(same[x])
    {
        datasame(l,v[x]);
        datasame(r,v[x]);
    }
    if(rev[x])
    {
        datarev(l);
        datarev(r);
    }
    same[x]=rev[x]=0;
}
void newnode(int &x,int val,int pre)
{
    if(top2)
      x=vst[top2--];
    else
    x=++top1;
    p[x]=pre;
    s[x]=1;
    ch[x][0]=ch[x][1]=same[x]=rev[x]=0;
    lm[x]=rm[x]=ma[x]=v[x]=sum[x]=val;
}
void build(int &x,int l,int r ,int pre)
{
    if(l>r)return;
    int mid=(l+r)>>1;
    newnode(x,a[mid],pre);
    build(ch[x][0],l,mid-1,x);
    build(ch[x][1],mid+1,r,x);
    up(x);
}
void init()
{
    top1=top2=p[0]=ch[0][0]=ch[0][1]=v[0]=s[0]=sum[0]=0;
    lm[0]=rm[0]=ma[0]=-inf;
    newnode(root,-inf,0);
    newnode(ch[root][1],-inf,root);
    s[root]=2;
    build(keytree,1,n,ch[root][1]);
    up(ch[root][1]);
    up(root);
}
void rot(int x,int f)
{
    int y=p[x];
    p[ch[x][f]]=y;
    ch[y][!f]=ch[x][f];
    p[x]=p[y];
    if(p[y]) ch[p[y]][ch[p[y]][1]==y]=x;
    p[y]=x;
    ch[x][f]=y;
    up(y);
}
void splay(int x,int goal)
{
    while(p[x]!=goal)
    {
        if(p[p[x]]==goal)rot(x,ch[p[x]][0]==x);
        else
        {
            int y=p[x],f=ch[p[y]][0]==y;
            if(ch[y][f]==x)
                rot(x,!f);
            else
                rot(y,f);
            rot(x,f);
        }
    }
    if(!goal) root=x;
    up(x);
}
void rotto(int k,int goal)
{
    int x=root;
    down(x);
    while(s[ch[x][0]]!=k)
    {
        if(s[ch[x][0]]>k)
            x=ch[x][0];
        else
        {
            k-=s[ch[x][0]]+1;
            x=ch[x][1];
        }
        down(x);
    }
    splay(x,goal);
}
void Same(int pos,int num,int c)
{
    rotto(pos-1,0);
    rotto(pos+num,root);
    datasame(keytree, c);
}
void Rev(int pos,int num)
{
    rotto(pos-1,0);
    rotto(pos+num,root);
    datarev(keytree);
}
void getsum(int pos,int num)
{
    rotto(pos-1,0);
    rotto(pos+num,root);
    printf("%d\n",sum[keytree]);
}
void maxsum()
{
    rotto(0,0);
    rotto(s[root]-1,root);
    printf("%d\n",ma[keytree]);
}
void eraser(int x)
{
    visit(x);
}
void insert(int pos,int num)
{
    rotto(pos,0);
    rotto(pos+1,root);
    build(keytree,1,num,ch[root][1]);
    up(ch[root][1]);
    up(root);
}
void del(int pos,int num)
{
    rotto(pos-1,0);
    rotto(pos+num,root);
    eraser(keytree);
    keytree=0;
    up(ch[root][1]);
    up(root);
}
int main()
{
    int i,pos,num,c;
    char op[20];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        init();
        while(m--)
        {
            scanf("%s",op);
            switch(op[0])
            {
                case 'I': scanf("%d%d",&pos,&num);
                          for(i=1;i<=num;i++)
                            scanf("%d",&a[i]);
                          insert(pos,num); break;
                case 'D': scanf("%d%d",&pos,&num);del(pos,num);break;
                case 'M':if(op[2]=='X') maxsum();
                          else
                          {
                            scanf("%d%d%d",&pos,&num,&c);
                            Same(pos,num,c);
                          }
                          break;
                case 'R':scanf("%d%d",&pos,&num);Rev(pos,num);break;
                case 'G':scanf("%d%d",&pos,&num);getsum(pos,num);break;
            }

        }
    }
    return 0;
}

今天的文章1500: [NOI2005]维修数列分享到此就结束了，感谢您的阅读。