Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ┓┏┓┏┓┃
- ┛┗┛┗┛┃
- ┓┏┓┏┓┃
- ┛┗┛┗┛┃
- ┓┏┓┏┓┃\○/
- ┛┗┛┗┛┃ / /
- ┓┏┓┏┓┃ノ
- ┛┗┛┗┛┃
- ┓┏┓┏┓┃
- ┛┗┛┗┛┃
- ┓┏┓┏┓┃
- ┛┗┛┗┛┃
- ┓┏┓┏┓┃
- ┛┗┛┗┛┃
- ┓┏┓┏┓┃┓
- ┛┗┛┗┛┃┃
- MIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSIC
- */
- // #define pragma
- #ifdef pragma
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC diagnostic ignored "-Wunused-result"
- #endif // pragma
- #include<bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define ll long long
- #define all(x) begin(x), end(x)
- #define pb push_back
- #define x first
- #define y second
- #define int long long
- #define zero(two) memset(two, 0, sizeof(two))
- using namespace std;
- using namespace __gnu_pbds;
- typedef vector<int> vi;
- typedef vector<bool> vb;
- typedef pair<int, int> pii;
- typedef long double ld;
- typedef vector<vi> matrix;
- template<typename T>
- using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- const ld PI = atan2(0, -1);
- void seriy() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cout << fixed << setprecision(10);
- #if 1
- freopen("input", "r", stdin);
- freopen("output", "w", stdout);
- #endif
- }
- struct rrq {
- int l, r, id, tp;
- };
- const int INF = 1e9 + 7;
- const int MAXN = 1e6 + 100;
- int k;
- vi a, ccc(MAXN);
- int curpos = 0;
- bool cmp(rrq a, rrq b) {
- if(a.l / k != b.l / k) {
- return a.l < b.l;
- }
- return a.r < b.r;
- }
- void addLeft(int pos) {
- pos = a[pos];
- ccc[pos]++;
- if(pos == curpos) {
- while(ccc[curpos]) {
- curpos++;
- }
- }
- }
- void addRight(int pos) {
- addLeft(pos);
- }
- void delLeft(int pos) {
- pos = a[pos];
- ccc[pos]--;
- if(ccc[pos] == 0 && pos < curpos) {
- curpos = pos;
- }
- }
- void delRight(int pos) {
- delLeft(pos);
- }
- int answer() {
- return curpos;
- }
- signed main() {
- seriy();
- int n, q;
- cin >> n >> q;
- a.resize(n);
- int mxx = 0;
- for(int i = 0; i < n; i++) {
- cin >> a[i];
- mxx = max(mxx, a[i]);
- }
- vector<char> rq(q);
- vi l(q), r(q);
- bool wasAssign = 0;
- vector<rrq> rqs(q);
- for(int i = 0; i < q; i++) {
- cin >> rq[i];
- cin >> l[i] >> r[i];
- if(rq[i] == '!') {
- mxx = max(mxx, r[i]);
- wasAssign = 1;
- }
- else {
- l[i]--, r[i]--;
- }
- rqs[i] = {l[i], r[i], i, tp};
- // cerr << mxx << " " << (rq[i] == '!' && r[i] > 10) << " " << r[i] << '\n';
- }
- int num = 0;
- if(!wasAssign) {
- k = sqrt(n);
- sort(all(rqs), cmp);
- vi ans(q);
- int curl = 1, curr = 0;
- for(int i = 0; i < q; i++) {
- while(curl > rqs[i].l) {
- curl--;
- addLeft(curl);
- }
- while(curr < rqs[i].r) {
- curr++;
- addRight(curr);
- }
- while(curl < rqs[i].l) {
- delLeft(curl);
- curl++;
- }
- while(curr > rqs[i].r) {
- delRight(curr);
- curr--;
- }
- ans[rqs[i].id] = answer();
- }
- for(auto i : ans) {
- cout << i << '\n';
- }
- }
- else if(mxx > 10) {
- while(q--) {
- if(rq[num] == '?') {
- int mn = INF, mx = 0;
- vi cnt(MAXN + 1);
- for(int i = l[num]; i <= r[num]; i++) {
- mn = min(mn, a[i]);
- mx = max(mx, a[i]);
- cnt[a[i]]++;
- }
- int ans = MAXN;
- for(int i = mn; i < MAXN; i++) {
- if(!cnt[i]) {
- ans = i;
- break;
- }
- }
- if(mn == 0) {
- cout << ans << '\n';
- }
- else {
- cout << "0\n";
- }
- }
- else {
- l[num]--;
- a[l[num]] = r[num];
- }
- num++;
- }
- }
- else {
- vector<set<int>> vs(11);
- for(int i = 0; i < n; i++) {
- vs[a[i]].insert(i);
- }
- while(q--) {
- if(rq[num] == '?') {
- int ans = 11;
- for(int i = 0; i < 11; i++) {
- // cerr << (vs[i].lower_bound(l[num]) == vs[i].end()) << '\n';
- if(vs[i].lower_bound(l[num]) == vs[i].end() || (*vs[i].lower_bound(l[num])) > r[num]) {
- ans = i;
- break;
- }
- }
- // cerr << '\n';
- cout << ans << '\n';
- }
- else {
- l[num]--;
- int ans = 0;
- for(int i = 0; i < 11; i++) {
- if(vs[i].lower_bound(l[num]) != vs[i].end() && (*vs[i].lower_bound(l[num])) == l[num]) {
- ans = i;
- break;
- }
- }
- vs[ans].erase(l[num]);
- vs[r[num]].insert(l[num]);
- }
- num++;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement