有人帮忙看看是哪里常数大吗
#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;
}