- 给定一个长度为(n)的序列，要求支持在序列前后加入或删除一个数。
- 对于该序列的一个子序列，如果满足其中每一个数都是前一个数的倍数，就称之为上升倍数子序列。
- 在所有操作之前及每次操作之后，求出最长上升倍数子序列长度及可能的开头个数。
- (n,qle10^5,Vle10^6)，保证每种数字最多被插入序列(10)次，且任意时刻序列中不存在相同的数
开桶维护答案+暴力
其实这题的想法非常暴力。。。
由于一个数的倍数至少是它的两倍，所以答案上界不可能超过(logV)。
所以我们直接对于每个位置，开一个大小为(logV)的桶，维护之后它的所有倍数转移到它的贡献。对于总答案也类似地开上一个桶来维护（而且发现这样有一个好处，本来题目就要我们求可能的开头个数，这样就顺带维护出来了）。
在前面插入一个数，只要枚举它的所有倍数向它转移即可，由于题目保证每种数字最多被插入(10)次，因此单次的平均复杂度可以看作(O(ln V))。
在前面删除一个数，显然不会对任何数产生影响，直接删除即可。
在后面插入一个数，首先(O(sqrt V))求出它的所有约数，显然只有这些数可能被更新到。
然后，我们先把它们的贡献从总答案中删去，再从小往大枚举每一个数把它们的贡献从它们的约数中删去。
接着从当前插入的数向所有约数转移，再从大往小枚举每一个数把它们的贡献加到它们的约数中，最后把所有数的贡献重新加回总答案里。
这个过程看起来暴力，复杂度是(O(d(V)^2))的。但同样由于每种数字最多被插入(10)次，实际运行效率还是挺高的。
在后面删除一个数应该是一个完全一样的过程，只要把“从当前插入的数向所有约数转移”这一步改成消除当前删除的数对所有约数的贡献即可。
具体实现可能要注意一些细节，但总体代码难度应该不高。
代码：(O(nd(V)^2))
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define V 1000000
#define L 20
using namespace std;
int n,m,p[V+5],H=N+1,T=N,s[3*N+5],f[3*N+5],g[3*N+5][L+5],ans,c[L+5];
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void write(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc(' ');}
Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('
');}
}using namespace FastIO;
I void A(int& f,int* g,CI x) {++g[x],x>f&&(f=x);}
I void D(int& f,int* g,CI x) {--g[x];W(!g[f]) --f;}
int d[V+5];I void F5(CI x,CI op)//在末尾加入/删除了x
{
RI i,j,F,t=0;for(i=1;i*i<=x;++i) !(x%i)&&(p[i]&&(d[++t]=i),p[x/i]&&i^(x/i)&&(d[++t]=x/i));sort(d+1,d+t+1);//找出所有约数排个序
for(i=1;i^t;++i) D(ans,c,f[p[d[i]]]);//消去在总答案中的贡献
for(i=1;i^t;++i) for(F=f[p[d[i]]]+1,j=1;j^i;++j) !(d[i]%d[j])&&p[d[j]]<p[d[i]]&&(D(f[p[d[j]]],g[p[d[j]]],F),0);//消去大数对小数的转移
for(i=1;i^t;++i) ~op?A(f[p[d[i]]],g[p[d[i]]],2):D(f[p[d[i]]],g[p[d[i]]],2);//更新末尾对前面的转移
for(i=t-1;i;--i) for(F=f[p[d[i]]]+1,j=1;j^i;++j) !(d[i]%d[j])&&p[d[j]]<p[d[i]]&&(A(f[p[d[j]]],g[p[d[j]]],F),0);//加回大数对小数的转移
for(i=1;i^t;++i) A(ans,c,f[p[d[i]]]);//加回总答案的贡献
}
I void AL(CI x)//在前面加入一个数
{
RI i,j;for(s[p[x]=--H]=x,g[H][f[H]=1]=1,i=2;i<=L;++i) g[H][i]=0;//清空桶
for(i=2*x;i<=m;i+=x) p[i]&&(A(f[H],g[H],f[p[i]]+1),0);A(ans,c,f[H]);//枚举所有倍数向它转移
}
I void AR(CI x) {s[p[x]=++T]=x,g[T][f[T]=1]=1,A(ans,c,1);for(RI i=2;i<=L;++i) g[T][i]=0;F5(x,1);}//在后面加入一个数
I void DL() {D(ans,c,f[H]),p[s[H++]]=0;}//在前面删除一个数
I void DR() {F5(s[T],-1),D(ans,c,1),p[s[T--]]=0;}//在后面删除一个数
int main()
{
RI Qt,i,x;for(read(n,m,Qt),i=1;i<=n;++i) read(x),AR(x);write(ans),writeln(c[ans]);//初始局面答案
for(RI op;Qt;write(ans),writeln(c[ans]),--Qt) switch(read(op),op)//每次操作后的答案
{case 0:read(x),AL(x);break;case 1:read(x),AR(x);break;case 2:DL();break;case 3:DR();break;}
return clear(),0;
}