4 条题解

  • 0
    @ 2026-8-12 8:49:18 
    #include<bits/stdc++.h>
using namespace std;

typedef long long LL;
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
#define MID ((L + R) >> 1)
const int N = 2e7 + 10;
const LL P = 998244353;

struct node {
	int ls, rs;
	LL a, b, sum;
	bool lazy;
} tr[N];
int trlen, rt;

LL a[N];

void modify(int x, LL ca, LL cb, LL L, LL R) {
	// sum = ca * sum + (r - l + 1) * cb 
	tr[x].sum = (ca * tr[x].sum % P + (R - L + 1) * cb % P ) % P;
	// ca * (a + b) + cb 
	tr[x].a = ca * tr[x].a % P;
	tr[x].b = (ca * tr[x].b % P + cb) % P; 
	tr[x].lazy = 1;
}

void pushup(int p) {
	tr[p].sum = (tr[lc(p)].sum + tr[rc(p)].sum) % P;
}

void newd(int &p) {
	trlen ++; p = trlen;
	tr[p] = {0, 0, 1, 0, 0, 0};
}

void pushdown(int p, LL L, LL R) {
	if (tr[p].lazy) {
		if (!lc(p)) {
			newd(lc(p));
		}
		if (!rc(p)) {
			newd(rc(p));
		}
		modify(lc(p), tr[p].a, tr[p].b, L, MID);
		modify(rc(p), tr[p].a, tr[p].b, MID + 1, R);
		tr[p].lazy = 0;
		tr[p].a = 1;
		tr[p].b = 0;
	}
}

void change(int &p, LL L, LL R, LL l, LL r, LL b, LL c) {
	if (!p) {
		newd(p);
	}
	if (r < L || R < l) {
		return ;
	}
	if (l <= L && R <= r) {
		modify(p, b, c, L, R);
		tr[p].lazy = 1;
		return ;
	}
	pushdown(p, L, R);
	change(lc(p), L, MID, l, r, b, c);
	change(rc(p), MID + 1, R, l, r, b, c);
	pushup(p);
}

LL query(int p, LL L, LL R, LL l, LL r) {
	if (!p || r < L || R < l) {
		return 0;
	}
	if (l <= L && R <= r) {
		return tr[p].sum;
	}
	pushdown(p, L, R);
	return (query(lc(p), L, MID, l, r) + query(rc(p), MID + 1, R, l, r)) % P;
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	LL n; int Q;
	cin >> n >> Q;
	
	trlen = 0; rt = 0;
	while (Q --) {
		int opt;
		cin >> opt;
		if (opt == 0) {
			LL l, r, b, c;
			cin >> l >> r >> b >> c;
			l ++;
			change(rt, 1ll, n, l, r, b, c);
		}
		else {
			LL l, r;
			cin >> l >> r;
			l ++;
			cout << query(rt, 1ll, n, l, r) << "\n";
		}
	}
	
	return 0;
}
    • 0
      @ 2026-8-9 9:31:35

      动态开点

      #include<bits/stdc++.h>
