萌新求助卡常
查看原帖
萌新求助卡常
55707
gxy001楼主2021/5/11 08:02

有人帮忙看看是哪里常数大吗k

#include<cstdio>
#include<list>
#include<algorithm>
namespace IO{
	#define BUFSIZE 30000000
	struct read{
		char buf[BUFSIZE],*p1,*p2,c;
		read():p1(buf),p2(buf){}
		inline char gc(void){
			return p1==p2?(p2=buf+fread(p1=buf,1,BUFSIZE,stdin),p1==p2?EOF:*p1++):*p1++;
		}
		inline read& operator >>(int& x){
			c=gc(),x=0;
			for(;c<'0'||c>'9';c=gc());
			for(;c>='0'&&c<='9';c=gc())x=x*10+c-'0';
			return *this;
		}
		inline read& operator >>(long long& x){
			c=gc(),x=0;
			for(;c<'0'||c>'9';c=gc());
			for(;c>='0'&&c<='9';c=gc())x=x*10+c-'0';
			return *this;
		}
	};
	struct write{
		char buf[2000000],*p1;
		write& operator <<(int x){
			static char b[15];
			static int len(0);
			do b[len++]=x%10+'0',x/=10; while(x);
			while(len){len--,*p1++=b[len];}
			*p1++='\n';
			return *this;
		}
		~write(){fwrite(buf,1,p1-buf,stdout),p1=buf;}
		write():p1(buf){}
	};
	read in;
	write out;
}
using IO::in;
using IO::out;
int const mod=1000000007;
int n,m,a[100010],p[100010];
std::list<std::pair<int,int>> lst[400010];
int lpos[400010],rpos[400010],rcs[400010],sum[400010],prod[400010],lv[400010],rv[400010];
struct node{
	int lpro,rpro,ans,h;
	inline node():lpro(),rpro(),ans(),h(){}
	inline node(int l,int r,int res,int hc):lpro(l),rpro(r),ans(res),h(hc){}
	inline friend node operator +(node const &l,node const &r){
		return node(l.lpro,r.rpro,(l.ans+r.ans)%mod,0);
	}
	inline friend node operator *(node const &l,node const &r){
		if(l.h&&r.h) return node(1ll*l.ans*r.ans%mod,1ll*l.ans*r.ans%mod,1ll*l.ans*r.ans%mod,1);
		if(l.h) return node(1ll*l.ans*r.lpro%mod,r.rpro,(r.ans+1ll*l.ans*r.lpro-r.lpro+mod)%mod,0);
		if(r.h) return node(l.lpro,1ll*r.ans*l.rpro%mod,(l.ans+1ll*r.ans*l.rpro-l.rpro+mod)%mod,0);
		return node(l.lpro,r.rpro,(l.ans+r.ans+1ll*r.lpro*l.rpro-r.lpro-l.rpro+mod*2)%mod,0);
	}
}tr[400010];
inline void pushup(int x,int ls,int rs,int l,int mid,int r){
	rcs[x]=rcs[rs];
	sum[x]=(sum[ls]+sum[rs])%mod;
	prod[x]=1ll*prod[ls]*prod[rs]%mod;
	lv[x]=lv[ls],rv[x]=rv[rs];
	if(rcs[ls]==0){
		lst[x].resize(lst[ls].size()+lst[rs].size());
		std::merge(lst[ls].begin(),lst[ls].end(),lst[rs].begin(),lst[rs].end(),lst[x].begin());
		for(std::list<std::pair<int,int>>::iterator it1=lst[x].begin(),it2=++lst[x].begin();it2!=lst[x].end();)if(it1->first==it2->first){
			it2->second+=it1->second;
			it1=lst[x].erase(it1);
			++it2;
		}else ++it1,++it2;
		lpos[x]=lpos[ls],rpos[x]=rpos[rs];
		tr[x]=tr[ls]+tr[rs];
	}else{
		if(lpos[ls]==mid-l+1) lpos[x]=mid-l+1+lpos[rs];
		else lpos[x]=lpos[ls];
		if(rpos[rs]==r-mid) rpos[x]=r-mid+rpos[ls];
		else rpos[x]=rpos[rs];
		lst[x].resize(lst[ls].size()+lst[rs].size());
		std::merge(lst[ls].begin(),lst[ls].end(),lst[rs].begin(),lst[rs].end(),lst[x].begin());
		for(std::list<std::pair<int,int>>::iterator it1=lst[x].begin(),it2=++lst[x].begin();it2!=lst[x].end();)if(it1->first==it2->first){
			it2->second+=it1->second;
			it1=lst[x].erase(it1);
			++it2;
		}else ++it1,++it2;
		int i=rpos[ls]+lpos[rs],book=0;
		for(std::list<std::pair<int,int>>::iterator it=lst[x].begin();it!=lst[x].end();){
			if(it->first==rpos[ls]) it->second--;
			if(it->first==lpos[rs]) it->second--;
			if(!book&&it->first>=i){
				if(it->first==i) it->second++;
				else lst[x].emplace(it,i,1);
				book=1;
			}
			if(!it->second) it=lst[x].erase(it);
			else ++it;
		}
		if(!book) lst[x].emplace(lst[x].end(),i,1);
		tr[x]=tr[ls]*tr[rs];
	}
}
int tagp[400010],tagv[400010];
inline void build(int x=1,int l=1,int r=n){
	tagv[x]=tagp[x]=-1;
	if(l==r){
		lst[x].emplace_back(1,1);
		tr[x].h=lpos[x]=rpos[x]=1;
		rcs[x]=p[l];
		tr[x].lpro=tr[x].rpro=tr[x].ans=sum[x]=prod[x]=lv[x]=rv[x]=a[l];
		return;
	}
	int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(x,ls,rs,l,mid,r);
}
inline void addtagp(int x,int v,int l,int r){
	if(v==0){
		lst[x].clear();
		lst[x].emplace_back(1,r-l+1);
		lpos[x]=rpos[x]=1;
		tr[x].h=rcs[x]=tagp[x]=0;
		tr[x].lpro=lv[x],tr[x].rpro=rv[x];
		tr[x].ans=sum[x];
		if(l==r) tr[x].h=1;
	}else{
		lst[x].clear();
		lst[x].emplace_back(r-l+1,1);
		lpos[x]=rpos[x]=r-l+1;
		tr[x].h=rcs[x]=tagp[x]=1;
		tr[x].lpro=tr[x].rpro=tr[x].ans=prod[x];
	}
}
inline int pow(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}
	return res;
}
inline void addtagv(int x,int v,int l,int r){
	tagv[x]=v;
	lv[x]=rv[x]=v;
	tr[x].lpro=pow(v,lpos[x]);
	tr[x].rpro=pow(v,rpos[x]);
	sum[x]=1ll*v*(r-l+1)%mod,prod[x]=pow(v,r-l+1);
	int last=0,ans=1;tr[x].ans=0;
	for(auto u:lst[x]){
		ans=1ll*ans*pow(v,u.first-last)%mod;
		last=u.first;
		tr[x].ans=(tr[x].ans+1ll*ans*u.second)%mod;
	}
}
inline void pushdown(int x,int ls,int rs,int l,int mid,int r){
	if(~tagv[x]) addtagv(ls,tagv[x],l,mid),addtagv(rs,tagv[x],mid+1,r),tagv[x]=-1;
	if(~tagp[x]) addtagp(ls,tagp[x],l,mid),addtagp(rs,tagp[x],mid+1,r),tagp[x]=-1;
}
inline void updatev(int pl,int pr,int v,int x=1,int l=1,int r=n){
	if(pl==l&&pr==r) return addtagv(x,v,l,r);
	int mid=(l+r)>>1,ls=x<<1,rs=x<<1|1;
	pushdown(x,ls,rs,l,mid,r);
	if(pr<=mid) updatev(pl,pr,v,ls,l,mid);
	else if(pl>mid) updatev(pl,pr,v,rs,mid+1,r);
	else updatev(pl,mid,v,ls,l,mid),updatev(mid+1,pr,v,rs,mid+1,r);
	pushup(x,ls,rs,l,mid,r);
}
inline void updatep(int pl,int pr,int v,int x=1,int l=1,int r=n){
	if(pl==l&&pr==r) return addtagp(x,v,l,r);
	int mid=(l+r)>>1,ls=x<<1,rs=x<<1|1;
	pushdown(x,ls,rs,l,mid,r);
	if(pr<=mid) updatep(pl,pr,v,ls,l,mid);
	else if(pl>mid) updatep(pl,pr,v,rs,mid+1,r);
	else updatep(pl,mid,v,ls,l,mid),updatep(mid+1,pr,v,rs,mid+1,r);
	pushup(x,ls,rs,l,mid,r);
}
inline node query(int pl,int pr,int x=1,int l=1,int r=n){
	if(pl==l&&pr==r) return tr[x];
	int mid=(l+r)>>1,ls=x<<1,rs=x<<1|1;
	pushdown(x,ls,rs,l,mid,r);
	if(pr<=mid) return query(pl,pr,ls,l,mid);
	else if(pl>mid) return query(pl,pr,rs,mid+1,r);
	else if(rcs[ls]==0) return query(pl,mid,ls,l,mid)+query(mid+1,pr,rs,mid+1,r);
	else return query(pl,mid,ls,l,mid)*query(mid+1,pr,rs,mid+1,r);
}
signed main(){
	long long tmp;
	in>>n>>m;
	for(int i=1;i<=n;i++) in>>tmp,a[i]=tmp%mod;
	for(int i=1;i<n;i++) in>>p[i];
	build();
	while(m--){
		int op,l,r,x;
		in>>op>>l>>r;
		if(op!=3) in>>tmp,x=tmp%mod;
		if(op==1) updatev(l,r,x);
		if(op==2) updatep(l,r,x);
		if(op==3) out<<query(l,r).ans;
	}
	return 0;
}
2021/5/11 08:02
加载中...