发一篇阎帝的猎奇题解

题目是要求点修区间查询，一眼线段树，再手搓一遍pushup的式子即可(本蒟蒻太久没做线段树，调了一个多小时T_T)

代码

#include<bits/stdc++.h>
#define int long long
#define lc(x) x<<1
#define rc(x) x<<1|1//线段树访问左右子树 
using namespace std;
const int N=5e5+10,P=998244353;
struct node{int l,r,a,b;}a[N<<2];//管辖范围l~r，表达式为ax+y 
void pu(int p)
{
	a[p].a=a[lc(p)].a*a[rc(p)].a%P;//左子树在里 
	a[p].b=(a[lc(p)].b*a[rc(p)].a%P+a[rc(p)].b)%P;//a1(a2x+b2)+b2=a1*a2*x+a1*b2+b1
}//子树有修改，改变自己的参数 
int A[N],B[N],cnt;
void build(int id,int l,int r)//建树 
{
	a[id]={l,r,0,0};
	if(l==r){a[id]={l,r,A[l],B[l]};return ;};
	int mid=l+r>>1;
	build(lc(id),l,mid);build(rc(id),mid+1,r);
	pu(id);//改变自己的参数 
}
void change(int p,int x,int c,int d)
{
	if(a[p].r<x||x<a[p].l)return ;//管辖范围与修改点八竿子打不着 
	if(a[p].l==x&&a[p].r==x){a[p].a=c;a[p].b=d;return ;}//找到了 
	change(lc(p),x,c,d);change(rc(p),x,c,d);//放给子树找 
	pu(p);//不能忘 
}
pair<int,int> query(int p,int l,int r)//pair存储往下访问到的a和b 
{
	if(a[p].r<l||r<a[p].l)return {1,0};//(1,0)可以让上一级无视它的贡献 
	if(l<=a[p].l&&a[p].r<=r)return {a[p].a,a[p].b};//目标完全覆盖管辖范围，直接返回 
	pair<int,int> n1=query(lc(p),l,r),n2=query(rc(p),l,r);//为了省事 
	return {n1.first*n2.first%P,n1.second*n2.first%P+n2.second};
}
signed main()
{
	int n,q;scanf("%lld%lld",&n,&q);
	for(int i=0;i<n;i++)scanf("%lld%lld",&A[i],&B[i]);
	build(1,0,n-1);//建树 
	while(q--)
	{
		int op,x,y,z;scanf("%lld%lld%lld%lld",&op,&x,&y,&z);
		if(op==0)
		{
			change(1,x,y,z);
		}
		else
		{
			pair<int,int>n1=query(1,x,y-1);
			printf("%lld\n",(z*n1.first%P+n1.second)%P);//把z代入表达式 
		}
	}
	return 0;//完结撒花 
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc(p) (p<<1)
#define rc(p) ((p<<1)|1)
#define MID ((l+r)>>1)
#define N 500010
#define mod 998244353
struct node{
	int l,r,a,b;
}tr[N<<2];
int n,q;
int a[N],b[N];
//c(ax+b)+d=ac*x+(bc+d)
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){
	if(l==r){
		tr[p]={l,r,a[l],b[l]};
		return;
	}
	tr[p]={l,r,0,0};
	build(lc(p),l,MID);build(rc(p),MID+1,r);
	pushup(p);
}
void change(int p,int id,int a,int b){
	if(tr[p].r<id||tr[p].l>id)return;
	if(tr[p].l==tr[p].r){
		tr[p].a=a,tr[p].b=b;
		return;
	}
	change(lc(p),id,a,b);change(rc(p),id,a,b);
	pushup(p);
}
int query(int p,int l,int r,int x){
	if(tr[p].r<l||tr[p].l>r)return x;
	if(l<=tr[p].l&&tr[p].r<=r)return (tr[p].a*x%mod+tr[p].b)%mod;
	return query(rc(p),l,r,query(lc(p),l,r,x));
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
	build(1,1,n);
	while(q--){
		int op;cin>>op;
		if(op==0){
			int p,x,y;cin>>p>>x>>y;p++;
			change(1,p,x,y);
		}
		else{
			int l,r,x;cin>>l>>r>>x;l++;
			cout<<query(1,l,r,x)<<'\n';
		}
	}
	
	return 0;
}