题解 P3567 【[POI2014]KUR-Couriers】

· · 题解

我非常喜欢暴力的算法，于是我用莫队a掉了这题

莫队是一种非常神奇的算法。上可吊打正解，下可卡成暴力。不会莫队？洛谷上的板子题P2709小B的询问

莫队的复杂度似乎不可以接受，但是常数小啊。再加上数据较水，侥幸能过不开氧跑当然悬

莫队的基本XJB操作我就不说了，另外加了玄学的东西，复杂度这种东西，说不准，看出题人心情，但是就算故意捏数据也不会卡太多的毕竟mo队

说点正经的。数据保证每个数都小于N，故省去离散化。我们先记录下每个数在数列中出现的总次数，按照大小排序。在每一次移动操作中更新每个数的出现次数。

然后就是玄学操作了。每次移动后，按总共出现的次数（一定是整个数列总的出现次数）从大到小检查是否有符合出现次数要求的，直至总的出现次数小于等于区间长度的一半。

要是在考场上肯定没有多少人敢打

移动过程中加了特判可以骗不少分

代码奉上 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=500007;
int a[N],n,m,size,Ans[N],num[N],flag,len;
const int ch_top=4e8+3;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
inline int read(){
    while(*++now_r<'0');
    register int x=*now_r-'0';
    while(*++now_r>='0')x=x*10+*now_r-'0';
    return x;
}//读入优化
inline void write(ll x){
    static char st[20];static int top;
    while(st[++top]='0'+x%10,x/=10);
    while(*++now_w=st[top],--top);
    *++now_w='\n';
}//输出优化
struct node1{int tot,id;}b[N];//存储出现次数
struct node2{int l,r,pos,id;}c[N];//存储询问信息
inline bool cmp1(node1 a,node1 b){
    if(a.tot==b.tot)return a.id<b.id;
    return a.tot>b.tot;
}
inline bool cmp2(node2 a,node2 b){
    if(a.pos==b.pos)return b.pos&1?a.r<b.r:a.r>b.r;
    return a.l<b.l;
}//莫队的玄学优化
int main(){
    fread(ch,1,ch_top,stdin);
    n=read(),m=read();
    size=sqrt(n);
    for(register int i=1;i<=n;++i){
        a[i]=read();
        b[a[i]].tot++;//记录每个数在数列中出现次数
        b[a[i]].id=a[i];//记录数值方便调用
    }
    for(register int i=1;i<=m;++i){
        c[i].l=read();//区间左端点
        c[i].r=read();//区间右端点
        c[i].id=i;//询问编号
        c[i].pos=(c[i].l-1)/size+1;//莫队日常
    }
    sort(b+1,b+n+1,cmp1);
    sort(c+1,c+m+1,cmp2);
    int l=1,r=0,ans=0;
    for(register int i=1;i<=m;++i){
        len=(c[i].r-c[i].l+1)>>1,flag=0;
        while(l<c[i].l)num[a[l++]]--;//左指针出界,调整
        while(r>c[i].r)num[a[r--]]--;//右指针出界,调整
        while(l>c[i].l)if(++num[a[--l]]>len)flag=1,ans=a[l];//左指针在区间内的情况
        while(r<c[i].r)if(++num[a[++r]]>len)flag=1,ans=a[r];//右指针在区间内的情况
        //若在区间内且满足条件,特判
        if(!flag){
            for(register int j=1;b[j].tot>len;++j)//按总出现次数进行枚举
                if(num[b[j].id]>len){
                    flag=1;
                    ans=b[j].id;
                    break;//满足条件后退出
                }
        }
        if(flag)Ans[c[i].id]=ans;//记录答案
            else Ans[c[i].id]=0;
    }
    for(register int i=1;i<=m;i++)write(Ans[i]);
    fwrite(ch,1,now_w-ch,stdout);//IO优化
}