BZOJ 1500 [NOI 2005] 수리 수열 (Splay)

제목 의 뜻 은 많 지 않다.이것 은 아마도 splay 의 최종 문제 라 고 할 수 있 겠 지, poj 3580 과 차이 가 많 지 않다.삽입: 왼쪽 단점 앞의 노드 와 오른쪽 단점 뒤의 노드 를 뿌리 와 뿌리의 오른쪽 아들 로 회전 시 킨 다음 에 나 무 를 만 드 는 것 처럼 오른쪽 아들 의 왼쪽 나 무 를 구성 합 니 다.삭제: 같은 회전 방식.뿌리 부분 을 지 운 오른쪽 아들 의 왼쪽 나무.동시에 존재 하 는 노드 가 500000 개 를 넘 지 않 지만 끊임없이 삽입 하고 삭제 하면 노드 번호 x 가 매우 커 져 RE 를 초래 할 수 있다.따라서 메모리 회수 가 필요 합 니 다. 삭 제 된 모든 노드 번 호 를 저장 하기 위해 스 택 을 열 어야 합 니 다.수정: 같은 회전 방식.오른쪽 아들 왼쪽 나무 에 게 으 름 표 시 를 하 다.뒤 집기: 같은 회전 방식.마찬가지 로 오른쪽 아들 왼쪽 나무 에 게 으 름 표 시 를 한다.구 화: 동일 한 회전 방식.오른쪽 아들 왼쪽 나무 가 대표 하 는 구간 의 합 을 출력 합 니 다.최대 와 하위 서열 을 구 합 니 다: 구간 이 왼쪽 끝 점 에서 최대 와 하위 서열 lmx, 오른쪽 에서 왼쪽으로 rmx, 그리고 구간 최대 와 하위 서열 mx 를 저장 해 야 합 니 다.그러면 이 구간 의 왼쪽 에서 오른쪽으로 가장 큰 하위 서열 은 왼쪽 아들 의 왼쪽 에서 오른쪽으로 가장 큰 하위 서열 또는 왼쪽 아들 의 합 에 v [x] 와 오른쪽 아들 이 왼쪽 에서 오른쪽으로 가장 큰 하위 서열, 즉 lmx [x] = Max (lmx [lch], sum [lch] + v [x] + lmx [rch]), rmx 의 구법 과 같다.구간 의 최대 하위 서열 과 좌우 하위 트 리, 중간 에 있 을 수 있 습 니 다. 그러면 mx [x] = Max (mx [lch], mx [rch], rmx [lch] + v [x] + lmx [rch]) 가 있 습 니 다.

