hdu 5497 Inversion 树状数组逆序对，单点修改

2021-07-28 18:58:19

Inversion

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5497

Description

你有一个序列\{a_1,a_2,...,a_n\}{a1,a2,...,an},然后你可以删除一个长度为mm的连续子序列. 问如何删除才能使逆序对最少.

Input

输入有多组数据, 第一行有一个整数TT表示测试数据的组数. 对于每组数据:

第一行包含2个整数n,m (1 \le n \le 10^5, 1 \le m < n)n,m(1≤n≤105,1≤m<n), 表示序列的长度. 第2行包含nn个整数a_1,a_2,...,a_n (1 \le a_i \le n)a1,a2,...,an(1≤ai≤n).

数据中所有nn的和不超过2 \times 10^62×106.

Output

对于每组数据, 输出最小的逆序对个数

Sample Input

Sample Output

0

1

HINT

题意

题解：

直接把所有情况都枚举出来就好了

假设原逆序对有ans个，L[i]表示在左边有L[i]个数比i大，R[i]表示在右边，有R[i]个数比i小

如果插入一个大小为x的点在y位置的话，答案就是 ans+L[i]+R[i]

如果删除一个大小为x的点在y位置的话，答案就是 ans -L[i]-R[i]

所以区间在滑动的时候，ans = ans + L[i] -L[i+m] + R[i] - R[i+m]

L[i]和R[i]用树状数组来维护

代码：

#include<iostream>

#include<stdio.h>

#include<queue>

#include<map>

#include<algorithm>

#include<string.h>

using namespace std;

#define maxn 100005

struct Bit

{

    int a[maxn];

    void init()

    {

        memset(a,,sizeof(a));

    }

    int lowbit(int x)

    {

        return x&(-x);

    }

    int query(int x)

    {

        int ans = ;

        for(;x;x-=lowbit(x))ans+=a[x];

        return ans;

    }

    void update(int x,int v)

    {

        for(;x<maxn;x+=lowbit(x))

            a[x]+=v;

    }

}L,R;

int a[maxn];

int main()

{

    int t;scanf("%d",&t);

    while(t--)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        L.init(),R.init();

        for(int i=;i<=n;i++)

            scanf("%d",&a[i]);

        long long tmp = ;

        for(int i=n;i>m;i--)

        {

            R.update(a[i],);

            tmp+=R.query(a[i]-);

        }

        long long ans = tmp;

        for(int i=;i<=n-m;i++)

        {

            R.update(a[i+m],-);

            tmp+=R.query(a[i]-);

            tmp-=R.query(a[i+m]-);

            tmp+=L.query(n+-(a[i]+));

            tmp-=L.query(n+-(a[i+m]+));

            L.update(n+-(a[i]),);

            ans=min(ans,tmp);

        }

        cout<<ans<<endl;

    }

}

码农公寓