#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define ll long long
#define ld long double
//#define int long long
#define endl "\n"
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define pb push_back
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int MOD = 1e9 + 7;
//const int MOD = 998244353 ;
const int N = 3e5 + 48;
const ll INF = 1e18;
const ll MIN = -1e18;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
int Tree[32 * N];
int l_child[32 * N];
int r_child[32 * N];
int lazy[32 * N];
int upd[32 * N];
int cnt;
int get_val(int id) {
if (id == -1)return 0;
return Tree[id];
}
int creat() {
Tree[cnt] = 0;
lazy[cnt] = 0;
upd[cnt] = 0;
l_child[cnt] = r_child[cnt] = -1;
return cnt++;
}
void unlazy(int id, int ns, int ne) {
if (id == -1)return;
if (upd[id] == 0) return;
if (l_child[id] == -1) {
l_child[id] = creat();
}
if (r_child[id] == -1) {
r_child[id] = creat();
}
Tree[id] = (ne - ns + 1);
lazy[l_child[id]] = lazy[r_child[id]] = lazy[id];
upd[id] = 0;
upd[r_child[id]] = upd[l_child[id]] = 1;
}
int query(int qs, int qe, int ns = 1, int ne = 1e9, int id = 0) {
if (id == -1)return 0;
unlazy(id, ns, ne);
if (ne < qs || ns > qe) return 0;
if (qs <= ns && ne <= qe) return Tree[id];
int idl = l_child[id], idr = r_child[id], md = ns + (ne - ns) / 2;
int one = query(qs, qe, ns, md, idl);
int two = query(qs, qe, md + 1, ne, idr);
return one + two;
}
int update(int qs, int qe, int val, int ns = 1, int ne = 1e9, int id = 0) {
unlazy(id, ns, ne);
if (qs > ne || qe < ns) return id;
if (id == -1)id = creat();
if (qs <= ns && ne <= qe) {
lazy[id] = val;
upd[id] = 1;
unlazy(id, ns, ne);
return id;
}
int md = ns + (ne - ns) / 2;
int idl = l_child[id];
int idr = r_child[id];
l_child[id] = update(qs, qe, val, ns, md, idl);
r_child[id] = update(qs, qe, val, md + 1, ne, idr);
Tree[id] = get_val(l_child[id]) + get_val(r_child[id]);
return id;
}
void solve() {
cnt = 0;
creat();
ll c = 0;
ll q;cin >> q;
while (q--) {
ll d, x, y; cin >> d >> x >> y;
if (d == 1) {
c = query(x + c, y + c);
cout << c << endl;
}
else {
update(x + c, y + c, 1);
}
}
}
signed main() {
FAST;
ll t = 1;
//cin>>t;
while (t--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |