tokitsukaze and Inverse Number

NC21191. tokitsukaze and Inverse Number

描述

tokitsukaze给你一个长度为n的序列，这个序列是1到n的一种排列。
然后她会进行q次操作。每次操作会给你L R k这三个数，表示区间[L,R]往右移动k次。
移动一次的定义是：一个数的位置是P(L≤P≤R-1)，它往右移动后就会在P+1这个位置上；如果一个数在R这个位置，它会移动到L这个位置。
在每次操作结束后，tokitsukaze想让你算出现在这个序列的逆序数的多少，简单起见，你只需要告诉她现在这个序列的逆序数是奇数还是偶数就行了。
提示：序列的逆序数指的是：a[i]>a[j](i<j)，满足条件的(i,j)的个数。

输入描述

第一行包括一个正整数n(1≤n≤10^5)。
接下来一行，包括一个长度为n的序列，序列为1到n的一种排列。
第三行包括一个正整数q(1≤q≤10^5)。
接下来q行，每行包括三个正整数L,R,k(1≤L≤R≤n，1≤k≤10^9)。
所有变量的含义题面均有给出。

输出描述

在每次操作后，逆序数如果是奇数，就输出1，如果是偶数，就输出0。

示例1

输入:

输出:

0
0
1

说明:

原序列为：2 3 1 4
第一次操作后，序列变为：3 1 2 4，逆序数为2，所以答案为0。
第二次操作后，序列变为：3 4 1 2，逆序数为4，所以答案为0。
第三次操作后，序列变为：3 1 4 2，逆序数为3，所以答案为1。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 83ms, 内存消耗: 1532K, 提交时间: 2018-12-07 19:32:27

#include<cstdio>
using namespace std;
int n,v[100006],a,b,tr[100007],ans,c;
void add(int x,int s){for(;x<=n;x+=x&-x)tr[x]+=s;}
int que(int x){int ans=0;while(x)ans+=tr[x],x-=x&-x;return ans;}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&v[i]);
		add(v[i],1);
		ans^=((que(n))-que(v[i])&1);
	}
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		if(((b-a)&c&1)==1)ans^=1;
		printf("%d\n",ans);
	}
}

上一题

下一题

详情