### folcotandiono's blog

By folcotandiono, history, 4 weeks ago, ,  Comments (7)
 » 4 weeks ago, # | ← Rev. 2 →   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: i < j and i2 > j2 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 hereSorry 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?
•  » » » » » Yes
•  » » » » » I agree, the concept lies below is the same
•  » » » » » Actually there is a similar problem on CF https://codeforces.com/gym/227122/problem/CThe following is my solution (C++) #include 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 #define pll pair #define fi first #define se second #define pld pair const ll MOD = 1000000007; const ll INF = 1000000000; template 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; 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; int a; int b; 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(); }