#include<bits/stdc++.h>
using namespace std;
int tree[3000005],lazy[3000005],ki[3000005],ka[3000005],node=2;
void updatenode(int now,int L,int R){
tree[now]=R-L+1;
lazy[now]=1;
}
void pushdown(int now,int L,int R){
if(lazy[now]==0)return;
if(ki[now]==0){
ki[now]=node;
node++;
}
if(ka[now]==0){
ka[now]=node;
node++;
}
int mid=(L+R)/2;
updatenode(ki[now],L,mid);
updatenode(ka[now],mid+1,R);
lazy[now]=0;
}
void update(int now,int L,int R,int x,int y){
if(tree[now]==R-L+1)return;
if(L>=x && R<=y){
updatenode(now,L,R);
return;
}
if(L>y || R<x)return;
int mid=(L+R)/2;
pushdown(now,L,R);
update(ki[now],L,mid,x,y);
update(ka[now],mid+1,R,x,y);
tree[now]=tree[ki[now]]+tree[ka[now]];
}
int query(int now,int L,int R,int x,int y){
if(L>=x && R<=y){
return tree[now];
}
if(L>y || R<x || now==0)return 0;
pushdown(now,L,R);
int mid=(L+R)/2;
return query(ki[now],L,mid,x,y)+query(ka[now],mid+1,R,x,y);
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int q,op,x,y,c=0;
cin >> q;
while(q--){
cin >> op >> x >> y;
x+=c;
y+=c;
if(op==1){
c=query(1,1,1e9,x,y);
cout << c << '\n';
}
else update(1,1,1e9,x,y);
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
