#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define SET(x, a) memset(x, a, sizeof x);
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pld pair<ld, ld>
const ll MOD = 1000000007;
const ll INF = 1000000000;
template <class T> inline void read(T &x) {
char c;
int flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag *= -1;
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = x * 10 + c - '0';
x *= flag;
return;
}
int bit[100005];
inline int sum(int x) {
int ret = 0;
for (; x; x -= x & (-x))
ret += bit[x];
return ret;
}
inline void update(int x) {
for (; x <= 100000; x += x & (-x))
bit[x]++;
}
int pos[100005];
int a[100005];
int b[100005];
inline void solve() {
memset(bit, 0, sizeof bit);
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= n; ++i) {
cin >> b[i];
pos[b[i]] = i;
}
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans += sum(n) - sum(pos[a[i]] - 1);
update(pos[a[i]]);
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
}
That's a fairly standard problem on BIT (binary indexed tree).
Let the position of the x-th router and the y-th router be i and j. And the position of the x-th and y-th contestant be i2 j2.
The two lines can only intersect in two cases:
Counting these pairs are standard problem and tutorials can be found throughout the internet, so i won't state it here
Sorry for bad English
So i just count all pair that is intersect with curreent pair in O(1)?
I think the counting of the pairs can only be done in O(log n) with BIT or seg tree given that there is update
I have senior that solve this problem during contest, he said he used LIS or LCS to solve this problem.. did u agree?
I agree, the concept lies below is the same
Actually there is a similar problem on CF https://codeforces.com/gym/227122/problem/C
The following is my solution (C++)