P10749 题解

· · 题解

题意简述

对于一个序列，你可以进行一种操作是取序列中两个值不同的数并消除掉它们。给定一个长为 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;
}