Basic

One Node Update Interval Query

One Node Plus & Interval Query

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
#include <iostream>
#define ll long long
#define mid (l + r) >> 1
#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r
const int maxn = 100010;
int n, m;
ll sum[maxn << 2];
using namespace std;

void pushup(int rt) {
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void build(int rt, int l, int r) {
    if (l == r) {
        cin >> sum[rt];
        return;
    }
    int m = mid;
    build(lson);
    build(rson);
    pushup(rt);
}

void update(int x, int add, int rt, int l, int r) {
    if (l == r) {
        sum[rt] += add;
        return;
    }
    int m = mid;
    if (x <= m) update(x, add, lson);
    else
        update(x, add, rson);
    pushup(rt);
}

ll query(int x, int y, int rt, int l, int r) {
    if (x <= l && r <= y) return sum[rt];
    int m = mid;
    ll ans = 0;
    if (x <= m) ans += query(x, y, lson);
    if (y > m) ans += query(x, y, rson);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    build(1, 1, n);
    int k;
    while (m--) {
        int order, x, y;
        cin >> order >> x >> y;
        if (order == 1) {
            update(x, y, 1, 1, n);
        } else {
            cout << query(x, y, 1, 1, n) << "\n";
        }
    }
    return 0;
}

单点修改，区间求积

Luogu P4588

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
#include <iostream>
#define ll long long
#define mid (l + r) >> 1
#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r
const int maxn = 100010;
int t, q, m;
long long mod;
ll mul[maxn << 2];
using namespace std;

void pushup(int rt) {
    mul[rt] = (mul[rt << 1] * mul[rt << 1 | 1]) % mod;
}

void build(int rt, int l, int r) {
    if (l == r) {
        mul[rt] = 1;
        return;
    }
    int m = mid;
    build(lson);
    build(rson);
    pushup(rt);
}

void update(int p, int num, int rt, int l, int r) {
    if (l == r) {
        mul[rt] = num;
        return;
    }
    int m = mid;
    if (p <= m) update(p, num, lson);
    else
        update(p, num, rson);
    pushup(rt);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> q >> mod;
        build(1, 1, q);
        for (int time_tag = 1; time_tag <= q; time_tag++) {
            int op, now;
            cin >> op >> now;
            if (op == 1) {
                update(time_tag, now, 1, 1, q);
                cout << mul[1] % mod << endl;
            } else {
                update(now, 1, 1, 1, q);
                cout << mul[1] % mod << endl;
            }
        }
    }
    return 0;
}

Interval Update & Query

Interval Plus & Query

Luogu P3372

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
#include <iostream>
#define ll long long
#define mid (l + r) >> 1
#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r
const int maxn = 100010;
int n, m;
ll sum[maxn << 2];
ll tag[maxn << 2];
using namespace std;

