题目 题意:给定长度为 n n n的排列 a a a,在所有 i < j , a i > a j ia_j iaj的点对 ( i , j ) (i,j) (i,j)中建立无向边。问最后得到的逆序图中,有多少个连通块。
思路:对于当前的点 x x x,后边任意小于 x x x的点 y y y,都和 x x x相连。因此,我们可以维护一个递增的单调栈 s t a c k stack stack。此外,对于当前点 c c c,如果 s t a c k [ p o s 1 ] < c < s t a c k [ p o s 2 ] stack[pos1]