Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Слава Україні, Героям слава
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 1e5 + 7, L = 20;
- const int M = 4 * N * L;
- const int INF = 1e9 + 7;
- namespace dseg {
- long long seg[M];
- int L[M], R[M], cnt = 2;
- void insert(int x, long long val, int p = 1, int l = 1, int r = INF) {
- seg[p] += val;
- if(l == r) {
- return;
- }
- int mid = (l + r) >> 1;
- if(x <= mid) {
- if(!L[p]) {
- L[p] = cnt++;
- }
- insert(x, val, L[p], l, mid);
- } else {
- if(!R[p]) {
- R[p] = cnt++;
- }
- insert(x, val, R[p], mid + 1, r);
- }
- }
- long long sum(int i, int j, int p = 1, int l = 1, int r = INF) {
- if(i > r or j < l) {
- return 0;
- }
- if(i <= l and r <= j) {
- return seg[p];
- }
- int mid = (l + r) >> 1;
- return sum(i, j, L[p], l, mid) + sum(i, j, R[p], mid + 1, r);
- }
- };
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int n, m, q;
- cin >> n >> m >> q;
- set<pair<long long, long long>> s;
- vector<int> v(m);
- for(int i = 0; i < m; i++) {
- cin >> v[i];
- }
- sort(v.begin(), v.end());
- for(int i = 0; i < m; i++) {
- int x = v[i];
- if(s.empty()) {
- s.insert({x, x});
- continue;
- }
- auto itr = s.end(); itr--;
- if(itr->second + 1 == x) {
- int l = itr->first;
- s.erase(itr);
- s.insert({l, x});
- } else {
- s.insert({x, x});
- }
- }
- for(auto e : s) {
- dseg::insert(e.first, (e.second - e.first + 1) * (e.second - e.first + 1));
- }
- while(q--) {
- string ss;
- cin >> ss;
- if(ss == "go") {
- int l, r;
- cin >> l >> r;
- if(l > r) {
- swap(l, r);
- }
- cout << dseg::sum(l, r) << "\n";
- } else if(ss == "add") {
- int x;
- cin >> x;
- auto itr = s.upper_bound({x, 0});
- itr--;
- auto tmp = *itr;
- if(itr->first < x and itr->second > x) {
- s.erase(itr);
- dseg::insert(tmp.first, -1ll * (tmp.second - tmp.first + 1) * (tmp.second - tmp.first + 1));
- s.insert({tmp.first, x - 1});
- dseg::insert(tmp.first, (x - 1 - tmp.first + 1) * (x - 1 - tmp.first + 1));
- s.insert({x + 1, tmp.second});
- dseg::insert(x + 1, (tmp.second - x - 1 + 1) * (tmp.second - x - 1 + 1));
- } else if(itr->first == x and itr->second > x) {
- s.erase(itr);
- dseg::insert(tmp.first, -1ll * (tmp.second - tmp.first + 1) * (tmp.second - tmp.first + 1));
- s.insert({x + 1, tmp.second});
- dseg::insert(x + 1, (tmp.second - x - 1 + 1) * (tmp.second - x - 1 + 1));
- } else if(itr->second == x and itr->first < x) {
- s.erase(itr);
- dseg::insert(tmp.first, -1ll * (tmp.second - tmp.first + 1) * (tmp.second - tmp.first + 1));
- s.insert({tmp.first, x - 1});
- dseg::insert(tmp.first, (x - 1 - tmp.first + 1) * (x - 1 - tmp.first + 1));
- } else {
- s.erase(itr);
- dseg::insert(tmp.first, -1 * (tmp.second - tmp.first + 1) * (tmp.second - tmp.first + 1));
- }
- } else if(ss == "rem") {
- int x;
- cin >> x;
- auto itr = s.lower_bound({x, 0});
- bool j = false;
- if(itr != s.end()) {
- if(itr->first == x + 1) {
- j = true;
- auto tmp = *itr;
- s.erase(itr);
- dseg::insert(tmp.first, -1ll * (tmp.second - tmp.first + 1) * (tmp.second - tmp.first + 1));
- s.insert({x, tmp.second});
- dseg::insert(x, (tmp.second - x + 1) * (tmp.second - x + 1));
- }
- }
- itr = s.lower_bound({x, 0});
- if(itr != s.begin()) {
- itr--;
- if(itr->second == x - 1) {
- if(j) {
- long long l = itr->first;
- itr++;
- long long r = itr->second;
- auto tmp = itr;
- itr--;
- dseg::insert(itr->first, -1ll * (itr->second - itr->first + 1) * (itr->second - itr->first + 1));
- dseg::insert(tmp->first, -1ll * (tmp->second - tmp->first + 1) * (tmp->second - tmp->first + 1));
- s.erase(itr);
- s.erase(tmp);
- s.insert({l, r});
- dseg::insert(l, (r - l + 1) * (r - l + 1));
- } else {
- j = true;
- auto tmp = *itr;
- dseg::insert(itr->first, -1ll * (itr->second - itr->first + 1) * (itr->second - itr->first + 1));
- s.erase(itr);
- s.insert({tmp.first, x});
- dseg::insert(tmp.first, (x - tmp.first + 1) * (x - tmp.first + 1));
- }
- }
- }
- if(!j) {
- s.insert({x, x});
- dseg::insert(x, 1);
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement