@srikanth we can use segment trees to get sum of an interval but there is another condition of sum of distinct numbers only. how can we take that into account in a segment tree?
On Thursday, 6 September 2012 17:35:59 UTC+5:30, srikanth reddy malipatel wrote: > > 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 <[email protected]<javascript:> > > 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 >> <[email protected]<javascript:> >> > 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 [email protected]<javascript:> >>> . >>> To unsubscribe from this group, send email to >>> [email protected] <javascript:>. >>> 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 [email protected]<javascript:> >> . >> To unsubscribe from this group, send email to >> [email protected] <javascript:>. >> 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/tBX6PSU32EkJ. 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.
