杂题小记（2023.02.24）

更好的阅读体验戳此进入

LG-P5251 [LnOI2019]第二代图灵机

题面

维护一堆奇奇怪怪的东西。

Solution

考虑线段树维护权值，支持单点修改区间 $max$$\max$ 和区间 $min$$\min$，ODT 维护颜色，然后在 ODT 上做双指针并在线段树上查询即可，细节巨多，双指针边界需要精细考虑并实现，还感觉有点类似莫队的思想，好题。

Code

xxxxxxxxxx
193
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define LIM (110000)
24
#define INF (0x3f3f3f3f)
25

26
template < typename T = int >
27
inline T read(void);
28

29
int N, M, C;
30
int val[LIM], col[LIM];
31
int cnt[110];
32

33
class SegTree{
34
private:
35
    int sum[LIM << 2], mn[LIM << 2], mx[LIM << 2];
36
    #define LS (p << 1)
37
    #define RS (LS | 1)
38
    #define MID ((gl + gr) >> 1)
39
public:
40
    SegTree(void){memset(mn, 0x3f, sizeof mn);}
41
    void Pushup(int p){
42
        sum[p] = sum[LS] + sum[RS];
43
        mn[p] = min(mn[LS], mn[RS]);
44
        mx[p] = max(mx[LS], mx[RS]);
45
    }
46
    void Build(int p = 1, int gl = 1, int gr = N){
47
        if(gl == gr)return sum[p] = mn[p] = mx[p] = val[gl = gr], void();
48
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
49
        Pushup(p);
50
    }
51
    void Modify(int pos, int val, int p = 1, int gl = 1, int gr = N){
52
        if(gl == gr)return sum[p] = mn[p] = mx[p] = val, void();
53
        if(pos <= MID)Modify(pos, val, LS, gl, MID);
54
        else Modify(pos, val, RS, MID + 1, gr);
55
        Pushup(p);
56
    }
57
    int QuerySum(int l, int r, int p = 1, int gl = 1, int gr = N){
58
        if(l <= gl && gr <= r)return sum[p];
59
        if(l > gr || r < gl)return 0;
60
        return QuerySum(l, r, LS, gl, MID) + QuerySum(l, r, RS, MID + 1, gr);
61
    }
62
    int QueryMin(int l, int r, int p = 1, int gl = 1, int gr = N){
63
        if(l <= gl && gr <= r)return mn[p];
64
        if(l > gr || r < gl)return INF;
65
        return min(QueryMin(l, r, LS, gl, MID), QueryMin(l, r, RS, MID + 1, gr));
66
    }
67
    int QueryMax(int l, int r, int p = 1, int gl = 1, int gr = N){
68
        if(l <= gl && gr <= r)return mx[p];
69
        if(l > gr || r < gl)return 0;
70
        return max(QueryMax(l, r, LS, gl, MID), QueryMax(l, r, RS, MID + 1, gr));
71
    }
72
}st;
73

74
struct Node{
75
    int l, r;
76
    mutable int val;
77
    friend const bool operator < (const Node &a, const Node &b){
78
        return a.l < b.l;
79
    }
80
};
81

