#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <array>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <memory>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#ifdef DBG
#define dbg 1
#define dpf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
#define dbg 0
#define dpf(...) 42
#endif
#define SIZE(c) int((c).size())
#define REP(i,c) for(auto &i : (c))
#define ALL(c) (c).begin(),(c).end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
typedef long long i64;
typedef unsigned long long u64;
const double EPS = 1e-12;
const int INF = 1e9 + 10;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PI;
template <typename T> inline void UpdateMax(T& x, T v) { x = max(x, v); }
template <typename T> inline void UpdateMin(T& x, T v) { x = min(x, v); }
template <typename T>
using MinPQ = priority_queue<T, vector<T>, greater<T>>;
// Splay Tree base class.
// Works like map<K, V>, do not allow duplicate key.
template <typename K, typename V>
class BaseSplayTree {
public:
struct Node {
K k;
V v;
int p = 0; // parent
int ch[2] = {0,0}; // child
};
vector<Node> a;
BaseSplayTree(int init_capacity = 0) { Reset(init_capacity); }
void Reset(int init_capacity = 0) {
a.resize(1);
a[0] = null_node();
a.reserve(init_capacity + 1);
empty_idx.clear();
}
inline int Side(int u) { return a[a[u].p].ch[1] == u; }
int Splay(int u) {
assert(u > 0);
while (1) {
int pu = a[u].p;
if (!pu) break;
int ppu = a[pu].p;
if(ppu) {
if(Side(pu) == Side(u)) {
Rotate(pu);
} else {
Rotate(u);
}
}
Rotate(u);
}
return u;
}
// Returns u that a[u].k == k, or 0 not found.
int Find(int& root, K k) {
int u = root;
while (u) {
if (a[u].k == k) {
return root = Splay(u);
}
if(a[u].k > k) {
u = a[u].ch[0];
} else {
u = a[u].ch[1];
}
}
return 0;
}
// Returns u that a[u].k is min.
int FindMin(int& root) {
if (!root) return 0;
int u=root;
while (a[u].ch[0]) u = a[u].ch[0];
return root = Splay(u);
}
// Returns u that a[u].k is max.
int FindMax(int& root) {
if (!root) return 0;
int u = root;
while (a[u].ch[1]) u = a[u].ch[1];
return root = Splay(u);
}
// Gets the prev node of root, or 0 if not present.
int Prev(int& root) {
int u = a[root].ch[0];
while (a[u].ch[1]) u = a[u].ch[1];
if (u) root = Splay(u);
return u;
}
// Gets the next node of root, or 0 if not present.
int Next(int& root) {
int u = a[root].ch[1];
while (a[u].ch[0]) u = a[u].ch[0];
if (u) root = Splay(u);
return u;
}
// Returns u that a[u].k is maximal and < k, or 0 not found.
int Prev(int& root, K k) {
bool insert_res = Insert(root, k);
int u = a[root].ch[0];
while (a[u].ch[1]) u = a[u].ch[1];
if (insert_res) assert(Delete(root, k));
if (u) root = Splay(u);
return u;
}
// Returns u that a[u].k is minimal and > k, or 0 not found.
int Next(int& root, K k) {
bool insert_res = Insert(root, k);
int u = a[root].ch[1];
while (a[u].ch[0]) u = a[u].ch[0];
if (insert_res) assert(Delete(root, k));
if (u) root = Splay(u);
return u;
}
// Returns false if the key already exists.
bool Insert(int& root, K k) {
int u = root;
int side = 0;
if (root) {
while (1) {
if (k == a[u].k) {
root = Splay(u);
return 0;
}
if (k < a[u].k) side=0; else side=1;
if(!a[u].ch[side]) break;
u = a[u].ch[side];
}
}
int v = NewNodeIdx();
InitNode(a[v], k);
if (root) {
a[u].ch[side] = v, a[v].p = u;
} else {
root=v;
}
root = Splay(v);
return 1;
}
// Merges two trees, all values of tree u must less than v.
// Returns new root.
int Merge(int u, int v) {
assert(!a[u].p);
assert(!a[v].p);
if(u==0) return v;
if(v==0) return u;
u=FindMax(u);
assert(!a[u].ch[1]);
a[u].ch[1]=v; a[v].p=u;
Maintain(u);
return u;
}
// Returns false if k doesn't exist.
bool Delete(int& root, K k) {
int u = Find(root, k);
if(!u) return 0;
int v0 = a[u].ch[0], v1 = a[u].ch[1];
a[v0].p = a[v1].p = 0;
empty_idx.pb(u);
root = Merge(v0, v1);
return 1;
}
protected:
inline virtual Node null_node() { return Node(); }
inline virtual void InitValue(Node& u) {}
inline virtual void Maintain(int u) {}
private:
VI empty_idx;
int NewNodeIdx() {
int u;
if (!empty_idx.empty()) {
u = empty_idx.back();
empty_idx.pop_back();
} else {
u = SIZE(a);
a.emplace_back();
}
return u;
}
void InitNode(Node& u, K k) {
u.k = k;
u.p = u.ch[0] = u.ch[1] = 0;
InitValue(u);
}
void Rotate(int u) {
int pu = a[u].p;
if (!pu) return;
int ppu = a[pu].p;
int uside = Side(u);
int uch = a[u].ch[uside ^ 1];
if (ppu) a[ppu].ch[Side(pu)] = u;
a[u].p = ppu;
a[pu].ch[uside] = uch, a[uch].p = pu;
a[u].ch[uside ^ 1] = pu, a[pu].p = u;
Maintain(pu);
Maintain(u);
}
};
// Key is {l, r}. Value is {node count, subtree size}.
class SplayTree : public BaseSplayTree<PI, PI> {
public:
using K = PI;
using V = PI;
using Node = typename BaseSplayTree<K, V>::Node;
void UpdateNode(int u) {
a[u].v.first = a[u].k.second - a[u].k.first;
Maintain(u);
}
void Debug() {
if (!dbg) return;
for (int u = 1; u < SIZE(a); ++u) {
dpf("%d: %d %d, %d %d %d\n",
u, a[u].k.first, a[u].k.second, a[u].p, a[u].ch[0], a[u].ch[1]);
}
}
protected:
inline virtual Node null_node() {
Node u;
u.v = {0, 0};
return u;
}
inline virtual void InitValue(Node& u) {
u.v.second = u.v.first = u.k.second - u.k.first;
}
inline virtual void Maintain(int u) {
this->a[u].v.second = this->a[this->a[u].ch[0]].v.second +
this->a[this->a[u].ch[1]].v.second +
this->a[u].v.first;
}
};
SplayTree st;
int root;
int QueryRange(int lu, int ru) {
int res = st.a[lu].k.second - st.a[lu].k.first;
if (lu == ru) return res;
root = st.Splay(lu);
int lu_rch = st.a[lu].ch[1];
assert(lu_rch);
st.a[lu_rch].p = 0;
st.Splay(ru);
st.a[lu].ch[1] = ru, st.a[ru].p = lu;
res += st.a[ru].v.second - st.a[st.a[ru].ch[1]].v.second;
return res;
}
int Query(int l,int r) {
st.Debug();
if (l >= r) return 0;
int res = 0;
int lu = 0, ru = 0;
int u = st.Prev(root, {l, INF});
dpf("start u: %d, %d %d\n", u, st.a[u].k.first, st.a[u].k.second);
if(u) {
if (st.a[u].k.second > l) {
if(st.a[u].k.second >= r) {
res += r - l;
return res;
}
res += st.a[u].k.second - l;
}
lu = st.Next(root);
} else {
lu = st.FindMin(root);
}
u = st.Prev(root, {r, -INF});
dpf("end u: %d, %d %d\n", u, st.a[u].k.first, st.a[u].k.second);
if (u) {
if (st.a[u].k.second >= r) {
res += r - st.a[u].k.first;
ru = st.Prev(root);
} else {
ru = u;
}
} else {
ru = 0;
}
dpf("lu: %d, %d %d\n", lu, st.a[lu].k.first, st.a[lu].k.second);
dpf("ru: %d, %d %d\n", ru, st.a[ru].k.first, st.a[ru].k.second);
if (lu && ru && st.a[lu].k <= st.a[ru].k) res += QueryRange(lu, ru);
return res;
}
void Add(int l, int r) {
if (l >= r) return;
int u = st.Prev(root, {l, INF});
if (u && st.a[u].k.second >= l) {
if (st.a[u].k.second >= r) return;
st.a[u].k.second = r;
st.UpdateNode(u);
} else {
st.Insert(root, {l, r});
u = root;
}
while (1) {
int v = st.Next(root, st.a[u].k);
if (!v || st.a[v].k.first > st.a[u].k.second) break;
root = st.Splay(u);
UpdateMax(st.a[u].k.second, st.a[v].k.second);
st.UpdateNode(u);
st.Delete(root, st.a[v].k);
}
}
void Solve() {
int nq;
scanf("%d",&nq);
st.Reset(nq);
root = 0;
int C = 0;
while(nq--) {
int t,l,r;
scanf("%d%d%d",&t,&l,&r);
dpf("Query %d %d %d\n", t, l, r);
l += C, r += 1 + C;
if(t==1) {
C = Query(l, r);
printf("%d\n",C);
} else {
Add(l, r);
}
// st.Debug();
}
}
int main() {
int t = 1;
// scanf("%d", &t);
for (int i = 1; i <= t; ++i) {
Solve();
}
return 0;
}
Compilation message
apple.cpp: In member function 'void SplayTree::Debug()':
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
32 | #define dpf(...) 42
| ^~
apple.cpp:274:7: note: in expansion of macro 'dpf'
274 | dpf("%d: %d %d, %d %d %d\n",
| ^~~
apple.cpp: In function 'int Query(int, int)':
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
32 | #define dpf(...) 42
| ^~
apple.cpp:322:3: note: in expansion of macro 'dpf'
322 | dpf("start u: %d, %d %d\n", u, st.a[u].k.first, st.a[u].k.second);
| ^~~
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
32 | #define dpf(...) 42
| ^~
apple.cpp:337:3: note: in expansion of macro 'dpf'
337 | dpf("end u: %d, %d %d\n", u, st.a[u].k.first, st.a[u].k.second);
| ^~~
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
32 | #define dpf(...) 42
| ^~
apple.cpp:349:3: note: in expansion of macro 'dpf'
349 | dpf("lu: %d, %d %d\n", lu, st.a[lu].k.first, st.a[lu].k.second);
| ^~~
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
32 | #define dpf(...) 42
| ^~
apple.cpp:350:3: note: in expansion of macro 'dpf'
350 | dpf("ru: %d, %d %d\n", ru, st.a[ru].k.first, st.a[ru].k.second);
| ^~~
apple.cpp: In function 'void Solve()':
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
32 | #define dpf(...) 42
| ^~
apple.cpp:387:5: note: in expansion of macro 'dpf'
387 | dpf("Query %d %d %d\n", t, l, r);
| ^~~
apple.cpp:379:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
379 | scanf("%d",&nq);
| ~~~~~^~~~~~~~~~
apple.cpp:386:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
386 | scanf("%d%d%d",&t,&l,&r);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
4 ms |
460 KB |
Output is correct |
| 5 |
Correct |
5 ms |
492 KB |
Output is correct |
| 6 |
Correct |
4 ms |
460 KB |
Output is correct |
| 7 |
Correct |
4 ms |
460 KB |
Output is correct |
| 8 |
Correct |
21 ms |
700 KB |
Output is correct |
| 9 |
Correct |
42 ms |
912 KB |
Output is correct |
| 10 |
Correct |
43 ms |
824 KB |
Output is correct |
| 11 |
Correct |
47 ms |
836 KB |
Output is correct |
| 12 |
Correct |
41 ms |
928 KB |
Output is correct |
| 13 |
Correct |
45 ms |
960 KB |
Output is correct |
| 14 |
Correct |
46 ms |
1024 KB |
Output is correct |
| 15 |
Correct |
46 ms |
1096 KB |
Output is correct |
| 16 |
Correct |
47 ms |
1152 KB |
Output is correct |
| 17 |
Correct |
43 ms |
964 KB |
Output is correct |
| 18 |
Correct |
44 ms |
932 KB |
Output is correct |
| 19 |
Correct |
46 ms |
1024 KB |
Output is correct |
| 20 |
Correct |
45 ms |
960 KB |
Output is correct |
