#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define stdI freopen("input.txt", "r", stdin);
#define stdO freopen("output.txt", "w", stdout);
#define all(x) x.begin(), x.end()
#define mp(x, y) make_pair(x, y)
#define int long long
#define F first
#define S second
#ifdef OMAIN
#include <tools/debug.h>
#else
#define dbg(...)
#define ddbg(...)
#endif
using namespace std;
using namespace __gnu_pbds;
template<typename T, template<typename> class order = less>
using ordered_set = tree<T,
null_type, order<T>, rb_tree_tag,
tree_order_statistics_node_update>;
typedef pair<int, int> pii;
const int MAXN = 1 << 30, MAXLOG = 18, MAXSQ = 500, INF = 1e18, MOD = 1e9 + 7;
struct segment
{
struct node
{
int q = 0, lzy = 0, lc = -1, rc = -1;
};
vector<node> sg; int root;
segment()
{
sg.emplace_back(); root = 0;
}
void push(int v, int vl, int vr)
{
if(sg[v].lzy != 0)
{
sg[v].q = sg[v].lzy; sg[v].lzy = 0;
if(vl == vr)
{
return;
}
if(sg[v].lc == -1)
{
sg[v].lc = sg.size(); sg.emplace_back();
}
if(sg[v].rc == -1)
{
sg[v].rc = sg.size(); sg.emplace_back();
}
int val = (vr - vl + 1) >> 1;
sg[sg[v].lc].lzy = sg[sg[v].rc].lzy = val;
}
}
void update(int v, int vl, int vr, int l, int r)
{
if(v == -1)
{
return;
}
push(v, vl, vr);
if(vl > r || vr < l)
{
return;
}
if(l <= vl && vr <= r)
{
sg[v].lzy = vr - vl + 1;
push(v, vl, vr);
return;
}
int mid = (vl + vr) >> 1;
if(sg[v].lc == -1)
{
sg[v].lc = sg.size(); sg.emplace_back();
}
if(sg[v].rc == -1)
{
sg[v].rc = sg.size(); sg.emplace_back();
}
update(sg[v].lc, vl, mid, l, r); update(sg[v].rc, mid + 1, vr, l, r);
int lq = sg[v].lc == -1 ? 0 : sg[sg[v].lc].q;
int rq = sg[v].rc == -1 ? 0 : sg[sg[v].rc].q;
sg[v].q = lq + rq;
}
int get(int v, int vl, int vr, int l, int r)
{
if(v == -1)
{
return 0;
}
push(v, vl, vr);
if(vl > r || vr < l)
{
return 0;
}
if(l <= vl && vr <= r)
{
return sg[v].q;
}
int mid = (vl + vr) >> 1;
return get(sg[v].lc, vl, mid, l, r) + get(sg[v].rc, mid + 1, vr, l, r);
}
} s;
void solve()
{
int q, c = 0; cin >> q;
while(q--)
{
int tp; cin >> tp;
if(tp == 1)
{
int l, r; cin >> l >> r; l += c - 1; r += c - 1;
c = s.get(0, 0, MAXN - 1, l, r);
cout << c << "\n";
}
else
{
int l, r; cin >> l >> r; l += c - 1; r += c - 1;
s.update(0, 0, MAXN - 1, l, r);
}
}
}
int32_t main()
{
IOS;
int t = 1;
//cin >> t;
while(t--)
{
solve();
}
#ifdef OMAIN
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |