sinEagle

bottlecode

0%

SDTBU-ACM集训队暑假训练（线段树 树状数组专题）

发表于
本文字数： 9.9k 阅读时长 ≈ 9 分钟

A题

单点修改， 询问区间和

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
//2021-08-08 10:58:58
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1e5+10;
int T, n;
int sum[N*4];

void change(int k1) {
    sum[k1] = sum[k1*2] + sum[k1*2+1];
}

void buildtree(int k1, int l, int r) {
    if(l == r) {
        scanf("%d", &sum[k1]);
        return;
    }
    int mid = l+r >> 1;
    buildtree(k1*2, l, mid);
    buildtree(k1*2+1, mid+1, r);
    change(k1);
}

void update(int k1, int l, int r, int p, int q) {
    if(l == r) {
        sum[k1] += q;
        return;
    }
    int mid = l+r >>1;
    if(p <= mid) update(k1*2, l, mid, p, q);
    else update(k1*2+1, mid+1, r, p, q);
    change(k1);
}

int Find(int k1, int l, int r, int L, int R) {
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) return sum[k1];
    int mid = l+r >> 1;
    return Find(k1*2, l, mid, L, R) + Find(k1*2+1, mid+1, r, L, R);
}

int main() {
    cin >> T;
    int xx = 0;
    while(T--) {
        printf("Case %d:\n", ++xx);
        scanf("%d", &n);
        buildtree(1, 1, n);
        string s;
        while(1) {
            cin >> s;
            if(s == "End") break;
            if(s == "Add") {
                int x, y;
                scanf("%d%d", &x, &y);
                update(1, 1, n, x, y);
            } else if(s == "Query") {
                int x, y;
                scanf("%d%d", &x, &y);
                printf("%d\n", Find(1, 1, n, x, y));
            } else if(s == "Sub") {
                int x, y;
                scanf("%d%d", &x, &y);
                update(1, 1, n, x, -y);
            }
        }

    }

    return 0;
}

B题

题意：有n头牛，编号为1~n，它们并没有按照编号的顺序排好队列,只知道每一个牛前面有多少只牛的编号比它大。问你能不能判断出所有牛的编号。

关键：每次最后一只牛的编号是可以确定的，即为pre[i]+1，将其编号从所有牛中删除，则倒数第二只牛的编号又可以确定为pre[i]+1，依此类推。

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
//2021-08-02 11:21:34
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 5e4+10;

int T, n;
int a[N], b[N];
int size[N*4];
void buildtree(int k, int l, int r) {
    size[k] = r-l+1;
    if(l == r) return;
    int mid = l + r >> 1;
    buildtree(k*2, l, mid);
    buildtree(k*2+1, mid+1, r);
}

int Find(int k, int l, int r, int val) {
    size[k]--;
    if(l == r) return l;
    int mid = l+r >> 1;
    if(val <= size[k*2]) {
        Find(k*2, l, mid, val);
    } else {
        Find(k*2+1, mid+1, r, val-size[k*2]);
    }
}

