CCPC 2023 北京市赛 G.【模板】线段树（线段树区间合并20次多项式）

题目

思路来源

lyw

题解

洛谷高仿题目P4247

(ai+x)(ai+x)(ai+x)注意到当x有超过20项时，20个2相乘，对2的20次方取模就为0

所以，维护0次项到19次项乘积的和，向上合并时，是两个多项式卷积，这里暴力相乘即可

下推标记，当下放一个区间加x的标记时，，其中，i<j<20

复杂度O(nlogn*20*20)，比较卡常

经典卡常技巧：将取模改成unsigned int自然溢出即可

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef unsigned int ui;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10,M=25,mod=(1<<20)-1;
int n,q;
ui b[N],C[M][M];
void add(ui &x,ui y){
	x+=y;
}
struct node{
	int l,r;
	ui c,p,a[21];
	node(){
		memset(a,0,sizeof a);
		c=0;
	}
}e[N*4];
struct segment{
	int n;
	#define l(x) e[x].l
	#define r(x) e[x].r
	#define c(x) e[x].c
	node mer2(node &x,node &y){
		int ls=x.r-x.l+1,rs=y.r-y.l+1;
		node z;
		int w=min(ls+rs,20);
		z.a[w]=1;
		z.l=x.l,z.r=y.r;
		rep(i,0,ls){
			rep(j,0,rs){
				if(i+j>=w)break;
				ui v=x.a[i]*y.a[j];
				add(z.a[i+j],v);
			}
		}
		return z;
	}
	void up(int p){
		e[p]=mer2(e[p<<1],e[p<<1|1]);
	}
	void psd2(node &x,ui v){
		int len=x.r-x.l+1,sz=min(20,len);
		vector<ui>pw(sz+1,1);
		rep(i,1,sz)pw[i]=pw[i-1]*v;
		rep(i,0,sz-1){
			rep(j,i+1,sz){
				ui v=x.a[j]*pw[j-i]*C[j][j-i];
				add(x.a[i],v);
			}
		}
	}
	void psd(int p){
		if(c(p)){
			psd2(e[p<<1],c(p));
			add(c(p<<1),c(p));
			psd2(e[p<<1|1],c(p));
			add(c(p<<1|1),c(p));
			c(p)=0;
		}
	}
	void bld(int p,int l,int r){
		l(p)=l,r(p)=r,c(p)=0;
		if(l==r){
			e[p].a[0]=b[l];
			e[p].a[1]=1;
			return;
		}
		int mid=(l+r)/2;
		bld(p<<1,l,mid);
		bld(p<<1|1,mid+1,r);
		up(p);
	}
	void init(int _n){
		n=_n;
		bld(1,1,n);
	}
	void upd(int p,int ql,int qr,ui x){
		if(ql<=l(p) && r(p)<=qr){
			psd2(e[p],x);
			add(c(p),x);
			return;
		}
		psd(p);
		int mid=(l(p)+r(p))/2;
		if(ql<=mid)upd(p<<1,ql,qr,x);
		if(qr>mid)upd(p<<1|1,ql,qr,x);
		up(p);
	}
	node ask(int p,int ql,int qr){
		if(ql<=l(p) && r(p)<=qr){
			return e[p];
		}
		psd(p);
		int mid=(l(p)+r(p))/2;
		if(ql<=mid && qr>mid){
			node L=ask(p<<1,ql,qr);
			node R=ask(p<<1|1,ql,qr);
			node res=mer2(L,R);
			return res;	
		}
		else if(ql<=mid){
			node L=ask(p<<1,ql,qr);
			return L;
		}
		else{
			node R=ask(p<<1|1,ql,qr);
			return R;
		}
	}
}seg;
void init(){
	C[0][0]=1;
	int up=21;
	rep(i,1,up){
		C[i][0]=C[i][i]=1;
		rep(j,1,i-1){
			C[i][j]=(C[i-1][j]+C[i-1][j-1]);
		}
	}
}
int op,l,r;
ui x;
int main(){
	init();
	sci(n),sci(q);
	rep(i,1,n)scanf("%u",&b[i]);
	seg.init(n);
	rep(i,1,q){
		scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			scanf("%u",&x);
			seg.upd(1,l,r,x);
		}
		else{
			printf("%u\n",seg.ask(1,l,r).a[0]&mod);
		}
	}
	return 0;
}