出题组题解 | CXXP#1 T4

T4 皮皮虾写书法

• 难度：普及+/提高
• 思路：计算原数组和绝对值数组的逆序对数量。偶次幂切换为绝对值判断，奇次幂切回原数组，验证逆序对 $≤k$ 且差值偶或者有重复则对，否则掉。

#include<bits/stdc++.h>
using namespace std;
const int CN=1e5+15;
int n,nn,x,m,w,vis;
bool repeat[2];  
long long k;
int a[CN],disc[CN],bitr[CN];
long long ans[2]; 

inline void read(int &x){
    x=0;
    bool neg=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch^'-') ch=getchar();
    if(ch=='-'){
        neg=true;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    if(neg) x*=-1;
    return;
}

inline void read(long long &x){
    x=0;
    bool neg=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch^'-') ch=getchar();
    if(ch=='-'){
        neg=true;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    if(neg) x*=-1;
    return;
}

inline int lowbit(const int &x){return x&-x;}

inline void update(const int &q,const int &c){
    for(int i=q;i<=nn;i+=lowbit(i)) bitr[i]+=c;
    return;
}

inline int query(const int &q){
    int res=0;
    for(int i=q;i>=1;i-=lowbit(i)) res+=bitr[i];
    return res;
}

inline int discre(){
    sort(disc+1,disc+1+n);
    return unique(disc+1,disc+1+n)-disc-1;
}

inline bool can(const long long &x){
    return x<=k&&(( (k-x) % 2 == 0 )||repeat[vis]);
}

int main(){
    read(n);read(k);read(m);
    vis = 0; 
    for(int i=1;i<=n;i++){
        read(a[i]);
        disc[i]=a[i];
    }

    nn=discre();
    repeat[0]=nn<n;
    for(int i=1;i<=n;i++){
        x=lower_bound(disc+1,disc+1+nn,a[i])-disc;
        ans[0]+=query(nn)-query(x);
        update(x,1);
    }

    memset(bitr,0,sizeof(bitr));
    for(int i=1;i<=n;i++) disc[i] = a[i]
    for(int i=1;i<=n;i++) if(disc[i]<0) disc[i]*=-1;
    nn=discre();
    repeat[1]=nn<n;
    for(int i=1;i<=n;i++){
        int val = (a[i]>=0) ? a[i] : -a[i];
        x=lower_bound(disc+1,disc+1+nn,val)-disc;
        ans[1]+=query(nn)-query(x);        update(x,1);
    }

    if(can(ans[vis])) puts("Yes"); 
    else puts("No");

    while(m--){
        read(w);
        if(w % 2 == 0) vis=1; 
        else vis=0;       
        if(can(ans[vis])) puts("Yes");
        else puts("No");
    }
    return 0;
}

题解仅供学习参考使用。
抄袭、复制题解，以达到刷 AC 率/AC 数量或其他目的的行为，在 ACGO 是严格禁止的。