noip2021 线段树专项

发表于 更新于 分类于 阅读次数： 本文字数： 690 阅读时长 ≈ 1 分钟

Link

Luogu P4198 楼房重建

考虑什么情况下能看到某个楼房，当且仅当它前面的楼房高度与原点 (0,0)(0,0) 的斜率都比它自己的小。

所以需要维护每个点的斜率和区间最大值，用来合并子树。

在 pushup 的时候注意一些细节就行了。

Code 
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#define lc rt<<1
#define rc rt<<1|1
#define db double

using namespace std;

const int N = 1e5 + 5;
int n, m;
db c[N], mx[N << 2];
int len[N << 2];

void pushup1(int rt)
{
    mx[rt] = max(mx[lc], mx[rc]);
}

int pushup2(db x, int l, int r, int rt)
{
    if(mx[rt] <= x) return 0;
    if(c[l] > x) return len[rt];
    if(l == r) return c[l] > x;
    int mid = (l + r) >> 1;
    if(mx[lc] <= x) return pushup2(x, mid + 1, r, rc);
    else return pushup2(x, l, mid, lc) + len[rt] - len[lc];
}

void upd(int x, int y, int l, int r, int rt)
{
    if(l == r)
    {
        mx[rt] = (db)y / x;
        len[rt] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) upd(x, y, l, mid, lc);
    else upd(x, y, mid + 1, r, rc);
    pushup1(rt);
    len[rt] = len[lc] + pushup2(mx[lc], mid + 1, r, rc);
}

int rd()
{
    int x = 0;
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
    return x;
}

int main()
{
    n = rd(), m = rd();
    while(m--)
    {
        int x = rd(), y = rd();
        c[x] = (db)y / x;
        upd(x, y, 1, n, 1);
        printf("%d\n", len[1]);
    }
    return 0;
}
// A.S.

HEOI2016/TJOI2016 排序

这题太妙了

首先二分一个答案 xx，将序列中大于 xx 的数赋为 11，小于 xx 的数赋为 00

在对区间 [l,r][l,r] 排序时，若为升序就将区间内的 00 都放到前面后面 11 都放到后面，反之则反之。因此只需要支持区间修改。

单点查询 qq 上的值，若为 11，说明 xx 小了，否则 xx 大了。

但是我们在修改时需要查询区间 11 的个数，所以还要维护个区间和，支持区间查询。

Code 
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
#include <iostream>
#include <cstdio>
#define ls rt << 1
#define rs rt << 1 | 1

using namespace std;

template <typename T>
void read(T &x)
{
    x = 0;
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
    return;
}

template <typename T>
void write(T x)
{
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
    return;
}

const int N = 1e5 + 5;
int n, m, q, a[N], op[N], L[N], R[N];
int b[N], sum[N << 2], tag[N << 2];

void pushup(int rt)
{
    sum[rt] = sum[ls] + sum[rs];
}

void pushdown(int l, int r, int rt)
{
    if(tag[rt] != -1)
    {
        int mid = (l + r) >> 1;
        sum[ls] = tag[rt] * (mid - l + 1);
        sum[rs] = tag[rt] * (r - mid);
        tag[ls] = tag[rt];
        tag[rs] = tag[rt];
        tag[rt] = -1;
    }
}

void build(int l, int r, int rt, int x)
{
    sum[rt] = 0, tag[rt] = -1;
    if(l == r)
    {
        sum[rt] = a[l] >= x;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ls, x);
    build(mid + 1, r, rs, x);
    pushup(rt);
}

void upd(int L, int R, int v, int l, int r, int rt)
{
    if(l > R || r < L) return;
    if(L <= l && r <= R)
    {
        sum[rt] = v * (r - l + 1);
        tag[rt] = v;
        return;
    }
    pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    upd(L, R, v, l, mid, ls);
    upd(L, R, v, mid + 1, r, rs);
    pushup(rt);
}

int qry(int L, int R, int l, int r, int rt)
{
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) return sum[rt];
    pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    return qry(L, R, l, mid, ls) + qry(L, R, mid + 1, r, rs);
}

bool chk(int x)
{
    build(1, n, 1, x);
    for(int i = 1; i <= m; i++)
    {
        int cnt = qry(L[i], R[i], 1, n, 1);
        upd(L[i], R[i], 0, 1, n, 1);
        if(!op[i]) upd(R[i] - cnt + 1, R[i], 1, 1, n, 1);
        else upd(L[i], L[i] + cnt - 1, 1, 1, n, 1);
    }
    return qry(q, q, 1, n, 1);
}

int main()
{
    read(n), read(m);
    for(int i = 1; i <= n; i++) read(a[i]);
    for(int i = 1; i <= m; i++) read(op[i]), read(L[i]), read(R[i]);
    read(q);

    int l = 1, r = n, ans;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(chk(mid)) l = mid + 1, ans = mid;
        else r = mid - 1;
    }

    write(ans);
    return 0;
}
// A.S.

