BJWC结业测试T3 - 神秘物质 atom

2017/01/20

17北京冬令营结业测试第三题。

前排膜 280 分的 wzj 大爷。

身为不会 Splay 的老年选手,考场上这题用 fhqtreap 写挂了(区间提取和上推都有错)。

题目描述

一个序列四种操作:

  1. merge x e:将 x 和 x+1 位置的两个元素替换为一个值为 e 的元素
  2. insert x e:在 x 号元素后插入一个值为 e 的元素
  3. max x y:求 [x, y] 中子区间的极差最大值
  4. min x y:求 [x, y] 中子区间的极差最小值

序列下标从 1 开始。

样例输入 1:

4 3
5 8 10 2
max 1 3
min 1 3
max 2 4

样例输出 1:

5
2
8

样例输入 2:

6 7
1 2 3 4 5 6
insert 1 3
max 2 4
merge 1 2
max 2 4
min 2 4
insert 6 1
max 5 7

样例输出 2:

1
2
1
5

代码

一个裸题,连懒标记都不用打。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

int rand() {
    static int k = 1364684579;
    return (k += (k<<2) + 1);
}

#define SZ(_) ((_) ? (_)->sz : 0)
struct node {
    int k, w, sz, mn, mx, ll, rr, jcmn;
    node *l, *r;
    static node* mknod(node*);

    void up() {
        mn = mx = k; sz = 1; jcmn = 1E9;
        ll = l ? l->ll : k;
        rr = r ? r->rr : k;
        if(l) {
            mn = min(mn, l->mn); mx = max(mx, l->mx); sz += l->sz;
            jcmn = min(jcmn, l->jcmn);
            jcmn = min(jcmn, abs(k - l->rr));
        }
        if(r) {
            mn = min(mn, r->mn); mx = max(mx, r->mx); sz += r->sz;
            jcmn = min(jcmn, r->jcmn);
            jcmn = min(jcmn, abs(k - r->ll));
        }
    }
}; const int PSIZ = 2E6 + 1E3;
node POOL[PSIZ]; int ppos;
node* GC[PSIZ]; int gpos;

node* node::mknod(node* w = NULL) {
    if(w) {
        GC[gpos++] = w;
    } else {
        w = (gpos ? GC[--gpos] : &POOL[ppos++]);
        w->k = w->mn = w->mx = w->jcmn = w->ll = w->rr = 0; w->w = rand();
        w->l = w->r = NULL;
    }
    return w;
}

struct Treap {
    node* root;
    Treap() : root(NULL) { }

    void ins(node* &p, int a, int k) {
        if(!p) {
            p = node::mknod();
            p->jcmn = 1E9; p->k = p->ll = p->rr = p->mn = p->mx = k; p->sz = 1;
        } else {
            if(SZ(p->l) >= a) {
                ins(p->l, a, k);
                node* q = p->l;
                if(q->w < p->w) {
                    p->l = q->r; q->r = p;
                    p = q; p->r->up();
                }
            } else {
                ins(p->r, a-SZ(p->l)-1, k);
                node* q = p->r;
                if(q->w < p->w) {
                    p->r = q->l; q->l = p;
                    p = q; p->l->up();
                }
            }
            p->up();
        }
    }

    void ins(int a, int k) { return ins(root, a, k); }

    static void merge(node* &p, node* x, node* y) {
        if(!x || !y) p = x ? x : y;
        else {
            if(x->w < y->w) {
                merge(x->r, x->r, y); x->up(); p = x;
            } else {
                merge(y->l, x, y->l); y->up(); p = y;
            }
        }
    }

    void del(node* &p, int a) {
        if(SZ(p->l) == a) {
            node* q = p;
            merge(p, p->l, p->r);
            node::mknod(q);
        } else {
            if(SZ(p->l) > a) {
                del(p->l, a);
            } else {
                del(p->r, a-SZ(p->l)-1);
            }
            p->up();
        }
    }

    void del(int a) { return del(root, a); }

    static void cut(node* p, node* &x, node* &y, int a) {
        if(a == 0) x = NULL, y = p;
        else if(a == SZ(p)) x = p, y = NULL;
        else {
            if(SZ(p->l) >= a) {
                y = p;
                cut(p->l, x, y->l, a);
                y->up();
            } else {
                x = p;
                cut(p->r, x->r, y, a-SZ(p->l)-1);
                x->up();
            }
        }
    }

    void dfs(node* p, int dep = 0) {
        if(!p) return;
        if(p->l) dfs(p->l, dep + 4);
        for(int i=0;i<dep;i++) putchar(' ');
        printf("%d %d %d %d %d \n", p->k, p->sz, p->mn, p->mx, p->jcmn);
        if(p->r) dfs(p->r, dep + 4);
    }

    void dfs() { dfs(root); }
} T;

int main() {
    int N, M;
    scanf("%d %d", &N, &M);

    int t;
    for(int i=0;i<N;i++) {
        scanf("%d", &t);
        T.ins(i, t);
    }

    char op[32]; int a, b;
    for(int i=0;i<M;i++) {
        scanf("%s %d %d", op, &a, &b);
        if(op[1] == 'a') { // mAx
            --a, --b;
            node *p, *q, *r;
            Treap::cut(T.root, p, q, a);
            Treap::cut(q, q, r, b-a+1);
            printf("%d\n", q->mx - q->mn);
            Treap::merge(q, q, r);
            Treap::merge(T.root, p, q);
        } else if(op[1] == 'i') {// mIn
            --a, --b;
            node *p, *q, *r;
            Treap::cut(T.root, p, q, a);
            Treap::cut(q, q, r, b-a+1);
            printf("%d\n", q->jcmn);
            Treap::merge(q, q, r);
            Treap::merge(T.root, p, q);
        } else if(op[1] == 'n') { // iNsert
            T.ins(a, b);
        } else if(op[1] == 'e') { // mErge
            --a;
            T.del(a); T.del(a); T.ins(a, b);
        }
    }
}

测试结果

std 2.5s, 我 3.6s

std 写的 sqrt(N) 分块,真是比我高到不知道哪里去了,就当这多出来的 1s