#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
struct Node{
int val,lazy,p,q;
Node *l,*r;
Node(int x,int y,int z):val(x),lazy(0),p(y),q(z),l(NULL),r(NULL){}
}*root;
void push(Node *&x){
int m=(x->p+x->q)/2;
if(x->l){
x->l->val=m-x->p+1;
x->l->lazy=1;
}
else x->l=new Node(m-x->p+1,x->p,m);
if(x->r){
x->r->val=x->q-m;
x->r->lazy=1;
}
else x->r=new Node(x->q-m,m+1,x->q);
x->lazy=0;
}
void update(Node *&x,int l,int r,int u,int v){
if(u>v)return;
if(!x)x=new Node(0,l,r);
if(l!=r&&x->lazy)push(x);
if(l==u&&r==v){
x->val=r-l+1;
x->lazy=1;
return;
}
int m=(l+r)/2;
update(x->l,l,m,u,min(m,v));
update(x->r,m+1,r,max(m+1,u),v);
x->val=(x->l?x->l->val:0)+(x->r?x->r->val:0);
}
int query(Node *&x,int l,int r,int u,int v){
if(u>v||!x)return 0;
if(l!=r&&x->lazy)push(x);
if(l==u&&r==v)return x->val;
int m=(l+r)/2;
return query(x->l,l,m,u,min(m,v))+query(x->r,m+1,r,max(m+1,u),v);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int c=0;
int q;cin>>q;
root=new Node(0,1,inf);
while(q--){
int t,x,y;cin>>t>>x>>y;
x+=c;y+=c;
if(t==2)update(root,1,inf,x,y);
else{
c=query(root,1,inf,x,y);
cout<<c<<"\n";
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |