题解：CF1514D Cut and Stick

可爱大黄兔 · 2025-02-09 11:43:15 · 题解

注意到若区间内一个数 x 出现次数 cnt \geq \dfrac{len}{2}，则它二进制下的第 k 位 a 的出现次数一定大于等于 \dfrac{len}{2}，因此我们可以以 \mathcal{O}(q) 的复杂度解决这题。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int ret=0;
    char c=getchar(),ch=' ';
    while(!('0'<=c&&c<='9')) ch=c,c=getchar();
    while('0'<=c&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ch=='-'?-ret:ret;
}
inline void write(int x){
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const int N=3*1e5+10;
int a[N];
int num[N];
int s[N][20];
vector<int> g[N];
int n,m;int x;
bool v[N];
int solve(int l,int r){
    int len=r-l+1;
    int x=0;
    for(int k=0;k<20;k++){
        int sum=s[r][k]-s[l-1][k];
        if((sum<<1)>len)x|=1<<k;
    }
    if(v[a[x]]==false){
        v[a[x]]=true;
        g[a[x]].push_back(n+1); 
    }
    int al=lower_bound(g[x].begin(),g[x].end(),l)-g[x].begin();
    int bl=upper_bound(g[x].begin(),g[x].end(),r)-g[x].begin();
    if((bl-al)*2 >= len){
        return bl-al;
    }
    return 0;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read(),g[a[i]].push_back(i);
    for(int i=1;i<=n;i++){
        for(int k=0;k<20;k++){
            s[i][k]=s[i-1][k];
            if(a[i]>>k & 1)s[i][k]++;
        }
    }
    while(m--){
        int l=read(),r=read(),len=r-l+1;
        int x=solve(l,r);
        if((len+1)/2>=x){
            puts("1");
        }else write(x+x-len),puts("");

    }
    return 0;
}