백준 2844번 자료구조

백준 2844번 자료구조

스플레이트리를 사용해서 문제를 해결할 수 있다.

3번과 4번쿼리는 별 거 없이 스플레이 트리의 기본 연산들로 처리할 수 있다. (split, merge)

1번쿼리 또한 레이지 프롭으로 쉽게 해결이 가능한 쿼리다.

2번 쿼리가 문제다.

스플레이트리로 선형 배열을 다룰 때 서브트리는 각각 어떤 구간을 담당하고 있는 것으로 볼 수 있다.

[L, R]을 담당하게 서브트리를 잘 모았다고 치면 이 구간에 들어오는 2번 쿼리는 초항이 X이고 공차가 X이며 길이가 R-L+1인 수열을 [L, R]에 더해주는 것이다. 그러면 이 쿼리를 어떻게 전파할 지 생각할 수 있다.

해당 서브트리의 루트가 위 구간에서 m번째 노드라고 하자. 그러면 왼쪽 서브트리는 [L, m-1]을 담당하고 오른쪽 서브트리는 [m+1, R]을 담당한다. 왼쪽엔 초항이 X이고 공차가 X인 수열이 그대로 전해지는 셈이 되고, 오른쪽엔 초항이 (m-L+1)X이고 공차가 X인 쿼리를 전파해주면 처리가 가능하다.

이거로 모든 쿼리가 처리 가능하다.

레이지 뿌릴 때 조심할 사항으로 1번 쿼리를 뿌릴 때 2번 쿼리를 리셋해줘야 한다.

아래는 코드다. push랑 pull을 제대로 된 위치에 넣어주기가 어려운거 같다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node {
    Node *l, *r, *p;
    int sz;
    ll val;
    // declare extra variables
    ll lazy1, lazys, lazyd, sum;
    Node() : l(nullptr), r(nullptr), p(nullptr) {};
    Node(ll _val) {
        l = r = p = nullptr;
        sz = 1;
        val = _val;
        // init extra variables
        sum = val; lazy1 = -1; lazys = lazyd = 0;
    }
} *root;

// push into children(lazy, inv etc)
void push(Node *cur) {
    // pushing process
    if(cur->lazy1 == -1 && cur->lazyd == 0) return ;
    if(cur->lazy1 != -1) {
        cur->val = cur->lazy1;
        cur->sum = cur->val * cur->sz;
        if(cur->l) {
            cur->l->lazy1 = cur->lazy1;
            cur->l->lazys = cur->l->lazyd = 0;
        }
        if(cur->r) {
            cur->r->lazy1 = cur->lazy1;
            cur->r->lazys = cur->r->lazyd = 0;
        }
        cur->lazy1 = -1;
    }
    if(cur->lazyd) {
        int shift = 1;
        if(cur->l) {
            shift += cur->l->sz;
            cur->l->lazys += cur->lazys;
            cur->l->lazyd += cur->lazyd;
        }
        cur->val += cur->lazys + shift * cur->lazyd;
        cur->sum += (2*cur->lazys + (cur->sz+1)*cur->lazyd) * cur->sz / 2;
        if(cur->r) {
            cur->r->lazys += cur->lazyd * shift + cur->lazys;
            cur->r->lazyd += cur->lazyd;
        }
        cur->lazys = cur->lazyd = 0;
    }
}

// pull from children(size, sum etc)
void pull(Node *cur) {
    // pulling process
    push(cur);
    cur->sz = 1;
    cur->sum = cur->val;
    if(cur->l) {
        push(cur->l);
        cur->sz += cur->l->sz;
        cur->sum += cur->l->sum;
    }
    if(cur->r) {
        push(cur->r);
        cur->sz += cur->r->sz;
        cur->sum += cur->r->sum;
    }
}

void rotate(Node *cur) {
    Node* p = cur->p;
    if(!p) return ; // cur is root
    pull(p);
    pull(cur);
    Node *tmp;
    if(p->l == cur) {
        tmp = cur->r;
        p->l = cur->r;
        cur->r = p;
    }
    else {
        tmp = cur->l;
        p->r = cur->l;
        cur->l = p;
    }
    Node *pp = p->p;
    cur->p = pp;
    p->p = cur;
    if(tmp) tmp->p = p;
    if(cur->p) {
        if(pp->l == p) pp->l = cur;
        else if(pp->r == p) pp->r = cur;
    }
    else root = cur;
    pull(p);
    pull(cur);
}

void splay(Node *cur) {
    while(cur->p) {
        Node *p = cur->p;
        Node *pp = p->p;
        if(pp) {
            if((pp->l == p) == (p->l == cur)) rotate(p);
            else rotate(cur);
        }
        rotate(cur);
    }
}

// split tree first <= cur, second > cur
pair<Node*, Node*> split(Node *cur) {
    splay(cur);
    Node *left = cur;
    Node *right = cur->r;
    if(left) left->p = nullptr;
    if(right) right->p = nullptr;
    return {left, right};
}

Node* merge(Node *left, Node *right) {
    if(left == nullptr) return right;
    if(right == nullptr) return left;
    Node *p = left;
    while(p->r) p = p->r;
    pull(p);
    splay(p);
    p->r = right;
    right->p = p;
    pull(p);
    return p;
}

Node* kth(Node *cur, int k) {
    Node *p = cur;
    pull(p);
    while(1) {
        while(p->l && p->l->sz > k) {
            p = p->l;
            pull(p);
        }
        if(p->l) k -= p->l->sz;
        if(!k) break;
        else --k;
        p = p->r;
        pull(p);
    }
    splay(p);
    return p;
}

// p->r->l represents [l,r]
Node* interval(Node *cur, int l, int r) {
    Node *p = kth(cur, l-1);
    Node *right = p->r;
    right->p = nullptr;
    right = kth(right, r-l+1);
    right->p = p;
    p->r = right;
    root = p;
    pull(p);
    return p;
}

int N, Q;
ll a[100005];

void init_tree() {
    Node *p = root = new Node(0);
    for(int i=1;i<=N;++i) {
        p->r = new Node(a[i]);
        p->r->p = p;
        p = p->r;
    }
    p->r = new Node(0);
    p->r->p = p;
    p = p->r;
    while(p) {
        pull(p);
        p = p->p;
    }
}

void query1(int l, int r, int x) {
    Node *p = interval(root, l, r);
    pull(p);
    pull(p->r);
    pull(p->r->l);
    p = p->r->l;
    p->lazy1 = x;
    p->lazys = p->lazyd = 0;
    while(p) {
        pull(p);
        p = p->p;
    }
}

void query2(int l, int r, int x) {
    Node *p = interval(root, l, r);
    pull(p);
    pull(p->r);
    pull(p->r->l);
    p = p->r->l;
    p->lazys = 0;
    p->lazyd = x;
    while(p) {
        pull(p);
        p = p->p;
    }
}

void query3(int pos, int val) {
    Node *p = kth(root, pos-1);
    pull(p);
    p = p->r;
    pull(p);
    while(p->l) {
        pull(p);
        p = p->l;
    }
    p->l = new Node(val);
    p->l->p = p;
    p = p->l;
    Node *pp = p;
    while(p) {
        pull(p);
        p = p->p;
    }
    splay(pp);
}

ll query4(int l, int r) {
    Node *p = interval(root, l, r);
    pull(p);
    pull(p->r);
    pull(p->r->l);
    assert(p->r->l->sz == r-l+1);
    return p->r->l->sum;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> Q;
    for(int i=1;i<=N;++i) cin >> a[i];
    init_tree();
    for(int i=0;i<Q;++i) {
        int q, l, r, x;
        cin >> q;
        if(q == 1) {
            cin >> l >> r >> x;
            query1(l,r,x);
        }
        else if(q == 2) {
            cin >> l >> r >> x;
            query2(l, r, x);
        }
        else if(q == 3) {
            cin >> l >> x;
            query3(l, x);
        }
        else {
            cin >> l >> r;
            cout << query4(l, r) << '\n';
        }
    }
    return 0;
}