11.8 联测

A

显然答案 $\le 3$。

不妨设字符按出现次数排序为 $c_1,c_2,c_3$。

1. 答案为 $0$。直接判断即可。
2. 答案为 $1$。此时必定覆盖为 $c_1$，选择一个子段使得子段外的 $cnt_{c_2}=cnt_{c_3}=n$。 直接做。
3. 答案为 $2$。先覆盖若干 $cnt_{c_3}-n$ 个 $c_3$ 为 $c_1$，然后把若干 $c_1$ 换为 $c_2$。

写了一个小时的拍子，最后低级错误爆零。

B

赛时想到的聪明做法。

设 $A$ 为题面中相等的值，$B=card(A)$，$card(x)$ 表示 $x$ 二进制表示下 $1$ 的个数。

考虑枚举 $B$。

不难发现 $card(a_i)<B$ 的一定放进 $S_1$，$card(a_i)>B$ 的放进 $S_2$。

需要决策 $card(a_i)=B$。

不难发现，如果这类数中有两个不同的 $a_i$，那么一定无解。

于是所有满足这个条件的数相同，设有 $cnt$ 个。

1. $cnt=0$。直接判断。
2. $cnt=1$。枚举这个数丢进哪一边。
3. $cnt\ge2$。两边都分配一个。

注意需要满足两边的集合都非空。

线段树维护区间 $card(a_i)$ 小于/等于/大于 $x$ 的 与/或 和。

时间复杂度 $O(q\log^2n)$。

也可以使用 ST 表做到查询单 $\log$，但是空间会炸。

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define ppc __builtin_popcount
int n,q,a[N],msk;
namespace SGT
{
	int pre[N<<2][31];
	void buildpre(int p,int l,int r)
	{
		if(l==r)
		{
			for(int i=ppc(a[l]);i<=30;i++)
				pre[p][i]=a[l];
			return ;
		}
		int mid=(l+r)>>1;
		buildpre(p<<1,l,mid);
		buildpre(p<<1|1,mid+1,r);
		for(int i=0;i<=30;i++)
			pre[p][i]=pre[p<<1][i]|pre[p<<1|1][i];
	}
	int querypre(int p,int l,int r,int x,int y,int id)
	{
		if(x<=l&&y>=r) return pre[p][id];
		int mid=(l+r)>>1,ret=0;
		if(x<=mid) ret|=querypre(p<<1,l,mid,x,y,id);
		if(y>mid) ret|=querypre(p<<1|1,mid+1,r,x,y,id);
		return ret;
	}
	int suf[N<<2][31];
	void buildsuf(int p,int l,int r)
	{
		if(l==r)
		{
			for(int i=0;i<=30;i++)
				suf[p][i]=ppc(a[l])>=i?a[l]:msk;
			return ;
		}
		int mid=(l+r)>>1;
		buildsuf(p<<1,l,mid);
		buildsuf(p<<1|1,mid+1,r);
		for(int i=0;i<=30;i++)
			suf[p][i]=suf[p<<1][i]&suf[p<<1|1][i];
	}
	int querysuf(int p,int l,int r,int x,int y,int id)
	{
		if(x<=l&&y>=r) return suf[p][id];
		int mid=(l+r)>>1,ret=msk;
		if(x<=mid) ret&=querysuf(p<<1,l,mid,x,y,id);
		if(y>mid) ret&=querysuf(p<<1|1,mid+1,r,x,y,id);
		return ret;
	}
	int tr[N<<2][31];
	void buildtr(int p,int l,int r)
	{
		if(l==r)
		{
			for(int i=0;i<=30;i++)
				tr[p][i]=i==ppc(a[l])?a[l]:msk;
			return ;
		}
		int mid=(l+r)>>1;
		buildtr(p<<1,l,mid);
		buildtr(p<<1|1,mid+1,r);
		for(int i=0;i<=30;i++)
			tr[p][i]=tr[p<<1][i]&tr[p<<1|1][i];
	}
	int querytr(int p,int l,int r,int x,int y,int id)
	{
		if(x<=l&&y>=r) return tr[p][id];
		int mid=(l+r)>>1,ret=msk;
		if(x<=mid) ret&=querytr(p<<1,l,mid,x,y,id);
		if(y>mid) ret&=querytr(p<<1|1,mid+1,r,x,y,id);
		return ret;
	}
}using namespace SGT;
int psum[31][N];
int ssum[31][N];
int sum[31][N];
inline int queryp(int x,int l,int r){return psum[x][r]-psum[x][l-1];}
inline int querys(int x,int l,int r){return ssum[x][r]-ssum[x][l-1];}
inline int query(int x,int l,int r){return sum[x][r]-sum[x][l-1];}
int main()
{
	scanf("%d%d",&n,&q);
	msk=(1<<30)-1;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		for(int j=0;j<=30;j++)
		{
			psum[j][i]=psum[j][i-1]+(ppc(a[i])<=j);
			ssum[j][i]=ssum[j][i-1]+(ppc(a[i])>=j);
			sum[j][i]=sum[j][i-1]+(ppc(a[i])==j);
		}
	}
	buildpre(1,1,n);
	buildsuf(1,1,n);
	buildtr(1,1,n);
	while(q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		int flag=0;
		for(int i=0;i<=30;i++)
		{
			int s1=i?querypre(1,1,n,l,r,i-1):0;
			int s2=i<30?querysuf(1,1,n,l,r,i+1):msk;
			int s3=querytr(1,1,n,l,r,i);
			int cnt1=i?queryp(i-1,l,r):0;
			int cnt2=i<30?querys(i+1,l,r):0;
			int cnt3=query(i,l,r);
			if(!cnt3)
			{
				if(s1==s2&&cnt1&&cnt2)
					{flag=1;break;}
			}
			else if(cnt3==1)
			{
				if((s1==s3&&((s2&s3)==s3)&&cnt1&&(cnt2+cnt3))||
					(s2==s3&&((s1|s3)==s3)&&cnt2&&(cnt1+cnt3)))
					{flag=2;break;}
			}
			else if(ppc(s3)==i)
			{
				if((s1|s3)==s3&&(s2&s3)==s3)
					{flag=3;break;}
			}
		}
		if(flag)
			printf("YES\n");
		else
			printf("NO\n");
	}
}