sinEagle

bottlecode

0%

SDTBU-ACM集训队暑假训练-----线段树加深

发表于 更新于
本文字数： 8.9k 阅读时长 ≈ 8 分钟

题目链接

A题

每次取出第K小，询问总和

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

const int N = 3e5+10;
int T, n, k;
int a[N];
long long sum = 0;
int siz[N*4];

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

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);
}

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

int main() {
    scanf("%d", &T);
    int xx = 0;
    while(T--) {
        xx++;
        sum = 0;
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= k; i++) {
            scanf("%d", &a[i]);
        }
        buildtree(1, 1, n);
        for(int i = 1; i <= k; i++) {
            update(1, 1, n, a[i], 0);
        }
        printf("Case %d: %lld\n", xx, sum);

    }

    return 0;
}

B题

题意：询问队列里第 $ \lfloor \frac {m} {2} \rfloor $ +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
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
//2021-08-06 10:18:48
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 1e5+10;
int n;
int a[N], b[N];
int siz[N*4];
//
//bool cmp(int a, int b) {
//    return a > b;
//}

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

void buildtree(int k1, int l, int r) {
    siz[k1] = 0;
    if(l == r) {
        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) {
        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);
    }
    change(k1);
}

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

int main() {
    int tt = 0;
    while(scanf("%d", &n) != EOF) {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        if(n == 0) break;
        printf("Case #%d:\n", ++tt);
        queue<int> Q;
        char s[30];
        int tot = 0;
        int in[N];
        buildtree(1, 1, N);
        for(int i = 1; i <= n; i++) {
            scanf("%s", s);
            if (s[0] == 'i') {
                scanf("%d", &a[++tot]);
                in[i] = 1;
                b[tot] = a[tot];
            } else if(s[0] == 'o') {
                in[i] = -1;
            } else if(s[0] == 'q') {
                in[i] = -2;
            }
        }
        sort(b+1, b+tot+1);
        for(int i = 1; i <= tot; i++)
            a[i] = lower_bound(b+1, b+tot+1, a[i]) - b;

        tot = 0;
        for(int i = 1; i <= n; i++) {
            if (in[i] >= 0) {
                update(1, 1, N, a[++tot], 1);
                Q.push(a[tot]);
            } else if(in[i] == -1) {
                if(Q.size() == 0) continue;
                int now = Q.front(); Q.pop();
                //printf("pop %d size = %d\n", now, Q.size());
                update(1, 1, N, now, 0);
            } else if(in[i] == -2) {
                if(Q.size() == 0) continue;
                int k = Q.size()/2 + 1;
                int pos = Find(1, 1, N, k);
                printf("%d\n", b[pos]);
            }
        }

    }

    return 0;
}

C题

线段树+扫描线

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iomanip>
using namespace std;
const int N = 2e4+10;

int n;
double x[N*2];

struct scanLine{
    double l, r, h;
    int mark;
}line[N*2];

bool cmp(scanLine aa, scanLine bb) {
    return aa.h < bb.h;
}

double len[N*4];
int val[N*4];
void buildtree(int k1, int l, int r) {
    val[k1] = 0;
    if(l == r) {
        return;
    }
    int mid = l+r >> 1;
    buildtree(k1*2, l, mid);
    buildtree(k1*2+1, mid+1, r);
}

void change(int k1, int l, int r) {
    if(val[k1]) {
        len[k1] = x[r+1] - x[l];
    }else {
        len[k1] = len[k1*2] + len[k1*2+1];
    }
}

void update(int k1, int l, int r, int L, int R, int c) {
    if(L <= l && r <= R) {
        val[k1] += c;
        change(k1, l, r);
        return;
    }
    //printf("*****\n");
    int mid = l+r >> 1;
    if(L <= mid) {
        update(k1*2, l, mid, L, R, c);
    }
    if(R > mid) {
        update(k1*2+1, mid+1, r, L, R, c);
    }
    change(k1, l, r);
}

int main() {
    int xx = 0;
    while(scanf("%d", &n) != EOF) {
        if(n == 0) break;
        memset(len, 0, sizeof(len));
        memset(val, 0, sizeof(val));
        memset(x, 0, sizeof(x));

        int cnt = 0;
        int tot = 0;
        for(int i = 1; i <= n; i++) {
            double x1, x2, y1, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            x[++cnt] = x1; x[++cnt] = x2;
            line[++tot].l = x1;
            line[tot].r = x2;
            line[tot].h = y1;
            line[tot].mark = 1;
            line[++tot].l = x1;
            line[tot].r = x2;
            line[tot].h = y2;
            line[tot].mark = -1;
        }
        n <<= 1;
        sort(x+1, x+cnt+1);
        cnt = unique(x+1, x+cnt+1) - x - 1; //去重
        buildtree(1, 1, cnt-1);

        sort(line+1, line+tot+1, cmp);


        double ans = 0;
        for(int i = 1; i < tot; i++) {
            int xx = lower_bound(x+1, x+cnt+1, line[i].l) - x;
            int yy = lower_bound(x+1, x+cnt+1, line[i].r) - x;
            update(1, 1, tot-1, xx, yy-1, line[i].mark);
            ans += (double)len[1] * (line[i+1].h - line[i].h);
        }
        printf("Test case #%d\n", ++xx);
        printf("Total explored area: ");
        cout << fixed<< setprecision(2) << ans;
        //printf("%.2lf", ans); //换成这个就会WA
        printf("\n\n");
    }

    return 0;
}

