tokitsukaze and Inverse Number(树状数组+逆序对定理)

题目链接：点击查看

题目大意：给出一个长度为 n 的排列 a，需要执行 q 次操作，每次操作会将区间 [ l , r ] 内的数循环右移 k 次，现在需要回答每次操作后排列的逆序对数，只需要回答奇偶即可

题目分析：首先需要知道逆序对定理，也就是对于一个排列来说，交换任意一对数都会改变逆序对的奇偶，证明如下：

又因为将区间 [ l , r ] 内的数字循环右移一次用 r – l 次对换一定是可以完成的，所以记录一下每次操作共需要多少次对换次数，就可以快速更新逆序对的奇偶关系了

当然最初始的逆序对用树状数组或者其他的算法随便做做就能求出来了

代码：
 

//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;

typedef long long LL;

typedef unsigned long long ull;

const int inf=0x3f3f3f3f;

const int N=1e6+100;

int n,c[N];

int lowbit(int x)
{
	return x&(-x);
}

void add(int x)
{
	for(int i=x;i<=n;i+=lowbit(i))
		c[i]++;
}

int ask(int x)
{
	int ans=0;
	for(int i=x;i>0;i-=lowbit(i))
		ans+=c[i];
	return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.ans.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	scanf("%d",&n);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		ans=(ans+ask(n)-ask(x))%2;
		add(x);
	}
	int q;
	scanf("%d",&q);
	while(q--)
	{
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		ans=(ans+((r-l)%2*k%2))%2;
		printf("%d\n",ans);
	}
















    return 0;
}

 

本文地址：https://blog.csdn.net/qq_45458915/article/details/110678141