post the logic not the code! BTW this problem can be done using segment trees.
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor On Thu, Sep 6, 2012 at 4:51 PM, bharat b <bagana.bharatku...@gmail.com>wrote: > Its better to write an O(n) solution for this problem as the # test cases > are very high and #elements are also very huge.. > use visited array for distinct numbers ... space--O(n).. time--O(n) > > > On Sat, Aug 25, 2012 at 2:39 AM, michael miller < > wentworth.miller6...@gmail.com> wrote: > >> Hi, >> You are given N numbers. You have to perform two kinds of operations: >> U x y - x-th number becomes equal to y. >> Q x y - calculate the sum of distinct numbers from x-th to y-th. It means >> that the sum for the set {1, 2, 3, 2, 7} will be equal to 13 (1+2+3+7). >> >> 1<=N<=50000 and >> t is the number of test cases where 1<=t<=100000 >> >> all numbers fit in the 32 bit integer range... >> >> suggest some solution.. >> >> here is my solution >> but it is giving wrong answer fo some unknown test case...plz suggest me >> the test case where i am getting wrong answer.... >> >> >> #include<stdio.h> >> #include<math.h> >> int main() >> { >> int list[50000],i,n,j,sum,k,l;char c;long t; >> scanf >> <http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html>("%d",&n); >> for(i=0;i<n;i++) >> { >> scanf >> <http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html>("%d",&list[i]); >> >> } >> scanf >> <http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html>("%ld",&t); >> >> t=2*t; >> while(t) >> { >> sum=0; >> scanf >> <http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html>("%c",&c); >> >> fflush(stdin); >> scanf >> <http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html>("%d >> %d",&k,&l); >> >> if(c=='Q') >> { >> for(i=k-1;i<l-1;i++) >> { >> for(j=i+1;j<l;j++) >> { >> if(list[i]==list[j]) >> break; >> else if((j==l-1) &&(list[i]!=list[j])) >> >> { >> sum=sum+list[i]; >> >> } >> } >> } >> >> printf >> <http://www.opengroup.org/onlinepubs/009695399/functions/printf.html>("%d\n",sum+list[l-1]); >> >> } >> if(c=='U') >> { >> list[k-1]=l; >> >> } >> t--; >> } >> return 0; >> } >> >> >> >> -- >> 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. > -- Srikanth Reddy M (M.Sc Tech.) Information Systems BITS-PILANI -- 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.
