[contest link](https://mirror.codeforces.com/gym/105173)↵
I got a TLE in G of this contest.↵
↵
Let me brief you on the question.↵
↵
There is an array a with a length n(2 <= n <= 1e5)(1 <= ai <= n)↵
There are T queries(1 <= T <= 1e5)↵
For every query, there are four integers l, r, p, q(1 <= l <= r <= n, 1 <= p < q <= n)↵
Then, change the array.↵
Keep the elements equal to p and q.↵
Remove other elements.↵
Output the inverse number of the array after changing.↵
After every query, the array becomes to the initial one.↵
↵
I came up with a divide and conquer algorithm.↵
↵
Let me describe my solution.[submission:282174326]↵
↵
The key point lies in how to get the answer of the big problem(the range of [l, r]) after getting the answer of the small problem(the range of [l, (l + r) / 2] and the range of [(l + r) / 2 + 1, r]).↵
↵
The inverse number of range[l, r] equals to the inverse number of range[l, (l + r) / 2] plus the inverse number of range[(l + r) / 2 + 1, r] plus the amount of q in range[l, (l + r) / 2] multiply the amount of p in range[(l + r) / 2 + 1, r], because p < q.↵
↵
I can get the amount of an element x in range[l, r] in O(logn) using binary search.↵
↵
Of course, I need to get the ID vector for each element before all the queries.↵
↵
↵
my code:↵
↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ll = long long;↵
vector<int> f[100005];↵
ll cnt(int l, int r, int tar)↵
{↵
return upper_bound(f[tar].begin(), f[tar].end(), r) -↵
lower_bound(f[tar].begin(), f[tar].end(), l);↵
}↵
ll solve(int l, int r, int p, int q)↵
{↵
if (l == r)↵
return 0LL;↵
int m = l + r >> 1;↵
return solve(l, m, p, q) + solve(m + 1, r, p, q) +↵
cnt(l, m, q) * cnt(m + 1, r, p);↵
}↵
int main()↵
{↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int n, T, a;↵
cin >> n >> T;↵
for (int i = 1; i <= n; i++)↵
{↵
cin >> a;↵
f[a].push_back(i);↵
}↵
for (int ttt = 1; ttt <= T; ++ttt)↵
{↵
int l, r, p, q;↵
cin >> l >> r >> p >> q;↵
cout << solve(l, r, p, q) << '\n';↵
}↵
return 0;↵
}
I got a TLE in G of this contest.↵
↵
Let me brief you on the question.↵
↵
There is an array a with a length n(2 <= n <= 1e5)(1 <= ai <= n)↵
There are T queries(1 <= T <= 1e5)↵
For every query, there are four integers l, r, p, q(1 <= l <= r <= n, 1 <= p < q <= n)↵
Then, change the array.↵
Keep the elements equal to p and q.↵
Remove other elements.↵
Output the inverse number of the array after changing.↵
After every query, the array becomes to the initial one.↵
↵
I came up with a divide and conquer algorithm.↵
↵
Let me describe my solution.[submission:282174326]↵
↵
The key point lies in how to get the answer of the big problem(the range of [l, r]) after getting the answer of the small problem(the range of [l, (l + r) / 2] and the range of [(l + r) / 2 + 1, r]).↵
↵
The inverse number of range[l, r] equals to the inverse number of range[l, (l + r) / 2] plus the inverse number of range[(l + r) / 2 + 1, r] plus the amount of q in range[l, (l + r) / 2] multiply the amount of p in range[(l + r) / 2 + 1, r], because p < q.↵
↵
I can get the amount of an element x in range[l, r] in O(logn) using binary search.↵
↵
Of course, I need to get the ID vector for each element before all the queries.↵
↵
↵
my code:↵
↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ll = long long;↵
vector<int> f[100005];↵
ll cnt(int l, int r, int tar)↵
{↵
return upper_bound(f[tar].begin(), f[tar].end(), r) -↵
lower_bound(f[tar].begin(), f[tar].end(), l);↵
}↵
ll solve(int l, int r, int p, int q)↵
{↵
if (l == r)↵
return 0LL;↵
int m = l + r >> 1;↵
return solve(l, m, p, q) + solve(m + 1, r, p, q) +↵
cnt(l, m, q) * cnt(m + 1, r, p);↵
}↵
int main()↵
{↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int n, T, a;↵
cin >> n >> T;↵
for (int i = 1; i <= n; i++)↵
{↵
cin >> a;↵
f[a].push_back(i);↵
}↵
for (int ttt = 1; ttt <= T; ++ttt)↵
{↵
int l, r, p, q;↵
cin >> l >> r >> p >> q;↵
cout << solve(l, r, p, q) << '\n';↵
}↵
return 0;↵
}
