题解 P2042 【[NOI2005]维护数列】

2018-02-02 10:44:23


指针版非旋Treap

本来写的好好的,然后调指针调的......大概是我太弱了

然后就拿了@曦月__OFN 大佬的代码来对着调

然后代码就长得极其相似......

似乎楼下题解还有一篇差不多的,但是我们不在意这些细节

指针的好处:

  1. 写多了其实就好调了

  2. 锻炼代码能力

  3. 方便递归

  4. 可以回收内存

  5. 有些操作方便

指针的坏处:

  1. 同一个程序在不同机子下的表现不同(例如32位和64位)

  2. 蒟蒻杀手,不方便调试

  3. 分配内存略慢(当然可以开内存池)

  4. 莫名RE

  5. 有些操作不方便

然后接下来是代码部分,最后一段的system是用来检测内存大小:

#include <cstdio>
#include <cctype>
#include <cstdlib>
using namespace std;
#define MAXN 500050
#define INF 0x3f3f3f3f
#define Finline __inline__ __attribute__ ((always_inline))

const int MODS = 5371321, PRI = 832211;

Finline char get_char(){
    static char buf[10000001], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 10000000, stdin), p1 == p2) ? EOF : *p1 ++;
}
inline int read(){
    int num = 0;
    char c, sf = 1;
    while (!isdigit(c = get_char()) && c != '-');
    if(c == '-') c = get_char(), sf = -1;
    while (num = num * 10 + c - 48, isdigit(c = get_char()));
    return num * sf;
}
inline void swap(int &x, int &y){
    int t = x;
    x = y;
    y = t;
}
Finline int max(int a, int b){
    int c = (a - b) >> 31;
    return (a & ~ c) | (b & c);
}
Finline int min(int a, int b){
    int c = (a - b) >> 31;
    return (a & c) | (b & ~ c);
}
Finline void upmin(int &a, const int &b){
    if(a > b) a = b;
}
Finline void upmax(int &a, const int &b){
    if(a < b) a = b;
}

struct Node{
    int size, val, wv, cov;
    int sum, lm, rm, sm;
    bool rev;
    Node *lc, *rc;
};

int top, cnt;
Node* root, *stack[MAXN];

inline void swap(Node* &x, Node* &y){
    Node* t = x;
    x = y;
    y = t;
}

inline Node* NewNode(int val){
    Node *ret;
    if((ret = (Node*)malloc(sizeof(Node))) == NULL) return NULL;
    if(cnt) cnt--;
    ret -> rev = false;
    ret -> size = 1;
    ret -> val = ret -> sum = ret -> sm = val;
    ret -> wv = rand();
    ret -> cov = INF;
    ret -> lm = ret -> rm = max(val, 0);
    ret -> lc = ret -> rc = NULL;
    return ret;
}

int n, m;

inline int rand(){
    static int sed = 15;
    return sed = 1ll * sed * PRI % MODS;
}

inline void Del(Node *node){
    if(node == NULL) return ;
    Del(node -> lc), Del(node -> rc);
    free(node);
    cnt++;
}

inline void Cover(Node *node, int val){
    node -> val = val;
    node -> sum = (node -> size) * val;
    node -> lm = node -> rm = max(node -> sum, 0);
    node -> sm = max(node -> sum, node -> val);
    node -> cov = val;
}

inline void Reverse(Node* &node){
    swap(node -> lc, node -> rc);
    swap(node -> lm, node -> rm);
    node -> rev ^= 1;  
}

inline void Push_Up(Node *node){
    bool l = node -> lc == NULL, r = node -> rc == NULL;
    node -> size = (l ? 0 : node -> lc -> size) + (r ? 0 : node -> rc -> size) + 1;
    node -> sum = (l ? 0 : node -> lc -> sum) + (r ? 0 : node -> rc -> sum) + node -> val;
    node -> sm = max(max((l ? -INF : node -> lc -> sm), (r ? -INF : node -> rc -> sm)), (l ? 0 : node -> lc -> rm) + (r ? 0 : node -> rc -> lm) + node -> val);
    node -> lm = max((l ? 0 : node -> lc -> lm), (l ? 0 : node -> lc -> sum) + (r ? 0 : node -> rc -> lm) + node -> val);
    node -> rm = max((r ? 0 : node -> rc -> rm), (r ? 0 : node -> rc -> sum) + (l ? 0 : node -> lc -> rm) + node -> val);
}

