folcotandiono's blog

By folcotandiono, history, 4 weeks ago, In English,
 
 
 
 
  • Vote: I like it  
  • -2
  • Vote: I do not like it  

»
4 weeks 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

  • »
    »
    4 weeks 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)?

    • »
      »
      »
      4 weeks 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

      • »
        »
        »
        »
        4 weeks 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?

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I agree, the concept lies below is the same

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Actually there is a similar problem on CF https://codeforces.com/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();
          }