评价

一道逆序对的题目，挺不错的。但数据问题好大啊！！！我一开始以为操作不是独立的，然后由于题面的数据范围有误导致我过了很久才AK，但是比赛结束了我开始写题解的时候看到赛事答疑帖里有人问操作是不是独立的然后回答竟然为是……

题意

简单来说就是有$n$个数，要希望能进行恰好k次操作使得它们按照从小到大的顺序排好序，但是会进行m次修改，每次修改是独立的，一次修改会将所有数字变成它的w次方，问一开始以及每次修改后是否有可能进行恰好k次操作使它们从小到大排序。

解析

众所周知，通过交换一个数组中的相邻数字来将这些数字从小到大（或从大到小）排序所需的交换次数是这组数字中的逆序对数，而题目中的操作并不会改变这些数字的大小关系，所以只需要统计逆序对数量……
打住，通过观察样例我们发现负数是一个肥肠大的变数，众所周知一个负数的偶数次方的结果为一个正数，但奇数次方却还是负数，所以我们这里不仅需要统计逆序对的数量，还要统计负数变成其绝对值时逆序对的数量。

从小到大排序所需的交换次数的问题解决了，但注意题目里要求的是恰好k次操作，怎么办呢？首先很显而易见的是，如果所需的交换次数比k还大那不用想了，肯定不行。还有，两个数字交换一次然后再交换一次还是原来的顺序，所以如果k减去交换次数是偶数也可以。最后，两个相同的数字交换后还是原来的顺序，所以如果有两个相同的数字也可以的。

问题解决了，不过还有三个小细节要注意：

1. 数据范围比较大要离散化（因为我用的是树状数组求逆序对，归并排序应该不需要离散化）
2. 统计逆序对的变量要开long long
3. 需要判断特殊情况n = 1，因为这种情况下无法交换数字，只有k = 0时才能输出$Yes$（不过鉴于这个数据很水我严重怀疑数据里面可能根本就没有n = 1

代码

#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int MAXN = 1e5 + 5;
int n;
vector<int> v1, v2; // 统计逆序对
int a[MAXN], t1[MAXN], t2[MAXN]; // 两个树状数组，t1代表绝对值的计数树状数组，t2代表普通的计数树状数组
void add1(int x){
    for (int i = x;i <= v1.size();i += i&(-i)){
		t1[i]++;
    }
}
void add2(int x){
    for (int i = x;i <= v2.size();i += i&(-i)){
		t2[i]++;
    }
}
int pre1(int x){
    int sum = 0;
    for (int i = x;i;i -= i&(-i)){
        sum += t1[i];
    }
    return sum;
}
int pre2(int x){
    int sum = 0;
    for (int i = x;i;i -= i&(-i)){
        sum += t2[i];
    }
    return sum;
}
int index1(int x){
    return lower_bound(v1.begin(), v1.end(), x) - v1.begin() + 1;
}
int index2(int x){
    return lower_bound(v2.begin(), v2.end(), x) - v2.begin() + 1;
}
int main(){
    int m, x;
    long long k, num1 = 0, num2 = 0; // 不开long long见祖宗
    bool f1 = false, f2 = false, flag1, flag2; // f1代表是否有绝对值相同的数，f2代表是否有相同的数，flag1 flag2分别代表在w为偶/奇数时是否可行
    cin >> n >> k >> m;
    if (n == 1){ // 特判
        for (int i = 0;i <= m;i++){
            if (k == 0){
                cout << "Yes\n";
            }else{
                cout << "No\n";
            }
        }
    }
    for (int i = 1;i <= n;i++){
        cin >> a[i];
        v1.push_back(abs(a[i]));
        v2.push_back(a[i]);
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    v1.erase(unique(v1.begin(), v1.end()), v1.end());
    v2.erase(unique(v2.begin(), v2.end()), v2.end());
    for (int i = 1;i <= n;i++){
        int u = index1(abs(a[i]));
        int v = index2(a[i]);
        if (pre1(u) - pre1(u - 1)){ // 如果有相同绝对值的数
            f1 = true;
        }
        if (pre2(v) - pre2(v - 1)){ // 如果有相同的数
            f2 = true;
        }
        // 统计逆序对
        num1 += pre1(v1.size()) - pre1(u);
        num2 += pre2(v2.size()) - pre2(v);
        add1(u);
        add2(v);
    }
    flag1 = ((k >= num1) && (f1 || ((k - num1) % 2 == 0)));
    flag2 = ((k >= num2) && (f2 || ((k - num2) % 2 == 0)));
    if (flag2){ // 一开始相当于1次方
        cout << "Yes\n";
    }else{
        cout << "No\n";
    }
    for (int i = 1;i <= m;i++){
        cin >> x;
        if (x % 2 == 0){
            if (flag1){
                cout << "Yes\n";
            }else{
                cout << "No\n";
            }
        }else{
            if (flag2){
                cout << "Yes\n";
            }else{
                cout << "No\n";
            }
        }
    }
}