#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
int n;
int q;
int k;
int v[mxN];
map<ll, int> vis;
bool appear[mxN];
struct SegmentTree{
struct Node{
vector<int> pre;
vector<int> suf;
int best;
};
int n;
vector<Node> t;
SegmentTree(){}
SegmentTree(int _n)
{
n = _n;
int offset = 1;
while(offset < n) offset *= 2;
t.resize(offset * 2);
}
Node union_node(Node &a, Node &b, int le1, int le2)
{
Node res;
for(int i = 1; i <= k; i++) appear[i] = false;
res.pre = a.pre;
for(auto it : res.pre) appear[v[it]] = true;
for(auto it : b.pre) {
if(sz(res.pre) == k) break;
if(appear[v[it]] == false) {
appear[v[it]] = true;
res.pre.pb(it);
}
}
for(int i = 1; i <= k; i++) appear[i] = false;
res.suf = b.suf;
for(auto it : res.suf) appear[v[it]] = true;
for(auto it : a.suf) {
if(sz(res.suf) == k) break;
if(appear[v[it]] == false) {
appear[v[it]] = true;
res.suf.pb(it);
}
}
// if(le1 + le2 == n) {
// for(auto it : a.suf) cout << it << ' ';
// cout << endl;
// for(auto it : b.pre) cout << it << ' ';
// cout << endl;
// }
res.best = inf;
int j = sz(b.pre) - 1;
ll rig = 0;
ll lef = 0;
ll fullmask = (1LL << k) - 1;
for(auto it : b.pre) rig |= (1LL << (v[it] - 1));
for(int i = 0; i < sz(a.suf); i++) {
lef |= (1LL << (v[a.suf[i]] - 1));
while(j > 0) {
ll remask = (rig ^ (1LL << (v[b.pre[j]] - 1)));
if((lef | remask) == fullmask) --j;
else break;
swap(rig, remask);
}
if((lef | rig) == fullmask) {
minimize(res.best, b.pre[j] - a.suf[i] + 1);
}
}
minimize(res.best, a.best);
minimize(res.best, b.best);
return res;
}
void build(int v, int tl, int tr)
{
if(tl == tr) {
t[v].pre.pb(tl);
t[v].suf.pb(tl);
t[v].best = inf;
}
else {
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
t[v] = union_node(t[v * 2], t[v * 2 + 1], tm - tl + 1, tr - tm);
}
}
void update(int v, int tl, int tr, int pos, int val)
{
if(tl == tr) {
}
else {
int tm = (tl + tr) / 2;
if(pos <= tm) update(v * 2, tl, tm, pos, val);
else update(v * 2 + 1, tm + 1, tr, pos, val);
t[v] = union_node(t[v * 2], t[v * 2 + 1], tm - tl + 1, tr - tm);
}
}
void update(int pos, int val)
{
update(1, 1, n, pos, val);
}
} seg;
void solve()
{
cin >> n >> k >> q;
for(int i = 1; i <= n; i++) cin >> v[i];
seg = SegmentTree(n);
seg.build(1, 1, n);
while(q--) {
int cmd;
cin >> cmd;
if(cmd == 1) {
int pos, val;
cin >> pos >> val;
v[pos] = val;
seg.update(pos, val);
}
else {
int ans = seg.t[1].best;
if(ans == inf) cout << -1 << endl;
else cout << ans << endl;
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen(TASK".inp" , "r" , stdin);
//freopen(TASK".out" , "w" , stdout);
int tc = 1;
//cin >> tc;
while(tc--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
1960 KB |
Output is correct |
| 2 |
Correct |
26 ms |
1876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
2124 KB |
Output is correct |
| 2 |
Correct |
47 ms |
2104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
416 ms |
7764 KB |
Output is correct |
| 2 |
Correct |
1192 ms |
26760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
589 ms |
16844 KB |
Output is correct |
| 2 |
Correct |
1249 ms |
30620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
820 ms |
15092 KB |
Output is correct |
| 2 |
Correct |
1280 ms |
28480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
971 ms |
18840 KB |
Output is correct |
| 2 |
Correct |
1339 ms |
29260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
964 ms |
18172 KB |
Output is correct |
| 2 |
Correct |
1318 ms |
30016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1129 ms |
31576 KB |
Output is correct |
| 2 |
Correct |
1311 ms |
31532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1331 ms |
31720 KB |
Output is correct |
| 2 |
Correct |
1534 ms |
31436 KB |
Output is correct |
