题解：P13688 【MX-X16-T6】「DLESS-3」XOR and Powerless Suffix Mode

· · 题解

被做局了。

考虑枚举众数，记 c_i 为出现次数，那么它对答案的贡献次数是 \sum_{T=1}^{pc_i\over 100}\prod_{i\neq j} \sum_{k=0}^T\binom{c_j}{k}。

根据 lucas 定理，容易得到 x! 的质因数分解有 x-\text{popcnt}(x) 个 2，所以 \binom{n}{m}\equiv [n\operatorname{and} m=m]\pmod 2。

所以关于 \sum_{k=0}^T\binom{c_j}{k}，我们只要判断 \le T 的最大的 c_j 的子集的最低位是否和 c_j 相同即可。仔细分析可以得到这等价于 T\operatorname{and} c_j-1=T。那我们把 j\neq i 的 c_j-1\ \operatorname{and} 起来以后只要求一个 \sum_{T=1}^{pc_i\over 100}[T\operatorname{and}x=T]，这个跟刚刚的形式完全一样，所以只要做一个前后缀和就可以 O(nq) 了。

然后这个贡献次数只和 c_i 有关，c_i 又只有 O(\sqrt{n}) 种，所以直接莫队+链表维护即可 O((n+q)\sqrt{n+q})。

但是直接写这个会 TLE，原因是虽然 2^{24} 可以开桶存，但是寻址很慢，所以加上离散化就可以过了。

还有一个优化是把链表改成只加数，最后再把不合法的数删掉，这样常数小很多。

#include <bits/stdc++.h>
#define uint unsigned int
using namespace std;
inline int read(){
    int x=0;bool f=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return f?x:-x;
}
int n,m,B,tot,a[250005],A[250005],bl[250005],ans[250005],cnt[250005],val[250005],
v[250005],ccnt[250005],pre[1145],suf[1145],b[250005];
bitset<250005> vis;
struct qr{
    int l,r,p,id;
    bool operator <(qr &x) const{
        return bl[l]^bl[x.l]?l<x.l:bl[l]&1?r<x.r:r>x.r;
    }
}q[250005];
void Add(int x,int vl=1){
    int v=cnt[x];
    ccnt[v]--,val[v]^=A[x];
    cnt[x]+=vl,v+=vl;
    if(!vis[v]) b[++tot]=v,vis[v]=1;
    ccnt[v]++,val[v]^=A[x];
}
bool check(int x,int v){
    return (x&v)==x;
}
int main(){
    n=read(),m=read(),B=sqrt(n);
    for(int i=1;i<=n;i++) A[i]=a[i]=read(),bl[i]=(i-1)/B+1;
    sort(A+1,A+n+1);
    int nn=unique(A+1,A+n+1)-A-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(A+1,A+nn+1,a[i])-A;
    for(int i=1;i<=m;i++) q[i]={read(),read(),read(),i};
    sort(q+1,q+m+1),ccnt[0]=n+1;
    int T=0;
    for(int L=1,R=0,i=1;i<=m;i++){
        while(L>q[i].l) Add(a[--L]);
        while(R<q[i].r) Add(a[++R]);
        while(L<q[i].l) Add(a[L++],-1);
        while(R>q[i].r) Add(a[R--],-1);
        for(int i=1;i<=tot;i++)
            if(!ccnt[b[i]])
                vis[b[i]]=0,swap(b[i],b[tot]),tot--,i--;
//      cout<<tot<<'\n';
        pre[0]=suf[tot+1]=(1<<18)-1;
        int lp=0,ls=tot+1;
        for(int j=1;pre[j-1]&&j<=tot;j++) lp=j,pre[j]=pre[j-1]&(b[j]-1);
        for(int j=tot;suf[j+1]&&j;j--) ls=j,suf[j]=suf[j+1]&(b[j]-1);
        for(int j=max(ls-1,1);j<=min(lp+1,tot);j++){
            int c=(ccnt[b[j]]>1?(lp==tot?pre[tot]:0):pre[j-1]&suf[j+1]);
            if(!check(b[j]*q[i].p/100,c-1)) ans[q[i].id]^=val[b[j]];
        }
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}