牛客练习赛33 D. tokitsukaze and Inverse Number(逆序数定理)

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,pre[maxn];
map<int,int> ma;
 
int lowbit(int x){return x & (-x);}
 
void Update(int x){
  for(int i=x;i<=n;i+=lowbit(i)){
    ma[i] ++;
  }
}
 
int Query(int x){
  int ans = 0;
  for(int i=x;i>=1;i-=lowbit(i)){
    ans += ma[i];
  }
  return ans;
}
 
int main()
{
  while(~scanf("%d",&n)){
    ma.clear();
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=n;i++){
      scanf("%d",&pre[i]);
      // pre[i]++;
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
      Update(pre[i]);
      ans += (i - Query(pre[i])) % 2;
    }
    int m;
    scanf("%d",&m);
    while(m--){
      int l, r, k;
      scanf("%d%d%d",&l,&r,&k);
      ans += (r - l) % 2 * k % 2;
      printf("%d\n",ans % 2);
    }
  }
  return 0;
}