链接:
来源:牛客网题目描述
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
输入
42 3 1 431 3 22 4 12 3 1
输出
001
说明
原序列为:2 3 1 4 第一次操作后,序列变为:3 1 2 4,逆序数为2,所以答案为0。 第二次操作后,序列变为:3 4 1 2,逆序数为4,所以答案为0。 第三次操作后,序列变为:3 1 4 2,逆序数为3,所以答案为1。 题意 : 每次选择一个区间循环变换, 求整个串的逆序数是奇数还是偶数 思路分析 : 首先可以很容易求出整个序列的逆序数是多少,然后循环移位某一个区间时,会有个小特点就是,移动一步时,逆序数变化只会取决于他前面可操作区间的长度,,若其为偶数,则逆序数的奇偶不会发生变化,否则会产生变化。 代码示例 :
int n;int a[maxn];int l, r, k;int c[maxn];int lowbit(int x){return x&(-x);}void add(int pos){ for(int i = pos; i <= n; i += lowbit(i)){ c[i] += 1; }}int query(int pos){ int res = 0; for(int i = pos; i ; i -= lowbit(i)){ res += c[i]; } return res;}int ans = 0;void solve() { for(int i = 1; i <= n; i++){ add(a[i]); ans += i-query(a[i]); ans = ans&1; }}int main() { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); cin >> n; for(int i = 1; i <= n; i++) scanf("%d", &a[i]); int q; solve(); //printf("+++++ %d \n", ans); cin >> q; while(q--){ scanf("%d%d%d", &l, &r, &k); k = k % (r-l+1); int len = (r-l)*k; if (len&1) ans += 1; ans = ans&1; printf("%d\n", ans); } return 0;}