#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct tree
{
struct node
{
node *l,*r;
bool minval;
int cnt;
bool lazy;
node(int _cnt)
{
l=nullptr;
r=nullptr;
minval=0;cnt=_cnt;
}
};
node* root=nullptr;
node* xd;
node* merge(node *n1,node *n2,int L,int R)
{
node *ret=new node(R-L+1);
int mid=(L+R)/2;
if(!n1)
{
tie(ret->minval,ret->cnt)=make_pair(n2->minval,n2->cnt);
if(ret->minval==0)ret->cnt+=mid-L+1;
else
{
ret->minval=0;
ret->cnt=mid-L+1;
}
ret->r=n2;
return ret;
}
if(!n2)
{
tie(ret->minval,ret->cnt)=make_pair(n1->minval,n1->cnt);
if(ret->minval==0)ret->cnt+=R-mid;
else
{
ret->minval=0;
ret->cnt=R-mid;
}
ret->l=n1;
return ret;
}
if(n1->minval==n2->minval)
{
tie(ret->minval,ret->cnt)=make_pair(n1->minval,n1->cnt+n2->cnt);
}
else tie(ret->minval,ret->cnt)=min(make_pair(n1->minval,n1->cnt),make_pair(n2->minval,n2->cnt));
ret->l=n1;ret->r=n2;
return ret;
}
void push(node* &t,int L,int R)
{
if(!t)return;
if(!t)t=new node(R-L+1);
if(t->lazy)
{
if(L!=R)
{
int mid=(L+R)/2;
if(t->l)
{
t->l->lazy=1;
}
else
{
t->l=new node(mid-L+1);
t->l->lazy=1;
}
if(t->r)
{
t->r->lazy=1;
}
else
{
t->r=new node(R-mid);
t->r->lazy=1;
}
}
t->minval=1;
t->lazy=0;
}
return;
}
void upd(node* &t,int L,int R,int ql,int qr)
{
if(L>qr||R<ql)return;
if(!t)t=new node(R-L+1);
push(t,L,R);
if(L>=ql&&R<=qr)
{
t->lazy=1;
return;
}
int mid=(L+R)/2;
if(mid+1>qr)
{
upd(t->l,L,mid,ql,qr);
}
else if(mid<ql)
{
upd(t->r,mid+1,R,ql,qr);
}
else
{
upd(t->l,L,mid,ql,qr);
upd(t->r,mid+1,R,ql,qr);
}
if(t->l&&t->l->lazy)push(t->l,L,mid);
if(t->r&&t->r->lazy)push(t->r,mid+1,R);
t=merge(t->l,t->r,L,R);
return;
}
int query(node *t,int L,int R,int ql,int qr)
{
if(L>qr||R<ql)return 0;
if(!t)return R-L+1;
push(t,L,R);
if(L>=ql&&R<=qr)
{
if(t->minval==0)return t->cnt;
else return 0;
}
int mid=(L+R)/2;
if(mid<ql)return query(t->r,mid+1,R,ql,qr);
else if(mid+1>qr)return query(t->l,L,mid,ql,qr);
return query(t->l,L,mid,ql,qr)+query(t->r,mid+1,R,ql,qr);
}
void print(node* t,int L,int R)
{
if(!t)return;
print(t->l,L,(L+R)/2);
print(t->r,(L+R)/2+1,R);
}
}st;
int main()
{
int c=0;
int m,d,x,y,xd;
cin>>m;
while(m--)
{
cin>>d>>x>>y;
x+=c;y+=c;
if(d==1)
{
xd=st.query(st.root,1,INF,x,y);
c=y-x+1-xd;
cout<<c<<endl;
}
else
{
st.upd(st.root,1,INF,x,y);
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