JSOI2008 最大数

线段树板子，单点修改、区间查询

Code 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long

using namespace std;

const ll maxn=200010;
ll n,m,d,t;
ll maxs[maxn<<2];

void pushup(ll rt)
{
    maxs[rt]=max(maxs[rt<<1],maxs[rt<<1|1])%d;
}

void update(ll x,ll y,ll l,ll r,ll rt)
{
    if(l==r)
    {
        maxs[rt]=y;
        return;
    }
    ll mid=(l+r)>>1;
    if(x<=mid) update(x,y,l,mid,rt<<1);
    else update(x,y,mid+1,r,rt<<1|1);
    pushup(rt);
}

ll query(ll L,ll R,ll l,ll r,ll rt)
{
    if(L<=l&&r<=R)
        return maxs[rt];
    ll mid=(l+r)>>1;
    ll ret=-1e9;
    if(L<=mid) ret=max(ret,query(L,R,l,mid,rt<<1));
    if(mid<R) ret=max(ret,query(L,R,mid+1,r,rt<<1|1));
    return ret;
}

int main()
{
    scanf("%lld%lld",&m,&d);
    for(int i=1;i<=m;i++)
    {
        char ch[5];
        ll x;
        scanf("%s%lld",ch,&x);
        if(ch[0]=='A')
        {
            x=(x+t)%d,n++;
            update(n,x,1,m,1);
        }
        else
        {
            t=query(n-x+1,n,1,m,1);
            printf("%lld\n",t);
        }
    }
    return 0;
}
// A.S.

AHOI2009 维护序列

线段树板子，区间乘、区间加、区间求和

Code 
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
#include <bits/stdc++.h>
#define ll long long
#define ls (rt << 1)
#define rs (rt << 1 | 1)

using namespace std;

template <typename T>
void read(T &x)
{
    x = 0; int f = 1; char c = getchar();
    while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
    while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x *= f;
}

template <typename T>
void write(T x)
{
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

const int N = 1e5 + 5;
int n, m, p;
ll a[N];
ll sum[N << 2], add[N << 2], mul[N << 2];

void pushup(int rt)
{
    sum[rt] = (sum[ls] + sum[rs]) % p;
}

void build(int l, int r, int rt)
{
    mul[rt] = 1;
    if(l == r)
    {
        sum[rt] = a[l] % p;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ls), build(mid + 1, r, rs);
    pushup(rt);
}

void pushdown(int l, int r, int rt)
{
    if(mul[rt] != 1)
    {
        sum[ls] = sum[ls] * mul[rt] % p;
        sum[rs] = sum[rs] * mul[rt] % p;
        mul[ls] = mul[ls] * mul[rt] % p;
        mul[rs] = mul[rs] * mul[rt] % p;
        add[ls] = add[ls] * mul[rt] % p;
        add[rs] = add[rs] * mul[rt] % p;
        mul[rt] = 1;
    }
    if(add[rt] != 0)
    {
        int mid = (l + r) >> 1;
        sum[ls] = (sum[ls] + add[rt] * (mid - l + 1) % p) % p;
        sum[rs] = (sum[rs] + add[rt] * (r - mid) % p) % p;
        add[ls] = (add[ls] + add[rt]) % p;
        add[rs] = (add[rs] + add[rt]) % p;
        add[rt] = 0;
    }
}

void upd_mul(int L, int R, ll k, int l, int r, int rt)
{
    if(l > R || r < L) return;
    if(L <= l && r <= R)
    {
        sum[rt] = sum[rt] * k % p;
        mul[rt] = mul[rt] * k % p;
        add[rt] = add[rt] * k % p;
        return;
    }
    pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    upd_mul(L, R, k, l, mid, ls);
    upd_mul(L, R, k, mid + 1, r, rs);
    pushup(rt);
}

void upd_add(int L, int R, ll k, int l, int r, int rt)
{
    if(l > R || r < L) return;
    if(L <= l && r <= R)
    {
        sum[rt] = (sum[rt] + k * (r - l + 1) % p) % p;
        add[rt] = (add[rt] + k) % p;
        return;
    }
    pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    upd_add(L, R, k, l, mid, ls);
    upd_add(L, R, k, mid + 1, r, rs);
    pushup(rt);
}

ll qry(int L, int R, int l, int r, int rt)
{
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) return sum[rt];
    pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    return (qry(L, R, l, mid, ls) + qry(L, R, mid + 1, r, rs)) % p;
}

