Luogu4224 简单数据结构

题面

简化题意

给定一个双端队列，每次对双端队列操作（左右插入、删除）时，求出序列的最长上升倍数子序列长度，和以多少个位置为开头可以得到一个最长上升倍数子序列。

最长上升倍数子序列定义：序列的后一项是前一项的倍数。

$n,q\leq 10^5$。数据满足如下性质：

• 任意时刻双端队列内只有 $[1,m]$ 的数（$m\leq 10^6$）。
• 任意时刻队列内数字互不相同。
• 同一个数字最多只会被插入 $10$ 次。

题解

暴力

先从暴力开始，设 $f_i$ 表示从 $i$ 开头能得到的最长上升子序列长度，仿照 LIS，枚举倍数转移即可。枚举倍数时，考虑到队列内相同数字只有一个，开个 $pos$ 数组标记每个数位置快速定位。

inline void DP(){
    memset(pos,-1,sizeof(pos));
    int n=q.size(),mx=1,R=1,cnt=0;
    for(register int i=0;i<n;++i){
        R=max(R,q[i]);
        pos[q[i]]=i,f[i]=1;
    }
    for(register int i=n-2;i>=0;--i){
        for(register int j=q[i]*2;j<=R;j+=q[i])
            if(pos[j]>i)
                f[i]=max(f[i],f[pos[j]]+1);
        mx=max(mx,f[i]);
    }
    for(register int i=0;i<n;++i)
        cnt+=(f[i]==mx);
    write(mx),putchar(' '),write(cnt),putchar('\n');
}

$pos$ 可以在修改的时候动态维护，因此关键在 $f$。

正解

• 队列内数字互不相同，且任意时刻队列内只有 $[1,m]$ 的数。

  所以最长上升倍数子序列长度不超过 $\log m$，开数组 $g_i$ 表示 $f_j=i$ 的 $j$ 的个数，单次查询答案就找最大的 $i$ 使 $g_i\neq 0$，复杂度 $\log m$。

• 同一个数字只会被插入 $10$ 次，而队列内数字互不同，所以一个数最多只会被删除 $11$ 次。

  所以插入和删除的复杂度有些大，撑不起 $n$ 次插/删。假设已经求得一个最长上升倍数子序列，右侧插入一个数时，如果暴力枚举约数算影响，枚举约数复杂度是 $\sqrt{m}$ 的。如果影响计算能很快，单次操作就是 $\sqrt{m}$。

  这貌似与 $10$ 没什么关系，但是考虑如果从左侧插入，就要枚举这个数的倍数了，枚举一个数的倍数是 $\log m$，每个数最多出现 $10$ 次，单次操作就是 $10\log m$。

有了一个很模糊的认识，再看每个操作：

• 左侧插入：

  和 LIS 类似的转移，枚举这个数的倍数，如果在队列里，$f_i\leftarrow \max\{f_j+1\}$。

• 左侧删除：

  因为转移是倒序的，左边的点不对右边的点算贡献，直接删除即可。

• 右侧插入：

  枚举约数，并“尝试”对序列造成影响（让这个序列后面接在这个数上），最后比较影响前后 $f$ 变大还是变小，取新 $f_i$ 和旧 $f_i$ 较大的一个。

  具体而言，开辅助数组 $h_{i,j}$ 表示以 $i$ 开头，长度为 $j$ 的子序列有多少个，因为长度小于 $20$，所以也可以 $\log m$ 用 $h$ 数组推得新 $f$ 数组。

• 右侧删除：

  同理右侧插入。

左侧相关复杂度为 $\log m$（或 $\operatorname{O}(1)$）；右侧相关复杂度为插入的数的所有约数的约数个数和，这个复杂度不太好估，但打表可得是恰好能接受的；查询复杂度为 $\log m$，可以通过。

代码

#include<bits/stdc++.h>
using namespace std;
const int max_n=1000006;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int n,m,Q;

struct Deque{
    int l,r,q[max_n*3];
    int f[max_n*3],g[22],h[max_n*3][22],pos[max_n];
    Deque(){l=1000006,r=1000005;}
    inline void ask(){
        for(register int i=21;i>=0;--i)
            if(g[i]){
                write(i),putchar(' '),write(g[i]),putchar('\n');
                break;
            }
    }
    inline void push_front(int x){
        q[--l]=x,pos[x]=l;
        memset(h[l],0,sizeof(h[l])),f[l]=h[l][1]=1;
        for(register int i=x*2;i<=m;i+=x)
            if(pos[i]>l){
                ++h[l][f[pos[i]]+1],
                f[l]=max(f[l],f[pos[i]]+1);
            }
        ++g[f[l]];
    }
    inline void pop_front(){
        --g[f[l]],pos[q[l++]]=0;
    }
    inline void upd(int x,int val,int dat){
        g[val]+=dat;
        for(register int i=1;i*i<=x;++i){
            if(x%i!=0) continue;
            if(pos[i]<pos[x])
                h[pos[i]][val+1]+=dat;
            if(i*i<x && pos[x/i] && pos[x/i]<pos[x])
                h[pos[x/i]][val+1]+=dat;
        }
    }
    int tmp[max_n*3],a[max_n*3],tot;
    inline void push(int x){
        tot=0;
        for(register int i=1;i*i<=x;++i){
            if(x%i!=0 || !pos[i]) continue;
            tmp[pos[i]]=f[pos[i]],
            a[++tot]=i;
        }
        for(register int i=sqrt(x);i>=1;--i){
            if(x%i!=0 || !pos[x/i]) continue;
            if(i*i<x && pos[x/i]){
                tmp[pos[x/i]]=f[pos[x/i]];
                a[++tot]=x/i;
            }
        }
    }
    inline void push_back(int x){
        q[++r]=x,pos[x]=r;
        memset(h[r],0,sizeof(h[r])),f[r]=h[r][1]=1;
        upd(x,f[r],1),push(x);
        for(register int i=tot;i>=1;--i) if(pos[a[i]]){
            for(register int j=21;j>=0;--j)
                if(h[pos[a[i]]][j]){
                    f[pos[a[i]]]=j;
                    break;
                }
            if(f[pos[a[i]]]!=tmp[pos[a[i]]])
                upd(a[i],tmp[pos[a[i]]],-1),
                upd(a[i],f[pos[a[i]]],1);
        }
    }
    inline void pop_back(){
        upd(q[r],f[r],-1),push(q[r]);
        for(register int i=tot;i>=1;--i) if(pos[a[i]]){
            for(register int j=21;j>=0;--j)
                if(h[pos[a[i]]][j]){
                    f[pos[a[i]]]=j;
                    break;
                }
            if(f[pos[a[i]]]!=tmp[pos[a[i]]])
                upd(a[i],tmp[pos[a[i]]],-1),
                upd(a[i],f[pos[a[i]]],1);
        }
        pos[q[r]]=0,f[r--]=0;
    }
    inline void init(){
        for(register int i=1;i<=n;++i)
            push_back(read());
        ask();
    }
}q;

signed main(){
    n=read(),m=read(),Q=read(),q.init();
    while(Q--){
        int op=read();
        if(op==0)
            q.push_front(read());
        if(op==1)
            q.push_back(read());
        if(op==2)
            q.pop_front();
        if(op==3)
            q.pop_back();
        q.ask();
    }
    return 0;
}