Untitled

 avatar
unknown
c_cpp
9 days ago
1.8 kB
3
Indexable
#include <bits/stdc++.h>
using namespace std;

const int N = 5e+5;

int cnt[N];
set<array<int,2>> ind;
set<array<int,2>> rng[N];

int main() 
{
    int n, q;
    cin >> n >> q;
    for(int i = 0; i < n; ++i){
      cnt[i] = 1;
      ind.insert({i, i});
      rng[i].insert({i, i});
    }
    
    auto apply = [&](int x, int tc) -> void{
        auto driveStart = *prev(ind.upper_bound({x, n}));
        int index = driveStart[0];
        int color = driveStart[1];
        if(color == tc) return;
        ind.erase(ind.find(driveStart));
        
        auto colorRange = *rng[color].lower_bound({index, 0});
        rng[color].erase(colorRange);
        
        array<int,2> curRng = colorRange;
        int startIndex = curRng[0];

        cnt[color] -= curRng[1]-curRng[0]+1;
        cnt[tc] += curRng[1]-curRng[0]+1;
        
        auto nextRng = rng[tc].upper_bound({index, n});
        auto prevRng (nextRng != rng[tc].begin() ? prev(nextRng) : rng[tc].end());
        if(nextRng != rng[tc].end() && (*nextRng)[0] == curRng[1] + 1){
          ind.erase({curRng[1] + 1, tc});
          curRng[1] = (*nextRng)[1];
          rng[tc].erase(nextRng);
        }

        if(prevRng != rng[tc].end() && (*prevRng)[1] == curRng[0] - 1){
            curRng[0] = (*prevRng)[0];
            startIndex = curRng[0];
            ind.erase({(*prevRng)[0], tc});
            rng[tc].erase(prevRng);
        }
        
        rng[tc].insert(curRng);
        ind.insert({startIndex, tc});
    };
    
    
    for(int i = 0; i < q; ++i){
      int t, x, c;
      cin >> t;
      if(t==1){
        cin >> x >> c;
        --x, --c;
        apply(x, c);
      } else {
        cin >> c;
        cout << cnt[--c] << '\n';
      }
      
    }
    return 0;
}
Editor is loading...
Leave a Comment