#include <iostream>
#include <set>
using namespace std;
using ll = long long;
const int kInf = 1e9;
const int kMod = 1e9 + 7;
void maxSelf(int &x, int y) {
if(y > x) {
x = y;
}
}
void minSelf(int &x, int y) {
if(y < x) {
x = y;
}
}
void addSelf(int &x, int y, int mod) {
x += y;
x %= mod;
}
int add(int x, int y, int mod) {
addSelf(x, y, mod);
return x;
}
struct Chtholly {
struct Node {
int l, r;
mutable ll v;
Node() {}
Node(int l, int r = -1, ll v = 0): l(l), r(r), v(v) {}
bool operator < (const Node &oth) const {
return l < oth.l;
}
};
int n;
set<Node> tree;
Chtholly() {}
Chtholly(int n): n(n) {
tree.emplace(0, n);
}
Chtholly(int n, const vector<int> &v): n(n) {
init(v);
}
void init(const vector<int> &v) {
for(int i = 0; i < n; i++) {
tree.emplace(i, i, v[i]);
}
tree.emplace(n, n, 0);
}
set<Node>::iterator split(int x) {
auto it = tree.lower_bound(Node(x));
if(it != tree.end() && it->l == x) {
return it;
}
// assert(it != tree.begin());
it = prev(it);
if(it->r < x) {
return tree.end();
}
int l = it->l, r = it-> r;
ll v = it->v;
tree.erase(it);
tree.emplace(l, x - 1, v);
return tree.emplace(x, r, v).first;
}
void flatten(int l, int r, int v) {
auto L = split(l), R = split(r + 1);
tree.erase(L, R);
tree.emplace(l, r, v);
}
void add(int l, int r, int v) {
auto L = split(l), R = split(r + 1);
while(L != R) {
L->v += v;
L = next(L);
}
}
int query_sum(int l, int r) {
auto L = split(l), R = split(r + 1);
int res = 0;
while(L != R) {
res += L->v * (L->r - L->l + 1);
L = next(L);
}
return res;
}
int query_max(int l, int r) {
auto L = split(l), R = split(r + 1);
int res = -kInf;
while(L != R) {
maxSelf(res, L->v);
L = next(L);
}
return res;
}
int query_min(int l, int r) {
auto L = split(l), R = split(r + 1);
int res = kInf;
while(L != R) {
minSelf(res, L->v);
L = next(L);
}
return res;
}
int query_kth(int l, int r, int k) {
auto L = split(l), R = split(r + 1);
vector<pair<int, int>> v;
while(L != R) {
v.emplace_back(L->v, L->r - L->l + 1);
L = next(L);
}
sort(v.begin(), v.end());
for(const auto &it: v) {
k -= it.second;
if(k <= 0) {
return it.first;
}
}
return v.back().first;
}
};
int main() {
#ifndef EVAL
freopen("f.in", "r", stdin);
freopen("f.out", "w", stdout);
#endif
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
Chtholly ds(1e9);
int c = 0;
for(int i = 0; i < n; i++) {
int t, l, r;
cin >> t >> l >> r;
l += c;
r += c;
if(t == 2) {
ds.flatten(l, r, 1);
} else {
int res = ds.query_sum(l, r);
cout << res << '\n';
c += res;
}
}
return 0;
}
Compilation message
apple.cpp:49:27: error: 'vector' does not name a type
49 | Chtholly(int n, const vector<int> &v): n(n) {
| ^~~~~~
apple.cpp:49:33: error: expected ',' or '...' before '<' token
49 | Chtholly(int n, const vector<int> &v): n(n) {
| ^
apple.cpp:52:21: error: 'vector' does not name a type
52 | void init(const vector<int> &v) {
| ^~~~~~
apple.cpp:52:27: error: expected ',' or '...' before '<' token
52 | void init(const vector<int> &v) {
| ^
apple.cpp: In constructor 'Chtholly::Chtholly(int, int)':
apple.cpp:50:14: error: 'v' was not declared in this scope
50 | init(v);
| ^
apple.cpp: In member function 'void Chtholly::init(int)':
apple.cpp:54:32: error: 'v' was not declared in this scope
54 | tree.emplace(i, i, v[i]);
| ^
apple.cpp: In member function 'int Chtholly::query_kth(int, int, int)':
apple.cpp:115:9: error: 'vector' was not declared in this scope
115 | vector<pair<int, int>> v;
| ^~~~~~
apple.cpp:3:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
2 | #include <set>
+++ |+#include <vector>
3 |
apple.cpp:115:29: error: expected primary-expression before '>' token
115 | vector<pair<int, int>> v;
| ^~
apple.cpp:115:32: error: 'v' was not declared in this scope
115 | vector<pair<int, int>> v;
| ^
apple.cpp:120:9: error: 'sort' was not declared in this scope; did you mean 'qsort'?
120 | sort(v.begin(), v.end());
| ^~~~
| qsort
