splay

splay的一道练习。。。忘记把虚拟头节点的m值设成-INF WA了一下午。。。

#include 
    
     #define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)using namespace std;typedef long long ll;inline int lowbit(int x){ return x & (-x); }inline int read(){    int X = 0, w = 0; char ch = 0;    while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }    while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();    return w ? -X : X;}inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }inline int lcm(int a, int b){ return a / gcd(a, b) * b; }template
     
      inline T max(T x, T y, T z){ return max(max(x, y), z); }template
      
       inline T min(T x, T y, T z){ return min(min(x, y), z); }template
       
        inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}const int N = 50005;int t;struct Node{    int val, size, lazy, flip, m;    Node *son[2], *fa;}a[N], *null, *NI, *root;Node *newNode(Node *fa, int val){    Node *node = &a[t++];    node->val = val, node->m = val, node->fa = fa;    node->size = 1, node->lazy = 0, node->flip = 0;    node->son[0] = node->son[1] = null;    return node;}void push_up(Node *node){    if(node == NI) return;    node->size = node->son[0]->size + node->son[1]->size + 1;    node->m = max(node->son[0]->m, node->son[1]->m, node->val);}void push_down(Node *node){    if(node->son[0] != null)        node->son[0]->lazy += node->lazy, node->son[0]->val += node->lazy, node->son[0]->m += node->lazy;    if(node->son[1] != null)        node->son[1]->lazy += node->lazy, node->son[1]->val += node->lazy, node->son[1]->m += node->lazy;    node->lazy = 0;    if(node->flip){        node->son[0]->flip ^= 1, node->son[1]->flip ^= 1;        swap(node->son[0]->son[0], node->son[0]->son[1]);        swap(node->son[1]->son[0], node->son[1]->son[1]);        node->flip = 0;    }}void rotate(Node *x, int p){    Node *y = x->fa;    push_down(y), push_down(x);    y->son[p^1] = x->son[p];    if(x->son[p] != null) x->son[p]->fa = y;    y->fa->son[y->fa->son[1] == y] = x;    x->fa = y->fa;    x->son[p] = y;    y->fa = x;    push_up(y);}void splay(Node *node, Node *goal){    if(node == goal) return;    while(node->fa != goal){        Node *fa = node->fa, *gfa = fa->fa;        if(gfa == goal){            rotate(node, fa->son[0] == node);            break;        }        int p = gfa->son[1] == fa;        if((fa->son[1] == node) == p){            rotate(fa, p^1);            rotate(node, p^1);        }        else{            rotate(node, p);            rotate(node, p^1);        }    }    push_up(node);    if(goal == NI) root = node;}void splay(int k, Node *goal){    Node *node = root;    push_down(node);    int n = node->son[0]->size;    // k + 1   while(1){        if(k < n) node = node->son[0];        else{            if(k == n) break;            else k -= n + 1, node = node->son[1];        }        push_down(node);        n = node->son[0]->size;    }    splay(node, goal);}Node *buildTree(Node *fa, int l, int r){    if(l > r) return null;    Node *node = newNode(fa, 0);    int mid = (l + r) >> 1;    node->son[0] = buildTree(node, l, mid - 1);    node->son[1] = buildTree(node, mid + 1, r);    push_up(node);    return node;}void add(int l, int r, int v){    splay(l - 1, NI);    splay(r + 1, root);    Node *key = root->son[1]->son[0];    key->lazy += v, key->m += v, key->val += v;}void reserve(int l, int r){    splay(l - 1, NI);    splay(r + 1, root);    Node *key = root->son[1]->son[0];    key->flip ^= 1;    swap(key->son[0], key->son[1]);    push_up(key), push_up(root->son[1]), push_up(root);}int query(int l, int r){    splay(l - 1, NI);    splay(r + 1, root);    return root->son[1]->son[0]->m;}int main(){    null = &a[t++], null->m = -INF,  NI = &a[t++], NI->m = -INF;    root = newNode(NI, -INF); root->son[0] = null;    root->son[1] = newNode(root, -INF); root->son[1]->son[1] = null;    int n = read(), m = read();    root->son[1]->son[0] = buildTree(root->son[1], 1, n);    while(m --){        int opt = read();        if(opt == 1){            int l = read(), r = read(), v = read();            add(l, r, v);        }        else if(opt == 2){            int l = read(), r = read();            reserve(l, r);        }        else if(opt == 3){            int l = read(), r = read();            printf("%d\n", query(l, r));        }        //inOrder(root);puts("");    }    return 0;}