#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define mt make_tuple
#define mp make_pair
#define all(x) (x).begin(), (x).end()
const int N = 1e5 + 10;
const int LG = 32;
const int INF = 1e9 + 10;
const ll LL_INF = 1e18 + 10;
const ll MOD1 = 1e9 + 7;
const ll MOD2 = 998244353;
const int MAXN = 1e9 + 10, MAXV = 1e6 + 10;
int q, Num = 0, C = 0;
struct Node{
int cnt, sz, L, R;
bool lazy;
Node (int cnt = 0, int sz = 0, int L = -1, int R = -1, bool lazy = 0){
this -> cnt = cnt;
this -> sz = sz;
this -> L = L;
this -> R = R;
this -> lazy = lazy;
}
void Upd(){
cnt = sz;
lazy = 1;
}
void Shift(Node &n1, Node &n2){
if(!lazy){
return;
}
n1.Upd();
n2.Upd();
lazy = 0;
}
void Merge(Node &n1, Node &n2){
sz = n1.sz + n2.sz;
cnt = n1.cnt + n2.cnt;
}
};
vector<Node> seg;
int Left(int id){
if(seg[id].L != -1){
return seg[id].L;
}
seg[id].L = ++Num;
seg.push_back(Node (0, seg[id].sz >> 1));
return Num;
}
int Right(int id){
if(seg[id].R != -1){
return seg[id].R;
}
seg[id].R = ++Num;
seg.push_back(Node (0, (seg[id].sz >> 1) + (seg[id].sz & 1)));
return Num;
}
void shift(int id){
seg[id].Shift(seg[Left(id)], seg[Right(id)]);
}
void merge(int id){
seg[id].Merge(seg[Left(id)], seg[Right(id)]);
}
void update(int l, int r, int st = 0, int en = MAXN, int id = 0){
if(st >= r || en <= l){
return;
}
if(st >= l && en <= r){
seg[id].Upd();
return;
}
shift(id);
int mid = (st + en) >> 1;
update(l, r, st, mid, Left(id));
update(l, r, mid, en, Right(id));
merge(id);
}
int get(int l, int r, int st = 0, int en = MAXN, int id = 0){
if(st >= r || en <= l){
return 0;
}
if(st >= l && en <= r){
return seg[id].cnt;
}
shift(id);
int mid = (st + en) >> 1;
return get(l, r, st, mid, Left(id)) + get(l, r, mid, en, Right(id));
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> q;
seg.push_back(Node (0, MAXN));
while(q--){
int t, l, r;
cin >> t >> l >> r;
--l;
if(t == 1){
auto val = get(l + C, r + C);
cout << val << '\n';
C += val;
}
else{
update(l + C, r + C);
}
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
