题目链接：
https://ac.nowcoder.com/acm/problem/20861
题面：
兔子最近喜欢上了逆序对。
一个逆序对(i,j) 需要满足 i < j 且 ai > aj
兔子觉得只是求一个序列的逆序对个数太没有意思了。
于是兔子想到了一个更有趣的问题！
兔子可以把区间[L,R] 反转，例如序列{1,2,3,4} 反转区间[1,3] 后是{3,2,1,4}。
兔子有m次反转操作，现在兔子想知道每次反转后逆序对个数是奇数还是偶数，兔子喜欢偶数，而讨厌奇数。
请注意，每一次反转操作都会对原序列进行改变。例如序列{1,2,3,4} 第一次操作区间[1,2] 后变成{2,1,3,4} 第二次反转区间[3,4] 后变成 {2,1,4,3} \
输入描述:
第一行一个整数 n，表示序列的大小。
第二行 n 个整数ai 表示序列的各个元素。
第三行一个整数m，表示操作个数。
接下来 m 行，每行两个整数 l，r，表示反转的区间。
输出描述:
输出共m行每行一个字符串，表示反转后序列逆序对个数的奇偶性，如果是逆序对个数奇数，输出"dislike"(不含引号)，如果是偶数，输出"like"。
input:
4
1 2 3 4
4
1 2
3 4
1 4
2 3
output:
dislike
like
like
dislike
说明
注意：以下的(i,j)指的是位置 i 和位置 j
a={2,1,3,4} 的逆序对是 (1,2) 共1个，1是奇数，所以是dislike
a={2,1,4,3} 的逆序对是 (1,2) (3,4)共2个,2是偶数，所以是like
a={3,4,1,2} 的逆序对是 (1,3) (1,4) (2,3) (2,4)共4个,4是偶数，所以是like
a={3,1,4,2} 的逆序对是 (1,2) (1,4) (3,4) 共3个,3是奇数，所以是dislike
对于20%的数据
1 ≤ n ≤ 100
1 ≤ m ≤ 10
对于40%的数据
1 ≤ n ≤ 2000
1 ≤ m ≤ 50
对于60%的数据
1 ≤ n ≤ 2000
1 ≤ m ≤ 104
对于100%的数据
1 ≤ n ≤ 105
1 ≤ m ≤ 2*106
对于所有数据 l ≤ r且 ai 是n的一个排列，即ai互不相同且ai ≤ n
由于读入数据较大，建议使用快速读入。
做题过程：
首先看到统计数组的逆序数，想到归并排序。 \
// 本段OS可以直接跳过。
结果题目没看完，以为每次逆转后就回归原位，就哐哧哐哧地写代码了（大忌 = 大寄） \
没看题目瞎写代码的思路： \
每次给定一个范围逆转，那从这个范围之后的数据(r+1, n)序列中每个数往前看对应的逆序对个数保持不变。 \
只要每次把原数组中的子序列逆转一下再统计一下从起始到 r 的这个逆序对个数即可
// 在写代码中发现的全局变量与递归的问题：
// 在不传入引用到函数中时。即，如果是main函数中定义的局部变量，然后在main中调用函数且只传局部变量的值进去，则该局部变量的数值不会被修改
// 在传入引用到函数中时。该局部变量的数值会被修改
// 在传入全局变量到函数中去时。该全局变量可能不会被修改。
上下参考：
https://blog.nowcoder.net/n/fd3f35f8348e40fe90e37510a3aa48e5
https://ac.nowcoder.com/acm/problem/15163
接着纠正错误后写完代码被卡TLE，只过40%。
#include<iostream>
using namespace std;
int n, m;
int a[2000010] = {};
int b[2000010] = {};
int c[2000010] = {};
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') {
f = -1;
}
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return f * x;
}
void merge(int l, int mid, int r, int& cnt) {
int i = l, j = mid + 1;
int k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
b[k++] = a[i++];
}
else if (a[i] > a[j]) {
b[k++] = a[j++];
cnt += (j - k);
}
}
while (i <= mid) {
b[k++] = a[i++];
}
while (j <= r) {
b[k++] = a[j++];
}
for (int p = l; p <= r; p++) {
a[p] = b[p];
}
}
void erfen (int l, int r, int & cnt) {
if (l >= r) return ;
int mid = (l + r) >> 1;
erfen(l, mid, cnt);
erfen(mid+1, r, cnt);
merge(l, mid, r, cnt);
}
int main () {
n = read();
for (int i = 1; i <= n; i++) {
c[i] = read();
}
m = read();
int l = 0, r = 0;
while (m--) {
int cnt = 0;
l = read();
r = read();
for (int i = 1; i <= l-1; i++) {
a[i] = c[i];
}
for (int i = l; i <= r; i++) {
a[i] = c[l + (r-i)];
}
for (int i = r+1; i <= n; i++) {
a[i] = c[i];
}
for (int i = 1; i <= n; i++) {
c[i] = a[i];
}
// cout << endl << "c[i] : ";
// for (int i = 1; i <= n; i++) {
// cout << c[i] << " ";
// }
erfen(1, n, cnt);
// cout << endl << "cnt : " << cnt << endl;
if (cnt % 2 == 0) {
cout << "like" << endl;
}
else {
cout << "dislike" << endl;
}
}
}
经过阅读他人代码发现这是一个思维题。 \
假设有一个长度为 n 的序列，其逆序对的个数为 x，经过逆转，其逆序对的个数为：
因为题目只要求判定逆转后的逆序对数量的奇偶性，因此，在已知原序列逆序对数量的奇偶性的情况下，只需要知道逆转前后逆序对数量变化量的奇偶性即可
逆转前后逆序对数量变化量：
由上式易得，逆转前后逆序对数量变化量的奇偶性由 的奇偶性决定。
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[100010] = {};
int b[100010] = {};
long long cnt = 0;
bool flag = 0;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') {
f = -1;
}
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return f * x;
}
/*
void merge(int l, int mid, int r) {
int i = l, j = mid + 1;
int k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
b[k++] = a[i++];
}
else if (a[i] > a[j]) {
b[k++] = a[j++];
cnt += (j - k);
// cnt = cnt&1;
// cnt += mid - i + 1;
}
}
while (i <= mid) {
b[k++] = a[i++];
}
while (j <= r) {
b[k++] = a[j++];
}
for (int p = l; p <= r; p++) {
a[p] = b[p];
}
}
*/
void erfen (int l, int r) {
if (l >= r) return ;
int mid = (l + r) >> 1;
erfen(l, mid);
erfen(mid+1, r);
int i = l, j = mid + 1;
int k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
b[k++] = a[i++];
}
else if (a[i] > a[j]) {
b[k++] = a[j++];
cnt += (j - k);
// cnt = cnt&1;
// cnt += mid - i + 1;
}
}
while (i <= mid) {
b[k++] = a[i++];
}
while (j <= r) {
b[k++] = a[j++];
}
for (int p = l; p <= r; p++) {
a[p] = b[p];
}
}
int main () {
std::ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
n = read();
for (int i = 1; i <= n; i++) {
a[i] = read();
}
m = read();
int l = 0, r = 0;
erfen(1, n);
if (cnt&1) flag = 1;
while (m--) {
l = read();
r = read();
long long judge = (r-l+1)*1LL*(r-l)/2;
if (judge&1) flag ^= 1;
if (flag) {
cout << "dislike" << endl;
}
else {
cout << "like" << endl;
}
}
}
令我百思不得其解的是，上面的代码通过率60%，报TLE。
下面的和我思路完全一致的代码，AC
#include <bits/stdc++.h>
using namespace std;
int a[100007], b[100007], cnt;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c>'9') {
if (c == '-') f = -1;
c = getchar();
}///整数符号
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}///挪位加数
return x * f;
}
void merge_sort(int l, int r) {
if (l == r) return;
int mid = l + r >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) b[k++] = a[i++];
else b[k++] = a[j++], cnt += mid - i + 1;
}
while (i <= mid) b[k++] = a[i++];
while (j <= r) b[k++] = a[j++];
for (int i = l;i <= r;i++) a[i] = b[i];
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n = read();
for (int i = 0;i < n;i++) a[i] = read();
merge_sort(0, n - 1);
bool flag = cnt & 1;
int m = read();
while (m--) {
int l = read(), r = read();
long long feat = 1LL * (r - l + 1) * (r - l) / 2;
if (feat & 1) flag ^= 1;
if (flag) cout << "dislike" << '\n';
else cout << "like" << '\n';
}
return 0;
}
经评论区大佬指正，把最后输出的cout换成printf，成功AC，感恩大佬
所以之前代码的TLE是输出超时的原因，
继续探索：
在网上找相关资料时看到的碎片信息汇总备忘
-
“用g++编译器，解除同步之后cout比printf快了好几倍。当然如果用的是VS的话cout肯定不行，因为VS的cout使用printf写的，g++的cout流本身比printf快得多。”
-
”总结来看还是要看 cout 的实现方式，不同版本实现略有区别。 gcc 使用的比g++要慢。“
于是，我把自己的代码的提交语言环境从C++(clang++ 11.0.1)切换到C++(g++ 7.5.0)，但是还是卡时间TLE（我猜可能编译器版本实现不同吧）
-
通过cin.tie与sync_with_stdio加速输入输出，可以将cin的速度接近scanf的速度，但具体要更具编译器的情况。
-
“当输出数据量比较大时，printf 比 cout 有更快的速度”
-
"设置 sync_with_stdio(false) , 用 '\n' 不用 endl 就好了. 关掉这个的 cout 应该比 printf 快. 另看到 benchmark 称 sstream 比 snprintf 慢。"
-
std::ios::sync_with_stdio(false);cin.tie(0); cin、cout之所以效率低，是因为先把要输出的东西存入缓冲区，再输出，导致效率降低，而这段语句可以来打消iostream的输入、输出缓存，可以节省许多时间
-
tie是将两个stream绑定的函数，空参数的话返回当前的输出流指针 sync_with_stdio 这个函数是一个“是否兼容stdio”的开关，C++为了兼容C，保证程序在使用了std::printf和std::cout的时候不发生混乱，将输出流绑到了一起。
-
在默认的情况下cin绑定的是cout，每次执行 << 操作符的时候都要调用flush，这样会增加IO负担。可以通过tie(0)（0表示NULL）来解除cin与cout的绑定，进一步加快执行效率。
-
......
以此题为鉴，大数据输出还是老老实实用printf比较稳。
京公网安备 11010502036488号