#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define vl vector<ll>
#define fi first
#define se second
#define in insert
#define mpr make_pair
#define lg(x) __lg(x)
#define bpc(x) __builtin_popcount(x)
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int mod = 998244353;
const int sz = 3e5+5; /// mind the sz
/*struct BIT{
vl e;
void init(ll n){
e.assign(n+1, -1);
}
ll base(ll x){
if(e[x] < 0){
return x;
}
return e[x] = base(e[x]);
}
bool unite(ll a, ll b){
a = base(a);
b = base(b);
if(a == b){return false;}
if(e[a] > e[b]){swap(a, b);}
}
};*/
struct Node{
ll data = 0;
Node *left = nullptr;
Node *right = nullptr;
bool ok = 0;
};
void update(ll tl, ll tr, ll l, ll r, Node *cur){
if( tl > r || tr < l ){return ;}
if(tl >= l && tr <= r){
cur -> ok = 1;
cur -> data = (tr - tl + 1);
return ;
}
ll tm = (tl + tr)>>1;
if(cur -> left == nullptr){
cur -> left = new Node;
}
update(tl, tm, l, r, cur->left);
if(cur -> right == nullptr){
cur -> right = new Node;
}
update(tm+1, tr, l, r, cur->right);
if(cur -> ok && cur -> data > 0){
update(tl, tm, tl, tm, cur -> left);
update(tm+1, tr, tm+1, tr, cur -> right);
}
cur -> data = (cur -> left -> data + cur -> right -> data);
}
ll get(ll tl, ll tr, ll l, ll r, Node *cur){
if( tl > r || tr < l){
return 0;
}
if(tl >= l && tr <= r){
return (cur->data);
}
if( tl <= l && tr >= r && (cur -> data == (tr - tl + 1))){
return (r - l + 1);
}
ll tm = (tl + tr) >> 1;
if(cur -> ok && cur -> data > 0){
if(cur -> left == nullptr){
cur -> left = new Node;
}
update(tl, tm, tl, tm, cur -> left);
if(cur -> right == nullptr){
cur -> right = new Node;
}
update(tm + 1, tr, tm + 1, tr, cur -> right);
}
ll ret1 = 0, ret2 = 0;
if(cur->left != nullptr){
ret1 = get(tl, tm, l, r, cur->left);
}
if(cur->right != nullptr){
ret2 = get(tm+1, tr, l, r, cur->right);
}
return ret1 + ret2;
}
void solve()
{
ll m, i, j, l, r, type;
ll n = 1, c = 0;
while(n < 1e9){n <<= 1;}
n <<= 1;
cin>>m;
Node *root = new Node;
for(i=1;i<=m;i++){
cin>>type>>l>>r;
if(type == 1){
ll ret = get(1, n, l + c, r + c, root);
cout << ret << endl;
c += ret;
}
else{
update(1, n, l + c, r + c, root);
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//precomp();
ll tst=1;
//cin>>tst;
while(tst--){
solve();
}
}
/*
ok.
*/
Compilation message
apple.cpp: In function 'void solve()':
apple.cpp:96:14: warning: unused variable 'j' [-Wunused-variable]
96 | ll m, i, j, l, r, type;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
