PROBLEM LINK:
Author: Ritesh Gupta
Tester: Subhadeep Chandra
Editorialist: Ritesh Gupta
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Mo’s algorithm
PROBLEM:
You are given a sequence A_1, A_2, \ldots, A_N. A pair of indices (i,j) in an array A is called Beautiful Pair if i \neq j and A[i] = A[j]. The strength of a beautiful pair (i,j) is |i-j|.
You are given q queries each having two integers l and r. For each query, print the sum of the strength of all beautiful pairs in the subarray of A ranging from l to r(inclusive of both l and r).
Constraints:
- 1 \le T \le 3
- 1 \le N,Q \le 10^5
- 1 \le |A_i| \le 10^9 for each valid i
- 1 \le l \le r \le N
EXPLANATION:
As queries are offline(without updates), we can use standard Mo's algorithm. Let suppose, we know the answer to some range and we want to find out the answer for another range.
We can have a map where the key represents the value of the element and the value is a pair in which the first element represents the sum of indexes of the key and second value represents the number occurrences of that key. To convert one range into another range we require four types of operation.
-
Add to the range from left: if we add an element to the left in the range then the answer for the new range is calculated by adding the contribution of this element in the current range answer. Here, the contribution of any element K is equal to the first value of key equal to K minus the product of the second value of the key equal to K and index of K(the element which we want to add). At the end of this operation, we will be adding the index of K into the first value of map with key equal to K and the second value will be incremented by 1.
-
Remove to the range from left: if we remove an element to the left in the range then the answer for the new range is calculated by subtracting the contribution of this element in the current range answer. Here, the contribution of any element K is equal to the first value of key equal to K minus the product of the second value of the key equal to K and index of K(the element which we want to add). At the end of this operation, we will be subtracting the index of K into the first value of map with key equal to K and the second value will be decremented by 1.
-
Add to the range from right: if we add an element to the right in the range then the answer for the new range is calculated by adding the contribution of this element in the current range answer. Here, the contribution of any element K is equal to the product of the second value of the key equal to K and index of K(the element which we want to add) - minus the first value of key equal to K. At the end of this operation, we will be adding the index of K into the first value of map with key equal to K and the second value will be incremented by 1.
-
Remove to the range from right: if we remove an element to the right in the range then the answer for the new range is calculated by subtracting the contribution of this element in the current range answer. Here, the contribution of any element K is equal to the product of the second value of the key equal to K and index of K(the element which we want to add) - minus the first value of key equal to K. At the end of this operation, we will be subtracting the index of K into the first value of map with key equal to K and the second value will be decremented by 1.
By using standard Mo’s algorithm we can answer all queries in offline mode.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define int long long
char input[] = “input00.txt”;
char output[] = “output00.txt”;
using namespace std;
int answers[100500];
int cnt[100100][2];
int BLOCK_SIZE;
pair< pair<int, int>, int> queries[100500];
inline bool mo_cmp(const pair< pair<int, int>, int> &x,
const pair< pair<int, int>, int> &y)
{
int block_x = x.first.first / BLOCK_SIZE;
int block_y = y.first.first / BLOCK_SIZE;
if(block_x != block_y)
return block_x < block_y;
return x.first.second < y.first.second;
}
int32_t main()
{
// freopen(input, “r”, stdin);
// freopen(output, “w”, stdout);
int t;
cin >> t;
while(t--)
{
int n,q;
cin >> n >> q;
BLOCK_SIZE = static_cast<int>(sqrt(n));
vector <int> v(n);
set <int> s;
for(int i=0;i<n;i++)
{
cin >> v[i];
s.insert(v[i]);
cnt[i][0] = cnt[i][1] = 0;
}
map <int,int> m;
int j = 1;
for(int i:s)
m[i] = j++;
for(int &i:v)
i = m[i];
for(int i = 0; i < q; i++)
{
cin >> queries[i].first.first >> queries[i].first.second;
queries[i].second = i;
}
sort(queries, queries + q, mo_cmp);
int mo_left = 0, mo_right = -1;
int current_answer = 0;
for(int i = 0; i < q; i++)
{
int left = queries[i].first.first-1;
int right = queries[i].first.second-1;
while(mo_right < right) {
mo_right++;
current_answer += (cnt[v[mo_right]][1]*mo_right - cnt[v[mo_right]][0]);
cnt[v[mo_right]][0] += mo_right;
cnt[v[mo_right]][1]++;
}
while(mo_right > right) {
current_answer -= (cnt[v[mo_right]][1]*mo_right - cnt[v[mo_right]][0]);
cnt[v[mo_right]][0] -= mo_right;
cnt[v[mo_right]][1]--;
mo_right--;
}
while(mo_left < left) {
current_answer -= (cnt[v[mo_left]][0] - cnt[v[mo_left]][1]*mo_left);
cnt[v[mo_left]][0] -= mo_left;
cnt[v[mo_left]][1]--;
mo_left++;
}
while(mo_left > left) {
mo_left--;
current_answer += (cnt[v[mo_left]][0] - cnt[v[mo_left]][1]*mo_left);
cnt[v[mo_left]][0] += mo_left;
cnt[v[mo_left]][1]++;
}
answers[queries[i].second] = current_answer;
}
for(int i = 0; i < q; i++)
cout << answers[i] << "\n";
}
}
Tester's Solution
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
using ll=long long;
int block;
struct node
{
ll l,r,ind;
};
bool comp(node i,node j)
{
if(i.l/block==j.l/block)
return i.r<j.r;
return i.l/block<j.l/block;
}
int main()
{
int n,q,l,r,t;
cin>>t;
while(t--)
{
cin>>n>>q;
vector<int> v(n);
for(int i=0;i<n;i++)
{
cin>>v[i];
}
map<ll,ll> m1,m2;
block=sqrt(n);
vector<node> query(q);
vector<ll> ans(q);
for(int i=0;i<q;i++)
{
cin>>l>>r;
l--,r--;
query[i]={l,r,i};
}
sort(query.begin(),query.end(),comp);
ll tmp=0;
l=0,r=0;
m1[v[0]]++;
for(int i=0;i<q;i++)
{
int x=query[i].l,y=query[i].r;
while(l<x)
{
m1[v[l]]--;
m2[v[l]]-=l;
tmp-=m2[v[l]]-m1[v[l]]*l;
l++;
}
while(l>x)
{
l--;
tmp+=m2[v[l]]-m1[v[l]]*l;
m1[v[l]]++;
m2[v[l]]+=l;
}
while(r<y)
{
r++;
tmp+=r*m1[v[r]]-m2[v[r]];
m1[v[r]]++;
m2[v[r]]+=r;
}
while(r>y)
{
m1[v[r]]--;
m2[v[r]]-=r;
tmp+=r*m1[v[r]]-m2[v[r]];
r--;
}
ans[query[i].ind]=tmp;
}
for(int i=0;i<q;i++)
{
cout<<ans[i]<<endl;
}
}
}