#include
#include
#include
#define MAXN 500010
#define INF 0x3f3f3f3f
#define key_pos ch[ch[root][1]][0]
using namespace std;
inline int Max(int a,int b) {return a>b?a:b;}
inline int Min(int a,int b) {return ainline void Swap(int &a,int &b) {int c = a; a = b; b = c;}
inline void GET(int &t)
{
    char c; int f = 1; t = 0;
    do{c = getchar(); if(c == '-') f = -1;}while(!isdigit(c));
    while(isdigit(c)) {t = t*10+c-'0'; c = getchar();} t *= f;
}
int ch[MAXN][2],v[MAXN],fa[MAXN],sz[MAXN];
int lz[MAXN],rev[MAXN],sum[MAXN],mxlen[MAXN],lmx[MAXN],rmx[MAXN];
int n,m,root,tot1,tot2,s[MAXN],a[MAXN];
void New(int &x,int father,int val)
{
    if(tot2) x = s[tot2--];
    else x = ++tot1;
    fa[x] = father;
    v[x] = sum[x] = mxlen[x] = lmx[x] = rmx[x] = val;
    sz[x] = 1;
    ch[x][0] = ch[x][1] = rev[x] = 0;
    lz[x] = INF;
}
void up_same(int x,int val)
{
    if(!x) return;
    v[x] = val;
    sum[x] = val*sz[x];
    mxlen[x] = lmx[x] = rmx[x] = Max(val,val*sz[x]);
    lz[x] = val;
}
void up_rev(int x)
{
    if(!x) return;
    Swap(ch[x][0],ch[x][1]);
    Swap(lmx[x],rmx[x]);
    rev[x] ^= 1;
}
void pushup(int x)
{
    int lch = ch[x][0],rch = ch[x][1],l = Max(0,lmx[rch]),r = Max(0,rmx[lch]);
    sz[x] = sz[lch]+sz[rch]+1;
    sum[x] = sum[rch]+sum[lch]+v[x];
    lmx[x] = Max(lmx[lch],sum[lch]+v[x]+l);
    rmx[x] = Max(rmx[rch],sum[rch]+v[x]+r);
    mxlen[x] = Max(mxlen[lch],mxlen[rch]);
    mxlen[x] = Max(mxlen[x],l+r+v[x]);
}
void pushdown(int x)
{
    if(lz[x] != INF)
    {
        up_same(ch[x][0],v[x]);
        up_same(ch[x][1],v[x]);
        lz[x] = INF;
    }
    if(rev[x])
    {
        up_rev(ch[x][0]);
        up_rev(ch[x][1]);
        rev[x] = 0;
    }
}
void build(int &x,int L,int R,int father)
{
    int mid = (L+R)/2;
    New(x,father,a[mid]);
    if(L == R) return;
    if(L < mid) build(ch[x][0],L,mid-1,x);
    if(R > mid) build(ch[x][1],mid+1,R,x);
    pushup(x);
}
void Init()
{
    GET(n); GET(m);
    lmx[root] = rmx[root] = mxlen[root] = -INF;
    New(root,0,-1);
    New(ch[root][1],root,-1);
    for(int i = 0; i < n; i++) GET(a[i]);
    build(key_pos,0,n-1,ch[root][1]);
    pushup(ch[root][1]);
    pushup(root);
}
void rotate(int x)
{ 
    int y = fa[x],z = fa[y],f = (ch[y][1] == x);
    ch[y][f] = ch[x][!f];
    if(ch[y][f]) fa[ch[y][f]] = y;
    ch[x][!f] = y,fa[y] = x;
    fa[x] = z;
    if(z) ch[z][ch[z][1]==y] = x;
    pushup(y);
}
void splay(int x,int goal)
{
    for(int y; (y=fa[x]) != goal; rotate(x))
    {
        int z = fa[y];
        if(z != goal)
        {
            if((ch[z][0] == y) == (ch[y][0] == x)) rotate(y);
            else rotate(x);
        }
    }
    if(!goal) root = x;
    pushup(x);
}
void rotateTo(int k,int goal)
{
    int x = root;
    while(1)
    {
        pushdown(x);
        if(sz[ch[x][0]]+1 < k) k -= sz[ch[x][0]]+1,x = ch[x][1];
        else if(sz[ch[x][0]]+1 > k) x = ch[x][0];
        else break;
    }
    splay(x,goal);
}
void Insert(int pos,int tot)
{
    for(int i = 0; i < tot; i++) GET(a[i]);
    rotateTo(pos+1,0);
    rotateTo(pos+2,root);
    build(key_pos,0,tot-1,ch[root][1]);
    pushup(ch[root][1]);
    pushup(root);
}
void Back(int x)
{
    if(!x) return;
    s[++tot2] = x;
    Back(ch[x][0]);
    Back(ch[x][1]);
}
void Delete(int pos,int tot)
{
    rotateTo(pos,0);
    rotateTo(pos+tot+1,root);
    Back(key_pos);
    fa[key_pos] = 0;
    key_pos = 0;
    pushup(ch[root][1]);
    pushup(root);
}
void Make_same(int pos,int tot,int val)
{
    rotateTo(pos,0);
    rotateTo(pos+tot+1,root);
    up_same(key_pos,val);
    pushup(ch[root][1]);
    pushup(root);
}
void Reverse(int pos,int tot)
{
    rotateTo(pos,0);
    rotateTo(pos+tot+1,root);
    up_rev(key_pos);
    pushup(ch[root][1]);
    pushup(root);
}
int Get_sum(int pos,int tot)
{
    rotateTo(pos,0);
    rotateTo(pos+tot+1,root);
    return sum[key_pos];
}
int Get_max(int pos,int tot)
{
    rotateTo(pos,0);
    rotateTo(pos+tot+1,root);
    return mxlen[key_pos];
}
int main()
{
    char ops[20];
    Init();
    for(int i = 1,x,y,z; i <= m; i++)
    {
        scanf("%s",ops);
        if(ops[0] == 'I') {GET(x),GET(y); Insert(x,y);}
        else if(ops[0] == 'D') {GET(x),GET(y); Delete(x,y);}
        else if(ops[2] == 'K') {GET(x),GET(y),GET(z); Make_same(x,y,z);}
        else if(ops[0] == 'R') {GET(x),GET(y); Reverse(x,y);}
        else if(ops[0] == 'G') {GET(x),GET(y); printf("%d
",Get_sum(x,y));}
        else printf("%d
",Get_max(1,sz[root]-2));
    }
}