首页 > 代码库 > Inversion_树状数组

Inversion_树状数组

2024-08-23 11:41:00   220人阅读

Problem Description
You have a sequence {a1,a2,...,an} and you can delete a contiguous subsequence of length m. So what is the minimum number of inversions after the deletion.
 

 

Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains two integers n,m(1≤n≤105,1≤m<n) - the length of the seuqence. The second line contains n integers a1,a2,...,an(1≤ai≤n).

The sum of n in the test cases will not exceed 2×106.
 

 

Output
For each test case, output the minimum number of inversions.
 

 

Sample Input
2 3 1 1 2 3 4 2 4 1 3 2
 

 

Sample Output
0 1

 

 

【题意】给出n个数，删除其中一个长度为m的一个连续序列，求最后最小逆序数

【思路】这题精华很多，有待吸收~~

每一次移动，显然会往这个序列中删除一个数，增加一个数

1.加入一个数：多了它后面所有比它小的数，多了它前面所有比它大的数

2.删除一个数：少了它后面所有比它小的数，少了它前面所有比它大的数

用两个树状数组动态维护删除的序列前面和后面部分。

直接memset会TLE，需要限制一下清空的范围。（大神让我学了一招！！！）

参考：http://blog.csdn.net/weizhuwyzc000/article/details/49745569

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<map>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=100000+10;
int n,m,a[N];
long long b[N*4],c[N*4];
int lowbit(int x)
{
    return x&(-x);
}
long long query(long long *d,int x)
{
    int res=0;
    while(x)
    {
        res+=d[x];
        x-=lowbit(x);
    }
    return res;
}
void update(long long *d,long long x,long long v )
{
    while(x<=n)
    {
        d[x]+=v;
        x+=lowbit(x);
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int cnt=0,ans=inf;
        scanf("%d%d",&n,&m);
        memset(b,0,(n+3)*sizeof(long long));
        memset(c,0,(n+3)*sizeof(long long));
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1+m;i<=n;i++)
        {
            cnt+=i-m-1-query(b,a[i]);
            update(b,a[i],1);
        }
        ans=cnt;
        for(int i=m+1;i<=n;i++)
        {
            cnt+=query(b,a[i-m]-1);
            cnt+=query(c,n)-query(c,a[i-m]);
            update(c,a[i-m],1);
            cnt-=query(b,a[i]-1);
            cnt-=query(c,n)-query(c,a[i]);
            update(b,a[i],-1);
            ans=min(ans,cnt);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

 

Inversion_树状数组


联系
我们