题解：AT_abc452_f

题面Interval Inversion Count问题描述给定一个正整数N NN和一个由1 , 2 , … , N 1 , 2 , \dots , N1,2,…,N组成的排列P ( P 1 , P 2 , … , P N ) P (P _ 1 , P _ 2 , \dots , P _ N)P(P1​,P2​,…,PN​)。给定一个整数K KK。求满足以下两个条件的整数对( l , r ) (l , r)(l,r)的数量。1 ≤ l r ≤ N 1 \le l r \le N1≤lr≤N子序列( P l , P l 1 , … , P r ) (P _ l , P _ {l 1} , \dots , P _ r)(Pl​,Pl1​,…,Pr​)的逆序数等于K KK。约束条件1 ≤ N ≤ 5 × 10 5 1 \le N \le 5 \times 10 ^ 51≤N≤5×1050 ≤ K ≤ N ( N − 1 ) 2 0 \le K \le \frac{N(N - 1)}{2}0≤K≤2N(N−1)​1 ≤ P i ≤ N 1 \le P _ i \le N1≤Pi​≤N1 ≤ i ≤ N 1 \le i \le N1≤i≤N∀ 1 ≤ i j ≤ N , P i ≠ P j \forall 1 \le i j \le N , P _ i \neq P _ j∀1≤ij≤N,Pi​Pj​所有输入值为整数。输入标准输入按以下格式给出N NNK KKP 1 P _ 1P1​P 2 P _ 2P2​… \dots…P N P _ NPN​输出输出满足条件的区间( l , r ) (l , r)(l,r)的个数。思路观察逆序数为K KK的区间的分布规律并非绝对单调性但注意到逆序数为K KK的区间个数等于总区间个数减逆序数小于与大于K KK的区间个数之和。而两者皆有绝对单调性所以使用双指针套树状数组来解决这两个子问题。求解逆序数小于K KK的区间个数对每个左端点l ∈ [ 1 , n ] l \in [1 , n]l∈[1,n]遍历找出最后一个r rr使得逆序数小于K KK并记录答案。大于则同理对每个左端点l ∈ [ 1 , n ] l \in [1 , n]l∈[1,n]同样遍历找出第一个r rr使得逆序数大于K KK并记录答案。双指针时间复杂度O ( n ) O(n)O(n)树状数组时间复杂度O ( log ⁡ n ) O(\log n)O(logn)总复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn)。代码#includebits/stdc.h#defineintlonglongusingnamespacestd;constintmaxn1e65;intp[maxn];intn,k;intd[maxn];intlowbit(intx){returnx(-x);}voidupdate(intpos,intx){for(;posn;poslowbit(pos)){d[pos]x;}}intquery(intpos){intres0;for(;pos;pos-lowbit(pos)){resd[pos];}returnres;}intsmaller(){if(k0)return0;intl1,r1,tot0,ans0;update(p[1],1);while(rn){if(totk)break;r;totr-l-query(p[r]);update(p[r],1);}if(totk){update(p[r],-1);tot-r-l-query(p[r]);r--;}ansr;while(ln){if(lr){r;totr-l-query(p[r]);update(p[r],1);}update(p[l],-1);tot-query(p[l]);l;while(rn){if(totk)break;r;totr-l-query(p[r]);update(p[r],1);}if(totk){update(p[r],-1);tot-r-l-query(p[r]);r--;}ansr-l1;}returnans;}intbigger(){for(inti1;in;i){d[i]0;}intl1,r1,tot0,ans0;update(p[l],1);while(rn){if(totk)break;r;totr-l-query(p[r]);update(p[r],1);}if(totk)return0;ansn-r1;while(ln){update(p[l],-1);tot-query(p[l]);l;while(rn){if(totk)break;r;totr-l-query(p[r]);update(p[r],1);}if(totk)returnans;ansn-r1;}returnans;}voidsolve(){cinnk;for(inti1;in;i){cinp[i];}coutn*(n1)/2-smaller()-bigger()\n;}signedmain(){intt1;while(t--){solve();}return0;}