#include<iostream>
using namespace std;
struct node
{
int num;
int l,r;
node * left;
node * right;
};
node * create(node * root,int start,int end);
node * update(node * root, int i,int j);
int query(node * root,int i,int j);
main()
{
int n,q;
cin>>n>>q;
node * root=new node;
root->num=0;
root->left=NULL;
root->right=NULL;
root=create(root,0,n-1);
while(q--)
{
int type,i,j;
cin>>type>>i>>j;
if(type==0)
root=update(root,i,j);
if(type==1)
cout<<query(root,i,j);
}
}
node * create(node * root,int start,int end)
{
if(start==end)
{
node * temp=new node();
temp->num=0;
temp->right=NULL;
temp->left=NULL;
temp->l=temp->r=start;
return temp;
}
if(start!=end)
{
if(root==NULL)
root=new node();
root->num=0;
root->l=start;
root->r=end;
root->left=create(root->left,start,(start+end)/2);
root->right=create(root->right,((start+end)/2)+1,end);
return root;
}
}
node * update(node * root,int i,int j)
{
if(root->l==root->r && (root->l >=i&&root->r <=j))
{
root->num=1-(root->num);
return root;
}
if(root->left)
root->left=update(root->left,i,j);
if(root->right)
root->right=update(root->right,i,j);
if(root->left && root->right)
root->num=root->left->num+root->right->num;
return root;
}
int query(node * root,int i,int j)
{
if(root->l>=i && root->r<=j)
return root->num;
int ans1,ans2;
if(root->left)
ans1=query(root->left,i,j);
if(root->right)
ans2=query(root->right,i,j);
if(!root->left && !root->right)
return 0;
return ans1+ans2;
}
this is my solution to http://www.spoj.pl/problems/LITE/ .
But i am getting wrong answer. Can someone suggest a few test cases for
which my solution might be failing ?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/h6UQhCs1W_0J.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
