题意:给出\(a[1...n]\),共\(n\)次操作,每次删除一个位置\(p_i\)(强制在线),此时区间会变为两个分离的区间,求每次操作的最大区间逆序对

首先要知道必要的工具,按权值建立的主席树可以在\(O(nlogn)\)内得到任意区间长为\(n\)的逆序对

但每次切除的点如果是不断沿着边来切,那么要统计的区间总长是\(O(n^2)\)

考虑逆序对的贡献是可以互为计算得到的,那么能否每次只对相对较小的区间的复杂度进行统计,得到\(O(nlogn)\)的区间统计总长?

如果已知一个区间\([L,R]\)的总逆序对\(oldans\),切点为\(M\),且更靠左边,

那可以对小区间的逆序数对进行暴力统计,得到\([L,M-1]\)的所有相互贡献,此时记为\(ans1\)

然后再\(O(logn)\)计算\(a[M]\)对\([L,M-1]\)的贡献,记为\(tmp\)

最后询问\(T[R]-T[K]\)的子树中比\(a[i],i∈[L,M]\)小的个数,记为\(tmp2\)

那么区间\([L,M-1]\)的逆序数对为\(ans1\),\([M+1,R]\)的逆序数对为\(oldans-ans1-tmp-tmp2\)

以上操作均可以在\(O(nlogn)\)内完成,\(n\)为小区间的长度

切点靠右同理,因此总的复杂度为\(O(nlog^2n)\)

还有一些细节需要处理,如何在一开始就得知\([L,R]\)的总逆序数对,

初始化时先计算出\([1,n]\)的贡献,剩下的必然在前面的操作中已经统计得到\(ans1\)或\(ans2\)

考虑区间总是不断分裂的,我们可以用简单的平衡树来维护位置\(M\)对应最近的\(L\)和\(R\)

并且答案总是对应于每一个\(L\),都有一个唯一的\(R\)和\(ans\)相对应,这部分只需用简单的数组即可得到

而\(ans\)的最优解需要在分裂时及时删除对应的元素,再多拿一个multiset动态维护最大值即可

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define rep(i,j,k) for(register int i=j;i<=k;i++)#define rrep(i,j,k) for(register int i=j;i>=k;i--)#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])#define fastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)#define println(x) printf("%lld\n",(ll)(x))using namespace std;typedef long long ll;typedef pair
          
            pr;const int MAXN = 1e5+11;const int MAXM = 4e6+11;const int MOD = 142857;const int INF = 1<<30;int T[MAXN];int a[MAXN],p[MAXN];struct FST{ int cnt[MAXM]; int lc[MAXM],rc[MAXM]; int tot; void init(){tot=0;lc[tot]=rc[tot]=cnt[tot]=0;} int build(int l,int r){ int cur=++tot; lc[cur]=rc[cur]=cnt[cur]=0; if(l==r) return cur; int mid=l+r>>1; lc[cur]=build(l,mid); rc[cur]=build(mid+1,r); return cur; } int update(int old,int l,int r,int k,int v){ int cur=++tot; lc[cur]=lc[old]; rc[cur]=rc[old]; cnt[cur]=cnt[old]+v; if(l==r) return cur; int mid=l+r>>1; if(k<=mid) lc[cur]=update(lc[old],l,mid,k,v); else rc[cur]=update(rc[old],mid+1,r,k,v); return cur; } ll query(int cur1,int cur2,int l,int r,int L,int R){//l r if((cur2|cur1)==0) return 0; if(L<=l&&r<=R) return cnt[cur2]-cnt[cur1]; ll ans=0; int mid=l+r>>1; if(L<=mid) ans+=query(lc[cur1],lc[cur2],l,mid,L,R); if(R>mid) ans+=query(rc[cur1],rc[cur2],mid+1,r,L,R); return ans; }}fst;multiset
           
             st;//multiset
            
              inv[MAXN];ll inv[MAXN],invans[MAXN];multiset
             
               ans;int main(){#ifndef ONLINE_JUDGE freopen("stdin.txt","r",stdin);#endif int Test; scanf("%d",&Test); while(Test--){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&p[i]); if(n==1){ printf("0\n"); continue; } fst.init(); T[0]=fst.build(1,n); for(int i=1;i<=n;i++){ T[i]=fst.update(T[i-1],1,n,a[i],1); } st.clear(); ans.clear(); st.insert(0),st.insert(n+1); for(int i=0;i<=n+1;i++) inv[i]=0; ll lastans=0; for(int i=1;i<=n;i++){ if(a[i]!=1){ lastans+=fst.query(T[i],T[n],1,n,1,a[i]-1); } } inv[1]=n,invans[1]=lastans; ans.insert(lastans); printf("%lld ",lastans); ll mx=lastans; for(int i=1;i