【题意】

N<=105的序列,求删去一个M<N的连续子序列后,剩余序列的最小逆序对数

【解题方法】

求逆序对当然要BIT辣,然后维护删去固定大小的序列可以用two pointers 
开两个BIT,b[]维护连续M子序列前面的,c[]维护后面的 
删去ai+m,影响就是少了后面所有比它小的逆序对数,以及前面所有比它大的逆序对数 
添加ai,同理,多了所有比它小的逆序对数,以及前面所有比它大的逆序对数 
注意有重复的数哟


【AC 代码】我真的被这题恶心到了，我自己写的无线TLE，都不知道为什么。

【别人写的AC代码】

int n, m, a[N], b[N], c[N];

void add(int *b, int i, int v)
{
    for(; i <= n; i += i & -i) b[i] += v;
}

int sum(int *b, int i)
{
    int ret = 0;
    for(; i; i -= i & -i) ret += b[i];
    return ret;
}

inline int read()
{
    int c, x;
    while(c = getchar(), !isdigit(c));
    x = c - '0';
    while(c = getchar(), isdigit(c)) x = x * 10 + c - '0';
    return x;
}

int main()
{
    int t;
    t = read();
    while(t--)
    {
        n = read();
        m = read();
        for(int i = 1; i <= n; ++i) a[i] = read();

        memset(b, 0, sizeof b);
        memset(c, 0, sizeof c);
        long long tmp = 0;
        for(int i = m + 1; i <= n; ++i)
        {
            tmp += i - m - 1 - sum(c, a[i]);
            add(c, a[i], 1);
        }

        long long ans = tmp;
        for(int i = m + 1; i <= n; ++i)
        {
            tmp -= sum(c, a[i] - 1);
            tmp -= sum(b, n) - sum(b, a[i]);
            add(c, a[i], -1);

            tmp += sum(c, a[i - m] - 1);
            tmp += sum(b, n) - sum(b, a[i - m]);
            add(b, a[i - m], 1);

            ans = min(ans, tmp);
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

【我TLE代码】 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+10;
const LL inf=1e10;
inline int read() {
    int c, x;
    while(c = getchar(), !isdigit(c));
    x = c - '0';
    while(c = getchar(), isdigit(c)) x = x * 10 + c - '0';
    return x;
}
int a[maxn];
int lowbit(int i){
    return i&(-i);
}
struct BIT{
    LL b[maxn];int n;
    void init(int _n){
        n=_n;
        memset(b,0,sizeof(b));
    }
    void update(int i,LL v){
        while(i<=n){
            b[i]+=v;
            i+=lowbit(i);
        }
    }
    LL getsum(int i){
        LL ret=0;
        while(i>0){
            ret+=b[i];
            i-=lowbit(i);
        }
        return ret;
    }
}bit[2];
int main()
{
    int T,n,m;
    T=read();
    while(T--){
        n=read(),m=read();
        for(int i=1; i<=n; i++){
            a[i]=read();
        }
        for(int i=0; i<2; i++){
            bit[i].init(n);
        }
        LL cur=0,ans=inf;
        for(int i=m+1; i<=n; i++){
            cur+=(i-m-1-bit[0].getsum(a[i]));
            bit[0].update(a[i],1);
        }
        ans=cur;
        for(int i=m+1; i<=n; i++){
            cur+=bit[0].getsum(a[i-m]-1);
            cur+=bit[1].getsum(n)-bit[1].getsum(a[i-m]);
            bit[1].update(a[i-m],1);//增加置1
            cur-=bit[0].getsum(a[i]-1);
            cur-=bit[1].getsum(n)-bit[1].getsum(a[i]);
            bit[0].update(a[i],-1);//去掉置0
            ans=min(ans,cur);
        }
        printf("%I64d\n",ans);
    }
}