放一篇点修区查的代码：

#include<bits/stdc++.h>
using namespace std;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
#define int long long
const int N=5e5+10,mod=998244353;
struct node
{
   int l,r,a,b;
}tr[N<<2];
void pushup(int p)
{
   tr[p].a=tr[rc(p)].a*tr[lc(p)].a%mod;
   tr[p].b=(tr[rc(p)].a*tr[lc(p)].b%mod+tr[rc(p)].b)%mod;
}
void build(int p,int l,int r)
{
   tr[p]={l,r,1,0};
   if(l==r)
   {
   	return ;
   }
   int mid=(l+r)>>1;
   build(lc(p),l,mid);
   build(rc(p),mid+1,r);
}
void change(int p,int x,int A,int B)
{
   if(tr[p].l==tr[p].r)
   {
   	tr[p].a=tr[p].a*A%mod;
   	tr[p].b=(tr[p].b*A%mod+B)%mod;
   	return ;
   }
   int mid=(tr[p].l+tr[p].r)>>1;
   if(x<=mid)
   {
   	change(lc(p),x,A,B);
   }
   else
   {
   	change(rc(p),x,A,B);
   }
   pushup(p);
}
void change1(int p,int x)
{
   if(tr[p].l==tr[p].r)
   {
   	tr[p].a=1;
   	tr[p].b=0;
   	return ;
   }
   int mid=(tr[p].l+tr[p].r)>>1;
   if(x<=mid)
   {
   	change1(lc(p),x);
   }
   else
   {
   	change1(rc(p),x);
   }
   pushup(p);
}
node query(int p,int l,int r)
{
   if(l<=tr[p].l&&tr[p].r<=r)
   {
   	return {0,0,tr[p].a,tr[p].b};
   }
   int mid=(tr[p].l+tr[p].r)>>1;
   node ans={0,0,1,0};
   if(l<=mid)
   {
   	node lc=query(lc(p),l,r);
   	ans.a=ans.a*lc.a%mod;
   	ans.b=(ans.b*lc.a%mod+lc.b)%mod;
   }
   if(r>mid)
   {
   	node rc=query(rc(p),l,r);
   	ans.a=ans.a*rc.a%mod;
   	ans.b=(ans.b*rc.a%mod+rc.b)%mod;
   }
   return ans;
}
signed main()
{
   int q;
   scanf("%lld",&q);
   build(1,1,q);
   int l=1,r=0;
   while(q--)
   {
   	int op;
   	scanf("%lld",&op);
   	if(op==0)
   	{
   		int A,B;
   		scanf("%lld%lld",&A,&B);
   		change(1,++r,A,B);
   	}
   	else if(op==1)
   	{
   		change1(1,l++);
   	}
   	else
   	{
   		int x;
   		scanf("%lld",&x);
   		if(l>r)
   		{
   			printf("%lld\n",x);
   			continue;
   		}
   		node ans=query(1,l,r);
   		printf("%lld\n",(ans.a*x%mod+ans.b)%mod);
   	}
   }
   return 0;
}

看了眼benny的代码，感觉太复杂了，这里将一个前缀和的方法。

思路

注意到操作三所求的式子即为所有加入过队列的函数再去除掉删除过的式子，这一过程可以用前缀和+双指针维护，具体式子见代码。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10,P=998244353;
int qpow(int a,int b)
{
	int res=1;
	for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;
	return res;
}
int a[N],b[N],l,r;
signed main()
{
	int q;scanf("%lld",&q);
	int nowa=1,nowb=0;
	a[0]=1;l=1,r=0;
	while(q--)
	{
		int op,x,y;scanf("%lld",&op);
		if(op==0)
		{
			scanf("%lld%lld",&x,&y);
			r++;
			a[r]=a[r-1]*x%P;b[r]=(b[r-1]*x%P+y)%P;
		}
		else if(op==1)l++;
		else
		{
			scanf("%lld",&x);
			int nowa=a[r]*qpow(a[l-1],P-2)%P,nowb=((b[r]-b[l-1]*nowa%P)%P+P)%P;
			printf("%lld\n",(nowa*x%P+nowb)%P);
		}
	}
	return 0;
}

本蒟蒻因模数打成了9982444353（多了个4）调了好久……

#include<bits/stdc++.h>
#define lc(p) ((p)<<1)
#define rc(p) ((p)<<1|1)
using namespace std;
typedef long long ll;
const int mod=998244353;
int q;
struct N{
	ll a,b,la1,la2;
}tr[2000010];
void merge(N &t,N l,N r){
	t.a=l.a*r.a%mod;
	t.b=(l.b*r.a%mod+r.b)%mod;
}
void pushdown(int p){
	if(tr[p].la1!=1){
		tr[lc(p)].a=tr[lc(p)].a*tr[p].la1%mod;
		tr[lc(p)].b=tr[lc(p)].b*tr[p].la1%mod;
		tr[lc(p)].la1=tr[lc(p)].la1*tr[p].la1%mod;
		tr[lc(p)].la2=tr[lc(p)].la2*tr[p].la1%mod;
		tr[rc(p)].a=tr[rc(p)].a*tr[p].la1%mod;
		tr[rc(p)].b=tr[rc(p)].b*tr[p].la1%mod;
		tr[rc(p)].la1=tr[rc(p)].la1*tr[p].la1%mod;
		tr[rc(p)].la2=tr[rc(p)].la2*tr[p].la1%mod;
		tr[p].la1=1;
	}
	if(tr[p].la2){
		tr[lc(p)].b=(tr[lc(p)].b+tr[p].la2)%mod;
		tr[lc(p)].la2=(tr[lc(p)].la2+tr[p].la2)%mod;
		tr[rc(p)].b=(tr[rc(p)].b+tr[p].la2)%mod;
		tr[rc(p)].la2=(tr[rc(p)].la2+tr[p].la2)%mod;
		tr[p].la2=0;
	}
}
void bt(int p,int l,int r){
	tr[p]={1,0,1,0};
	if(l==r)return ;
	int mid=(l+r)>>1;
	bt(lc(p),l,mid);
	bt(rc(p),mid+1,r);
}
void change(int p,int l,int r,int x,int y,ll a,ll b){
	if(l>=x&&r<=y){
		tr[p].a=tr[p].a*a%mod;
		tr[p].b=(tr[p].b*a%mod+b)%mod;
		tr[p].la1=tr[p].la1*a%mod;
		tr[p].la2=(tr[p].la2*a%mod+b)%mod;
		return ;
	}
	pushdown(p);
	int mid=(l+r)>>1;
	if(x<=mid)change(lc(p),l,mid,x,y,a,b);
	if(y>mid)change(rc(p),mid+1,r,x,y,a,b);
	merge(tr[p],tr[lc(p)],tr[rc(p)]);
}
N find(int p,int l,int r,int x){
	if(l==r)return tr[p];
	pushdown(p);
	int mid=(l+r)>>1;
	if(x<=mid)return find(lc(p),l,mid,x);
	else return find(rc(p),mid+1,r,x);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>q;
	bt(1,1,q);
	int l=1,r=0;
	for(int _=1;_<=q;_++){
		int op;
		cin>>op;
		if(op==0){
			ll a,b;
			cin>>a>>b;
			r++;
			change(1,1,q,l,r,a,b);
		}
		else if(op==1)l++;
		else{
			ll x;
			cin>>x;
			if(l>r){
				cout<<x<<'\n';
				continue;
			}
			N ans=find(1,1,q,l);
			cout<<(x*ans.a%mod+ans.b)%mod<<'\n';
		} 
	}
	return 0;
}