[Splay] POJ3468 A Simple Problem with Integers

전형 적 인 선분 나무 제목 이 내 가 SPLAY 연습 을 가 져 왔 다.
다음 구간 의 구 화, lazy 구간 업데이트 에 익숙 합 니 다.
SPLAY 의 회전 동작 은 정말 강하 다. AVL 에서 회전 을 배 운 후 잠시 도 지체 하지 않 고 SPLAY 를 배 웠 다.
SPLAY 도 원래 이 진 트 리 입 니 다. 우 리 는 SPLAY 의 계층 구조 에 관심 이 없습니다. 임의의 회전 작업 이 중간 순 서 를 바 꾸 지 않 는 다 는 것 을 알 아야 수열 을 유지 할 수 있 습 니 다.
두 개의 무관 한 노드 를 미리 삽입 하 는 기술 이 있 습 니 다. ROOT 와 ROOT - > rightkid。그리고 작업 할 노드 를 ROOT - > right 에 삽입 합 니 다.kid 의 왼쪽 나 무 는 전체 구간 을 조작 할 수 있 도록 확보 할 수 있 습 니 다.
그래서 [L, R] 구간 을 조작 할 때 L - 1 에 대응 하 는 노드 를 뿌리 로 회전 시 키 고 R + 1 에 대응 하 는 노드 를 뿌리 로 회전 시 키 는 오른쪽 아들 이기 때문에 ROOT - > rightkid 의 왼쪽 나 무 는 전체 구간 에 대응 합 니 다.
주의해 야 할 것 은 노드 와 상 관 없 이 진정 으로 해 야 한 다 는 것 이다. 예 를 들 어 우리 가 최소 치 를 유지 해 야 한다 면 이 두 노드 의 값 은 INF 로 설정 해 야 한다. 그렇지 않 으 면 루트 에 통계 하면 오류 가 발생 할 수 있다.

#include<algorithm>
#include<cstdio>
#define lson(x) (kid[x][0])
#define rson(x) (kid[x][1])
#define ll long long int
using namespace std;
const int N = 100005;
int pre[N], size[N], kid[N][2];
ll data[N], sum[N], lazy[N];
int root, cnt;
void NewNode(int &x, int val, int f){
    x = ++cnt;
    pre[x] = f;
    size[x] = 1;
    data[x] = sum[x] = val;
    lazy[x] = lson(x) = rson(x) = 0;
}
void push_up(int x){
    size[x] = size[lson(x)] + size[rson(x)] + 1;
    sum[x] = sum[lson(x)] + sum[rson(x)] + data[x] + lazy[x];
}
void push_down(int x){
    ll &k = lazy[x];
    if(k){
        data[x] += k;
        lazy[lson(x)] += k;
        sum[lson(x)] += k*size[lson(x)];

        lazy[rson(x)] += k;
        sum[rson(x)] += k*size[rson(x)];
        k = 0;
    }
}
void Rotate(int x, int f){
    int y = pre[x];
    push_down(y); push_down(x);
    kid[y][!f] = kid[x][f];
    pre[kid[x][f]] = y;
    if(pre[y]) kid[pre[y]][ kid[pre[y]][1] == y] = x;
    pre[x] = pre[y];
    kid[x][f] = y;
    pre[y] = x;
    push_up(y); //      x
}
void Splay(int x, int goal){ //           orz,          
    push_down(x);
    while(pre[x] != goal){
        if(pre[pre[x]] == goal){
            Rotate(x, kid[pre[x]][0] == x);
        }
        else{
            int y = pre[x], z = pre[y];
            int f = (kid[z][0] == y);
            if(kid[y][f] == x){
                Rotate(x, !f);
                Rotate(x, f);
            }
            else{
                Rotate(y, f);
                Rotate(x, f);
            }
        }
    }
    push_up(x);
    if(goal == 0) root = x;
}
void RotateTo(int k, int goal){
    int x = root;
    push_down(x);
    while(size[lson(x)] != k){
        if(k < size[lson(x)]){
            x = lson(x);
        }
        else{
            k -= (size[lson(x)]+1);
            x = rson(x);
        }
        push_down(x);
    }
    Splay(x, goal);
}
int n, q;
int a[N];
void build(int &x, int l, int r, int f){
    if(l > r) return;
    int m = (l+r) >> 1;
    NewNode(x, a[m], f);
    build(lson(x), l, m-1, x);
    build(rson(x), m+1, r, x);
    push_up(x);
}
void query(int l, int r){
    RotateTo(l-1, 0);
    RotateTo(r+1, root);
    printf("%lld
", sum[lson(rson(root))]);
}
void update(int l, int r){
    ll tmp;
    scanf("%lld%*c", &tmp);
    RotateTo(l-1, 0);
    RotateTo(r+1, root);
    lazy[lson(rson(root))] += tmp;
    sum[lson(rson(root))] += tmp*size[lson(rson(root))];
}
int main(){
    char p;
    int n1, n2;
    while(scanf("%d %d%*c", &n, &q) != EOF){
        for(int i = 0; i < n; ++i) scanf("%d%*c", &a[i]);
        root = cnt = 0;
        pre[0] = kid[0][0] = kid[0][1] = size[0] = data[0] = lazy[0] = 0;
        sum[0] = 0;
        NewNode(root, -1, 0);  //            ，               ROOT->right_kid    。
        NewNode(rson(root), -1, root);
        size[root] = 2;
        build(lson(rson(root)), 0, n-1,rson(root));
        push_up(rson(root));
        push_up(root);
        while(q--){
            scanf("%c %d %d%*c", &p, &n1, &n2);
            if(p == 'Q') query(n1, n2);
            else if(p == 'C') update(n1, n2);
        }
        
    }
}