题解：CF1514D Cut and Stick

#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;
}