强制在线不带修区间众数相关 学习笔记

区间众数是和分块脱不了干系的。

[BZOJ 2724][Violet 6]蒲公英

草怎么是权限题

[Luogu 4168][Violet]蒲公英

题意简述

给出一个长为$n$的数列，$m$次询问一段区间内最小的区间众数，强制在线。

$1\leq l\leq r\leq40000,m\leq50000,1\leq a_i\leq 10^9$。

主要思路1

引理1

设$\operatorname{mode}(A)$为可重集合$A$的最小众数，则有$\operatorname{mode}(A\cup B)\in\operatorname{mode}(A)\cup B$。

引理1的证明

几乎是显然的。令$t=\operatorname{mode}(A\cup B)$，若$t$既不是$\operatorname{mode}(A)$，也不属于$B$，则$t$的出现次数就是在$A$中出现的次数。而这个次数应是不大于$\operatorname{mode}(A)$出现的次数的，出现矛盾。故引理1成立。

算法

离散化，分块，块大小$S$。

对于询问$[l,r]$，根据引理1，答案只可能是 $l,r$间所有完整块的最小众数 或 不完整块中出现的数。

对于一段完整块的最小众数$f[a][b]$，可以预处理，选定最左的块$a$后$O(n)$求出$f[a][i]$，其中$a\leq i$，总预处理复杂度$O(n\lfloor\frac{n}{S}\rfloor)$。

对于不完整的块，我们可以求出每种数在$[l,r]$中出现的次数。

怎么求出某种数在$[l,r]$中出现的次数？我们可以把每种数出现的位置按顺序丢到一个$\text{vector}$里，查找时找到第一个在$l$或其后出现的位置和最后一个在$r$或其前出现的位置即可，每次查询复杂度$O(\log_2cnt[a_i])=O(\log_2n)$。

所以每次询问区间$[l,r]$时间复杂度$O(Slog_2n)$。

平衡一下，块大小取$\sqrt{\frac{n}{\log_2n}}$，总复杂度$O(n\sqrt{n\log_2n})$（$n,m$同阶）。

若本人推错了请指出

优化

有没有办法把这个$\sqrt{\log_2n}$去掉呢？

观察发现这个常数来自求某种数在$[l,r]$中出现的次数。

设$Sum(i,x)$表示$[1,i]$间$x$的个数，我们需要回答的就是$Sum(r,x)-Sum(l-1,x)$。

处理$C[b][x]$表示第$1$到第$b$块中$x$出现的次数，需要$O(n\lfloor\frac{n}{S}\rfloor)$的空间与时间。

处理$A[b][i][x]$表示从第$b$块开头开始的$i$个数中$x$的出现次数。因为每个块最多只有$S$种数，故复杂度$O(S^2\lfloor\frac{n}{S}\rfloor)=O(nS)$。

然后就可以$O(1)$地回答$Sum(i,x)$，可以将块大小设为$\sqrt{n}$，时空复杂度均为$O(n\sqrt{n})$（$n,m$同阶）。

参考代码

然后你就会发现这玩意难写得很，所以我放弃了……

主要思路2

我们希望找到一个空间可以较小，且码量也较小的方法。

仍然离散化分块，块大小$S$，仍求出$f[a][b]$为一段完整块的最小众数，并附带求出该数的出现次数$num[a][b]$。

仍把每种数$x$的出现位置开一个$\text{vector}$（名$pos[x]$）按顺序存起来，同时对于数列中每个位置标记该位置在$\text{vector}$中的下标$id[i]$。

什么？没看懂？那就多看几遍

算法

设询问区间为$[l,r]$，包含完整块$[a,b]$。

首先$mode=f[a][b]$，出现次数$cnt=num[a][b]$。

然后处理两边的不完整块。

例如，对于$l$到块$a-1$的结尾处这部分：

假设处理到位置$i$，$a_i=x$。

那么，若$pos[x][id[i]+cnt]$仍存在且不在$r$的右边，显然可以更新$mode=x,cnt++$。

对于块$b+1$开头到$r$的这一部分，同理，只不过改成看$pos[x][id[i]-cnt]$是否不在$l$的左边。

可以发现，$cnt$最多更新$2S$次，若超过$2S$次则说明有数$x$在这段完整块$[a,b]$中出现次数大于$num[a][b]$，固然矛盾。所以每次询问时间复杂度$O(S)$。