82
class ODT{
83
private:
84
    set < Node > tr;
85
public:
86
    auto Insert(Node p){return tr.insert(p);}
87
    auto Split(int p){
88
        auto it = tr.lower_bound(Node{p});
89
        if(it != tr.end() && it->l == p)return it;
90
        advance(it, -1);
91
        if(it->r < p)return tr.end();
92
        auto l = it->l, r = it->r, val = it->val;
93
        tr.erase(it);
94
        Insert(Node{l, p - 1, val});
95
        return Insert(Node{p, r, val}).first;
96
    }
97
    void Assign(int l, int r, int val){
98
        auto itR = Split(r + 1), itL = Split(l);
99
        tr.erase(itL, itR);
100
        Insert(Node{l, r, val});
101
    }
102
    int Query3(int l, int r){
103
        if(C == 1)return st.QueryMin(l, r);
104
        int ans(INT_MAX);
105
        int tot(0);
106
        auto itR = Split(r + 1), itL = Split(l);
107
        auto itl = itL, itr = itL;
108
        while(itl != itR){
109
            while(tot < C && itr != itR)if(!cnt[(itr++)->val]++)++tot;
110
            if(tot == C){
111
                while(cnt[itl->val] > 1)--cnt[(itl++)->val];
112
                ans = min(ans, st.QuerySum(itl->r, prev(itr)->l));
113
                while(tot == C && itl != itR)if(!--cnt[(itl++)->val])--tot;
114
            }
115
            if(itr == itR)while(itl != itR)--cnt[(itl++)->val];
116
        }return ans == INT_MAX ? -1 : ans;
117
    }
118
    int Query4(int l, int r){
119
        int ans = st.QueryMax(l, r);
120
        auto itR = Split(r + 1), itL = Split(l);
121
        auto itl = itL, itr = itL;
122
        while(itl != itR){
123
            while(itr != itR && itr->r - itr->l + 1 == 1 && !cnt[itr->val])cnt[(itr++)->val]++;
124
            if(itr != itR && itr->r - itr->l + 1 > 1){
125
                if(!cnt[itr->val])ans = max(ans, st.QuerySum(itl->r, itr->l));
126
                else if(itl != itr){
127
                    ans = max(ans, st.QuerySum(itl->r, prev(itr)->l));
128
                    while(cnt[itr->val])cnt[(itl++)->val]--;
129
                    ans = max(ans, st.QuerySum(itl->r, itr->l));
130
                }
131
                while(itl != itr)cnt[(itl++)->val]--;
132
                cnt[(itr++)->val]++;
133
                continue;
134
            }
135
            if(itl != itr){
136
                ans = max(ans, st.QuerySum(itl->r, prev(itr)->l));
137
                if(itr == itR)while(itl != itR)cnt[(itl++)->val]--;
138
                else while(itl != itR && cnt[itr->val])cnt[(itl++)->val]--;
139
            }
140
        }return ans;
141
    }
142
}odt;
143

144
int main(){
145
    N = read(), M = read(), C = read();
146
    for(int i = 1; i <= N; ++i)val[i] = read();
147
    for(int i = 1; i <= N; ++i)col[i] = read(), odt.Insert(Node{i, i, col[i]});
148
    st.Build();
149
    while(M--){
150
        int opt = read();
151
        switch(opt){
152
            case 1:{
153
                int p = read(), v = read();
154
                st.Modify(p, v);
155
                break;
156
            }
157
            case 2:{
158
                int l = read(), r = read(), v = read();
159
                odt.Assign(l, r, v);
160
                break;
161
            }
162
            case 3:{
163
                int l = read(), r = read();
164
                printf("%d\n", odt.Query3(l, r));
165
                break;
166
            }
167
            case 4:{
168
                int l = read(), r = read();
169
                printf("%d\n", odt.Query4(l, r));
170
                break;
171
            }
172
            default:break;
173
        }
174
    }
175
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
176
    return 0;
177
}
178

179
template < typename T >
180
inline T read(void){
181
    T ret(0);
182
    int flag(1);
183
    char c = getchar();
184
    while(c != '-' && !isdigit(c))c = getchar();
185
    if(c == '-')flag = -1, c = getchar();
186
    while(isdigit(c)){
187
        ret *= 10;
188
        ret += int(c - '0');
189
        c = getchar();
190
    }
191
    ret *= flag;
192
    return ret;
193
}

LG-P3765 总统选举

题面

给定 $n$$n$ 个人的投票，$m$$m$ 次询问给定 $l,r,s,k$$l, r, s, k$ 求 $[l,r]$$[l, r]$ 区间严格众数，若不存在则认为为 $s$$s$，并给定 $k$$k$ 个数将这些人的投票均改为求出的严格众数，每次输出求得的区间严格众数，特别地，所有操作完成后需要再对 $[1,n]$$[1, n]$ 求一次区间严格众数，不存在则输出 -1。

Solution

首先摩尔投票默认为前置知识不再提了，不难发现区间众数不支持合并，而摩尔众数形式表示的区间众数则支持，合并是平凡的，则开一颗权值线段树即可。同时考虑验证部分，不难想到对每个人开一个平衡树记录有哪些人对其投票了，这样可以支持动态修改，然后每次查询一下 $[l,r]$$[l, r]$ 内有多少并与总长度比较判断即可。值得一提的是不难发现本题平衡树功能平凡，于是考虑直接使用 tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > 维护即可，可以大幅减少码量以及错误率，但时间上略有降低。

