网站优化一年多少钱,邢台太行中学地址,做的比较好的海鲜网站,网站后台示演链接#xff1a;https://ac.nowcoder.com/acm/contest/308/D来源#xff1a;牛客网 题目描述 tokitsukaze给你一个长度为n的序列#xff0c;这个序列是1到n的一种排列。然后她会进行q次操作。每次操作会给你L R k这三个数#xff0c;表示区间[L,R]往右移动k次。移动一次的…链接https://ac.nowcoder.com/acm/contest/308/D来源牛客网 题目描述 tokitsukaze给你一个长度为n的序列这个序列是1到n的一种排列。 然后她会进行q次操作。每次操作会给你L R k这三个数表示区间[L,R]往右移动k次。 移动一次的定义是一个数的位置是P(L≤P≤R-1)它往右移动后就会在P1这个位置上如果一个数在R这个位置它会移动到L这个位置。 在每次操作结束后tokitsukaze想让你算出现在这个序列的逆序数的多少简单起见你只需要告诉她现在这个序列的逆序数是奇数还是偶数就行了。 提示序列的逆序数指的是a[i]a[j](ij)满足条件的(i,j)的个数。 输入描述: 第一行包括一个正整数n(1≤n≤10^5)。接下来一行包括一个长度为n的序列序列为1到n的一种排列。第三行包括一个正整数q(1≤q≤10^5)。接下来q行每行包括三个正整数L,R,k(1≤L≤R≤n1≤k≤10^9)。所有变量的含义题面均有给出。 输出描述: 在每次操作后逆序数如果是奇数就输出1如果是偶数就输出0。 示例1 输入 复制 4
2 3 1 4
3
1 3 2
2 4 1
2 3 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。题意 每次选择一个区间循环变换 求整个串的逆序数是奇数还是偶数思路分析 首先可以很容易求出整个序列的逆序数是多少然后循环移位某一个区间时会有个小特点就是移动一步时逆序数变化只会取决于他前面可操作区间的长度若其为偶数则逆序数的奇偶不会发生变化否则会产生变化。代码示例 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 ans1;}
}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-l1);int len (r-l)*k;if (len1) ans 1;ans ans1;printf(%d\n, ans);}return 0;
}转载于:https://www.cnblogs.com/ccut-ry/p/10087216.html