预处理时间复杂度$O(n\lfloor\frac{n}{S}\rfloor)$，询问总时间复杂度$O(nS)$，故$S$取$\sqrt{n}$时复杂度降至最优$O(n\sqrt{n})$。

而空间复杂度，我们发现无论是$f,num$，还是$id,pos$，总共都只有$O(n)$的大小。

什么？没看懂？那就看看代码吧

参考代码

由于STL依赖症心血来潮，直接写了个$\text{pair}$……

#include<bits/stdc++.h>
namespace my_std{
    using namespace std;
    #define reg register
    #define Rint register int
    #define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
    #define ROF(i,a,b) for(register int i=(a);i>=(b);--i)
    #define FORit(templ,arr,i,a,b) for(register templ *i=(arr)+(a);i!=(arr)+(b)+1;++i)
    #define ROFit(templ,arr,i,a,b) for(register templ *i=(arr)+(a);i!=(arr)+(b)-1;--i)
    #define GO(x,p,e,i,v) for(register int i=p[x].head,v;i;i=e[i].link)
    #define MEM(x,v) memset(x,v,sizeof(x))
    #define fir first
    #define sec second
    #define pq priority_queue
    #define pb push_back
    #define PII pair<int,int>
    #define MP make_pair
    typedef long long LL;
    typedef double DB;
    inline int read(){
        int ans=0,f=1;char c=getchar();
        while(!isdigit(c)){ f^=(c=='-'); c=getchar(); }
        for(;isdigit(c);c=getchar()) ans=(ans<<1)+(ans<<3)+(c^48); return f?ans:-ans;
    }
    const int mod = 998244353 , N = 100010 , SN = 320;
    inline void inc(int &x,const int &y){ x+=y; if(x>=mod) x-=mod; }
    inline int ksm(int x,LL y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod; return res;}
    inline int gcd(int x,int y){ if(x<y) swap(x,y); return y?gcd(y,x%y):x; }
    #define FILE(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
}
using namespace my_std;
#define rsiz(h) ((int)((h)->size()))
int n,blo,ary[N],a[N],bl[N],id[N],cnt[N],m;
vector<int> pos[N];
PII f[SN][SN];

inline void checkR(int l,int r,int R,PII &res){
    Rint ans = res.sec;
    FOR(i,l,r){
        while(id[i] + ans < rsiz(pos + a[i]) && pos[a[i]][id[i] + ans] <= R) ++ans;
        if(ans > res.sec) res = MP(a[i],ans);
        else if(a[i] < res.fir && id[i] + ans <= rsiz(pos + a[i]) && pos[a[i]][id[i] + ans - 1] <= R) res.fir = a[i];
    }
    return;
}

inline PII query(int l,int r){
    Rint lb = bl[l] , rb = bl[r] , ans;
    reg PII res = (rb - lb < 2) ? MP(a[l],1) : f[lb + 1][rb - 1];
    if(lb == rb){
        checkR(l,r,r,res);
        return res;
    }
    checkR(l,blo * lb,r,res);
    ans = res.sec;
    FOR(i,blo*(rb-1)+1,r){
        while(id[i] - ans >= 0 && pos[a[i]][id[i] - ans] >= l) ++ans;
        if(ans > res.sec) res = MP(a[i],ans);
        else if(a[i] < res.fir && id[i] - ans >= -1 && pos[a[i]][id[i] - ans + 1] >= l) res.fir = a[i];
    }
    return res;
}

int main(){
    n = read() , blo = ceil(sqrt(n)) , m = read();
    Rint c = 1;
    FOR(i,1,n){
        ary[i] = a[i] = read();
        bl[i] = c;
        if(!(i % blo)) ++c;
    }
    sort(ary + 1,ary + n + 1);
    Rint siz = unique(ary + 1,ary + n + 1) - ary - 1 , l , r , lastans = 0;
    FOR(i,1,n){
        a[i] = lower_bound(ary + 1,ary + siz + 1,a[i]) - ary;
        pos[a[i]].pb(i);
        id[i] = rsiz(pos + a[i]) - 1;
    }
    FOR(i,1,bl[n]){
        MEM(cnt,0);
        reg PII res = MP(0,0);
        FOR(j,blo * (i - 1) + 1,n){
            ++cnt[a[j]];
            if(cnt[a[j]] > res.sec) res = MP(a[j],cnt[a[j]]);
            else if(cnt[a[j]] == res.sec && a[j] < res.fir) res.fir = a[j];
            f[i][bl[j]] = res;
        }
    }
    FOR(i,1,m){
        l = (read() + lastans - 1) % n + 1 , r = (read() + lastans - 1) % n + 1;
        if(l > r) swap(l,r);
        printf("%d\n",lastans = ary[query(l,r).fir]);
    }
    return 0;
}

