维护一堆奇奇怪怪的东西。
考虑线段树维护权值,支持单点修改区间 好题。
xxxxxxxxxx
1931
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25
26template < typename T = int >
27inline T read(void);
28
29int N, M, C;
30int val[LIM], col[LIM];
31int cnt[110];
32
33class SegTree{
34private:
35 int sum[LIM << 2], mn[LIM << 2], mx[LIM << 2];
36
37
38
39public:
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
74struct 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
82class ODT{
83private:
84 set < Node > tr;
85public:
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
144int 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
179template < typename T >
180inline 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}
给定 -1
。
首先摩尔投票默认为前置知识不再提了,不难发现区间众数不支持合并,而摩尔众数形式表示的区间众数则支持,合并是平凡的,则开一颗权值线段树即可。同时考虑验证部分,不难想到对每个人开一个平衡树记录有哪些人对其投票了,这样可以支持动态修改,然后每次查询一下 tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update >
维护即可,可以大幅减少码量以及错误率,但时间上略有降低。
xxxxxxxxxx
1081
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13using namespace __gnu_pbds;
14
15mt19937 rnd(random_device{}());
16int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
17bool rnddd(int x){return rndd(1, 100) <= x;}
18
19typedef unsigned int uint;
20typedef unsigned long long unll;
21typedef long long ll;
22typedef long double ld;
23
24template < typename T = int >
25inline T read(void);
26
27int N, M;
28int vote[510000];
29tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > tr[510000];
30
31class SegTree{
32private:
33 int tr[510000 << 2], cnt[510000 << 2];
34
35
36
37public:
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
66int 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
94template < typename T >
95inline 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}
update-2023_02_24 初稿