int main()
{
    read(n), read(p);
    for(int i = 1; i <= n; i++) read(a[i]);
    read(m);
    build(1, n, 1);
    while(m--)
    {
        int op, x, y;
        ll k;
        read(op), read(x), read(y);
        if(op == 1) read(k), upd_mul(x, y, k, 1, n, 1);
        else if(op == 2) read(k), upd_add(x, y, k, 1, n, 1);
        else write(qry(x, y, 1, n, 1)), puts("");
    }
    return 0;
}
// A.S.

HNOI2012 永无乡

权值线段树（？

写的 fhq treap

用并查集维护一下子树，进行启发式合并，合并的时候就将小的那棵树的每个点依次插入到大的那棵树上。

查询第 kk 大即可。

Code 
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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
template <typename T>
void read(T &x)
{
    x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
    return;
}

template <typename T>
void write(T x)
{
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
    return;
}

int n, m, q;
int cnt, fa[N], val[N], dat[N], siz[N], ls[N], rs[N];
int id[N];

int Newnode(int v)
{
    cnt++;
    val[cnt] = v;
    dat[cnt] = rand();
    siz[cnt] = 1;
    ls[cnt] = rs[cnt] = 0;
    id[v] = cnt;
    return cnt;
}

int Find(int x)
{
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}

void pushup(int p)
{
    siz[p] = siz[ls[p]] + siz[rs[p]] + 1;
}

void Split(int p, int v, int &x, int &y)
{
    if(!p) {x = y = 0; return;}
    if(val[p] <= v)
    {
        x = p;
        Split(rs[p], v, rs[x], y);
    }
    else
    {
        y = p;
        Split(ls[p], v, x, ls[y]);
    }
    pushup(p);
    return;
}

int Merge(int x, int y)
{
    if(!x || !y) return x + y;
    if(dat[x] < dat[y])
    {
        rs[x] = Merge(rs[x], y);
        pushup(x);
        return x;
    }
    else
    {
        ls[y] = Merge(x, ls[y]);
        pushup(y);
        return y;
    }
}

void Insert(int &rt, int p)
{
    int x, y;
    int v = val[p];
    Split(rt, v, x, y);
    rt = Merge(Merge(x, p), y);
    return;
}

void dfs(int &x, int y)
{
    if(!y) return;
    dfs(x, ls[y]), dfs(x, rs[y]);
    ls[y] = rs[y] = 0;
    Insert(x, y);
    return;
}

void Union(int x, int y)
{
    x = Find(x), y = Find(y);
    if(x == y) return;
    if(siz[x] < siz[y]) swap(x, y);
    int z = x;
    dfs(z, y);
    fa[x] = fa[y] = fa[z] = z;
    return;
}

int Kth(int p, int k)
{
    while(1)
    {
        if(siz[ls[p]] >= k) p = ls[p];
        else if(siz[ls[p]] + 1 == k) return p;
        else k -= siz[ls[p]] + 1, p = rs[p];
    }
    return p;
}

int main()
{
    srand((unsigned)time(NULL));

    read(n), read(m);
    for(int i = 1, v; i <= n; i++)
    {
        read(v);
        fa[i] = Newnode(v);
    }
    for(int i = 1, x, y, z; i <= m; i++)
    {
        read(x), read(y);
        Union(x, y);
    }

    read(q);
    while(q--)
    {
        char op[5];
        int x, y;
        scanf("%s", op);
        read(x), read(y);
        if(op[0] == 'Q')
        {
            if(siz[Find(x)] < y) puts("-1");
            else write(id[val[Kth(Find(x), y)]]), puts("");
        }
        else Union(x, y);
    }

    return 0;
}
// A.S.

SCOI2010 序列操作

真·码农题

不过写的时候还是挺顺利的，就一个小错（但还是调了一晚上 qaq

区间最长连续个数就比较套路的记一下左边和右边的，再合并中间的。

但是因为有区间取反，所以 00 和 11 的连续最长的长度都要记下来，取反时 swap 一下。

在区间赋值时把区间取反标记去掉，但是在区间取反的时候不能去掉区间赋值标记。

所以 pushdown 里要先下传区间赋值，再下传区间取反。

Code 
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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

namespace IO
{
    template <typename T>
    void read(T &x)
    {
        x = 0; char c = getchar();
        while(!isdigit(c)) c = getchar();
        while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
        return;
    }

    template <typename T>
    void write(T x)
    {
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
        return;
    }
}
using namespace IO;

