Square Root Decomposition
Problem A - Little Elephant and Array
The Little Elephant loves playing with arrays. He has array a, consisting of n positive integers, indexed from 1 to n. Let’s denote the number with index i as ai. Additionally the Little Elephant has m queries to the array, each query is characterised by a pair of integers lj and rj (1 ≤ lj ≤ rj ≤ n). For each query lj, rj the Little Elephant has to count, how many numbers x exist, such that number x occurs exactly x times among numbers alj, alj + 1, …, arj. Help the Little Elephant to count the answers to all queries.
#include <bits/stdc++.h>
using namespace std;
int const sqN = 320;
int add(int a, int b);
int sub(int a, int b);
int arr[100005];
struct query{
int index;
int l;
int r;
int ans;
};
bool comp(query &a, query &b){
if(a.l/sqN != b.l/sqN){
return a.l/sqN<b.l/sqN;
}
return a.r<b.r;
}
bool comp_by_index(query &a, query &b)
{
return a.index < b.index;
}
int main()
{
int n, m, aux, l, r, cnt;
cin >> n >> m ;
vector<int> F;
F.push_back(0);
for(int i = 0; i < n ; i ++)
{
cin >> aux;
if(aux > 100000)
aux = 0;
F.push_back(aux);
}
vector<query> Q;
for(int i = 0 ; i < m ; i++)
{
cin >> l >> r;
query inp;
inp.index = i;
inp.l = l;
inp.r = r;
Q.push_back(inp);
}
sort(Q.begin(), Q.end(), comp);
memset(arr, 0, sizeof(arr));
r = 1;
l = 0;
cnt = ( F[1] == 1) ? 1 : 0;
arr[F[1]] += 1;
for(int i = 0 ; i < m ; i ++ )
{
query curq = Q[i];
while(r < Q[i].r)
{
r ++;
cnt += sub(arr[F[r]], F[r]);
arr[F[r]] += 1;
cnt += add(arr[F[r]], F[r]);
}
while(l < Q[i].l - 1 )
{
l++;
cnt += sub(arr[F[l]], F[l]);
arr[F[l]] -= 1;
cnt += add(arr[F[l]], F[l]);
}
while(l >= Q[i].l)
{
cnt += sub(arr[F[l]], F[l]);
arr[F[l]] += 1;
cnt += add(arr[F[l]], F[l]);
l--;
}
while(r > Q[i].r )
{
cnt += sub(arr[F[r]], F[r]);
arr[F[r]] -=1;
cnt += add(arr[F[r]], F[r]);
r --;
}
Q[i].ans = cnt;
}
sort(Q.begin(), Q.end(), comp_by_index);
for(int i = 0; i < Q.size() ; i ++)
cout << Q[i].ans << endl;
}
int add(int a, int b)
{
if(b > 0 and b == a) return 1;
return 0;
}
int sub(int a, int b)
{
if(b > 0 and b == a) return -1;
return 0;
}Problem B - Powerful array
An array of positive integers a1, a2, …, an is given. Let us consider its arbitrary subarray al, al + 1…, ar, where 1 ≤ l ≤ r ≤ n. For every positive integer s denote by Ks the number of occurrences of s into the subarray. We call the power of the subarray the sum of products Ks·Ks·s for every positive integer s. The sum contains only finite number of nonzero summands as the number of different values in the array is indeed finite. You should calculate the power of t given subarrays.
#include <bits/stdc++.h>
using namespace std;
int sqN ;
long long add(long long cnt, long long number);
long long sub(long long cnt, long long number);
int arr[200005];
int F[1000002];
struct query{
int index;
int l;
int r;
long long ans;
};
bool comp(query &a, query &b){
if(a.l/sqN != b.l/sqN){
return a.l/sqN<b.l/sqN;
}
return a.r<b.r;
}
bool comp_by_index(query &a, query &b)
{
return a.index < b.index;
}
int main()
{
int n, t, aux, x, y;
cin >> n >> t;
sqN = sqrt(n);
vector<query> Q;
for(int i = 0 ; i < n; i ++)
scanf("%d",&arr[i + 1]);
for(int i = 0 ; i< t ;i ++)
{
scanf("%d%d",&x,&y);
query tmp;
tmp.l = x;
tmp.r = y;
tmp.index = i;
Q.push_back(tmp);
}
sort(Q.begin(), Q.end(), comp);
int l = 0, r = 1;
long long res = (long long ) arr[1];
F[arr[1]] += 1;
for(int i = 0 ;i < t ; i++)
{
query tmp = Q[i];
while(r < Q[i].r)
{
r++;
res -= add(F[arr[r]], arr[r]);
F[arr[r]] += 1;
res += add(F[arr[r]], arr[r]);
}
while( l >= Q[i].l )
{
res -= add(F[arr[l]], arr[l]);
F[arr[l]] += 1;
res += add(F[arr[l]], arr[l]);
l--;
}
while(r > Q[i].r)
{
res -= add(F[arr[r]], arr[r]);
F[arr[r]] -= 1;
res += add(F[arr[r]], arr[r]);
r --;
}
while(l < Q[i].l - 1)
{
l++;
res -= add(F[arr[l]], arr[l]);
F[arr[l]] -= 1;
res += add(F[arr[l]], arr[l]);
}
Q[i].ans = res;
}
sort(Q.begin(), Q.end(), comp_by_index);
int sz = Q.size();
for(int ii =0 ; ii < sz ; ii++)
printf("%I64d\n",Q[ii].ans);
}
long long add (long long cnt, long long number)
{
return (cnt * cnt * number);
}