inline void Push_Down(Node *node){
    if(node -> rev){
        node -> rev = false;
        if(node -> lc != NULL) Reverse(node -> lc);
        if(node -> rc != NULL) Reverse(node -> rc);
    }
    if(node -> cov != INF){
        if(node -> lc != NULL) Cover(node -> lc, node -> cov);
        if(node -> rc != NULL) Cover(node -> rc, node -> cov);
        node -> cov = INF;
    }
}

inline Node* Merge(Node* x, Node* y){
    if(x != NULL) Push_Down(x);
    if(y != NULL) Push_Down(y);
    if(x == NULL || y == NULL) return x == NULL ? y : x;
    if(x -> wv < y -> wv){
        x -> rc = Merge(x -> rc, y);
        Push_Up(x);
        return x;
    } else {
        y -> lc = Merge(x, y -> lc);
        // if(y == y -> lc) printf("Dead in line %d of %d\n", __LINE__, y -> wv);
        Push_Up(y);
        return y;
    }
}

inline void Split(Node* node, int k, Node* &x, Node* &y){
    if(node == NULL){
        x = y = NULL;
        return;
    }
    Push_Down(node);
    if((node -> lc == NULL ? 0 : node -> lc -> size) >= k){
        y = node;
        Split(node -> lc, k, x, node -> lc);
    } else {
        x = node;
        Split(node -> rc, k - 1 - (node -> lc == NULL ? 0 : node -> lc -> size), node -> rc, y);
    }
    Push_Up(node);
}

int main(){
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    n = read(), m = read();
    for(int i = 1; i <= n; i++){
        int val = read();
        Node *p = NewNode(val), *tmp = NULL;
        if(top) stack[top] -> rc = p;
        p -> lc = tmp, stack[++top] = p;
    }
    while(top) Push_Up(stack[top--]);
    root = stack[1];
    while(m--){
        char cons;
        while(!isalpha(cons = get_char()));
        if(cons == 'I'){
            int st = read(), tot = read();
            for(int i = 1; i <= tot; i++){
                int val = read();
                Node *p = NewNode(val), *tmp = NULL;
                while(cnt && stack[top] != NULL && stack[top] -> wv > p -> wv){
                    Push_Up(stack[top]);
                    tmp = stack[top];
                    stack[top--] = NULL;
                }
                if(top) stack[top] -> rc = p;
                p -> lc = tmp, stack[++top] = p;
            }
            Node *ls = NULL, *rs = NULL, *tmp;
            while(top) Push_Up(stack[top--]);
            tmp = stack[1];
            Split(root, st, ls, rs);
            root = Merge(Merge(ls, tmp), rs);
        } else if(cons == 'D'){
            int st = read(), k = read();
            Node *ls = NULL, *rs = NULL, *xs = NULL, *ys = NULL;
            Split(root, st - 1, ls, rs);
            Split(rs, k, xs, ys);
            root = Merge(ls, ys);
            cnt += xs == NULL ? 0 : xs -> size;
            Del(xs);
        } else if(cons == 'R'){
            int st = read(), k = read();
            Node *ls = NULL, *rs = NULL, *xs = NULL, *ys = NULL;
            Split(root, st - 1, ls, rs);
            Split(rs, k, xs, ys);
            Reverse(xs);
            root = Merge(ls, Merge(xs, ys));
        } else if(cons == 'G'){
            while(!isspace(get_char()));
            int st = read(), k = read();
            Node *ls = NULL, *rs = NULL, *xs = NULL, *ys = NULL;
            Split(root, st - 1, ls, rs);
            Split(rs, k, xs, ys);
            if(xs == NULL) puts("0");
            else printf("%d\n", xs -> sum);
            root = Merge(ls, Merge(xs, ys));
        } else {
            cons = get_char(), cons = get_char();
            while(!isspace(get_char()));
            if(cons == 'X') printf("%d\n", root -> sm);
            else {
                int st = read(), k = read(), val = read();
                Node *ls = NULL, *rs = NULL, *xs = NULL, *ys = NULL;
                Split(root, st - 1, ls, rs);
                Split(rs, k, xs, ys);
                Cover(xs, val);
                root = Merge(ls, Merge(xs, ys));
            }
        }
    }
    // Debug Get Running Memery
    // system("wmic process where name=\"a.exe\" get WorkingSetSize");
    return 0;
}