你有一个序列\{a_1,a_2,...,a_n\}{a?1??,a?2??,...,a?n??},然后你可以删除一个长度为mm的连续子序列. 问如何删除才能使逆序对最少.
输入有多组数据, 第一行有一个整数TT表示测试数据的组数. 对于每组数据:
第一行包含2个整数n,m (1 \le n \le 10^5, 1 \le m < n)n,m(1≤n≤10?5??,1≤m<n), 表示序列的长度. 第2行包含nn个整数a_1,a_2,...,a_n (1 \le a_i \le n)a?1??,a?2??,...,a?n??(1≤a?i??≤n).
数据中所有nn的和不超过2 \times 10^62×10?6??.
对于每组数据, 输出最小的逆序对个数.
2 3 1 1 2 3 4 2 4 1 3 2
0 1
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=100010; const int INF=(1<<29); int n,m; int a[maxn]; int cL[maxn],cR[maxn]; int lowbit(int x) { return x&(-x); } void add(int *c,int p,int x) { while(p<=n){ c[p]+=x; p+=lowbit(p); } } ll sum(int *c,int p) { ll res=0; while(p>0){ res+=c[p]; p-=lowbit(p); } return res; } int main() { int T;cin>>T; while(T--){ scanf("%d%d",&n,&m); REP(i,1,n) scanf("%d",&a[i]); MS0(cL);MS0(cR); ll now=0; for(int i=n;i>m;i--){ now+=sum(cR,a[i]-1); add(cR,a[i],1); } ll ans=now; REP(i,1,n-m){ int x=a[i],y=a[i+m]; now+=(sum(cL,n)-sum(cL,x))+sum(cR,x-1); add(cL,x,1); now-=(sum(cL,n)-sum(cL,y))+sum(cR,y-1); add(cR,y,-1); ans=min(ans,now); } printf("%I64d\n",ans); } return 0; }
bestcoder#58(div2) 1004 树状数组维护逆序数
原文：http://www.cnblogs.com/--560/p/4857599.html
