tokitsukaze and Inverse Number ( 逆序数定理 + 思维 )
程序员文章站
2022-03-21 17:41:56
...
解题报告:
交换任意相邻的数会改变逆序数奇偶性
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int tree[maxn],n,a[maxn];
int lowbit(int x)
{
return x&(-x);
}
void modify(int x)
{
for(int i=x;i<=n;i+=lowbit(i)){
tree[i]++;
}
}
int getsum(int x)
{
int ans=0;
for(int i=x;i>0;i-=lowbit(i)){
ans+=tree[i];
}
return ans;
}
int main()
{
int ans=0,q,l,r,k;
memset(tree,0,sizeof(tree));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
ans+=(i-getsum(a[i])-1);
modify(a[i]);
}
scanf("%d",&q);
while(q--){
scanf("%d%d%d",&l,&r,&k);
ans=(ans+(r-l)*k)%2;
if(ans&1){printf("1\n");}
else{printf("0\n");}
}
return 0;
}
上一篇: php echo 输出字符串函数详解
下一篇: 学php前要学c语言吗?