i already mentioned the link where i got this approach.. //from spoj forum I have tried this problem with the following approach:- 1. any expression can be expressed as ))...)+a_correct_expression+((...( 2.at each node i am storing 1.no_of ')' at start and 2.no_of '(' at end of expression that the node is holding (ignoring the correct part)...... 3.whenever u r merging two nodes to form its parent, it looks like following:- left_child[))...)((..(]++right_child[))..)((..(] =))...)++((..())..)++((..( =[))..)++))..)]++((..( OR, ))..)++[((..(++((..(] i.e. comparing the no_of '(' in the left and no_of ')' in the right , u can recalculate the no_of ')' and no_of '(' for the parent node) 4.for the leaf node, if the character is '(' =>no_of '('=1 and no_of ')'=0, otherwise just the opposite case 5.finally, if the whole expression is correct , there will be 0,0 entry in the root node, otherwise whole expression is not correct...
i guess it explains all.. :) On Sat, Mar 26, 2011 at 6:32 PM, sukhmeet singh <sukhmeet2...@gmail.com>wrote: > Bharath can u tell me how u came with the combine function ??? I can't > understand the logic behind it ... do reply > > On Wed, Mar 16, 2011 at 10:24 PM, Bharath 2009503507 CSE < > bharathgo...@gmail.com> wrote: > >> i am new to segment trees..i tried this problem in spoj.. >> http://www.spoj.pl/problems/BRCKTS >> am getting WA.. >> pls help... >> >> code: >> >> #include<iostream> >> #include<vector> >> #include<cstdio> >> #include<cmath> >> #include<string> >> using namespace std; >> class pi >> { >> public: >> int a,b; >> pi() {a=0;b=0;} >> pi(int x,int y) {a=x;b=y;} >> }; >> vector<pi> tree; >> string str; >> pi combine(pi a,pi b) >> { >> pi x; >> if(a.b==b.a) >> { >> x.a=a.a; >> x.b=b.b; >> } >> else if(a.b > b.a) >> { >> x.a=a.a; >> x.b=a.b-b.a+b.b; >> } >> else >> { >> x.b=b.b; >> x.a=b.a-a.b+a.a; >> } >> return x; >> } >> void build(int node,int b,int e) >> { >> if(b==e) >> { >> if(str[b]=='(') >> { >> tree[node].a=0; >> tree[node].b=1; >> } >> else >> { >> tree[node].a=1; >> tree[node].b=0; >> } >> return; >> } >> // cout<<node<<"\n"; >> int mid=(b+e)/2; >> build(node*2,b,mid); >> build(node*2+1,mid+1,e); >> tree[node]=combine(tree[node*2],tree[node*2+1]); >> } >> void update(int node,int b,int e,int index) >> { >> if(index < b || index >e) return; >> if(b==e) >> { >> if(tree[node].a==1) >> tree[node].a=0; >> else >> tree[node].a=1; >> if(tree[node].b==1) >> tree[node].b=0; >> else >> tree[node].b=1; >> return; >> } >> int mid=(b+e)/2; >> update(node*2,b,mid,index); >> update(node*2+1,mid+1,e,index); >> tree[node]=combine(tree[node*2],tree[node*2+1]); >> } >> main() >> { >> for(int test=1;test<=10;test++) >> { >> printf("Test %d:\n",test); >> int n; >> scanf("%d",&n); >> if(!n) continue; >> int size=(1<<(int(log10(n)/log10(2))+2)); >> // cout<<size<<"\n"; >> vector<pi> temp(size); >> tree=temp; >> temp.clear(); >> string s; >> cin>>s; >> str=s; >> s.clear(); >> build(1,0,str.size()-1); >> int x; >> scanf("%d",&x); >> while(x--) >> { >> int k; >> scanf("%d",&k); >> if(k==0) >> { >> if(!tree[1].a && !tree[1].b) >> printf("Yes\n"); >> else >> printf("No\n"); >> } >> else >> update(1,0,str.size()-1,k-1); >> } >> } >> >> } >> >> Thanks in advace.. >> Bharath.. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.