using namespace std;
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
#define mid ((tr[p].l+tr[p].r)>>1)
typedef long long LL;
const int N=2e7+10,mod=998244353;
struct node
{
	int ls,rs,l,r,tag;
	LL s,tag1,tag2;
}tr[N];
int tsp,rt;
int newd(int l,int r)
{
	tr[++tsp]={0,0,l,r,0,0,1,0};
	return tsp;
}
void pushup(int p)
{
    LL ls=lc(p)?tr[lc(p)].s:0;
   	LL rs=rc(p)?tr[rc(p)].s:0;
    tr[p].s=(ls+rs)%mod;
}
void pushdown(int p)
{
	if(!lc(p))
	{
		lc(p)=newd(tr[p].l,mid);
	}
	if(!rc(p))
	{
		rc(p)=newd(mid+1,tr[p].r);
	}
	LL &x=tr[p].tag1,&y=tr[p].tag2;
	if(tr[p].tag)
	{
		tr[lc(p)].s=(tr[lc(p)].s*x%mod+y*(tr[lc(p)].r-tr[lc(p)].l+1)%mod)%mod;
		tr[rc(p)].s=(tr[rc(p)].s*x%mod+y*(tr[rc(p)].r-tr[rc(p)].l+1)%mod)%mod;
		tr[lc(p)].tag1=tr[lc(p)].tag1*x%mod;
		tr[rc(p)].tag1=tr[rc(p)].tag1*x%mod;
		tr[lc(p)].tag2=(tr[lc(p)].tag2*x+y)%mod;
		tr[rc(p)].tag2=(tr[rc(p)].tag2*x+y)%mod;
		tr[lc(p)].tag=tr[rc(p)].tag=1;
		x=1;
		y=0;
		tr[p].tag=0;
	}
}
void change(int &p,int st,int ed,int l,int r,LL x,LL y)
{
	if(!p)
	{
		p=newd(st,ed);
	}
	if(l<=tr[p].l&&tr[p].r<=r)
	{
		tr[p].s=(tr[p].s*x%mod+y*(tr[p].r-tr[p].l+1)%mod)%mod; 
		tr[p].tag1=tr[p].tag1*x%mod;
		tr[p].tag2=(tr[p].tag2*x%mod+y)%mod;
		tr[p].tag=1;
		return ;
	}
	pushdown(p); 
	if(l<=mid)
	{
		change(lc(p),st,mid,l,r,x,y);
	}
	if(r>mid)
	{
		change(rc(p),mid+1,ed,l,r,x,y);
	}
	pushup(p);
}
int query(int p,int l,int r)
{	
	if(!p)
	{
		return 0;
	}
	if(tr[p].r<l|r<tr[p].l)
	{
		return 0;
	}
	if(l<=tr[p].l&&tr[p].r<=r)
	{
		return tr[p].s;
	}
	pushdown(p);
	if(r<=mid)
	{
		return query(lc(p),l,r);
	}
	if(l>mid)
	{
		return query(rc(p),l,r);
	}
	return (query(lc(p),l,r)+query(rc(p),l,r))%mod;
}
signed main()
{
	int n,Q;
	scanf("%d%d",&n,&Q);
	int rt=0;
	while(Q--)
	{
		int op;
		scanf("%d",&op);
		if(op==0)
		{
			int l,r,x,y;
			scanf("%d%d%d%d",&l,&r,&x,&y);
			l++;
			change(rt,1,n,l,r,x,y);
		}
		else
		{
			int l,r;
			scanf("%d%d",&l,&r);
			l++;
			printf("%d\n",query(1,l,r));
		}
	}
	return 0;
}
      • 0
        @ 2026-8-4 9:18:49

        请叫我重载运算符仙人

        #include<bits/stdc++.h>
