#include "bits/stdc++.h" using namespace std; #define intt int #define fi first #define se second const intt mxN = 2e5 + 5; const intt LG = 20; const intt inf = 1e18; intt n, k, m; vector<intt> a(mxN); struct nod { vector<pair<intt,intt>> pre, suf; intt l, r, ans; }; vector<nod>seg(4*mxN); nod combine(nod &sol, nod &sag) { nod ret; ret.ans = min(sol.ans, sag.ans); ret.l = sol.l; ret.r = sag.r; // cout << "check1"<<endl; intt L = 0; for(intt R = (intt)sag.pre.size()-1; R >= 0; R--) { while(L < (intt)sol.suf.size() && (sag.pre[R].fi | sol.suf[L].fi) != (1 << k) - 1) { ++L; } if(L <= (intt)sol.suf.size()-1 && (sag.pre[R].fi | sol.suf[L].fi) == (1 << k) - 1) { ret.ans = min(ret.ans, sag.pre[R].se - sol.suf[L].se + 1); } } // merging vector<pair<intt,intt>> newpre = sol.pre, newsuf = sag.suf; for(intt i = 0; i < (intt)sol.suf.size(); i++) { if(not newsuf.empty() && newsuf.back().fi == (sag.suf.back().fi | sol.suf[i].fi)) continue; newsuf.push_back({sag.suf.back().fi | sol.suf[i].fi, sol.suf[i].se}); } for(intt i = 0; i < sag.pre.size(); i++) { if(not newpre.empty() && newpre.back().fi == (sol.pre.back().fi | sag.pre[i].fi)) continue; newpre.push_back({sol.pre.back().fi | sag.pre[i].fi, sag.pre[i].se}); } ret.pre = newpre; ret.suf = newsuf; // if(ret.l == 1 && ret.r == 4) { // cout << "1 2" << endl; // for(auto u : ret.pre) { // cout << u.fi << " " << u.se << endl; // } // cout << endl; // for(auto u : ret.suf) { // cout << u.fi << " " << u.se << endl; // } // cout << ret.ans << endl; // } return ret; } void build(intt node, intt l, intt r) { if(l == r) { seg[node].l = seg[node].r = l; seg[node].pre.push_back({(1<<a[l]),l}); seg[node].suf.push_back({(1<<a[l]),r}); if(k == 1) seg[node].ans = 1; else seg[node].ans = inf; return; } intt mid = (l + r) / 2; build(node * 2, l, mid); build(node * 2 + 1, mid + 1, r); seg[node] = combine(seg[node * 2], seg[node * 2 + 1]); } void update(intt node, intt l, intt r, intt pos, intt val) { if(l == r) { --val; seg[node].pre.clear(); seg[node].pre.push_back({(1<<val), l}); seg[node].suf.clear(); seg[node].suf.push_back({(1<<val), r}); return; } intt mid = (l + r) / 2; if(pos <= mid) { update(node * 2, l, mid, pos, val); } else { update(node * 2 + 1, mid + 1, r, pos, val); } seg[node] = combine(seg[node*2], seg[node*2+1]); } nod get(intt node, intt l, intt r, intt ql, intt qr) { if(ql > r || qr < l || ql > qr) { nod temp; temp.l = l; temp.r = r; temp.ans = inf; temp.pre.clear(); temp.suf.clear(); return temp; } if(ql <= l && r <= qr) { return seg[node]; } intt mid = (l + r) / 2; nod left = get(node * 2, l, mid, ql, qr); nod right = get(node * 2 + 1, mid + 1, r, ql, qr); return combine(left, right); } void _() { cin >> n >> k >> m; a.resize(n+1); seg.resize(4*n+1); for(intt i = 1; i <= n; i++) { cin >> a[i]; --a[i]; } build(1, 1, n); while(m--) { intt type; cin >> type; if(type == 1) { intt pos, val; cin >> pos >> val; update(1, 1, n, pos, val); } else { nod boo = get(1, 1, n, 1, n); if(boo.ans == inf) { cout << -1 << endl; } else { cout << boo.ans << endl; } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); intt t = 1, buu = 1; // cin >> t; while(t--){ // cout << "Case #" << buu++ << ": "; _(); } }

nekameleoni.cpp:9:18: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    9 | const intt inf = 1e18;
      |                  ^~~~