### KunalSin9h's blog

By KunalSin9h, history, 6 weeks ago, ### Yesterday I created problems using the Polygon system.

there is one Problem with two Parts($n \le 400$ and $n \le 2\times10^5$)

i would love if you see and solve the problems! easy, Comments (25)
 » good problems, first one is easy but second one is not easy.
 » Auto comment: topic has been updated by KunalSin9h (previous revision, new revision, compare).
 » I am unable to solve this problem
 » The problem is interesting (second part), but it requires just one observation and one standard algorithm.Overall this is a good problem.
•  » » thanks
 » Now Watch Leetcode copy your problem without giving any credit xD
 » An awesome problem bro. Keep adding more to the community with this kind of creativity...
 » Nice problem. I'd say it would make a good Div2 C problem!
•  » » I think maybe Div2 D is more accurate
 » 6 weeks ago, # | ← Rev. 2 →   Nice one, enjoyed it !!
 » Probably inspired from this problem.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   not from that, problem but from this Problem
 » Forget using long long. :(
 » Enjoyed solving it!
 » Nice.
 » Nice (but a bit standard) problem with a good idea. I felt the editorial was somewhat unclear, so here's how I thought about it.Consider another permutation $p$, and apply $p$ to both $a$ and $b$ to get $a'$ and $b'$ respectively (i.e., $a'_i = p_{a_i}$ and $b'_i = p_{b_i}$). The answer doesn't change, because of the bijection mapping pairs of indices $(i, j)$ to $(p_i, p_j)$ that also preserves cross connections (and pairs which don't form a cross connection are not mapped to cross connections). Now we can simply choose $p$ to be $a^{-1}$, which would make $a'$ the identity permutation, and $b'$ can be computed in $O(n)$. After that, we just need to count inversions in $b'$, which can be done by Fenwick trees, segment trees, any BBST, or merge sort.
 » 6 weeks ago, # | ← Rev. 2 →   Nice Problem! solved with ordered set (pbds).
 » Good problem, wonder why you still pupil if you can think about segment tree problem like that, recently I see a lot of round using segment tree so that weird :v
•  » » Currently I don't know about segment trees. But I know about Fenwick Trees and BBST. So I solved using them.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   Try to learn segment tree if you already familiar with Fenwick Tree because ST have way more application, I think the only bad think about segment tree is that if you don't use library then try to implement it will a little long but since the contest are online so it always benefit you
•  » » » » And segment trees are much slower than fenwick trees and takes more memory.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 4 →   But the different in performance is not much, I have never encounter a problem that BIT pass but ST fail. I think it like compare vector and array :v
•  » » » » » » Well try CF837G (
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   imo segtree implementation isn't that long. my code#include using namespace std; using ll=long long; vector tree(1<<18); const int sz=1<<17; void update(int idx,ll v){ --idx|=sz; tree[idx]=v; while(idx>>=1) tree[idx]=tree[idx<<1]+tree[idx<<1|1]; } ll query(int l,int r){ --l|=sz; --r|=sz; ll res=0; while(l<=r){ if(l&1) res+=tree[l++]; if(~r&1) res+=tree[r--]; l>>=1; r>>=1; } return res; } 
 » 6 weeks ago, # | ← Rev. 2 →   SpoilerHere's a way to solve it much less cleverly without transforming one of the permutations to the identity lol: https://codeforces.com/gym/382640/submission/157913381(usually I'd explain the solution in words, but the code is so short)