/**
* author: wxhtzdy
* created: 07.08.2022 13:53:02
**/
#include <bits/stdc++.h>
using namespace std;
int k;
class segtree {
public:
struct node {
// don't forget to set default value (used for leaves)
// not necessarily neutral element!
int ans = (k == 1 ? 1 : 1e9);
vector<pair<int, int>> L;
vector<pair<int, int>> R;
long long mask = 0;
void apply(int l, int r, int v) {
L = {{v, l}};
R = {{v, r}};
mask = (1LL << v);
}
};
node unite(const node &a, const node &b) const {
node res;
{
res.ans = min(a.ans, b.ans);
res.mask = a.mask | b.mask;
long long maskL = 0;
long long maskR = b.mask;
int j = (int) b.L.size() - 1;
for (int i = 0; i < (int) a.R.size(); i++) {
maskL = maskL | (1LL << a.R[i].first);
while (j >= 0 && (maskL | (maskR ^ (1LL << b.L[j].first))) == (1LL << k) - 1) {
maskR ^= (1LL << b.L[j].first);
j -= 1;
}
if (j >= 0 && (maskL | maskR) == (1LL << k) - 1) {
res.ans = min(res.ans, b.L[j].second - a.R[i].second + 1);
}
}
}
{
res.L.clear();
long long mask = 0;
for (auto& p : a.L) {
if (!(mask >> p.first & 1)) {
mask |= (1LL << p.first);
res.L.push_back(p);
}
}
for (auto& p : b.L) {
if (!(mask >> p.first & 1)) {
mask |= (1LL << p.first);
res.L.push_back(p);
}
}
}
{
res.R.clear();
long long mask = 0;
for (auto& p : b.R) {
if (!(mask >> p.first & 1)) {
mask |= (1LL << p.first);
res.R.push_back(p);
}
}
for (auto& p : a.R) {
if (!(mask >> p.first & 1)) {
mask |= (1LL << p.first);
res.R.push_back(p);
}
}
}
return res;
}
inline void push(int x, int l, int r) {
}
inline void pull(int x, int z) {
tree[x] = unite(tree[x + 1], tree[z]);
}
int n;
vector<node> tree;
void build(int x, int l, int r) {
if (l == r) {
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
build(x + 1, l, y);
build(z, y + 1, r);
pull(x, z);
}
template <typename M>
void build(int x, int l, int r, const vector<M> &v) {
if (l == r) {
tree[x].apply(l, r, v[l]);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
build(x + 1, l, y, v);
build(z, y + 1, r, v);
pull(x, z);
}
node get(int x, int l, int r, int ll, int rr) {
if (ll <= l && r <= rr) {
return tree[x];
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push(x, l, r);
node res{};
if (rr <= y) {
res = get(x + 1, l, y, ll, rr);
} else {
if (ll > y) {
res = get(z, y + 1, r, ll, rr);
} else {
res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
}
}
pull(x, z);
return res;
}
template <typename... M>
void modify(int x, int l, int r, int ll, int rr, const M&... v) {
if (ll <= l && r <= rr) {
tree[x].apply(l, r, v...);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push(x, l, r);
if (ll <= y) {
modify(x + 1, l, y, ll, rr, v...);
}
if (rr > y) {
modify(z, y + 1, r, ll, rr, v...);
}
pull(x, z);
}
int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res;
if (f(tree[x + 1])) {
res = find_first_knowingly(x + 1, l, y, f);
} else {
res = find_first_knowingly(z, y + 1, r, f);
}
pull(x, z);
return res;
}
int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
if (!f(tree[x])) {
return -1;
}
return find_first_knowingly(x, l, r, f);
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res = -1;
if (ll <= y) {
res = find_first(x + 1, l, y, ll, rr, f);
}
if (rr > y && res == -1) {
res = find_first(z, y + 1, r, ll, rr, f);
}
pull(x, z);
return res;
}
int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res;
if (f(tree[z])) {
res = find_last_knowingly(z, y + 1, r, f);
} else {
res = find_last_knowingly(x + 1, l, y, f);
}
pull(x, z);
return res;
}
int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
if (!f(tree[x])) {
return -1;
}
return find_last_knowingly(x, l, r, f);
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res = -1;
if (rr > y) {
res = find_last(z, y + 1, r, ll, rr, f);
}
if (ll <= y && res == -1) {
res = find_last(x + 1, l, y, ll, rr, f);
}
pull(x, z);
return res;
}
segtree(int _n) : n(_n) {
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1);
}
template <typename M>
segtree(const vector<M> &v) {
n = v.size();
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1, v);
}
node get(int ll, int rr) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return get(0, 0, n - 1, ll, rr);
}
node get(int p) {
assert(0 <= p && p <= n - 1);
return get(0, 0, n - 1, p, p);
}
template <typename... M>
void modify(int ll, int rr, const M&... v) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
modify(0, 0, n - 1, ll, rr, v...);
}
// find_first and find_last call all FALSE elements
// to the left (right) of the sought position exactly once
int find_first(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return find_first(0, 0, n - 1, ll, rr, f);
}
int find_last(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return find_last(0, 0, n - 1, ll, rr, f);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> k >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
--a[i];
}
segtree st(a);
while (m--) {
int op;
cin >> op;
if (op == 1) {
int p, v;
cin >> p >> v;
--p; --v;
st.modify(p, p, v);
} else {
int ans = st.get(0, n - 1).ans;
cout << (ans == 1e9 ? -1 : ans) << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
12 ms |
1332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
1668 KB |
Output is correct |
| 2 |
Correct |
23 ms |
1748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
2132 KB |
Output is correct |
| 2 |
Correct |
38 ms |
2128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
372 ms |
7940 KB |
Output is correct |
| 2 |
Correct |
1076 ms |
25136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
602 ms |
19696 KB |
Output is correct |
| 2 |
Correct |
1139 ms |
34156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
774 ms |
15664 KB |
Output is correct |
| 2 |
Correct |
1171 ms |
29788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
946 ms |
23396 KB |
Output is correct |
| 2 |
Correct |
1155 ms |
31264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
959 ms |
21812 KB |
Output is correct |
| 2 |
Correct |
1199 ms |
33000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1198 ms |
36420 KB |
Output is correct |
| 2 |
Correct |
1183 ms |
36052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1212 ms |
36480 KB |
Output is correct |
| 2 |
Correct |
1202 ms |
35992 KB |
Output is correct |
