Untitled
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