题解：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≤l<r≤N
- 子序列( P l , P l + 1 , … , P r ) (P _ l , P _ {l + 1} , \dots , P _ r)(Pl,Pl+1,…,Pr)的逆序数等于K KK。
约束条件
- 1 ≤ N ≤ 5 × 10 5 1 \le N \le 5 \times 10 ^ 51≤N≤5×105
- 0 ≤ 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≤N（1 ≤ 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≤i<j≤N,Pi=Pj
- 所有输入值为整数。
输入
标准输入按以下格式给出：
N NNK KK
P 1 P _ 1P1P 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)。
代码
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintmaxn=1e6+5;intp[maxn];intn,k;intd[maxn];intlowbit(intx){returnx&(-x);}voidupdate(intpos,intx){for(;pos<=n;pos+=lowbit(pos)){d[pos]+=x;}}intquery(intpos){intres=0;for(;pos;pos-=lowbit(pos)){res+=d[pos];}returnres;}intsmaller(){if(k==0)return0;intl=1,r=1,tot=0,ans=0;update(p[1],1);while(r<n){if(tot>=k)break;r++;tot+=r-l-query(p[r]);update(p[r],1);}if(tot>=k){update(p[r],-1);tot-=r-l-query(p[r]);r--;}ans+=r;while(l<n){if(l==r){r++;tot+=r-l-query(p[r]);update(p[r],1);}update(p[l],-1);tot-=query(p[l]);l++;while(r<n){if(tot>=k)break;r++;tot+=r-l-query(p[r]);update(p[r],1);}if(tot>=k){update(p[r],-1);tot-=r-l-query(p[r]);r--;}ans+=r-l+1;}returnans;}intbigger(){for(inti=1;i<=n;i++){d[i]=0;}intl=1,r=1,tot=0,ans=0;update(p[l],1);while(r<n){if(tot>k)break;r++;tot+=r-l-query(p[r]);update(p[r],1);}if(tot<=k)return0;ans+=n-r+1;while(l<n){update(p[l],-1);tot-=query(p[l]);l++;while(r<n){if(tot>k)break;r++;tot+=r-l-query(p[r]);update(p[r],1);}if(tot<=k)returnans;ans+=n-r+1;}returnans;}voidsolve(){cin>>n>>k;for(inti=1;i<=n;i++){cin>>p[i];}cout<<n*(n+1)/2-smaller()-bigger()<<"\n";}signedmain(){intt=1;while(t--){solve();}return0;}