use the concept of segment tree+lazy propagation
On Saturday, August 25, 2012 2:39:54 AM UTC+5:30, wentworth miller 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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/wLRpyiBiLuoJ.
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.