#define ls(p) tr[p].son[0]
#define rs(p) tr[p].son[1]
using namespace std;
const int mod=998244353;
struct f{
	long long a,b;
	f operator *(const f &ano)const{
		return {a*ano.a%mod,(a*ano.b%mod+b)%mod};
	}
};
struct node{
	int l,r;
	int son[2];
	f tag;
	long long val;
	node operator *(const f &ano)const{
		node ans;
		ans.l=l;
		ans.r=r;
		ans.son[0]=son[0];
		ans.son[1]=son[1];
		ans.tag=ano*tag;
		ans.val=(val*ano.a%mod+ano.b*(r-l+1)%mod)%mod;
		return ans;
	}
};
node tr[7000005];
int rt,cnt;
int make(int l,int r){
	cnt++;
	tr[cnt].son[0]=tr[cnt].son[1]=tr[cnt].val=0;
	tr[cnt].tag={1,0};
	tr[cnt].l=l;
	tr[cnt].r=r;
	return cnt;
}
void up(int rot){
	tr[rot].val=(tr[ls(rot)].val+tr[rs(rot)].val)%mod;
}
void down(int rot){
	int l=tr[rot].l,r=tr[rot].r;
	int mid=(l+r)>>1;
	if(!ls(rot)){
		ls(rot)=make(l,mid);
	}
	if(!rs(rot)){
		rs(rot)=make(mid+1,r);
	}
	tr[ls(rot)]=tr[ls(rot)]*tr[rot].tag;
	tr[rs(rot)]=tr[rs(rot)]*tr[rot].tag;
	tr[rot].tag={1,0};
}
void change(int &rot,int l,int r,int x,int y,f val){
	if(!rot){
		rot=make(l,r);
	}
	if(x<=l && r<=y){
		tr[rot]=tr[rot]*val;
		return;
	}
	down(rot);
	int mid=(l+r)>>1;
	if(x<=mid){
		change(ls(rot),l,mid,x,y,val);
	}
	if(y>mid){
		change(rs(rot),mid+1,r,x,y,val);
	}
	up(rot);
}
long long query(int rot,int l,int r,int x,int y){
	if(!rot){
		return 0;
	}
	if(x<=l && r<=y){
		return tr[rot].val;
	}
	down(rot);
	int mid=(l+r)>>1;
	long long ans=0;
	if(x<=mid){
		ans=(ans+query(ls(rot),l,mid,x,y))%mod;
	}
	if(y>mid){
		ans=(ans+query(rs(rot),mid+1,r,x,y))%mod;
	}
	return ans;
}
int main(){
	int n,q;
	cin>>n>>q;
	while(q--){
		int op;
		cin>>op;
		if(op==0){
			int l,r;
			f cg;
			cin>>l>>r>>cg.a>>cg.b;
			l++;
			change(rt,1,n,l,r,cg);
		}
		if(op==1){
			int l,r;
			cin>>l>>r;
			l++;
			cout<<query(rt,1,n,l,r)<<"\n";
		}
	}
	return 0;
}
        • 0
          @ 2025-12-21 11:19:16 
          #include<bits/stdc++.h>
#define lc(p) tr[p].lc
#define rc(p) tr[p].rc 
#define int ll
using namespace std;
typedef long long ll;
const int mod=998244353;
int n,q,a[500010],id;
struct N{
	int lc,rc;
	ll c,k,b;
}tr[20000010];
void pushup(int p){
	if(!lc(p))tr[lc(p)=++id]={0,0,0,1,0};
	if(!rc(p))tr[rc(p)=++id]={0,0,0,1,0};
	tr[p].c=(tr[lc(p)].c+tr[rc(p)].c)%mod;
} 
void pushdown(int p,int l,int r){
	int mid=(l+r)>>1;
	if(!lc(p))tr[lc(p)=++id]={0,0,0,1,0};
	if(!rc(p))tr[rc(p)=++id]={0,0,0,1,0};
	tr[lc(p)].c=(tr[lc(p)].c*tr[p].k%mod+tr[p].b*(mid-l+1)%mod)%mod;
	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)].c=(tr[rc(p)].c*tr[p].k%mod+tr[p].b*(r-mid)%mod)%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;
	pushup(p);
}
void change(int &p,int l,int r,int x,int y,ll k,ll b){
	if(!p){
		tr[p=++id]={0,0,0,1,0};
	}
	if(l>=x&&r<=y){
		tr[p].c=(tr[p].c*k%mod+b*(r-l+1)%mod)%mod;
		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);
	pushup(p);
}
ll find(int p,int l,int r,int x,int y){
	if(!p)return 0;
	if(l>=x&&r<=y)return tr[p].c;
	pushdown(p,l,r);
	int mid=(l+r)>>1;
	if(y<=mid)return find(lc(p),l,mid,x,y);
	else if(x>mid) return find(rc(p),mid+1,r,x,y);
	return (find(lc(p),l,mid,x,y)+find(rc(p),mid+1,r,x,y))%mod;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	int rt=0;
	while(q--){
		int op;
		cin>>op;
		if(op==0){
			int l,r,k,b;
			cin>>l>>r>>k>>b;
			l++;
			change(rt,1,n,l,r,k,b);
		}
		else{
			int x,y;
			cin>>x>>y;
			x++;
			cout<<find(rt,1,n,x,y)<<'\n';
		}
	} 
	return 0;
}
          • 1

          区间仿射区间和（大数组）（Range Affine Range Sum (Large Array)）

          信息

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