Code

xxxxxxxxxx
108
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13
using namespace __gnu_pbds;
14

15
mt19937 rnd(random_device{}());
16
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
17
bool rnddd(int x){return rndd(1, 100) <= x;}
18

19
typedef unsigned int uint;
20
typedef unsigned long long unll;
21
typedef long long ll;
22
typedef long double ld;
23

24
template < typename T = int >
25
inline T read(void);
26

27
int N, M;
28
int vote[510000];
29
tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > tr[510000];
30

31
class SegTree{
32
private:
33
    int tr[510000 << 2], cnt[510000 << 2];
34
    #define LS (p << 1)
35
    #define RS (LS | 1)
36
    #define MID ((gl + gr) >> 1)
37
public:
38
    pair < int, int > Merge(pair < int, int > l, pair < int, int > r){
39
        if(l.first == r.first)return {l.first = r.first, l.second + r.second};
40
        if(l.second >= r.second)return {l.first, l.second - r.second};
41
        else return {r.first, r.second - l.second};
42
    }
43
    void Pushup(int p){
44
        tie(tr[p], cnt[p]) = Merge({tr[LS], cnt[LS]}, {tr[RS], cnt[RS]});
45
    }
46
    void Build(int p = 1, int gl = 1, int gr = N){
47
        if(gl == gr)return tr[p] = vote[gl = gr], cnt[p] = 1, void();
48
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
49
        Pushup(p);
50
    }
51
    void Modify(int pos, int p = 1, int gl = 1, int gr = N){
52
        if(gl == gr)return tr[p] = vote[gl = gr], void();
53
        if(pos <= MID)Modify(pos, LS, gl, MID);
54
        else Modify(pos, RS, MID + 1, gr);
55
        Pushup(p);
56
    }
57
    pair < int, int > Query(int l, int r, int p = 1, int gl = 1, int gr = N){
58
        if(l <= gl && gr <= r)return {tr[p], cnt[p]};
59
        pair < int, int > ret{0, -1};
60
        if(l <= MID)ret = Merge(Query(l, r, LS, gl, MID), ret);
61
        if(r >= MID + 1)ret = Merge(Query(l, r, RS, MID + 1, gr), ret);
62
        return ret;
63
    }
64
}st;
65

66
int main(){
67
    N = read(), M = read();
68
    for(int i = 1; i <= N; ++i)tr[vote[i] = read()].insert(i);
69
    st.Build();
70
    while(M--){
71
        int l = read(), r = read(), s = read(), k = read();
72
        auto win = st.Query(l, r).first;
73
        int rnkR = tr[win].order_of_key(r);
74
        if(*tr[win].find_by_order(rnkR) != r)--rnkR;
75
        int rnkL = tr[win].order_of_key(l);
76
        if(rnkR - rnkL + 1 > ((r - l + 1) >> 1))s = win;
77
        while(k--){
78
            int p = read();
79
            tr[vote[p]].erase(p), tr[s].insert(p);
80
            vote[p] = s, st.Modify(p);
81
        }printf("%d\n", s);
82
    }
83
    int l = 1, r = N, s = -1;
84
    auto win = st.Query(l, r).first;
85
    int rnkR = tr[win].order_of_key(r);
86
    if(*tr[win].find_by_order(rnkR) != r)--rnkR;
87
    int rnkL = tr[win].order_of_key(l);
88
    if(rnkR - rnkL + 1 > ((r - l + 1) >> 1))s = win;
89
    printf("%d\n", s);
90
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
91
    return 0;
92
}
93

94
template < typename T >
95
inline T read(void){
96
    T ret(0);
97
    int flag(1);
98
    char c = getchar();
99
    while(c != '-' && !isdigit(c))c = getchar();
100
    if(c == '-')flag = -1, c = getchar();
101
    while(isdigit(c)){
102
        ret *= 10;
103
        ret += int(c - '0');
104
        c = getchar();
105
    }
106
    ret *= flag;
107
    return ret;
108
}

UPD

update-2023_02_24 初稿