#include<bits/stdc++.h>
using namespace std;
struct node
{
node* left;
node* right;
unsigned long long val;
node()
{
left=NULL;
right=NULL;
val=0;
}
void c()
{
if(left==NULL)left=new node();
if(right==NULL)right=new node();
}
};
node* root=new node();
//node* lazy=new node();
void update(node* root,unsigned long long l,unsigned long long r,unsigned long long ql,unsigned long long qr)
{
if(l>r || ql>qr || ql>r || l>qr)return;
if(ql<=l && r<=qr){root->val=(r-l+1);return;}
root->c();
if(root->val==r-l+1)root->left->val=((l+r)/2-l+1),root->right->val=(r-(l+r)/2);
update(root->left,l,(l+r)/2,ql,qr),update(root->right,(l+r)/2+1,r,ql,qr);
root->val=(root->left->val)+(root->right->val);
}
unsigned long long query(node* root,unsigned long long l,unsigned long long r,unsigned long long ql,unsigned long long qr)
{
//cout<<"A "<<l<<" "<<r<<endl;
if(l>r || ql>qr || ql>r || l>qr)return 0;
if(ql<=l && r<=qr)return root->val;
root->c();
if(root->val==r-l+1)root->left->val=((l+r)/2-l+1),root->right->val=(r-(l+r)/2);
return query(root->left,l,(l+r)/2,ql,qr)+query(root->right,(l+r)/2+1,r,ql,qr);
}
int main()
{
int m;
cin>>m;
unsigned long long c=0;
while(m--)
{
int t;
cin>>t;
if(t==1)
{
unsigned long long l,r;
cin>>l>>r;
l--;r--;
cout<<query(root,0,999999999,l+c,r+c)<<endl;
c+=query(root,0,999999999,l+c,r+c);
}
else
{
unsigned long long l,r;
cin>>l>>r;
l--;r--;
update(root,0,999999999,l+c,r+c);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
