TODO: https://contest.cs.cmu.edu/295/s20/tutorials/counting.mark
The weight of a sequence is defined as the number of unordered pairs of indexes (i, j)
(here i < j
) with same value (a𝑖 = a𝑗)
. For example, the weight of sequence a = [1,1,2,2,1]
is 4
. The set of unordered pairs of indexes with same value are (1,2), (1,5), (2,5), and (3,4)
.
You are given a sequence a
of n
integers. Print the sum of the weight of all subsegments of a
.
A sequence b
is a subsegment of a sequence a
if b
can be obtained from a
by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
Solution
For each subsegment, we have i
possible choices for starting position of the subsegment and (n - j + 1)
for ending position of the subsegment. For each element a[i]
it is counted towards weight for any segment which start with index less than i
, hence we can maintain a map to count how many times can it be included m[a[i]] += i
. Now for every segment whose end is greater than i
we count the sum of weight of all segments till this index i
as follows.
#define int long long
const int N = 1e5 + 5;
int n;
int a[N];
int main()
{
int t;
cin >> t;
while(t--)
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
map<int, int> m;
int ans = 0;
for(int i = 1; i <= n; i++)
{
ans += (n - i + 1) * (m[a[i]]);
m[a[i]] += i;
}
cout << ans << endl;
}
return 0;
}
source: https://codeforces.com/contest/1527/submission/116770682