4 条题解

  • 2
    @ 2026-8-3 15:20:53

    又是一道没有一篇带解释的题解的题

    前置知识：线段树

    思路

    区间修改，单点查询，很明显用线段树做很合适，我们考虑用结构体定义一个节点，包含其覆盖范围，两个懒标记（方便快速计算）。

    对于同一个点的先后两次变化ai=b1×ai+c1a_i=b_1\times a_i+c_1和ai=b2×ai+c2a_i=b_2\times a_i+c_2，合并后有ai=b2×(b1×ai+c1)+c2a_i=b_2\times(b_1\times a_i+c_1)+c_2，展开得ai=b1b2ai+b2c1+c2a_i=b_1b_2a_i+b_2c_1+c_2，就得到了新的两个系数。

    剩下的就是线段树的事了

    AC代码

    #include<bits/stdc++.h>
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
#define int long long
using namespace std;
const int N=5e5+10,P=998244353;
struct node{int l,r,tag,a,b;}tr[N<<2];
int a[N];
void pd(int p)
{
	if(tr[p].tag)//如果带有懒标记 
	{
		tr[lc(p)].a=tr[lc(p)].a*tr[p].a%P;tr[rc(p)].a=tr[rc(p)].a*tr[p].a%P;//对新的a的赋值 
		tr[lc(p)].b=(tr[p].a*tr[lc(p)].b%P+tr[p].b)%P;//对新的b的赋值 
		tr[rc(p)].b=(tr[p].a*tr[rc(p)].b%P+tr[p].b)%P;
		tr[lc(p)].tag=tr[rc(p)].tag=1;//子节点也带有标记 
		tr[p].a=1;tr[p].b=0;tr[p].tag=0;//清空本节点
		//a赋值为1是因为a*1+0=a（废话）（很重要！） 
	}
}
void build(int p,int l,int r)//建线段树 
{
	tr[p]={l,r,0,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 l,int r,int a,int b)
{
	if(tr[p].r<l||r<tr[p].l)return ;//不在目标区域内 
	if(l<=tr[p].l&&tr[p].r<=r)//被完全覆盖 
	{
		tr[p].a=tr[p].a*a%P;tr[p].b=(tr[p].b*a%P+b)%P;
		tr[p].tag=1;
		return ;
	}
	pd(p);//千万别漏！如果不加会导致两次计算顺序颠倒！ 
	change(lc(p),l,r,a,b);change(rc(p),l,r,a,b);//交给儿子去干 
}
int query(int p,int x)
{
	if(tr[p].r<x||x<tr[p].l)return 0;
	if(tr[p].l==tr[p].r)
	{
		a[x]=(a[x]*tr[p].a%P+tr[p].b)%P;//更新 
		tr[p].a=1;tr[p].b=0;//清空 
		return a[x];
	}
	pd(p);
	return query(lc(p),x)+query(rc(p),x);//统计 
}
signed main()
{
	int n,q;scanf("%lld%lld",&n,&q);
	for(int i=0;i<n;i++)scanf("%lld",&a[i]);
	build(1,0,n-1);//别忘建线段树（别问我怎么知道的） 
	while(q--)
	{
		int op,x,y,l,r;scanf("%lld",&op);
		if(op==0)
		{
			scanf("%lld%lld%lld%lld",&l,&r,&x,&y);
			r--;//根据题意（细节） 
			change(1,l,r,x,y);
		}
		else
		{
			scanf("%lld",&x);
			printf("%lld\n",query(1,x));
		}
	}
	return 0;//完结撒花 
}

    依旧线段树神力

    • 0
      @ 2026-8-5 14:47:02

      线段树的一个我认为比较新奇的trick。

      记录每个节点的乘数a与加数b，然后一通暴力推导可知若先后对节点进行两次更改(b1,c1)(b1,c1)与(b2,c2)(b2,c2)，最终会变成(b1b2,b2c1+c2)(b1b2,b2c1+c2)。 然后就跑线段树就可以了。

      tips1:节点编号从0到n-1

      tips2:lazy更新完要变成(1,0)（x*1+0=x）

      带马：

      #include<bits/stdc++.h>
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
#define int long long
using namespace std;
const int N=5e5+10,mod=998244353;
struct node{
	int l,r,lazy;
	int b,c;
}tr[N<<2];
int a[N];
void pushdown(int p){
	if(tr[p].lazy){
		tr[lc(p)].lazy=tr[rc(p)].lazy=1; 
		tr[lc(p)].b=tr[lc(p)].b*tr[p].b%mod;
		tr[lc(p)].c=(tr[p].b*tr[lc(p)].c%mod+tr[p].c)%mod;
		tr[rc(p)].b=tr[rc(p)].b*tr[p].b%mod;
		tr[rc(p)].c=(tr[p].b*tr[rc(p)].c%mod+tr[p].c)%mod;
		tr[p].b=1;tr[p].c=0;tr[p].lazy=0;
	}
}
void build(int p,int l,int r){
	tr[p]={l,r,0,1,0};
	if(l==r)return;
	int mid=(l+r)/2;
	build(lc(p),l,mid);build(rc(p),mid+1,r);
}
void change(int p,int l,int r,int b,int c){
	if(tr[p].r<l||r<tr[p].l)return; 
	if(l<=tr[p].l&&tr[p].r<=r){
		tr[p].b=tr[p].b*b%mod;tr[p].c=(tr[p].c*b%mod+c)%mod;
		tr[p].lazy=1;
		return;
	}
	pushdown(p);
	change(lc(p),l,r,b,c);change(rc(p),l,r,b,c);
}
int query(int p,int x){
	if(tr[p].r<x||x<tr[p].l)return 0;
	if(tr[p].l==tr[p].r){	
		a[x]=(a[x]*tr[p].b%mod+tr[p].c)%mod;
		tr[p].b=1;tr[p].c=0;
		return a[x];
	}
	pushdown(p);
	return query(lc(p),x)+query(rc(p),x);
}
signed main(){
	int n,q;scanf("%lld%lld",&n,&q);
	for(int i=0;i<n;i++)scanf("%lld",&a[i]);
	build(1,0,n-1);
	while(q--){
		int op,x,y,l,r;scanf("%lld",&op);
		if(op==0){
			scanf("%lld%lld%lld%lld",&l,&r,&x,&y);r--;
			change(1,l,r,x,y);
		}
		else{
			scanf("%lld",&x);
			printf("%lld\n",query(1,x));
		}
	}
	return 0;
}
      • 0
        @ 2025-12-21 10:52:47 
        #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 n,q,a[500010];
struct N{
	ll c,k,b;
}tr[2000010];
void pushdown(int p,int l,int r){
	tr[lc(p)].b=(tr[p].k*tr[lc(p)].b%mod+tr[p].b)%mod;
	tr[lc(p)].k=tr[lc(p)].k*tr[p].k%mod;
	tr[rc(p)].b=(tr[p].k*tr[rc(p)].b%mod+tr[p].b)%mod;
	tr[rc(p)].k=tr[rc(p)].k*tr[p].k%mod;
	tr[p].k=1;
	tr[p].b=0;
}
void bt(int p,int l,int r){
	tr[p]={0,1,0};
	if(l==r){
		tr[p]={a[l],1,0};
		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 k,ll b){
	if(l>=x&&r<=y){
		tr[p].b=(tr[p].b*k%mod+b)%mod;
		tr[p].k=tr[p].k*k%mod;
		return ;
	}
	pushdown(p,l,r);
	int mid=(l+r)>>1;
	if(x<=mid)change(lc(p),l,mid,x,y,k,b);
	if(y>mid)change(rc(p),mid+1,r,x,y,k,b);
}
ll find(int p,int l,int r,int x){
	if(l==r)return (tr[p].c*tr[p].k%mod+tr[p].b)%mod;
	pushdown(p,l,r);
	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>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	bt(1,1,n);
	while(q--){
		int op;
		cin>>op;
		if(op==0){
			int l,r,k,b;
			cin>>l>>r>>k>>b;
			l++;
			change(1,1,n,l,r,k,b);
		}
		else{
			int x;
			cin>>x;
			x++;
			cout<<find(1,1,n,x)<<'\n';
		}
	} 
	return 0;
}
        • 0
          @ 2025-12-18 18:28:32 
          #include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10,P=998244353;
void mod(int &x){x=((x%P)+P)%P;}
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
struct node{int l,r,s,tag,lazy;}tr[N<<2];int a[N];
void pushup(int p){tr[p].s=tr[lc(p)].s+tr[rc(p)].s;}
void pushdown(int p)
{
	if(tr[p].tag!=1)
	{
		tr[lc(p)].s*=tr[p].tag;tr[rc(p)].s*=tr[p].tag;
		mod(tr[lc(p)].s);mod(tr[rc(p)].s);
		tr[lc(p)].lazy*=tr[p].tag;tr[rc(p)].lazy*=tr[p].tag;
		mod(tr[lc(p)].lazy);mod(tr[rc(p)].lazy);
		tr[lc(p)].tag*=tr[p].tag;tr[rc(p)].tag*=tr[p].tag;
		mod(tr[lc(p)].tag);mod(tr[rc(p)].tag);
		tr[p].tag=1;
	}
	if(tr[p].lazy)
	{
		tr[lc(p)].s+=tr[p].lazy*(tr[lc(p)].r-tr[lc(p)].l+1);
		tr[rc(p)].s+=tr[p].lazy*(tr[rc(p)].r-tr[rc(p)].l+1);
		mod(tr[lc(p)].s);mod(tr[rc(p)].s);
		tr[lc(p)].lazy+=tr[p].lazy;tr[rc(p)].lazy+=tr[p].lazy;
		mod(tr[lc(p)].lazy);mod(tr[rc(p)].lazy);
		tr[p].lazy=0;
	}
}
void bt(int p,int l,int r)
{
	tr[p]={l,r,0,1,0};
	if(l==r){tr[p].s=a[l];return;}
	int mid=(l+r)>>1;
	bt(lc(p),l,mid);bt(rc(p),mid+1,r);
	pushup(p);
}
void change1(int p,int l,int r,int k)
{
	if(tr[p].l>r||tr[p].r<l)return;
	if(l<=tr[p].l&&tr[p].r<=r)
	{
		tr[p].s*=k;tr[p].tag*=k,tr[p].lazy*=k;
		mod(tr[p].s);mod(tr[p].tag);mod(tr[p].lazy);
		return ;
	}
	pushdown(p);
	change1(lc(p),l,r,k);change1(rc(p),l,r,k);
	pushup(p);
}
void change2(int p,int l,int r,int k)
{
	if(tr[p].l>r||tr[p].r<l)return;
	if(l<=tr[p].l&&tr[p].r<=r)
	{
		tr[p].s+=k*(tr[p].r-tr[p].l+1);tr[p].lazy+=k;
		mod(tr[p].s);mod(tr[p].lazy);
		return ;
	}
	pushdown(p);
	change2(lc(p),l,r,k);change2(rc(p),l,r,k);
	pushup(p);
}
int query(int p,int x)
{
	if(tr[p].l>x||tr[p].r<x)return 0;
	if(tr[p].l==tr[p].r)return tr[p].s;
	pushdown(p);
	return query(lc(p),x)+query(rc(p),x);
} 
signed main()
{
	int n,q;cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	bt(1,1,n);
	while(q--)
	{
		int op,l,r,b,c;cin>>op;
		if(op==0)
		{
			cin>>l>>r>>b>>c;l++;
			change1(1,l,r,b);change2(1,l,r,c);
		}
		else
		{
			cin>>l;l++;
			cout<<query(1,l)<<'\n';
		}
	}
	return 0;
}
          • 1

          区间仿射点查（Range Affine Point Get）

          信息

          ID
          8124
          时间
          1000ms
          内存
          1024MiB
          难度
          7
          标签
          递交数
          58
          已通过
          13
          上传者
          1. Language
          2. 兼容模式
          3. 主题
          3. Worker 0, 10ms
          4. Powered by Hydro v5.0.1 Community