题目大意

给出一个长度为 \(n\) 的排列 \(a\)。每次交换两个数，求逆序对数对 \(2\) 取模的结果。

输入格式
第一行一个正整数\(n\) 。

第二行 \(n\)个数，表示给出的排列 \(a\)。

第三行一个正整数\(q\) 。

接下来 \(q\)行，每行两个正整数 ，表示交换 \(a_i\)和 \(a_j\)。

输出格式
输出共 \(q\)行，表示每次交换后逆序对数对 \(2\)取模的结果。
样例
【输入1样例】

4
1 2 3 4
2
1 2
1 2

【输出1样例】

1
0

【输入2样例】

8
4 1 5 2 6 8 7 3
10
6 4
7 8
2 2
1 1
7 7
1 7
3 3
2 4
2 6
5 7

【输出2样例】

0
1
1
1
1
0
0
1
0
1

对于\(100\%\)的数据，\(n,q\le100000\)

基本思路

首先我们肯定要求修改前的逆序对数，那就要用到树状数组。基本原理是先从大到小将所有数排好，再逐个按位置顺序装进树状数组里，每装进一个就统计它前面有几个数，因为先于它装进去肯定会比它大。但是我们要注意相同大小的数是不能计算逆序对的，所以对于相同的数还要按位置从大到小排。

在此之前我们需要注意到题目只要我们给出奇偶性，那么事出反常必有因，这很可能是个结论题，大的方向就是哪些因素会影响逆序对数的奇偶性。

那么对于询问修改的如何统计呢？首先我们要明白若以交换的两个数之间为区间，那么此区间外的逆序对数是不会改变的，因为相对位置不变。

那么我们来考虑区间里面，首先对于两个交换的数肯定会对改变奇偶性产生 \(1\) 的贡献的，因为只要两个数不同交换就会产生加减 \(1\) 的改变。那么对于区间里面的数呢？比\(a_i\)和\(a_j\)都大或都小肯定产生不了贡献。如果夹在它们两个中间呢？那么我们可以轻易得出贡献是加减 \(2\) ，对奇偶性没影响。最终得出结论：只要交换的两个数不相等那么就改变奇偶性。（但在实践上好像只需要位置不同就可以了）

核心代码

#include <bits/stdc++.h>
using namespace std;
#define num first

#define pos second

typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+10;
int n,a[N],q,sum[N];
ll ans;
pii cnt[N];
bool compare(pii nx,pii ny){
	if(nx.num==ny.num) return nx.pos>ny.pos;
	return nx.num>ny.num;
}
int query(int x){
	int ret=0;
	for(;x;x-=(x&(-x)))
		ret+=sum[x];
	return ret;
}
int add(int x){
	int ret=query(x-1);
	for(;x<=n;x+=(x&(-x)))
		sum[x]++;
	return ret;
}
int main(){
	freopen("lyk.in","r",stdin);
	freopen("lyk.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		cnt[i].num=a[i];
		cnt[i].pos=i;
	}
	sort(cnt+1,cnt+1+n,compare);
	for(int i=1;i<=n;i++)
		ans+=add(cnt[i].pos);
	ans=ans&1;
	cin>>q;
	for(register int i=1,u,v;i<=q;i++){
		cin>>u>>v;
		if(a[u]!=a[v]) ans=!ans;
		cout<<ans<<endl;
	}
    return 0;
}