树状数组求逆序对

树状数组模板：

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(\log n)$O(logn)相比线段树的系数要少很多。

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

建树过程：

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]，我需要遍历所有的$lowbit$lowbit，也即sum[7]=a[7]+a[6]+a[4]

​ 具体过程:

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

普通逆序对

​ 在插入前先扫一遍，之前插入的数中比他大的数的个数之和也就是$et_sum(n)-get_sum(x)$ets​um(n)−gets​um(x)，然后每次对每个数更新都是$update(x,1)$update(x,1)，给$x$x位置加上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

翻转逆序对

每次翻转：$C_{n}^{2}-原来的逆序对个数$Cn2​−原来的逆序对个数就是现在的逆序对个数，然后根据奇偶性

假设逆序对的个数为$ans$ans则：反转后

$ans=ans-x+C_n^2-x$ans=ans−x+Cn2​−x显然$-2x$−2x为偶数，所以只需要判断$ans和C_n^2$ans和Cn2​

当$C_n^2,ans$Cn2​,ans都为奇数时，$ans$ans变为偶数，也就是翻转后逆序对的个数为偶数个。

这个变化是可以看出只有当$C_n^2$Cn2​为奇数时才会变化$ans$ans的奇偶性

#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