自动搬运

查看原文

来自洛谷，原作者为

	Hadtsti See you in the next world.

搬运于2025-08-24 23:00:53，当前版本为作者最后更新于2024-08-29 17:06:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述

对于一个序列，你可以进行一种操作是取序列中两个值不同的数并消除掉它们。给定一个长为 $n$ 的序列 $a_i$，多次查询对 $a_i$ 的一个区间尽可能多地做操作，最后剩下的相同的数有多少种。

题目分析

首先我们考虑对一个确定的序列这个种数怎么求。设序列长度为 $n$，那么如果一个数出现的次数大于等于 $\lceil\frac n2\rceil$，别的数一定不会剩下。但这个数本身在一种特殊情况下也不会剩下：$n$ 为偶数且序列只有两种数，同时它们的出现次数都是 $\frac n2$，这时没有数会剩下。

其他情况，对于一个数 $x$，我们让其它的数互相消除直到不能消下去。则一定存在一种消除方式使得剩下的其它数个数不大于 $x$ 出现次数，反之对于所有消除方式剩下的那种数 $y$ 都会消除掉其它的包括 $x$ 在内的所有数，与不存在绝对众数矛盾！事实上 $x$ 出现了多于一次就可以保留至少 $1$ 个，否则当数的总个数是奇数时才可以。

放到区间里就求一下是否有绝对众数、出现数的种数和只出现一次的数个数。前者可以转化为主席树求区间中位数，后者用莫队简单维护即可。实现细节看代码。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,q,ID[500010],T,a[500010],rt[500010],cnt,CT[500010],ct1,ct,ans[500010];
struct node
{
	int ls,rs,id;
	int cnt;
}tr[20000010];
vector<int>pos[500010];
struct query
{
	int l,r,id;
	friend bool operator <(query a,query b)
	{
		return ID[a.l]^ID[b.l]?ID[a.l]<ID[b.l]:ID[a.l]&1?a.r<b.r:a.r>b.r;
	}
}Q[500010];
void add(int x)
{
	if(!CT[a[x]])
		ct++,ct1++;
	if(CT[a[x]]==1)
		ct1--;
	CT[a[x]]++;
}
void del(int x)
{
	CT[a[x]]--;
	if(!CT[a[x]])
		ct--,ct1--;
	if(CT[a[x]]==1)
		ct1++;
}
void build(int &p,int l,int r)
{
	p=++cnt;
	tr[p].cnt=0;
	if(l==r)
		return;
	int mid=l+r>>1;
	build(tr[p].ls,l,mid);
	build(tr[p].rs,mid+1,r);
}
void change(int &p,int x,int l,int r)
{
	tr[++cnt]=tr[p];
	p=cnt;
	tr[p].cnt++;
	if(l==r)
		return;
	int mid=l+r>>1;
	if(mid>=x)
		change(tr[p].ls,x,l,mid);
	else
		change(tr[p].rs,x,mid+1,r);
}
int query(int p,int q,int l,int r,int k)
{
	if(l==r)
		return l;
	int x=tr[tr[q].ls].cnt-tr[tr[p].ls].cnt,mid=l+r>>1;
	if(x>=k)
		return query(tr[p].ls,tr[q].ls,l,mid,k);
	else
		return query(tr[p].rs,tr[q].rs,mid+1,r,k-x);
}
int calc(int x,int l,int r)
{
	return upper_bound(pos[x].begin(),pos[x].end(),r)-lower_bound(pos[x].begin(),pos[x].end(),l);
}
int main()
{
	scanf("%d%d",&n,&q);
	T=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		ID[i]=(i-1)/T+1;
	}
	build(rt[0],1,n);
	for(int i=1;i<=n;i++)
	{
		pos[a[i]].push_back(i);
		rt[i]=rt[i-1];
		change(rt[i],a[i],1,n);
	}
	for(int i=1;i<=q;i++)
		scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
	sort(Q+1,Q+q+1);
	for(int i=1,L=1,R=0;i<=q;i++)
	{
		int l=Q[i].l,r=Q[i].r;
		while(L>l)
			add(--L);
		while(L<l)
			del(L++);
		while(R<r)
			add(++R);
		while(R>r)
			del(R--);
		int mx=query(rt[l-1],rt[r],1,n,(r-l+1)/2),smx=query(rt[l-1],rt[r],1,n,r-l+2-(r-l+1)/2);
		int c=max(calc(mx,l,r),calc(smx,l,r));
		if(r-l+1&1)	
		{
			if(c>=(r-l+2)/2)
				ans[Q[i].id]=1;
			else
				ans[Q[i].id]=ct;
		}
		else
		{
			if(c>=(r-l+1)/2)
			{
				if(ct==2&&mx^smx)
					ans[Q[i].id]=0;
				else
					ans[Q[i].id]=1;
			}
			else
				ans[Q[i].id]=ct-ct1;
		}
	}
	for(int i=1;i<=q;i++)
		printf("%d\n",ans[i]);
	return 0;
}