namespace SegTree
{
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)
    #define swap(a, b) a ^= b ^= a ^= b

    int len[N << 2], sum[N << 2], tag[N << 2], rev[N << 2];
    int mx[N << 2][2], lmx[N << 2][2], rmx[N << 2][2];

    void pushup(int rt)
    {
        sum[rt] = sum[ls] + sum[rs];

        lmx[rt][0] = lmx[ls][0];
        rmx[rt][0] = rmx[rs][0];
        lmx[rt][1] = lmx[ls][1];
        rmx[rt][1] = rmx[rs][1];

        if(lmx[rt][0] == len[ls]) lmx[rt][0] += lmx[rs][0];
        if(rmx[rt][0] == len[rs]) rmx[rt][0] += rmx[ls][0];
        if(lmx[rt][1] == len[ls]) lmx[rt][1] += lmx[rs][1];
        if(rmx[rt][1] == len[rs]) rmx[rt][1] += rmx[ls][1];

        mx[rt][0] = max(max(mx[ls][0], mx[rs][0]), rmx[ls][0] + lmx[rs][0]);
        mx[rt][1] = max(max(mx[ls][1], mx[rs][1]), rmx[ls][1] + lmx[rs][1]);
    }

    void Swap(int x)
    {
        swap(mx[x][0], mx[x][1]);
        swap(lmx[x][0], lmx[x][1]);
        swap(rmx[x][0], rmx[x][1]);
    }

    void pushdown(int rt)
    {
        if(~tag[rt])
        {
            sum[ls] = len[ls] * tag[rt];
            sum[rs] = len[rs] * tag[rt];

            tag[ls] = tag[rt];
            tag[rs] = tag[rt];

            rev[ls] = rev[rs] = 0;

            int x = tag[rt], y = tag[rt] ^ 1;
            mx[ls][x] = lmx[ls][x] = rmx[ls][x] = len[ls];
            mx[rs][x] = lmx[rs][x] = rmx[rs][x] = len[rs];
            mx[ls][y] = lmx[ls][y] = rmx[ls][y] = 0;
            mx[rs][y] = lmx[rs][y] = rmx[rs][y] = 0;

            tag[rt] = -1;
        }

        if(rev[rt])
        {
            sum[ls] = len[ls] - sum[ls];
            sum[rs] = len[rs] - sum[rs];

            rev[ls] ^= rev[rt];
            rev[rs] ^= rev[rt];

            Swap(ls), Swap(rs);

            rev[rt] = 0;
        }
    }

    void build(int l, int r, int rt)
    {
        len[rt] = r - l + 1;
        tag[rt] = -1;
        if(l == r)
        {
            int a; read(a);
            sum[rt] = a;
            mx[rt][a] = lmx[rt][a] = rmx[rt][a] = 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, ls);
        build(mid + 1, r, rs);
        pushup(rt);
    }

    void update(int L, int R, int x, int l, int r, int rt)
    {
        if(l > R || r < L) return;
        if(L <= l && r <= R)
        {
            if(~x)
            {
                sum[rt] = len[rt] * x;
                tag[rt] = x;
                rev[rt] = 0;
                mx[rt][x] = lmx[rt][x] = rmx[rt][x] = len[rt];
                mx[rt][x ^ 1] = lmx[rt][x ^ 1] = rmx[rt][x ^ 1] = 0;
            }
            else
            {
                rev[rt] ^= 1;
                sum[rt] = len[rt] - sum[rt];
                Swap(rt);
            }
            return;
        }
        pushdown(rt);
        int mid = (l + r) >> 1;
        update(L, R, x, l, mid, ls);
        update(L, R, x, mid + 1, r, rs);
        pushup(rt);
    }

    int qry_cnt(int L, int R, int l, int r, int rt)
    {
        if(l > R || r < L) return 0;
        if(L <= l && r <= R) return sum[rt];
        pushdown(rt);
        int mid = (l + r) >> 1;
        return qry_cnt(L, R, l, mid, ls) + qry_cnt(L, R, mid + 1, r, rs);
    }

    int qry_max(int L, int R, int l, int r, int rt)
    {
        if(l > R || r < L) return 0;
        if(L <= l && r <= R) return mx[rt][1];
        pushdown(rt);
        int mid = (l + r) >> 1, res = min(rmx[ls][1], mid - L + 1) + min(lmx[rs][1], R - mid);
        return max(res, max(qry_max(L, R, l, mid, ls), qry_max(L, R, mid + 1, r, rs)));
    }
}
using namespace SegTree;

namespace Acestar
{
    void main()
    {
        int n, m;
        read(n), read(m);

        build(1, n, 1);

        while(m--)
        {
            int op, l, r;
            read(op), read(l), read(r);
            l++ , r++;
            if(op == 0) update(l, r, 0, 1, n, 1);
            if(op == 1) update(l, r, 1, 1, n, 1);
            if(op == 2) update(l, r, -1, 1, n, 1);
            if(op == 3) write(qry_cnt(l, r, 1, n, 1)), putchar('\n');
            if(op == 4) write(qry_max(l, r, 1, n, 1)), putchar('\n');
        }

        return;
    }
}

int main()
{
    Acestar :: main();
    return 0;
}
// A.S.

数据结构题主要还是多写（