P11750 「TPOI-1D」谢谢您。题解

Reunite · 2025-02-15 18:38:46 · 题解

这是两个时间复杂度 O(n\sqrt n)，空间复杂度 O(n) 的做法，下文设 n,m,q 同阶。

不考虑阈值分治，而是直接考虑对区间序列分块，设块长为 B。

先考虑整块，设 f_{i,j} 为第 i 个块 j 的最大出现次数。显然有包含关系的区间，小的区间一定没有贡献，直接删去，现在该块内所有区间 l_i,r_i 同时单调上升，我们维护 t_i,h_i 分别为当前区间每个数出现次数，以及每个数的最大出现次数，用两个指针 L,R 表示当前取到的区间，显然因为端点同时单调，顺次取到每个区间的复杂度为 O(n)，现在考虑如何更新答案。

注意到，我们从 [l_i,r_i] 移动到 [l_i+x,r_i+y] 的过程中，如果我们先移动左指针，再移动右指针，同时动态更新 t,h，那一定是对的，因为是取 \max，容易发现我们在移动过程中任意时刻任意数的出现次数，一定不大于其应在相邻两个区间中的出现次数，也就是正确的。注意过程中可以出现 L>R 的情况，但无所谓。

现在考虑散块，就转化为 O(nB) 次询问区间某个数出现次数，直接 \text{vector} 上二分复杂度 O(nB\log)，很不牛。于是分出了两种做法：

• 注意到本质不同的区间只有 O(n) 个，因此可以对这些区间做莫队，处理完一整个区间之后，遍历其对应的块中的所有询问并更新答案，因为一个询问最多拆到两个散块上，复杂度为 O(nB+m\sqrt n)。

• 还有一种做法是，把询问的 [l,r,k] 挂在 k 上，顺次做所有的 k，我们设 b_i=[a_i=k]，那询问就是区间和，使用 O(\sqrt n)-O(1) 再次分块平衡即可 O(1) 查询。

这两种做法总复杂度显然都可以做到 O(n\sqrt n)，现在考虑空间复杂度，我们不维护 f_{i,j}，而是离线逐块处理，这样整块空间复杂度线性。对于散块，做法一空间直接就是线性的；做法二注意到一次询问会被拆到散块中的两个连续区间，只记录端点即可做到空间线性。

这样总复杂度就是时间 O(n\sqrt n)，空间 O(n) 了。口胡没写。

写了，莫队最后遍历常数太大，用第二种方法过的，给一个卡常前的代码。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define B 600
#define BB 500
using namespace std;

int n,m,q,cnt;
int a[200005];
int p[200005];
int t[200005];
int h[200005];
int g[200005];
int bl[200005];
int lf[200005];
int rt[200005];
int ll[200005];
int rr[200005];
bool mp[200005];
int ans[200005];
vector <int> F[200005];
vector <int> G[200005];
struct node{int l,r,x;}qq[200005];

inline void in(int &n){
    n=0;
    char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
    return ;
}

int llf[200005];
int rrt[200005];
int bll[200005];

inline void add(int x,int y){
    for(int i=bll[x];i<=bll[n];i++) t[i]+=y;
    for(int i=x;i<=rrt[bll[x]];i++) h[i]+=y;
    return ;
}

inline int ask(int x){return t[bll[x]-1]+h[x];}

int main(){
    in(n),in(m),in(q);
    for(int i=1;i<=n;i++) in(a[i]),F[a[i]].emplace_back(i);

    for(int i=1;i<=m;i++) bl[i]=(i+B-1)/B;
    for(int i=1;i<=m;i++) rt[bl[i]]=i;
    for(int i=m;i>=1;i--) lf[bl[i]]=i;

    for(int i=1;i<=n;i++) bll[i]=(i+BB-1)/BB;
    for(int i=1;i<=n;i++) rrt[bll[i]]=i;
    for(int i=n;i>=1;i--) llf[bll[i]]=i;

    for(int i=1;i<=m;i++) in(ll[i]),in(rr[i]),p[i]=i;
    for(int i=1;i<=q;i++) in(qq[i].l),in(qq[i].r),in(qq[i].x);
    for(int i=1;i<=bl[m];i++){
        for(int j=lf[i];j<=rt[i];j++) h[j]=j;
        sort(h+lf[i],h+rt[i]+1,[](int x,int y){return ll[x]==ll[y]?rr[x]>rr[y]:ll[x]<ll[y];});
        int R=0,mm=0;
        for(int j=lf[i];j<=rt[i];j++){
            if(R>=rr[h[j]]) continue;
            g[++mm]=h[j];
            R=max(R,rr[h[j]]);
        }
        for(int j=1;j<=n;j++) t[j]=h[j]=0;
        int L=1;R=0;
        for(int j=1;j<=mm;j++){
            while(L<ll[g[j]]) t[a[L++]]--;
            while(R<rr[g[j]]) t[a[++R]]++,h[a[R]]=max(h[a[R]],t[a[R]]);
        }
        for(int j=1;j<=q;j++) if(qq[j].l<=lf[i]&&qq[j].r>=rt[i]) ans[j]=max(ans[j],h[qq[j].x]);
    }
    for(int i=1;i<=q;i++) G[qq[i].x].emplace_back(i);
    memset(t,0,sizeof(t));
    memset(h,0,sizeof(h));
    for(int i=1;i<=n;i++){
        for(int v:F[i]) add(v,1);
        for(int v:G[i]){
            int x=0,l,r;
            if(bl[qq[v].l]+1>=bl[qq[v].r]){
                l=qq[v].l,r=qq[v].r;
                for(int j=l;j<=r;j++) x=max(x,ask(rr[j])-ask(ll[j]-1));
                ans[v]=max(ans[v],x);
                continue;
            }
            l=qq[v].l,r=rt[bl[l]];
            for(int j=l;j<=r;j++) x=max(x,ask(rr[j])-ask(ll[j]-1));
            r=qq[v].r,l=lf[bl[r]];
            for(int j=l;j<=r;j++) x=max(x,ask(rr[j])-ask(ll[j]-1));
            ans[v]=max(ans[v],x);
        }
        for(int v:F[i]) add(v,-1);
    }
    for(int i=1;i<=q;i++) printf("%d\n",ans[i]);

    return 0;
}