#include <bits/stdc++.h>
using namespace std;
struct node{
long long lc=-1;
long long rc=-1;
long long val=0;
};
template<class node> class lazySegTree{
private:
long long n;
node *st;
long long *laz;
long long cn=1;
public:
lazySegTree(long long siz, long long maxnode){
st = new node[maxnode];
laz = new long long[maxnode];
node def;
def.lc=-1;
def.rc=-1;
def.val=0;
fill(st,st+maxnode,def);
n=siz;
fill(laz,laz+maxnode,0);
makeKids(0);
}
void makeKids(long long ind){
if(st[ind].lc==-1||st[ind].rc==-1){
st[ind].lc=cn++;
st[ind].rc=cn++;
}
}
void push(long long ind, long long l, long long r){
if(l!=r)
makeKids(ind);
if(laz[ind]!=0){
st[ind].val=laz[ind]*(r-l+1);
if(l!=r){
laz[st[ind].lc]=laz[ind];
laz[st[ind].rc]=laz[ind];
}
laz[ind]=0;
}
}
void realUpdate(long long l, long long r, long long s, long long e, long long ind, long long val){
//l-r is real range, s-e is to be updated
push(ind,l,r);
if(l>e||r<s){
return;
}
if(s<=l&&r<=e){
st[ind].val=val*(r-l+1);
laz[st[ind].lc]=val;
laz[st[ind].rc]=val;
return;
}
long long mid = (l+r)/2;
realUpdate(l,mid,s,e,st[ind].lc,val);
realUpdate(mid+1,r,s,e,st[ind].rc,val);
st[ind].val=st[st[ind].lc].val+st[st[ind].rc].val;
}
void update(long long l, long long r, long long val){
realUpdate(0,n,l,r,0,val);
}
long long realQuery(int l, int r, int s, int e, int ind){
//l-r is real range, s-e is query
push(ind,l,r);
if(e<l||s>r)
return 0;
if(s<=l&&r<=e){
return st[ind].val;
}
long long mid = (l+r)/2;
return realQuery(l,mid,s,e,st[ind].lc)+realQuery(mid+1,r,s,e,st[ind].rc);
}
long long query(long long l, long long r){
return realQuery(0,n,l,r,0);
}
};
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int m;
cin >> m;
long long c=0;
lazySegTree<node> lst((long long)1e12,(long long)(64*1e5));
while(m--){
long long d,x,y;
cin >> d >> x >> y;
if(d==2){
lst.update(x+c,y+c,1);
}
else{
c = lst.query(x+c,y+c);
cout << c << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
200776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
