#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 500;
int n, m, k;
int a[N];
struct tree {
tree *L, *R;
int val;
vector <pair <ll, int> > pf, sf;
tree () {
val = 1e9;
pf.clear();
sf.clear();
}
pair <pair <vector <pair <ll, int> >, vector <pair <ll, int> > >, int> combine(tree *lft, tree *rgt) {
vector <pair <ll, int> > res_pf, res_sf;
int cur_val = 1e9;
vector <pair <ll, int> > left, right;
left = (lft -> pf);
right = (rgt -> pf);
res_pf = left;
for (int i = 0; i < int(right.size()); ++i)
if ((res_pf.back().first | right[i].first) != res_pf.back().first)
res_pf.push_back(make_pair(res_pf.back().first | right[i].first, right[i].second));
left = (lft -> sf);
right = (rgt -> sf);
res_sf = right;
for (int i = 0; i < int(left.size()); ++i)
if ((res_sf.back().first | left[i].first) != res_sf.back().first)
res_sf.push_back(make_pair(res_sf.back().first | left[i].first, left[i].second));
left = (lft -> sf);
right = (rgt -> pf);
cur_val = min(lft -> val, rgt -> val);
int p = int(right.size()) - 1;
for (int i = 0; i < int(left.size()); ++i) {
while (p >= 0 && (left[i].first | right[p].first) == (1ll << k) - 1)
--p;
if (p + 1 < int(right.size()) && (left[i].first | right[p + 1].first) == (1ll << k) - 1)
cur_val = min(cur_val, right[p + 1].second - left[i].second + 1);
}
return make_pair(make_pair(res_pf, res_sf), cur_val);
}
void build(int l, int r) {
if (l > r)
return;
if (l == r) {
val = 1e9;
if (k == 1)
val = 1;
pf.push_back(make_pair((1ll << a[l]), l));
sf.push_back(make_pair((1ll << a[l]), l));
return;
}
int md = (l + r) >> 1;
L = new tree();
R = new tree();
L -> build(l, md);
R -> build(md + 1, r);
auto cur = combine(L, R);
pf = cur.first.first;
sf = cur.first.second;
val = cur.second;
}
void upd(int l, int r, int p, int v) {
if (l == r) {
val = 1e9;
if (k == 1)
val = 1;
a[l] = v;
pf[0] = sf[0] = make_pair((1ll << a[l]), l);
return;
}
int md = (l + r) >> 1;
if (p <= md) L -> upd(l, md, p, v);
else R -> upd(md + 1, r, p, v);
auto cur = combine(L, R);
pf = cur.first.first;
sf = cur.first.second;
val = cur.second;
}
/*void show(int l, int r) {
if (l > r)
return;
cerr << l + 1 << " " << r + 1 << "\n";
cerr << val << "\n";
for (int i = 0; i < int(pf.size()); ++i)
cerr << pf[i].first << " " << pf[i].second << "\n";
cerr << "---\n";
for (int i = 0; i < int(sf.size()); ++i)
cerr << sf[i].first << " " << sf[i].second << "\n";
cerr << "!--------------\n\n";
if (l == r)
return;
int md = (l + r) >> 1;
L -> show(l, md);
R -> show(md + 1, r);
}*/
};
int main() {
cin >> n >> k >> m;
for (int i = 0; i < n; ++i)
cin >> a[i], --a[i];
tree t;
t.build(0, n - 1);
//t.show(0, n - 1);
for (int i = 0; i < m; ++i) {
int type;
cin >> type;
if (type == 1) {
int p, v;
cin >> p >> v;
--p; --v;
t.upd(0, n - 1, p, v);
} else cout << (t.val == 1e9 ? -1 : t.val) << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
1664 KB |
Output is correct |
| 2 |
Correct |
33 ms |
1664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
2296 KB |
Output is correct |
| 2 |
Correct |
76 ms |
2216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
2728 KB |
Output is correct |
| 2 |
Correct |
95 ms |
2680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
836 ms |
10488 KB |
Output is correct |
| 2 |
Correct |
2676 ms |
33120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1295 ms |
25872 KB |
Output is correct |
| 2 |
Correct |
2639 ms |
43784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1685 ms |
20340 KB |
Output is correct |
| 2 |
Correct |
2729 ms |
38212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1948 ms |
31356 KB |
Output is correct |
| 2 |
Correct |
2788 ms |
40088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2009 ms |
28964 KB |
Output is correct |
| 2 |
Correct |
2805 ms |
42340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2496 ms |
46972 KB |
Output is correct |
| 2 |
Correct |
2830 ms |
46520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2388 ms |
47096 KB |
Output is correct |
| 2 |
Correct |
2746 ms |
46300 KB |
Output is correct |