int main() {
    while(scanf("%d", &n) != EOF) {
        memset(size, 0, sizeof(size));
        for(int i = 2; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        buildtree(1, 1, n);
        for(int i = n; i >= 1; i--) {
            b[i] = Find(1, 1, n, a[i]+1);
        }
        for(int i = 1; i <= n; i++) {
            printf("%d\n", b[i]);
        }
    }

    return 0;
}

D题

区间更新

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
//2021-08-03 09:35:42
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 2e5+10;

int T;
int n, q;
int A[N*4], siz[N*4], B[N*4];

void change(int k1) {
    A[k1] = A[k1*2] + A[k1*2+1];
}
void buildtree(int k1, int l, int r) {
    siz[k1] = r-l+1;
    if(l == r) {
        A[k1] = 1;
        return;
    }
    int mid = l+r >> 1;
    buildtree(k1*2, l, mid);
    buildtree(k1*2+1, mid+1, r);
    change(k1);
}

void update(int k1, int val) {
    B[k1] = val;
    A[k1] = val*siz[k1];
}

void pushdown(int k1) {
    if(B[k1]) {
        update(k1*2, B[k1]);
        update(k1*2+1, B[k1]);
        B[k1] = 0;
    }
}
void update(int k1, int L, int R, int l, int r, int val) {
    if(L > r || R < l) return;
    if(L >= l && R <= r) {
        update(k1, val);
        return;
    }
    int mid = L+R >> 1;
    pushdown(k1);
    update(k1*2, L, mid, l, r, val);
    update(k1*2+1, mid+1, R, l, r, val);
    change(k1);
}

int Find(int k1, int L, int R, int l, int r) {
    if(L > r || R < l) return 0;
    if(L >= l && R <= r) return A[k1];
    int mid = L+R >> 1;
    pushdown(k1);
    return Find(k1*2, L, mid, l, r) + Find(k1*2+1, mid+1, R, l, r);

}
//
//void printree(int k1, int l, int r) {
//    if(l == r) {
//        //printf("B[%d] = %d**%d->%d\n", l, A[k1], k1, l);
//        return;
//    }
//    int mid = l+r >> 1;
//    printree(k1*2, l, mid);
//    printree(k1*2+1, mid+1, r);
//}

int main() {
    scanf("%d", &T);
    int tt = 0;
    while(T--) {
        memset(B, 0, sizeof(B));
        memset(A, 0, sizeof(A));
        memset(siz, 0, sizeof(siz));
        tt++;
        scanf("%d%d", &n, &q);
        buildtree(1, 1, n);
        int x, y, z;
        for(int i = 1; i <= q; i++) {
            scanf("%d%d%d", &x, &y, &z);
            update(1, 1, n, x, y, z);
            //cout << Find(1, 1, n, 1, n) << "***" << endl;
        }
        //printree(1, 1, n);
        printf("Case %d: The total value of the hook is %d.\n", tt, Find(1, 1, n, 1, n));
    }

    return 0;
}

E题

单点修改，区间最大值

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
//2021-08-02 16:35:21
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 2e5+10;

int n, m;
int A[N*4];

void change(int k) {
    A[k] = max(A[k*2], A[k*2+1]);
}

void buildtree(int k, int l, int r) {
    if(l == r) {
        scanf("%d", &A[k]);
        return;
    }
    int mid = l+r >> 1;
    buildtree(k*2, l, mid);
    buildtree(k*2+1, mid+1, r);
    change(k);
}

void update(int k1, int l, int r, int p, int q) {
    if(l == r) {
        A[k1] = q;
        //printf("##### B[%d] = %d\n", l, q);
        return;
    }
    int mid = l+r >> 1;
    if(p <= mid) {
        update(k1*2, l, mid, p, q);
    } else {
        update(k1*2+1, mid+1, r, p, q);
    }
    change(k1);
}

int Find(int k1, int L, int R, int l, int r) {
    if(L > r || R < l) return 0;
    if(L >= l && R <= r) {
        return A[k1];
    }
    int mid = L+R >> 1;
    return max(Find(k1*2, L, mid, l, r), Find(k1*2+1, mid+1, R, l, r));
}

void printree(int k1, int l, int r) {
    if(l == r) {
        //printf("B[%d] = %d**%d->%d\n", l, A[k1], k1, l);
        return;
    }
    int mid = l+r >> 1;
    printree(k1*2, l, mid);
    printree(k1*2+1, mid+1, r);
}

int main() {
    while(scanf("%d%d", &n, &m) != EOF) {
        buildtree(1, 1, n);
        //printree(1, 1, n);
        for(int i = 1; i <= m; i++) {
            char ch;
            cin >> ch;
            int a, b;
            scanf("%d%d", &a, &b);
            if(ch == 'Q') {
                printf("%d\n", Find(1, 1, n, a, b));
            } else if(ch == 'U') {
                update(1, 1, n, a, b);
                //printree(1, 1, n);
            }

        }
        //printree(1, 1, n);
    }

    return 0;
}

F题

线段树求逆序数

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
//2021-08-04 10:15:12
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 5e5+10;

int n;
struct node{
    int val;
    int id;
}a[N];
int siz[N*4];

bool cmp(node a, node b) {
    return a.val < b.val;
}

void change(int k1) {
    return;
}

void buildtree(int k1, int l, int r) {
    siz[k1] = r-l+1;
    if(l == r) {
        return;
    }
    int mid = l+r >> 1;
    buildtree(k1*2, l, mid);
    buildtree(k1*2+1, mid+1, r);
    change(k1);
}

int Find(int k1, int l, int r, int L, int R) {
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) {
        return siz[k1];
    }
    int mid = l+r >> 1;
    return Find(k1*2, l, mid, L, R) + Find(k1*2+1, mid+1, r, L, R);
}

void update(int k1, int l, int r, int p, int q) {
    if(l == r) {
        siz[k1] = q;
        return;
    }
    int mid = l+r >> 1;
    if(p <= mid) {
        update(k1*2, l, mid, p, q);
    } else {
        update(k1*2+1, mid+1, r, p, q);
    }
    siz[k1] = siz[k1*2] + siz[k1*2+1];

}

int main() {
    while(scanf("%d", &n) != EOF) {
        if(n == 0) break;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i].val);
            a[i].id = i;
        }
        sort(a+1, a+n+1, cmp);
        buildtree(1, 1, n);
        ll ans = 0;
        for(int i = 1; i <= n; i++) {
           ans += Find(1, 1, n, 1, a[i].id-1);
           update(1, 1, n, a[i].id, 0);
        }
        printf("%lld\n", ans);
    }


    return 0;
}

G题

插队问题

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
//2021-08-05 08:41:36
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 2e5+10;

int n;
int sum[N*4], siz[N*4];
int ans[N], a[N], b[N];

void change(int k1) {
    sum[k1] = sum[k1*2] + sum[k1*2+1];
    return;
}
void buildtree(int k1, int l, int r) {
    siz[k1] = r-l+1;
    if(l == r) {
        sum[k1] = 1;
        return;
    }
    int mid = l+r >> 1;
    buildtree(k1*2, l, mid);
    buildtree(k1*2+1, mid+1, r);
    change(k1);
}

void update(int k1, int l, int r, int p, int q) {
    if(l == r) {
        ans[l] = q;
        sum[k1] = 0;
        return;
    }
    int mid = l+r >> 1;
    if(p <= sum[k1*2]) {
        update(k1*2, l, mid, p, q);
    } else update(k1*2+1, mid+1, r, p-sum[k1*2], q);
    change(k1);
}

int main() {
    while(scanf("%d", &n) != EOF) {
        for(int i = 1; i <= n; i++) {
            scanf("%d%d", &a[i], &b[i]);
            a[i]++;
        }
        buildtree(1, 1, n);
        for(int i = n; i >= 1; i--) {
            update(1, 1, n, a[i], b[i]);
        }
        for(int i = 1; i <= n; i++) {
            printf("%d ", ans[i]);
        }printf("\n");
    }

    return 0;
}

H题

给出一些星星的横坐标和纵坐标，而且星星的纵坐标按非递减排列，如果纵坐标相等，则横坐标按递增排列，任意两颗星星不会重合。如果有n颗星星的横坐标比某颗星星小而且纵坐标不大于那颗星星（即有n颗星星位于那颗星星的左下角或者左边）则此星星的等级为n，最后输出等级为0至n-1的星星的数量。

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
//2021-08-05 14:49:01
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 2e5+10;

int sum[N*4], siz[N*4];
int n;
struct node {
    int x, y;
}a[N];

void change(int k1) {
    sum[k1] = sum[k1*2] + sum[k1*2+1];
}
void buildtree(int k1, int l, int r) {
    siz[k1] = r-l+1;
    if(l == r) {
        sum[k1] = 0;
        return;
    }
    int mid = l+r >> 1;
    buildtree(k1*2, l, mid);
    buildtree(k1*2+1, mid+1, r);
    change(k1);
}

int vis[N];

void update(int k1, int l, int r, int p, int q) {
    if(l == r) {
        sum[k1]++;
        return;
    }
    int mid = l+r >> 1;
    if(p <= mid) {
        update(k1*2, l, mid, p, q);
    } else update(k1*2+1, mid+1, r, p, q);
    change(k1);
}

int Find(int k1, int l, int r, int L, int R) {
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) return sum[k1];
    int mid = l+r >> 1;
    return Find(k1*2, l, mid, L, R) + Find(k1*2+1, mid+1, r, L, R);
}

int main() {
    memset(vis, 0, sizeof(vis));
    scanf("%d", &n);
    buildtree(1, 0, N);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].x++;
        int tmp = Find(1, 1, N, 1, a[i].x);
        vis[tmp]++;
        update(1, 1, N, a[i].x, 1);
    }
    for(int i = 0; i < n; i++) {
        printf("%d\n", vis[i]);
    }

    return 0;
}
求大佬赏个饭