P11016 XOR Pairs 题解

· · 题解

P11016 XOR Pairs 题解

很有意思的一道数学题。随机跳到的，做完后发现似乎题解没有相似的思路（？）于是尝试交一发题解。

详细的证明请看其他的题解，这里来讲一下蒟蒻开题的思路。

看到题目后，毫无思路，怎么办？

我们首先按照题意模拟一下

规律这不就到手了^-^

可以得到在比x大的情况下，满足题目的数与 log_2x 相关

然后我们分别统计xmod 2^y>2^{y-1}

(1<=y<=20)

的数量（即在以2^{y-1}为周期上数的数量） 和每个y对答案的贡献

修改a_x的同时修改贡献和周期上的数即可

#include<iostream>
using namespace std;
int n,q,cnt[25][2],a[1000005],cc[25];//cc为贡献统计，cnt[x][1]为以2^x为周期上为1的数的数量
long long ans;
int getw(int num){
    int p=0;
    while(num>=(1<<p)){
        p++;
    }
    return p;
}//log2 +1
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        for(int c=1;c<=19;c++){
            int mid=1<<(c-1),s=1<<c;
            if(a[i]>=s){
                if(a[i]%s<mid){
                    cnt[c][1]++;
                }
                else{
                    cnt[c][0]++;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        //cout<<<<" ";
        int w=getw(a[i]);
        ans+=cnt[w][1];
        cc[w]++;
    }

    for(int i=1;i<=q;i++){
        int x,y;
        cin>>x>>y;

        for(int c=1;c<=19;c++){
            int mid=1<<(c-1),s=1<<c;
            if(a[x]>=s){
                if(a[x]%s<mid){
                    cnt[c][1]--;
                }
                else{
                    cnt[c][0]--;
                }
            }
        }
        for(int c=1;c<=19;c++){
            int mid=1<<(c-1),s=1<<c;
            if(y>=s){
                if(y%s<mid){
                    cnt[c][1]++;
                }
                else{
                    cnt[c][0]++;
                }
            }
        }
        cc[getw(a[x])]--;
        cc[getw(y)]++;
        a[x]=y;
        ans=0;
        for(int i=1;i<=20;i++)ans+=cc[i]*cnt[i][1];
        cout<<ans<<endl;
    }
    return 0;
}

大概是新思路，求过吧