Codeforce Volga Region Time To read

http://codeforces.ru/gym/100186/attachments

debug de 超久＝ ＝

反正就是用treap或線段樹作合併

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<utility>
using namespace std;
class _node{
public:
    _node():left(nullptr), right(nullptr), anc(nullptr), 
            color(0), value(0), size(1){
        fixvalue = rand(); 
        return;
    }
    void update_size(){
        size = 1; // self
        if(left != nullptr) size += left->size;
        if(right != nullptr) size += right->size;
        return;
    }
    _node* left; _node* right; _node* anc;
    int color, fixvalue, value, size;
};
typedef _node node;
typedef pair<node*, node*> pii;
void print(node* prc){
    if(prc == nullptr)
        fprintf(stderr, "X");
    else{
        fprintf(stderr, "(%d):{", prc->value);
        print(prc->left);
        fprintf(stderr, ", ");
        print(prc->right);
        fprintf(stderr, "}");
    }
    return;
}
void update(node* prc){
    if(prc == nullptr) return;
    prc->update_size();
    if(prc->left != nullptr)
        prc->left->anc = prc;
    if(prc->right != nullptr)
        prc->right->anc = prc;
    return;
}
node* merge(node* a, node* b){ 
    if(a == nullptr ) return b;
    if(b == nullptr ) return a;
    if(a->value > b->value)
        swap(a, b);
    if(a->fixvalue > b->fixvalue){
        a->right = merge(a->right, b);
        update(a);
        return a;
    }else{
        b->left = merge(b->left, a);
        update(b);
        return b;
    }
}
pair<node*,node*> split(node* prc, int t){
    if(prc == nullptr)
        return pii(nullptr, nullptr);
    node *a, *b;
    if(prc->value <= t){
        a = prc;
        tie(a->right, b) = split(prc->right, t);
        update(a);
    }else{
        b = prc;
        tie(a, b->left) = split(prc->left, t);
        update(b);
    }
    return pii(a, b);
}
node* cut(node*& prc, int ll, int rr){ // cut [ll, rr]
    if(prc == nullptr) return nullptr;
    node *a, *b, *c;
    int color = prc->color;
    //print(prc);fprintf(stderr, "\n");
    tie(a, b) = split(prc, ll-1);
    tie(b, c) = split(b, rr);
    prc = merge(a, c);
    //print(prc);fprintf(stderr, "\n");
    if(prc != nullptr){
        prc->color = color;
        prc->anc = nullptr;
    }
    return b;
}
int find(node* prc){
    if(prc == nullptr) return 0;
    //fprintf(stderr, "ask%d ", prc->value);
    if(prc->anc == nullptr){
        //fprintf(stderr, "\n");
        return prc->color;
    }
    //fprintf(stderr, "->");
    return find(prc->anc);
}
node* ns[3000005];
node* ln[3000005];
int main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    srand(71227122);
    int n, q;scanf("%d %d", &n, &q);
    for(int lx = 1;lx <= n;lx++){
        ln[lx] = new node;
        ln[lx]->value = lx;
    }
    for(int lx = 0;lx <= q;lx++)
        ns[lx] = nullptr;
    for(int lx = 1;lx <= n;lx++){
        ns[0] = merge(ns[0], ln[lx]);
    }
    long long int ans = 0;
    /*fprintf(stderr, "------\n");
    fprintf(stderr, "white:");
    print(ns[0]);
    fprintf(stderr, "\n");*/
    for(int lx = 1;lx <= q;lx++){
        int ll, rr; scanf("%d %d", &ll, &rr);
        //fprintf(stderr, "range[%d, %d]\n", ll, rr);
        int c = find(ln[ll]);
        //fprintf(stderr, "ask color = %d\n", c);
        //fprintf(stderr, "on cut 1\n");
        node* t1 = cut(ns[0], ll, rr);
        //fprintf(stderr, "after cut1: color0 become:\n");
        //print(ns[0]);fprintf(stderr,"\n");
        //fprintf(stderr, "on cut 2\n");
        node* t2 = cut(ns[c], ll, rr);
        //print(ns[c]);
        //printf("\n");
        //fprintf(stderr, "to merge\n");
        ns[lx] = merge(ns[lx], t1);
        ns[lx] = merge(ns[lx], t2);
        //fprintf(stderr, "merge ok\n");
        //print(ns[lx]);
        //fprintf(stderr,"\n");
        if(ns[lx] != nullptr){
            ns[lx]->color = lx;
            ns[lx]->anc = nullptr;
            update(ns[lx]);
            ans += (long long int)ns[lx]->size;
            //fprintf(stderr, "salcAL\n");
        }
        //fprintf(stderr, "cal ok\n");
        /*printf("%d: ", lx);
        print(ns[lx]);
        printf("\n");*/
    }
    printf("%I64d\n", ans);
    return 0;
}