naevis's blog

How to solve this problem?
By naevis, history, 6 years ago, In English

https://training.ia-toki.org/problemsets/88/problems/459/

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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:

  1. i < j and i2 > j2
  2. i > j and i2 < j2

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So i just count all pair that is intersect with curreent pair in O(1)?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I have senior that solve this problem during contest, he said he used LIS or LCS to solve this problem.. did u agree?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I agree, the concept lies below is the same

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Actually there is a similar problem on CF https://codeforces.net/gym/227122/problem/C

          The following is my solution (C++)

          #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();
}
          → Reply