这部分给出一些数据结构的模版，和处理技巧

线段树

单点修改模版

UVA12299

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
const int inf = 0x3f3f3f3f;
const int maxnode = 1<<18;
const int maxn = 100000 + 10;
int A[maxn];
int n, q;

// == struct segment tree ==
class segTree {
public:
    int l, r;
    int dat;
};
segTree tree[maxnode];
#define l(x) tree[x].l
#define r(x) tree[x].r
#define dat(x) tree[x].dat
// == struct finished ==

void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    //debug(p), debug(l(p)),debug(r(p));
    //cout << endl;
    if(l == r) {
        dat(p) = A[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    dat(p) = min(dat(p << 1), dat(p << 1 | 1));
}

void change(int p, int x, int v) {
    // change A[x] = v, segment API is change(1, x, v)
    if(l(p) == r(p)) {
        dat(p) = v;
        return;
    }

    int mid = (l(p) + r(p)) >> 1;
    if(x <= mid) change(p << 1, x, v);
    else change(p << 1 | 1, x, v);
    dat(p) = min(dat(p << 1), dat(p << 1 | 1));
}

int ask(int p, int ql, int qr) {
    if(ql <= l(p) && r(p) <= qr) return dat(p);

    int mid = (l(p) + r(p)) >> 1;
    //debug(p);
    //debug(l(p)), debug(r(p));
    int val = inf;
    if(ql <= mid) val = min(val, ask(p << 1, ql, qr));
    if(qr > mid) val = min(val, ask(p << 1 | 1, ql, qr));
    return val;
}


const int maxl = 30 + 2;
void solve(const char* cmd) {
    int args[maxl], buf[maxl];
    int len = strlen(cmd);

    int k = 0;
    args[k] = 0;
    _for(i, 6, len) {
        if(isdigit(cmd[i])) args[k] = args[k] * 10 + cmd[i] - '0';
        else {
            k++;
            args[k] = 0;
        }
    }

    // debug args

    if(cmd[0] == 'q') {
        int ql = args[0];
        int qr = args[1];
        //debug(ql);
        //debug(qr);
        //cout << endl;
        printf("%d\n", ask(1, ql, qr));
    }
    else {
        // shift rmq
        _for(i, 0, k) buf[i] = A[args[i]];
        _for(i, 0, k) {
            int p = args[i];
            A[p] = buf[(i + 1) % k];
            int v = A[p];
            change(1, p, v);
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    cin >> n >> q;
    _rep(i, 1, n) scanf("%d", &A[i]);
    build(1, 1, n);

    while (q--) {
        char cmd[maxl];
        scanf("%s", cmd);
        //debug(cmd);
        solve(cmd);
    }
}

延迟标记模版

有一类延迟标记问题是描述区间中 minv,maxvminv, maxv 的问题
这类问题注意两点就可以

第一，某个区间的值修改成 tagtag，那么它的所有子区间，也就是
代表这个区间的点的所有子节点，maxv,minvmaxv, minv 都会同步变化
同时变成 tagtag

第二，这种问题常常用贡献值来计算
比如修改后的值 val≤minvval \leq minv，比区间最小值都小，
那么这个值无贡献，诸如此类

UVA1232

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

const int maxn = 100000 + 10;

class segTree {
public:
    int l, r;
    int maxv, minv, tag;
} tree[maxn << 2];

#define l(x) tree[x].l
#define r(x) tree[x].r
#define maxv(x) tree[x].maxv
#define minv(x) tree[x].minv
#define tag(x) tree[x].tag

void pushup(int p) {
    maxv(p) = max(maxv(p<<1), maxv(p<<1 | 1));
    minv(p) = min(minv(p<<1), minv(p<<1 | 1));
}

void pushdown(int p) {
    if(tag(p) && l(p) != r(p)) {
        tag(p<<1) = tag(p);
        maxv(p<<1) = minv(p<<1) = tag(p);

        tag(p<<1 | 1)= tag(p);
        maxv(p<<1 | 1) = minv(p<<1 | 1) = tag(p);

        tag(p) = 0;
    }
}

void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    tag(p) = 0;
    minv(p) = maxv(p) = 0;

    if(l == r) return;
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
}

int change(int p, int l, int r, int val) {
    if(l(p) == l && r(p) == r && minv(p) > val) return 0;
    if(l(p) == l && r(p) == r && maxv(p) <= val) {
        // update segment node
        if(maxv(p) < val) {
            tag(p) = val;
            maxv(p) = minv(p) = val;
        }
        //debug(r - l + 1);
        return r - l + 1;
    }

    pushdown(p);

    int ans = 0;
    int mid = (l(p) + r(p)) >> 1;
    if(r <= mid) ans = change(p << 1, l, r, val);
    else if(l > mid) ans = change(p << 1 | 1, l, r, val);
    else ans = change(p << 1, l, mid, val) + change(p << 1 | 1, mid + 1, r, val);

    pushup(p);
    return ans;
}


int n, li, ri, h;

void solve() {
    int ans = 0;
    build(1, 1, maxn);
    scanf("%d", &n);
    _for(i, 0, n) {
        scanf("%d%d%d", &li, &ri, &h);
        ans += change(1, li, ri - 1, h);
    }
    printf("%d\n", ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    while (true) {
        scanf("%d", &kase);
        if(kase == 0) break;

        while (kase--) {
            solve();
        }
    }

}

延迟标记思想的应用

UVA1455
UVA1455

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
171
172
173
174
175
176
177
178
179

const int maxn = 1000000 + 10;
const int maxm = maxn * 2;

int n, m;

struct _A {
    int x, y;
} A[maxn];

int pa[maxn], miny[maxn], maxy[maxn], cnt[maxn];
int top = 0;

int findset(int x) {
    return x == pa[x] ? x : pa[x] = findset(pa[x]);
}

void init() {
    _rep(i, 0, n) pa[i] = i;
    Set(miny, 0);
    Set(maxy, 0);
    Set(cnt, 0);
    top = 0;
}

// == seg Tree ==
class segTree {
public:
    int l, r;
    int num, city;
    int tag1, tag2;
} tree[maxm << 2];
#define l(x) tree[x].l
#define r(x) tree[x].r
#define num(x) tree[x].num
#define city(x) tree[x].city
#define tag1(x) tree[x].tag1
#define tag2(x) tree[x].tag2

void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    num(p) = city(p) = 0;
    tag1(p) = tag2(p) = 0;

    if(l == r) return;
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
}

void pushdown(int p) {
    if(tag1(p) && l(p) != r(p)) {
        // deal with tag1, num
        tag1(p<<1) += tag1(p);
        num(p<<1) += (r(p<<1) - l(p<<1) + 1) * tag1(p);

        tag1(p<<1|1) += tag1(p);
        num(p<<1|1) += (r(p<<1|1) - l(p<<1|1) + 1) * tag1(p);

        tag1(p) = 0;
    }

    if(tag2(p) && l(p) != r(p)) {
        // deal with tag2, city
        tag2(p<<1) += tag2(p);
        city(p<<1) += (r(p<<1) - l(p<<1) + 1) * tag2(p);

        tag2(p<<1|1) += tag2(p);
        city(p<<1|1) += (r(p<<1|1) - l(p<<1|1) + 1) * tag2(p);

        tag2(p) = 0;
    }
}

void pushup(int p) {
    num(p) = num(p<<1) + num(p<<1|1);
    city(p) = city(p<<1) + city(p<<1|1);
}

void change(int p, int l, int r, int a, int b) {
    if(l(p) == l && r(p) == r) {
        tag1(p) += a;
        num(p) += (r(p) - l(p) + 1) * a;

        tag2(p) += b;
        city(p) += (r(p) - l(p) + 1) * b;

        return;
    }

    pushdown(p);

    int mid = (l(p) + r(p)) >> 1;
    if(r <= mid) change(p<<1, l, r, a, b);
    else if(l > mid) change(p<<1|1, l, r, a, b);
    else {
        change(p<<1, l, mid, a, b);
        change(p<<1|1, mid + 1, r, a, b);
    }

    pushup(p);
}

int query(int p, int C) {
    if(l(p) == r(p)) return p;

    pushdown(p);
    int mid = (l(p) + r(p)) >> 1;
    if(C <= mid) return query(p<<1, C);
    else return query(p<<1|1, C);
}
// == seg Tree finished ==

void inp() {
    scanf("%d", &n);
    init();

    _for(i, 0, n) {
        scanf("%d%d", &A[i].x, &A[i].y);
        A[i].y <<= 1;

        top = max(top, A[i].y);
        maxy[i] = miny[i] = A[i].y;
        cnt[i] = 1;
    }

    build(1, 0, top);
    _for(i, 0, n) change(1, A[i].y, A[i].y, 1, 1);
}

void solve() {
    scanf("%d", &m);
    while (m--) {
        char cmd[10];
        scanf("%s", cmd);

        if(cmd[0] == 'r') {
            int a, b;
            scanf("%d%d", &a, &b);

            a = findset(a);
            b = findset(b);

            if(a == b) continue;

            change(1, miny[a], maxy[a], -1, -cnt[a]);
            change(1, miny[b], maxy[b], -1, -cnt[b]);

            pa[b] = a;
            cnt[a] += cnt[b];
            miny[a] = min(miny[a], miny[b]);
            maxy[a] = max(maxy[a], maxy[b]);

            change(1, miny[a], maxy[a], 1, cnt[a]);
        }
        else {
            double c;
            scanf("%lf", &c);
            int C = c * 2 + 0.5;

            if(C > top) puts("0 0");
            else {
                int ans = query(1, C);
                printf("%d %d\n", num(ans), city(ans));
            }
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    scanf("%d", &kase);

    while (kase--) {
        inp();
        solve();
    }
}

扫描线算法

HDU4052
HDU4052

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

const int maxn = 100000 + 10;
const int inf = 0x3f3f3f3f;

class Node {
public:
    int x;
    int y1, y2;
    int k;

    Node() {}
    Node(int x, int y1, int y2, int k) : x(x), y1(y1), y2(y2), k(k) {}

    bool operator< (const Node& rhs) const {
        return x < rhs.x;
    }
} node[maxn];

struct Rec {
    int x1, y1, x2, y2;
    void read() {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        if(x1 > x2) swap(x1, x2);
        if(y1 > y2) swap(y1, y2);
    }
} rec[maxn];

map<int, int> ny;
int raw[maxn];

void init() {
    ny.clear();
    Set(raw, 0);
}

// == seg Tree ==
class segTree {
public:
    int l, r, cover;
    int len;
} tree[maxn << 2];

#define l(x) tree[x].l
#define r(x) tree[x].r
#define cover(x) tree[x].cover
#define len(x) tree[x].len

void build(int p, int l, int r) {
    cover(p) = len(p) = 0;
    l(p) = l, r(p) = r;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
}

inline void pushup(int p) {
    if(cover(p)) len(p) = (raw[r(p)] - raw[l(p) - 1]);
    else if (l(p) == r(p)) len(p) = 0;
    else len(p) = len(p<<1) + len(p<<1|1);
}

void change(int p, int l, int r, int d) {
    if(l <= l(p) && r(p) <= r) {
        cover(p) += d;
        pushup(p);
        return;
    }

    int mid = (l(p) + r(p)) >> 1;
    //debug(l(1)), debug(r(1));
    //debug(mid);
    if(l <= mid) change(p<<1, l, r, d);
    if(r > mid) change(p<<1|1, l, r, d);

    pushup(p);
}
// == seg Tree finished ==


// == solve the problem ==
int w, h, m;
int N, n;

void discrete(int _n) {
    sort(raw + 1, raw + 1 + _n);
    sort(node + 1, node + 1 + _n);
    N = unique(raw + 1, raw + 1 + _n) - raw - 1;

    _rep(i, 1, N) ny[raw[i]] = i;
}

ll solve(int _n) {
    if(m > h) return 0;
    ny.clear();

    int L, R;
    _rep(i, 1, _n) {
        int k = i << 1;
        L = raw[k - 1] = rec[i].y1;
        R = raw[k] = min(h, rec[i].y2 + m - 1) + 1;

        node[k - 1] = Node(rec[i].x1, L, R, 1);
        node[k] = Node(rec[i].x2 + 1, L, R, -1);
    }
    _n <<= 1;
    L = 1, R = 1 + min(h, m - 1);

    node[_n + 1] = Node(1, L, R, 1);
    raw[_n + 1] = L;
    node[_n + 2] = Node(1 + w, L, R, -1);
    raw[_n + 2] = R;

    _n += 2;

    discrete(_n);

    ll ans = 0;
    // == main solve() ==
    if(N) build(1, 1, N);
    _rep(i, 1, _n - 1) {
        int L = ny[node[i].y1] + 1, R = ny[node[i].y2];
        assert(L != 0 && R != 0);

        //debug(node[i].y1), debug(node[i].y2), debug(node[i].x), debug(node[i].k);
        //cout << endl;

        if(L <= R) change(1, L, R, node[i].k);
        ans += (ll) len(1) * (node[i + 1].x - node[i].x);
    }

    ans = (ll) w * h - ans;
    return ans;
    // == finished ==
}
// == solve finsihed ==


int main() {
    freopen("input.txt", "r", stdin);
    while (~scanf("%d%d%d%d", &w, &h, &n, &m)) {
        init();
        int n2 = n;

        _rep(i, 1, n) {
            rec[i].read();
        }

        ll ans = solve(n);

        _rep(i, 1, n2) {
            swap(rec[i].y1, rec[i].x1);
            swap(rec[i].y2, rec[i].x2);
        }
        swap(w, h);

        ans += solve(n2);

        if(m == 1) ans /= 2;
        printf("%lld\n", ans);

    }
}

动态开点与线段树合并

NEERC2011F
flights01
flights02
flights03
flights04

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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312

const int maxn = 50000 + 10;
const int maxm = 8000000;
const double eps = 1e-10;
int n, m;
int mx = 0;


class Parabola {
public:
    int x, y, p;
    double a, b, c;
    inline double cal(double x) {
        return a*x*x + b*x + c;
    }

    void read(int& mx) {
        scanf("%d%d%d", &p, &x, &y);

        a = (double)y * 1.0 / (1ll * (x - p) * (p - x) * 1.0);
        b = -2 * a * x;
        c = -a*p*p - b*p;

        mx = max(mx, 2*x-p);
    }
} para[maxn];

// == seg Tree nested seg Tree ==
int tot = 0;
int rt[maxn << 2];
double X[maxn << 2], _X[maxn << 2];

void init() {
    tot = 0;
    Set(rt, 0);
    Set(X, 0);
    Set(_X, 0);
}

class segTree {
public:
    int l, r;
} tree[maxn << 2];
#define l(x) tree[x].l
#define r(x) tree[x].r

class nestTree {
public:
    int ls, rs;
    double maxh;
} ntree[maxm];
#define ls(x) ntree[x].ls
#define rs(x) ntree[x].rs
#define maxh(x) ntree[x].maxh

void spread1(int& o, int l, int r, int x, int y) {
    if(!o) o = ++tot;
    maxh(o) = y;

    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) spread1(ls(o), l, mid, x, y);
    else spread1(rs(o), mid + 1, r, x, y);
}

int merge1(int p, int q, int l, int r) {
    if(!p || !q) return p + q;
    if(l == r) return maxh(p) > maxh(q) ? p : q;

    int u = ++tot;
    int mid = (l + r) >> 1;
    ls(u) = merge1(ls(p), ls(q), l, mid);
    rs(u) = merge1(rs(p), rs(q), mid + 1, r);
    maxh(u) = max(maxh(ls(u)), maxh(rs(u)));
    return u;
}

// usage, build1(1, 1, n)
void build1(int p, int l, int r) {
    // leaf node means lth parabola
    // spread 2D-segTree
    l(p) = l, r(p) = r;
    if(l == r) {
        spread1(rt[p], 0, mx, para[l].x, para[l].y);
        return;
    }
    int mid = (l + r) >> 1;
    build1(p<<1, l, mid);
    build1(p<<1|1, mid + 1, r);
    rt[p] = merge1(rt[p<<1], rt[p<<1|1], 0, mx);
}

// query 2D, usage, query2(rt[p], 0, mx, x1, x2)
// query interval [x1, x2]
// query2(p), query2(ls(p), ..), query2(rs(p), ...)
double query2(int p, int l, int r, int ql, int qr) {
    if(!p || ql > r || qr < l) return 0;
    if(ql <= l && r <= qr) return maxh(p);
    int mid = (l + r) >> 1;
    return max(query2(ls(p), l, mid, ql, qr), query2(rs(p), mid + 1, r, ql, qr));
}

// usage, query1(1, t1, t2, x1, x2)
double query1(int p, int tl, int tr, int xl, int xr) {
    if(r(p) < tl || l(p) > tr) return 0;
    if(tl <= l(p) && r(p) <= tr) return query2(rt[p], 0, mx, xl, xr);

    return max(query1(p<<1, tl, tr, xl, xr), query1(p<<1|1, tl, tr, xl, xr));
}
// == seg Tree nested finished ==

// == outline seg Tree, build by parabola id, solve interval endpoint ==
struct Line {
    double xl, xr;
    int id;

    Line(double _xl = 0.0, double _xr = 0.0, int _id = 0) : xl(_xl), xr(_xr), id(_id) {}

    bool operator< (const Line& rhs) const {
        return xr < rhs.xr;
    }
};

class outlineTree {
public:
    int _l, _r;
    vector<Line> lines;
} lineTree[maxn << 2];
#define _l(x) lineTree[x]._l
#define _r(x) lineTree[x]._r
#define lines(x) lineTree[x].lines

inline double intersection(int i, int j, double l, double r) {
    // find intersction of two parabola in seg [l, r]
    const Parabola& u = para[i];
    const Parabola& v = para[j];

    double A = u.a - v.a;
    double B = u.b - v.b;
    double C = u.c - v.c;

    if(fabs(A) < eps) {
        // A = 0, find solution
        // B = 0, no solution, return xr
        if(fabs(B) < eps) return r;
        double ans = -C / B;
        if(l + eps < ans && ans < r - eps) return ans;
        return r;
    }

    double D = B*B - 4*A*C;
    if(D < -eps) return r;

    D = sqrt(D);
    double ans = r;

    double x1 = (-B - D) / A / 2;
    if(l + eps < x1 && x1 < r - eps) ans = x1;
    double x2 = (-B + D) / A / 2;
    if(l + eps < x2 && x2 < r - eps) ans = min(ans, x2);

    return ans;
}

vector<Line> tmp;
inline void combine(vector<Line>& A, vector<Line>& B, vector<Line>& C) {
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    if(A.size() == 0) {
        C = B;
        return;
    }
    if(B.size() == 0) {
        C = A;
        return;
    }

    // solve all (x, 0) to a new array _X, then unique to X
    tmp.clear();
    int tot = 0;
    _for(i, 0, A.size()) {
        _X[++tot] = A[i].xl;
        _X[++tot] = A[i].xr;
    }
    _for(i, 0, B.size()) {
        _X[++tot] = B[i].xl;
        _X[++tot] = B[i].xr;
    }
    sort(_X + 1, _X + 1 + tot);

    int sz = 0;
    for(int i = 1; i <= tot; ) {
        int j = i;
        for(; j < tot && fabs(_X[j + 1] - _X[j]) < eps; j++);
        X[++sz] = _X[j];
        i = j + 1;
    }

    // X[1,..,sz] is the sub segment
    // {l, r, paraID} construct outline
    int p1 = 0, p2 = 0;
    _for(i, 1, sz) {
        double l = X[i], r = X[i + 1];
        while (p1 < A.size() && A[p1].xr + eps < r) p1++;
        while (p2 < B.size() && B[p2].xr + eps < r) p2++;

        if(((p1 == A.size()) || (A[p1].xl > l + eps)) && ((p2 == B.size()) || (B[p2].xl > l + eps))) continue;
        if((p1 == A.size()) || (A[p1].xl > l + eps)) {
            tmp.push_back(Line(l, r, B[p2].id));
            continue;
        }
        if((p2 == B.size()) || (B[p2].xl > l + eps)) {
            tmp.push_back(Line(l, r, A[p1].id));
            continue;
        }

        // intersction [l, x1, x2, ..., r], get point
        while (l + eps < r) {
            double x = intersection(A[p1].id, B[p2].id, l, r);
            double phi = (l + x) / 2;

            if(para[A[p1].id].cal(phi) > para[B[p2].id].cal(phi)) {
                if(para[A[p1].id].cal(phi) >= 0) tmp.push_back(Line(l, x, A[p1].id));
            }
            else {
                if(para[B[p2].id].cal(phi) >= 0) tmp.push_back(Line(l, x, B[p2].id));
            }

            l = x;
        }
    }

    C.clear();
    for(int i = 0; i < tmp.size(); ) {
        int j = i;
        for(; j < tmp.size()-1 && tmp[j + 1].id == tmp[i].id; j++);
        C.push_back(Line(tmp[i].xl, tmp[j].xr, tmp[i].id));
        i = j + 1;
    }
}

void build2(int p, int l, int r) {
    _l(p) = l, _r(p) = r;
    if(l == r) {
        const Parabola& cur = para[l];
        lines(p).push_back(Line(cur.p, 2*cur.x-cur.p, l));
        return;
    }

    int mid = (l + r) >> 1;
    build2(p<<1, l, mid);
    build2(p<<1|1, mid + 1, r);
    combine(lines(p<<1), lines(p<<1|1), lines(p));
}
// == outline seg Tree finished ==

// == solve the problem ==
inline double work(int p, double x) {
    int l = 0, r = lines(p).size()-1;
    int ans = r;

    while (l <= r) {
        int mid = (l + r) >> 1;
        if(lines(p)[mid].xr >= x + eps) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return para[lines(p)[ans].id].cal(x);
}

void solve(int p, int tl, int tr, int x1, int x2, double& ans) {
    if(tl > _r(p) || tr < _l(p)) return;
    if(tl <= _l(p) && _r(p) <= tr) {
        ans = max(ans, work(p, x1));
        ans = max(ans, work(p, x2));
        return;
    }

    solve(p<<1, tl, tr, x1, x2, ans);
    solve(p<<1|1, tl, tr, x1, x2, ans);
}
// == solve finished ==

int main() {
    freopen("flights.in", "r", stdin);
    freopen("flights.out", "w", stdout);

    scanf("%d", &n);
    _rep(i, 1, n) {
        para[i].read(mx);
    }

    build1(1, 1, n);
    build2(1, 1, n);

    scanf("%d", &m);
    _rep(i, 1, m) {
        int t1, t2, x1, x2;
        scanf("%d%d%d%d", &t1, &t2, &x1, &x2);
        double ans = 0.0;
        ans = query1(1, t1, t2, x1, x2);
        solve(1, t1, t2, x1, x2, ans);
        cout << ans << endl;
    }

    // debug(para[1].cal(11));
    // debug(mx);

}

并查集处理几何问题的思路

HDU4056

树状数组解决数位统计问题

HDU3670
HDU3670

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

const int maxn = 100000 + 5;
const int mod = (int)(1<<16);
const int maxm = mod + 10;

int n, m;
int cas = 0;

class Fwick {
public:
    int C[16][maxm];
    void init() {
        Set(C, 0);
    }

    void update(int k, int x, int val) {
        x++;
        while (x < maxm) {
            C[k][x] += val;
            x += lowbit(x);
        }
    }

    int sum(int k, int x) {
        x++;
        int ret = 0;
        while (x) {
            ret += C[k][x];
            x -= lowbit(x);
        }
        return ret;
    }
} fwick;

void solve() {
    ll add = 0, ans = 0;
    char cmd[10];
    while (scanf("%s", cmd) == 1) {
        if(cmd[0] == 'E') break;

        if(cmd[0] == 'C') {
            int x;
            scanf("%d", &x);
            add += x;
            if(add >= mod) add %= mod;
        }
        else {
            int t;
            scanf("%d", &t);
            int tail = add % (1<<t);

            if(add & (1<<t)) {
                ans += fwick.sum(t, (1<<t) - 1 - tail);
                ans += fwick.sum(t, (1<<(t+1)) - 1) - fwick.sum(t, (1<<(t+1)) - 1 - tail);
            }
            else {
                ans += fwick.sum(t, (1<<(t+1)) - 1 - tail) - fwick.sum(t, (1<<t) - 1 - tail);
            }
        }
    }
    printf("Case %d: %lld\n", ++cas, ans);
}

int main() {
    freopen("input.txt", "r", stdin);

    char cmd[10];
    while (scanf("%d", &n) == 1) {
        if(n == -1) break;
        fwick.init();

        _for(i, 0, n) {
            int x;
            scanf("%d", &x);
            _for(k, 0, 16) fwick.update(k, (x % (1<<(k+1))), 1);
        }

        solve();
    }

}