给定一个数列，删除一个连续长度m的序列，使剩下的序列逆序对对数最少
把删除的序列左右两侧的数各放在一颗线段树中统计 ，每次移动一步，求逆序对
注意数组清0时不能直接memset，否则TLE
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
typedef long long ll;
class SegmentTree
{
ll a[MAXN*4],sumv[MAXN*4],addv[MAXN*4];
int n;
public:
SegmentTree(){MEM(a) MEM(sumv) MEM(addv) }
SegmentTree(int _n):n(_n){MEM(a) MEM(sumv) MEM(addv) }
void mem(int _n)
{
n=_n;
MEM(a) MEM(sumv) MEM(addv)
}
void maintain(int o,int L,int R)
{
sumv[o]=0;
if (L<R) //只考虑左右子树
{
sumv[o]=sumv[Lson]+sumv[Rson];
} //只考虑add操作
sumv[o]+=addv[o]*(R-L+1);
}
int y1,y2,v;
void update(int o,int L,int R) //y1,y2,v
{
if (y1<=L&&R<=y2) {
addv[o]+=v;
}
else{
pushdown(o);
int M=(R+L)>>1;
if (y1<=M) update(Lson,L,M); else maintain(Lson,L,M);
if (M< y2) update(Rson,M+1,R); else maintain(Rson,M+1,R);
}
maintain(o,L,R);
}
void pushdown(int o)
{
if (addv[o])
{
addv[Lson]+=addv[o];
addv[Rson]+=addv[o];
addv[o]=0;
}
}
ll _sum;
void query2(int o,int L,int R,ll add)
{
if (y1<=L&&R<=y2)
{
_sum+=sumv[o]+add*(R-L+1);
} else {
int M=(L+R)>>1;
if (y1<=M) query2(Lson,L,M,add+addv[o]);
if (M< y2) query2(Rson,M+1,R,add+addv[o]);
}
}
void add(int l,ll v)
{
y1=l,y2=l;this->v=v;
update(1,1,n);
}
ll ask(int l,int r)
{
if (l>r) return 0;
_sum=0;
y1=l,y2=r;
query2(1,1,n,0);
return _sum;
}
}S1,S2;
int n,m,a[MAXN];
int main()
{
// freopen("d.in","r",stdin);
// freopen(".out","w",stdout);
S1.mem(100000); S2.mem(100000);
int T;cin>>T;
while(T--) {
cin>>n>>m;
For(i,n) scanf("%d",&a[i]);
int l=1,r=m;
ll s=0;
ForkD(i,r+1,n)
{
s+=S2.ask(1,a[i]-1);
S2.add(a[i],1);
}
ll ans=s;
while (r<n) {
s+=S1.ask(a[l]+1,n);
s+=S2.ask(1,a[l]-1);
S1.add(a[l],1);
r++;
s-=S1.ask(a[r]+1,n);
s-=S2.ask(1,a[r]-1);
S2.add(a[r],-1);
ans=min(ans,s);
l++;
}
cout<<ans<<endl;
For(i,l-1) S1.add(a[i],-1);
}
return 0;
}