#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int val,laz,tl,tr;
int lc,rc;
bool has;
node(){
val=0; laz=0; tl=0; tr=0; lc=0; rc=0; has=0;
}
};
node seg[4000000];
int cnt;
void pushdown(int id){
int tm=(seg[id].tl+seg[id].tr)/2;
if (!seg[id].lc){
cnt++;
seg[id].lc=cnt;
seg[cnt].tl=seg[id].tl;
seg[cnt].tr=tm;
}
if (!seg[id].rc){
cnt++;
seg[id].rc=cnt;
seg[cnt].tl=tm+1;
seg[cnt].tr=seg[id].tr;
}
seg[seg[id].lc].val=seg[id].laz*(tm-seg[id].tl+1);
seg[seg[id].rc].val=seg[id].laz*(seg[id].tr-tm+1);
seg[seg[id].lc].laz=seg[id].laz;
seg[seg[id].rc].laz=seg[id].laz;
seg[seg[id].lc].has=1;
seg[seg[id].rc].has=1;
seg[id].has=0;
}
void update(int id,int l,int r,int v){
if (l>r) return;
if (l<=seg[id].tl&&seg[id].tr<=r){
seg[id].val=v*(seg[id].tr-seg[id].tl+1);
seg[id].laz=v;
seg[id].has=1;
return;
}
if (seg[id].has) pushdown(id);
int tm=(seg[id].tl+seg[id].tr)/2;
if (!seg[id].lc){
cnt++;
seg[id].lc=cnt;
seg[cnt].tl=seg[id].tl;
seg[cnt].tr=tm;
}
update(seg[id].lc,l,min(r,tm),v);
if (!seg[id].rc){
cnt++;
seg[id].rc=cnt;
seg[cnt].tl=tm+1;
seg[cnt].tr=seg[id].tr;
}
update(seg[id].rc,max(l,tm+1),r,v);
seg[id].val=(seg[id].lc?seg[seg[id].lc].val:0ll)+(seg[id].rc?seg[seg[id].rc].val:0ll);
}
int query(int id,int l,int r){
if (l>r) return 0;
if (l<=seg[id].tl&&seg[id].tr<=r) return seg[id].val;
if (seg[id].has) pushdown(id);
int tm=(seg[id].tl+seg[id].tr)/2;
int lx=(seg[id].lc?query(seg[id].lc,l,min(r,tm)):0ll);
int rx=(seg[id].rc?query(seg[id].rc,max(l,tm+1),r):0ll);
return lx+rx;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int q;
cin>>q;
seg[1].tl=1; seg[1].tr=1e9;
cnt++;
int c=0;
while (q--){
int type,l,r;
cin>>type>>l>>r;
l+=c; r+=c;
if (type==1){
c=query(1,l,r);
cout<<c<<'\n';
} else {
update(1,l,r,1);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
219468 KB |
Output is correct |
| 2 |
Incorrect |
97 ms |
219404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