G题

线段树维护区间众数，前面博客写过这题

点我

J题

区间开根号，询问区间和

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
//2021-08-07 09:34:58
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;

const int N = 1e5+10;
int n, m;
ll sum[N*4], siz[N*4];
ll flag[N*4];

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

void buildtree(int k1, int l, int r) {
    siz[k1] = r-l+1;
    if(l == r) {
        scanf("%lld", &sum[k1]);
        if(sum[k1] <= 1) flag[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 L, int R) {
    if(flag[k1] == 1) return;
    if(l == r) {
        sum[k1] = floor(sqrt(sum[k1]));
        if(sum[k1] <= 1) {
            flag[k1] = 1;
        }
        return;
    }
    int mid = l+r >> 1;
    if(L <= mid) {
        update(k1*2, l, mid, L, R);
    }
    if(mid < R) {
        update(k1*2+1, mid+1, r, L, R);
    }
    change(k1);
}

ll 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() {
    scanf("%d", &n);
    int x, l, r;
    buildtree(1, 1, n);
    scanf("%d", &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &l, &r);
        if(x == 1) {
            printf("%lld\n", Find(1, 1, n, l, r));
        }else {
            update(1, 1, n, l, r);
        }
    }

    return 0;
}

I题

题目大意：n个连续的房间m个操作。操作分两种，第一种以1 x形式给出，找到最左的能连续容下x个人的连续房间，并输出左端点的编号，如果找不到就输出0.第二种以2 l x的形式给出，表示以l为起点的x个房间都清空。
线段树区间合并的板子题。
参考博客

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iomanip>
using namespace std;

const int N = 5e4+10;
int n, k;

int sum[N*4], lsum[N*4], rsum[N*4];
int A[N*4];
void buildtree(int k1, int l, int r) {
    sum[k1] = lsum[k1] = rsum[k1] = r-l+1;
    A[k1] = -1;
    if(l == r) return;
    int mid = l+r >> 1;
    buildtree(k1*2, l, mid);
    buildtree(k1*2+1, mid+1, r);
}

void change(int k1, int val) {
    lsum[k1] = lsum[k1*2];
    rsum[k1] = rsum[k1*2+1];
    if(lsum[k1*2] == val-val/2) {
        lsum[k1] += lsum[k1*2+1];
    }
    if(rsum[k1*2+1] == val/2) {
        rsum[k1] += rsum[k1*2];
    }
    sum[k1] = max(lsum[k1*2+1]+rsum[k1*2], max(sum[k1*2], sum[k1*2+1]));
}

void pushdown(int k1, int val) {
    if(A[k1] != -1) {
        A[k1*2] = A[k1*2+1] = A[k1];
        sum[k1*2] = lsum[k1*2] = rsum[k1*2] = A[k1]?0:val-val/2;
        sum[k1*2+1] = lsum[k1*2+1] = rsum[k1*2+1] = A[k1]?0:val/2;
        A[k1] = -1;
    }
}

void update(int k1, int l, int r, int L, int R, int val) {
    if(L <= l && r <= R) {
        A[k1] = val;
        if(val)
            sum[k1] = rsum[k1] = lsum[k1] = 0;
        else if(val == 0) {
            sum[k1] = rsum[k1] = lsum[k1] = r-l+1;
        }
        return;
    }
    int mid = l+r >> 1;
    pushdown(k1, r-l+1);
    if(L <= mid) update(k1*2, l, mid, L, R, val);
    if(R > mid) update(k1*2+1, mid+1, r, L, R, val);
    change(k1, r-l+1);

}

int Find(int k1, int l, int r, int val) {
    if(l == r) return l;
    pushdown(k1, r-l+1);
    int mid = l+r >> 1;
    if(val <= sum[k1*2]) {
        return Find(k1*2, l, mid, val);
    } else if(rsum[k1*2] + lsum[k1*2+1] >= val) {
        return mid-rsum[k1*2]+1;
    }
    return Find(k1*2+1, mid+1, r, val);
}

int main() {
    while(scanf("%d%d", &n, &k) != EOF) {
        buildtree(1, 1, n);
        while(k--) {
            int op, a;
            scanf("%d%d", &op, &a);
            if (op == 1) {
                if(sum[1] < a) {
                    printf("0\n");
                    continue;
                }
                int p = Find(1, 1, n, a);
                printf("%d\n", p);
                update(1, 1, n, p, p+a-1, 1);
            } else {
                int b;
                scanf("%d", &b);
                update(1, 1, n, a, a+b-1, 0);
            }
        }
    }

    return 0;
}
求大佬赏个饭