扩展

[Ynoi2019模拟赛]Yuno loves sqrt technology III

这题是求区间众数的在区间中的出现次数。做法同上主要思路2（实际上$\text{lxl}$可能是国内第一个写这个思路的人？）。

注意卡常。

留下了卡不进总时间6.5s的泪水……

参考代码

#include<bits/stdc++.h>
namespace my_std{
    using namespace std;
    #define reg register
    #define Rint register int
    #define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
    #define ROF(i,a,b) for(register int i=(a);i>=(b);--i)
    #define FORit(templ,arr,i,a,b) for(register templ *i=(arr)+(a);i!=(arr)+(b)+1;++i)
    #define ROFit(templ,arr,i,a,b) for(register templ *i=(arr)+(a);i!=(arr)+(b)-1;--i)
    #define GO(x,p,e,i,v) for(register int i=p[x].head,v;i;i=e[i].link)
    #define MEM(x,v) memset(x,v,sizeof(x))
    #define fir first
    #define sec second
    #define pq priority_queue
    #define pb push_back
    #define PII pair<int,int>
    #define MP make_pair
    typedef long long LL;
    typedef double DB;
    inline int read(){
        int ans=0,f=1;char c=getchar();
        while(!isdigit(c)){ f^=(c=='-'); c=getchar(); }
        for(;isdigit(c);c=getchar()) ans=(ans<<1)+(ans<<3)+(c^48); return f?ans:-ans;
    }
    const int mod = 998244353 , N = 500005 , SN = 1505;
    inline void inc(int &x,const int &y){ x+=y; if(x>=mod) x-=mod; }
    inline int ksm(int x,LL y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod; return res;}
    inline int gcd(int x,int y){ if(x<y) swap(x,y); return y?gcd(y,x%y):x; }
    #define FILE(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
}
using namespace my_std;
#define rsiz(h) ((int)((h)->size()))
int n,blo,ary[N],a[N],bl[N],id[N],cnt[N],m;
vector<int> pos[N];
int f[SN][SN];

inline int query(int l,int r){
    Rint lb = bl[l] , rb = bl[r] , ans = f[lb + 1][rb - 1];
    if(!ans) ans = 1;
    if(lb == rb){
        FOR(i,l,r){
            while(id[i] + ans < rsiz(pos + a[i]) && pos[a[i]][id[i] + ans] <= r) ++ans;
        }
        return ans;
    }
    FOR(i,l,blo * lb){
        while(id[i] + ans < rsiz(pos + a[i]) && pos[a[i]][id[i] + ans] <= r) ++ans;
    }
    FOR(i,blo*(rb-1)+1,r){
        while(id[i] - ans >= 0 && pos[a[i]][id[i] - ans] >= l) ++ans;
    }
    return ans;
}

int main(){
    n = read() , m = read() ;
    blo = ceil(sqrt(n));
    Rint c = 1;
    FOR(i,1,n){
        ary[i] = a[i] = read();
        bl[i] = c;
        if(!(i % blo)) ++c;
    }
    sort(ary + 1,ary + n + 1);
    Rint siz = unique(ary + 1,ary + n + 1) - ary - 1 , l , r , lastans = 0;
    FOR(i,1,n){
        a[i] = lower_bound(ary + 1,ary + siz + 1,a[i]) - ary;
        pos[a[i]].pb(i);
        id[i] = rsiz(pos + a[i]) - 1;
    }
    FOR(i,1,bl[n]){
        MEM(cnt,0);
        FOR(j,i,bl[n]){
            f[i][j] = f[i][j - 1];
            FOR(k,(j - 1) * blo + 1,min(j * blo,n)){
                f[i][j] = max(f[i][j] , ++cnt[a[k]]);
            }
        }
    }
    FOR(i,1,m){
        l = read() ^ lastans , r = read() ^ lastans;
        if(l > r) swap(l,r);
        printf("%d\n",lastans = query(l,r));
    }
    return 0;
}

参考

区间众数解题报告 - 陈立杰

OldDriverTree(lxl)的博客

Tiger0132 Ynoi2019T3题解