You are not logged in. Please login at to post your questions!


In search of an editorial of Poo Poo

Hello guys!
I am in search of a detailed editorial on the problem Poo Poo from the recent LoC Aug contest. It would be of great help to me and many others if any one can step up for this!!

I personally would request @likecs to at least explain his solution because I saw his submission took very less execution time and I am learning Segment Tree too. Also the editorials he posted for LunchTime were just amazing!!

Thanks for the help :)

asked 29 Aug '17, 00:54

dishant_18's gravatar image

accept rate: 12%

edited 29 Aug '17, 00:56

Let us take an example, $A = [a,\ b,\ c]$

The subsequences of $A$ with their PooPoo sum are:

[a] : (a)^2 = a^2
[b] : (b)^2 = b^2
[c] : (c)^2 = c^2
[a, b] : (a - b)^2 = a^2 + b^2 - 2ab
[a, c] : (a - c)^2 = a^2 + c^2 - 2ac
[b, c] : (b - c)^2 = b^2 + c^2 - 2bc
[a, b, c] : (a - b + c)^2 = a^2 + b^2 + c^2 + 2(-ab - bc + ac)

If we add them, we get :- $4[(a^2 + b^2 + c^2)\ -\ (ab + bc)]$

For 4 elements, we get :- $8[(a^2 + b^2 + c^2 + d^2)\ -\ (ab + bc + cd)]$

As you would have guessed from the pattern, the answer for array $A$ of $n$ elements is: $$ 2^{n-1}\ \Big(\ \sum_{i\ =\ 1}^{n}\ A_i^2\ - \sum_{i\ =\ 1}^{n-1}\ A_i * A_{i+1}\ \Big)$$

Now the question reduces to the following:

For a given range $[L,\ R]$, find the sum of squares of the elements and the sum of the product of adjacent elements, along with point updates.

The above operations deal with range sums and point updates and hence can be solved by using Segment Trees or Binary Indexed Trees (BIT) / Fenwick Tree.

Here are my codes:

Using Segment Tree:

Using Fenwick Tree:

To keep things separate, I've used one tree to store the sum of squares of elements and the other to store the sum of the product of adjacent elements.


answered 29 Aug '17, 01:46

c_utkarsh's gravatar image

accept rate: 17%


Thank u so much :)

(29 Aug '17, 10:01) dishant_184★

Hey! Did you solve ALATE? I got only 20 points for it. Can you please explain it so that I can pass Sub task 2 without TLE? Please provide an improvement.

Here is my code.

include bits/stdc++.h

define ll long long

define MOD 1000000007

define N 1000005

using namespace std; ll a[N],n; ll func(ll x) { ll k,sum=0; for(ll i=x;i<=n;i+=x) { k=(a[i]a[i])%MOD; sum=(sum+(a[i]a[i]))%MOD; sum%=MOD; } return sum; } int main() { ll t,q,i,j,qno,x,y; scanf("%lld",&t); while(t--) { scanf("%lld%lld",&n,&q); for(i=1;i<=n;i++) scanf("%lld",&a[i]); for(j=1;j<=q;j++) { scanf("%lld",&qno); if(qno==1) { scanf("%lld",&x); printf("%lld\n",func(x));
} else { scanf("%lld%lld",&x,&y); a[x]=y; }
} } return 0; }


answered 29 Aug '17, 01:31

ramini's gravatar image

accept rate: 8%

@ramini If you are searching for a solution to Always Late, just look at @rns_kjch 's solution. It is very intuitive and easy to understand.

P.S.: Sorry, I didn't know how to comment on an answer :).


answered 29 Aug '17, 16:42

pixel0x8's gravatar image

accept rate: 0%

edited 29 Aug '17, 16:43

Can we solve this problem with square root decomposition?


answered 29 Aug '17, 22:20

phantomhive's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 29 Aug '17, 00:54

question was seen: 484 times

last updated: 29 Aug '17, 22:20