A question for a enthusiast like me but from a difficult topic.......(MO's ALGORITHM)

→ Pay attention

Before contest
2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
25:49:04
Register now »

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
5	adamant	158
7	awoo	157
8	TheScrasse	154
8	nor	154
10	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

prabal_1997's blog

A question for a enthusiast like me but from a difficult topic.......(MO's ALGORITHM)

By prabal_1997, history, 6 years ago, In English

question goes like this.... given an array of n nos.and queries q the queries follow like this given range l to r (l<=r) for every query we have to find sum of elements which have an odd frequency in the given range

note : 1 based indexing is followed.............................................................................................

example : 5......n

1 2 2 2 1....elements

3..queries...

1 3...

1 4......

1 5......

output: 1..... 7..... 6.....

explanation : 1. in range 1 to 3 only 1 has odd frequecy i.e 1 so ans =1 !!! 2.in range 1 to 4 1 has frequency 1 and 2 has frequecy 3 so ans = 1*1 + 2*3 = 6 !!!

I am not able to solve this......question if time limit is 1 second.

prabal_1997
6 years ago
7

Comments (4)

Show archived | Write comment?

xoxo

6 years ago, # |

We sum all entries of element in range?

→ Reply

tenshi_kanade

6 years ago, # |

Using the standard Mo's algorithm with two pointers should work within 1 second time limit for N ≤ 10⁵. To keep the frequencies and the answer, do the following...

Let freq[x] be the frequency of number x. Initially all frequencies are 0 and ans = 0. Parity changes with every insertion/removal, so suppose we shrink/expand current range and we need to add/remove number x. If freq[x] is currently odd, we perform ans = ans - x * freq[x] and then update freq[x], and if, on the other hand, freq[x] is currently even, we first update freq[x] and then perform ans = ans + x * freq[x].

→ Reply

prabal_1997

6 years ago, # ^ |

-24

i know this but i am not able to code this....

→ Reply

tenshi_kanade

6 years ago, # ^ |

This is how I usually code Mo's...

Mo's C++ Code

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define all(x) x.begin(), x.end()
#define f(i,a,b) for(int i = (a); i <= (b); i++)
#define pb push_back

const int BLOCK = 300;

struct Query
{
    int l,r,id;
    Query(int _l, int _r, int _id) : l(_l), r(_r), id(_id) {};
    friend bool operator < (Query q1, Query q2)
    {
        if(q1.l / BLOCK != q2.l / BLOCK) return q1.l / BLOCK < q2.l / BLOCK;
        else return q1.r < q2.r;
    }
};

int A[100005], Freq[100005], N, Q;
ll Ans[100005];
vector<Query> Queries;

int main()
{
    cin >> N;
    f(i,1,N) cin >> A[i];
    cin >> Q;
    f(q,1,Q)
    {
        int l,r;
        cin >> l >> r;
        Queries.pb(Query(l,r,q));
    }
    sort(all(Queries));
    int l = 1, r = 0;
    ll ans = 0;
    for(Query q : Queries)
    {
        while(r < q.r)
        {
            ll x = A[r+1];
            r++;
            if(Freq[x]&1)
            {
                ans -= x*Freq[x];
                Freq[x]++;
            }
            else
            {
                Freq[x]++;
                ans += x*Freq[x];
            }
        }
        while(l > q.l)
        {
            ll x = A[l-1];
            l--;
            if(Freq[x]&1)
            {
                ans -= x*Freq[x];
                Freq[x]++;
            }
            else
            {
                Freq[x]++;
                ans += x*Freq[x];
            }
        }
        while(l < q.l)
        {
            ll x = A[l];
            l++;
            if(Freq[x]&1)
            {
                ans -= x*Freq[x];
                Freq[x]--;
            }
            else
            {
                Freq[x]--;
                ans += x*Freq[x];
            }
        }
        while(r > q.r)
        {
            ll x = A[r];
            r--;
            if(Freq[x]&1)
            {
                ans -= x*Freq[x];
                Freq[x]--;
            }
            else
            {
                Freq[x]--;
                ans += x*Freq[x];
            }
        }
        Ans[q.id] = ans;
    }
    f(q,1,Q) cout << Ans[q] << "\n";
}

→ Reply