void pushup(int rt) {
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void pushdown(int rt, int l, int r) {
    int l_node = rt << 1,r_node = rt << 1 | 1;
    if (tag[rt]) {
        tag[l_node] += tag[rt];
        tag[r_node] += tag[rt];
        int m = mid;
        sum[l_node] += (m - l + 1) * tag[rt];
        sum[r_node] += (r - m) * tag[rt];
        tag[rt] = 0;
    }
}

void build(int rt, int l, int r) {
    if (l == r) {
        cin >> sum[rt];
        return;
    }
    int m = mid;
    build(lson);
    build(rson);
    pushup(rt);
}

void update(int x, int y, int add, int rt, int l, int r) {
    if (x <= l && r <= y) {
        sum[rt] += (r - l + 1) * add;
        tag[rt] += add;
        return;
    }
    pushdown(rt, l, r);
    int m = mid;
    if (x <= m) update(x, y, add, lson);
    if (y > m) update(x, y, add, rson);
    pushup(rt);
}

ll query(int x, int y, int rt, int l, int r) {
    if (x <= l && r <= y) return sum[rt];
    pushdown(rt, l, r);
    int m = mid;
    ll ans = 0;
    if (x <= m) ans += query(x, y, lson);
    if (y > m) ans += query(x, y, rson);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    build(1, 1, n);
    int add_num;
    while (m--) {
        int order, x, y;
        cin >> order >> x >> y;
        if (order == 1) {
            cin >> add_num;
            update(x, y, add_num, 1, 1, n);
        } else {
            cout << query(x, y, 1, 1, n) << "\n";
        }
    }
    return 0;
}

Interval Multiply & Query

Luogu P3373

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
#include <iostream>
#define ll long long
#define mid (l + r) >> 1
#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r
const int maxn = 100010;
int n, m, p;
ll sum[maxn << 2];
struct node {
    ll mul, add;
} tag[maxn << 2];
;
using namespace std;

void pushup(int rt) {
    sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % p;
}

void pushdown(int rt, int l, int r) {
    int l_node = rt << 1, r_node = rt << 1 | 1, m = mid;
    sum[l_node] = (sum[l_node] * tag[rt].mul % p + tag[rt].add * (m - l + 1) % p) % p;
    tag[l_node].mul = (tag[l_node].mul * tag[rt].mul) % p;
    tag[l_node].add = (tag[l_node].add * tag[rt].mul + tag[rt].add) % p;

    sum[r_node] = (sum[r_node] * tag[rt].mul % p + tag[rt].add * (r - (m + 1) + 1) % p) % p;
    tag[r_node].mul = (tag[r_node].mul * tag[rt].mul) % p;
    tag[r_node].add = (tag[r_node].add * tag[rt].mul + tag[rt].add) % p;

    tag[rt].add = 0;
    tag[rt].mul = 1;
}

void build(int rt, int l, int r) {
    if (l == r) {
        cin >> sum[rt];
        return;
    }
    int m = mid;
    build(lson);
    build(rson);
    pushup(rt);
}

void update(char op, int x, int y, int num, int rt, int l, int r) {
    if (x <= l && r <= y) {
        if (op == 'A') {
            sum[rt] = (sum[rt] + (ll) (r - l + 1) * num % p) % p;
            tag[rt].add = (tag[rt].add + num) % p;
        } else {
            sum[rt] = (sum[rt] * num) % p;
            tag[rt].mul = (tag[rt].mul * num) % p;
            tag[rt].add = (tag[rt].add * num) % p;
        }
        return;
    }
    pushdown(rt, l, r);
    int m = mid;
    if (x <= m) update(op, x, y, num, lson);
    if (y > m) update(op, x, y, num, rson);
    pushup(rt);
}

ll query(int x, int y, int rt, int l, int r) {
    if (x <= l && r <= y) return sum[rt];
    pushdown(rt, l, r);
    int m = mid;
    ll ans = 0;
    if (x <= m) ans += query(x, y, lson);
    if (y > m) ans += query(x, y, rson);
    return ans;
}

void init(int n) {
    for (int i = 1; i <= 4 * n; i++) {
        tag[i].add = 0;
        tag[i].mul = 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> p;
    init(n);
    build(1, 1, n);
    int num;
    while (m--) {
        int order, x, y;
        cin >> order >> x >> y;
        if (order == 1) {
            cin >> num;
            update('M', x, y, num, 1, 1, n);
        } else if (order == 2) {
            cin >> num;
            update('A', x, y, num, 1, 1, n);
        } else {
            cout << query(x, y, 1, 1, n) % p << "\n";
        }
    }
    return 0;
}

Weighted

Luogu P3839

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
#include <algorithm>
#include <iostream>
#include <map>
#define ll long long
#define mid (l + r) >> 1
#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r
#define fast std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn = 1000010;
int n, m, cnt = 0;
ll seg_tree[maxn << 2], x[maxn], bucket[maxn], a[maxn];
int opt[maxn];
map<int, int> mp;

void pushup(int rt){
    seg_tree[rt] = seg_tree[rt << 1] + seg_tree[rt << 1 | 1];
}

void update(int x, int val, int rt, int l, int r) {
    if (l == r) {
        seg_tree[rt] += val;
        return;
    }
    int m = mid;
    if (x <= m) update(x, val, lson);
    else update(x, val, rson);
    pushup(rt);
}

ll query_x_rank(int x, int rt, int l, int r) {//get the rank of X(num)
    if (l == r) return 1;
    int m = mid;
    ll ans = 0;
    if (x <= m) ans += query_x_rank(x, lson);
    else ans += query_x_rank(x, rson) + seg_tree[rt << 1]; //IMP
    return ans;
}

ll query_rank_xth(int x, int rt, int l, int r) {
    if (l == r) return l;
    int m = mid, l_node = rt << 1, r_node = rt << 1 | 1;
    return (x <= seg_tree[l_node]) ? query_rank_xth(x , lson):query_rank_xth(x-seg_tree[l_node], rson) ;
}

void discrete() {
    sort(a + 1, a + 1 + cnt);
    int len = unique(a + 1, a + 1 + cnt) - a - 1;
    cnt = len;
    for (int i = 1; i <= cnt; i++)
        mp[a[i]] = i;
}

int main() {
    fast
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> opt[i] >> x[i];
        if (opt[i] != 2 && opt[i] != 4) a[++cnt] = x[i];
    }
    discrete();
    for (int i = 1; i <= n; i++) {
        int now=mp[x[i]];
        switch (opt[i]) {
            case 1:
                bucket[now]++;
                update(now, 1, 1, 1, cnt);
                break;
            case 2:
                bucket[now]--;
                update(now, -1, 1, 1, cnt);
                break;
            case 3:
                cout << query_x_rank(now, 1, 1, cnt)  << "\n";
                break;
            case 4:
                cout << a[query_rank_xth(x[i], 1, 1, cnt)] << "\n";
                break;
            case 5:
                cout << a[query_rank_xth(query_x_rank(now , 1, 1, cnt) - 1, 1, 1,  cnt)] << "\n";
                break;
            case 6:
                cout << a[query_rank_xth(query_x_rank(now,1,1,cnt)+bucket[now],1,1,cnt)] << "\n";
                break;
        }
    }
}

Persistent

visit past version

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
#include <algorithm>
#include <iostream>
#define ll long long
#define mid (l + r) >> 1
#define fast std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn = 1000010;
int n, m, cnt_tree = 0;
ll x[maxn], root[maxn], a[maxn];

struct node {
    int l,r,val;
}tree[maxn << 5];

int build(int l,int r){
    int rt = ++cnt_tree;
    if (l==r) tree[rt].val = a[l];
    if (l<r){
        int m = mid;
        tree[rt].l=build(l,m);
        tree[rt].r=build(m+1,r);
    }
    return rt;
}

int update(int pre, int x,int val,  int l, int r) {
    int rt = ++cnt_tree;     //dynamic new node
    tree[rt] = tree[pre];
    if (l==r && l==x){
        tree[rt].val = val;
        return rt;
    }
    int m = mid;
    if (l<r){
        if (x <= m)
            tree[rt].l = update(tree[pre].l, x,val, l, m);
        else
            tree[rt].r = update(tree[pre].r, x, val,m + 1, r);
    }
    return rt;
}

ll query(int x,int rt,int l, int r) {
    if (l == r && l == x) return tree[rt].val;
    int m = mid;
    return (x <= m) ? query(x ,tree[rt].l,l, m) : query(x ,tree[rt].r, m+1, r);
}

int main() {
    fast
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    root[0] = build(1, n);
    for (int i = 1; i <= m; i++) {
        int ver, opt, loc, val;
        cin >> ver >> opt >>loc;
        if (opt == 1) {
            cin >> val;
            root[i] = update(root[ver], loc, val, 1, n);
        } else {
            root[i] = root[ver];
            cout << query(loc, root[ver],1, n) << "\n";
        }
    }
    return 0;
}

Interval kth min

Luogu P3834

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
#include <algorithm>
#include <iostream>
#define ll long long
#define mid (l + r) >> 1
#define fast std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn = 200010;
int n, m, cnt = 0,  cnt_tree = 0;
ll x[maxn], root[maxn], a[maxn];

struct node {
    int l,r,val;
}tree[maxn << 5];

int update(int pre, int x,  int l, int r) { //build a new segment tree
    int rt = ++cnt_tree;     //dynamic new node
    tree[rt] = tree[pre];
    tree[rt].val++;
    int m = mid;
    if (l<r){
        if (x <= m)
            tree[rt].l = update(tree[pre].l, x, l, m);
        else
            tree[rt].r = update(tree[pre].r, x, m + 1, r);
    }
    return rt;
}

ll query(int u, int v,int x, int l, int r) {     //find the xth min in [u,v]
    if (l == r) return l;             //find the leaf node and ans is a[l];
    int left_nodes = tree[tree[v].l].val-tree[tree[u].l].val;
    int m = mid;
    return (x > left_nodes) ? query(tree[u].r, tree[v].r,x - left_nodes, m + 1, r) : query(tree[u].l, tree[v].l,x, l, m);
}

void discrete() {
    sort(a + 1, a + 1 + n);
    cnt = unique(a + 1, a + 1 + n) - a - 1;
}

int main() {
    fast
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        a[i] = x[i];
    }
    discrete();
    for (int i=1;i<=n;i++) {
        int pos = lower_bound(a+1,a+1+cnt,x[i])-a; // find x[i] in a
        root[i] = update(root[i-1],pos,1,cnt); //build ith segment tree
    }
    while (m--){
        int left, right, k;
        cin >> left >> right >> k;
        int index = query(root[left-1],root[right],k,1,cnt); //yth seg_tree - (x-1)th seg_tree is [x,y]seg_tree
        cout << a[index] << "\n";
    }
    return 0;
}