RT，我的想法是考虑到第二个操作询问的东西即为多项式在 $x=w_{4096}^k$ 时的取值，于是可以做 DFT 维护点值；同时又有单点修改，因此可以对暴力修改和暴力重构进行根号平衡，复杂度 $O(q\sqrt{n\log n})$，理论上需要较小的常数。

题目要求操作数不超过 $5\times2^{17}=655360$，但蒟蒻的写法的极限操作数达到了 $1086000$ 左右，离要求还差了好多。求问各位神仙有没有复杂度更优秀的做法？

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=998244353,w4096=63912897;
int n,q,L=0,type[4105],x[4105],c[4105],dp[4105][4105],ch[4105],id[4105],nwp[4105],pos[4105],pw[4105],pres[4105],tag[4105],r[4105],oper[2000005],o1[2000005],o2[2000005];
void ins(int tp,int x=0,int y=0){L++;oper[L]=tp;o1[L]=x;o2[L]=y;}
int ksm(int d,int cf)
{
	int ans=1;
	while(cf)
	{
		if(cf&1) ans=1ll*ans*d%mod;
		d=1ll*d*d%mod;cf>>=1;
	}
	return ans;
}
void doDFT()
{
	for(int i=0;i<4096;i++) pres[i]=pos[id[i]];
	for(int i=1;i<4096;i*=2)
		for(int j=0;j<4096;j+=i*2)
			for(int k=0,w=0,wn=2048/i;k<i;k++)
			{
				ins(6,pw[w],pres[j+k+i]);
				int pt1=pres[j+k],pt2=L-1;
				ins(4,pt1,pt2);pres[j+k]=L-1;
				ins(5,pt1,pt2);pres[j+k+i]=L-1;
				w+=wn;
			}
}
void init()
{
	for(int i=0;i<n;i++) ins(1),nwp[i]=pos[i]=L-1;
	for(int i=n;i<=4095;i++) ins(3,0),nwp[i]=pos[i]=L-1;
	for(int i=0;i<=4095;i++) ins(3,ksm(w4096,i)),pw[i]=L-1,tag[i]=1;
	for(int i=0;i<=4095;i++) id[i]=i,r[i]=(r[i>>1]>>1)|((i&1)<<11);
	for(int i=0;i<=4095;i++) if(i<r[i]) swap(id[i],id[r[i]]);
	doDFT();
}
void rebuild()
{
	for(int i=0;i<n;i++) if(tag[i]!=1) ins(4,pos[i],nwp[i]),pos[i]=L-1;
	for(int i=0;i<n;i++) tag[i]=1;doDFT();
}
void dfs(int x,int y)
{
	if(x==0) return;
	if(type[x]==1) dfs(x-1,y-1);
	if(type[x]==2)
	{
		if(y!=0){ch[x]=1;dfs(x-1,y);}
		else
		{
			if(dp[x-1][0]!=-1&&dp[x-1][0]+1==dp[x][0]){ch[x]=1;dfs(x-1,0);return;}
			int mn=1<<30,wz=0;
			for(int j=0;j<n;j++)
				if(dp[x-1][j]!=-1){if(dp[x-1][j]+j+73728<mn)mn=dp[x-1][j]+j+73728,wz=j;}
			ch[x]=2;dfs(x-1,wz);
		}
	}
}
int main()
{
	scanf("%d%d",&n,&q);
	init();
	for(int i=1;i<=q;i++)
	{
		scanf("%d",&type[i]);
		if(type[i]==1) scanf("%d%d",&x[i],&c[i]);
		if(type[i]==2) scanf("%d",&x[i]),x[i]%=4096;
	}
	memset(dp,-1,sizeof(dp));dp[0][0]=0;
	for(int i=1;i<=q;i++)
	{
		int bes=1<<30;
		for(int j=0;j<q;j++)
			if(dp[i-1][j]!=-1)
			{
				if(type[i]==1) dp[i][j+1]=dp[i-1][j]+2;
				if(type[i]==2)
				{
					bes=min(bes,dp[i-1][j]+j+73728);
					dp[i][j]=dp[i-1][j]+2*j+1;
				}
			}
		if(bes!=1<<30) dp[i][0]=dp[i][0]==-1?bes:min(bes,dp[i][0]);
	}
	int mn=1<<30,wz=0;
	for(int i=0;i<q;i++)
		if(dp[q][i]!=-1&&dp[q][i]<mn){mn=dp[q][i];wz=i;}
	dfs(q,wz);
	for(int i=1;i<=q;i++)
	{
		scanf("%d",&type);
		if(type[i]==1) tag[x[i]]=1ll*tag[x[i]]*c[i]%mod,ins(3,tag[x[i]]-1),ins(6,pos[x[i]],L-1),nwp[x[i]]=L-1;
		if(type[i]==2)
		{
			if(ch[i]==1)
			{
				int cur=pres[x[i]];
				for(int j=0;j<n;j++)
					if(tag[j]!=1) ins(6,nwp[j],pw[j*x[i]%4096]),ins(4,cur,L-1),cur=L-1;
				ins(2,cur);
			}
			if(ch[i]==2) rebuild(),ins(2,pres[x[i]]);
		}
	}
	printf("%d\n",L);
	for(int i=1;i<=L;i++)
	{
		if(oper[i]==1) printf(">\n");
		if(oper[i]==2) printf("< %d\n",o1[i]);
		if(oper[i]==3) printf("S %d\n",o1[i]);
		if(oper[i]==4) printf("+ %d %d\n",o1[i],o2[i]);
		if(oper[i]==5) printf("- %d %d\n",o1[i],o2[i]);
		if(oper[i]==6) printf("* %d %d\n",o1[i],o2[i]);
	}
	return 0;
}