欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树状数组求逆序对

程序员文章站 2022-07-13 21:23:22
...

树状数组模板:

int d[maxn];int n;
inline int lowbit(int x){return -x&x;}
int get_sum(int x){
    int ans=0;
    while(x){
        ans+=d[x];x-=lowbit(x);
    }
    return ans;
}

void update(int x,int y){
    while(x<=n){
        d[x]+=y;x+=lowbit(x);
    }
}

主要讲一下状数组的建立和逆序对的求解方法

树状数组:

  • 修改和查询的复杂度均为O(logn)O(\log n)相比线段树的系数要少很多。

树状数组求逆序对

采用了二进制的方法建树,仅有左儿子而无右儿子.

建树过程:

void update(int x,int y){//给x位置加上y
    while(x<=n){
        d[x]+=y;x+=lowbit(x);
    }
}

建树时要一个一个更新建树,比如说我给a[2]a[2]+1,那么本来的a[4],a[8]a[4],a[8]都要加上1,具体的添加过程可以看建树的代码

求和过程:

int get_sum(int x){
    int ans=0;
    while(x){
        ans+=d[x];x-=lowbit(x);
    }
    return ans;
}

在求和时是一层一层去求解的,比如说我求sum[7]sum[7],我需要遍历所有的lowbitlowbit,也即sum[7]=a[7]+a[6]+a[4]

​ 具体过程:

​ 7=111111那么我们遍历二进制时候先加上111=7111=7位置数,然后继续遍历下一个子节点110=6110=6,然后继续下一个子节点100100这个过程是和lowbitlowbit有关的。

普通逆序对

​ 在插入前先扫一遍,之前插入的数中比他大的数的个数之和也就是etsum(n)getsum(x)et_sum(n)-get_sum(x),然后每次对每个数更新都是update(x,1)update(x,1),给xx位置加上1,也就是这个位置的数的个数。

然后跑一边:

for(int i=1;i<=n;++i){
    ans+=ask(sum)-ask(d[i]);
    update(d[i],1);
}
https://ac.nowcoder.com/acm/problem/15163

翻转逆序对

每次翻转:Cn2C_{n}^{2}-原来的逆序对个数就是现在的逆序对个数,然后根据奇偶性

假设逆序对的个数为ansans则:反转后

ans=ansx+Cn2xans=ans-x+C_n^2-x显然2x-2x为偶数,所以只需要判断ansCn2ans和C_n^2

Cn2,ansC_n^2,ans都为奇数时,ansans变为偶数,也就是翻转后逆序对的个数为偶数个。

这个变化是可以看出只有当Cn2C_n^2为奇数时才会变化ansans的奇偶性

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '\n'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<"  : "<<x<<endl;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
using namespace std;
const int maxn = 5e5 + 10;
struct cmp {
    bool operator ()(const int& a, const int& b)const {
        return a > b;
    }
};
template<typename T>void read(T &res) {
	bool flag=false;
	char ch;
	while(!isdigit(ch=getchar()))
		(ch=='-')&&(flag=true);
	for(res=ch-48;isdigit(ch=getchar());
	res=(res<<1)+(res<<3)+ch - 48);
	flag&&(res=-res);
}
int d[maxn];int n;
inline int lowbit(int x){return -x&x;}

int get_sum(int x){
    int ans=0;
    while(x){
        ans+=d[x];x-=lowbit(x);
    }
    return ans;
}

void update(int x,int y){
    while(x<=n){
        d[x]+=y;x+=lowbit(x);
    }
}
int main()
{
    int tt,t;scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&tt);
        t+=get_sum(n)-get_sum(tt);
        update(tt,1);
    }
    t=t&1;
    int m;scanf("%d",&m);
    while(m--){
        int l,r;scanf("%d%d",&l,&r);
        int tmp=(r-l+1)*(r-l)>>1;
        if(tmp&1)t=1-t;
        if(t&1)printf("dislike\n");
        else printf("like\n");
    }

}
https://ac.nowcoder.com/acm/problem/20861