P5608 文化课
题面
题解
考虑线段树，发现线段树的区间合并比较容易。
然后区间赋值要求能够快速计算幂，要求能够维护一段内有多少个乘法连续段，分别有多长。
仍然考虑到连续段只有不超过 \(\sqrt{2len}+O(1)\) 种不同的值，然后使用光速幂，这样，稍微分析一下就可以得到单次操作 \(O(\sqrt n)\) 的复杂度，可以通过本题。
警告
本题码量特别大，作者写了 11.64k。
Code
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
const ui ppp=1000000007;
ui n,q;
ui a[100005];
ui b[100005];
ui lg2[100005];
namespace seg2{//维护具体数值
ui s[270005];
void build(ui p,ui l,ui r){
if(l==r){
s[p]=a[l]; return;
}ui m=l+r>>1; build(p<<1,l,m); build(p<<1|1,m+1,r);
}
void down(ui p){
if(s[p]){
s[p<<1]=s[p<<1|1]=s[p]; s[p]=0;
}
}
void update(ui p,ui l,ui r,ui x,ui y,ui v){
if(x>r||y<l) return;
if(x<=l&&r<=y){
s[p]=v; return;
}down(p); ui m=l+r>>1;
update(p<<1,l,m,x,y,v); update(p<<1|1,m+1,r,x,y,v);
}
ui query(ui p,ui l,ui r,ui x){
if(x>r||x<l) return 0; if(s[p]) return s[p];
ui m=l+r>>1; return query(p<<1,l,m,x)+query(p<<1|1,m+1,r,x);
}
}
namespace seg1{
ui qpw(ui x,ui y){
ui res=1;
while(y){
if(y&1){
res=1ull*res*x%ppp;
}x=1ull*x*x%ppp; y>>=1;
}return res;
}
ui pw1[513],pw2[513],lm;
ui pw3[513],pw4[513],lm2;
void init(ui h,ui _lm){
pw1[0]=pw2[0]=1; lm=_lm;
for(ui i=1;i<=(1<<_lm);i++) pw1[i]=1ull*pw1[i-1]*h%ppp;
for(ui i=1;i<=(1<<_lm-1);i++) pw2[i]=1ull*pw2[i-1]*pw1[1<<lm]%ppp;
}
ui pw(ui b){
return 1ull*pw1[b&((1<<lm)-1)]*pw2[b>>lm]%ppp;
}
void init2(ui h,ui _lm){
pw3[0]=pw4[0]=1; lm2=_lm;
for(ui i=1;i<=(1<<_lm);i++) pw3[i]=1ull*pw3[i-1]*h%ppp;
for(ui i=1;i<=(1<<_lm);i++) pw4[i]=1ull*pw4[i-1]*pw3[1<<lm2]%ppp;
}
ui pww(ui b){
return 1ull*pw3[b&((1<<lm2)-1)]*pw4[b>>lm2]%ppp;
}
ui memory[6000005],*nw=memory;
struct node{
ui lim;//<=lim的算小len，建树时设定，lim*lim>=r-l+1
ui *p1;//存储小len出现次数，不含左右乘数段
ui *p2,cnt;//大len（要求数量<=lim），不含左右乘数段
ui ans;//区间答案（不含最左段乘数、最右段乘数）
ui sum,mul;//维护区间和、区间积
ui cntl,cntr;//前缀乘数数量、后缀乘数数量
ui mull,mulr;//最左段乘积、最右段乘积
ui tag1=-1,tag2=-1;//数的覆盖操作、符号覆盖操作
ui len;//所表示线段树区间长度
ui lst;//区间末尾后面是+还是*
ui getans(){
if(cntl==len) return mull;
return (ans+mull+mulr)%ppp;
}
node operator+(const node &b)const{//不合并数组！
node c; c.lim=c.mul=c.ans=0; c.p1=c.p2=nw; c.cnt=0; c.tag1=c.tag2=-1;
if(cntl==len&&lst){
c.cntl=b.cntl+cntl;
c.mull=1ull*mull*b.mull%ppp;
}else{
c.cntl=cntl;
c.mull=mull;
}
if(b.cntr==b.len&&lst){
c.cntr=b.cntr+cntr;
c.mulr=1ull*mulr*b.mulr%ppp;
}else{
c.cntr=b.cntr;
c.mulr=b.mulr;
}
c.ans=ans+b.ans;
c.ans%=ppp;
if(cntl!=len&&b.cntl!=b.len){
if(lst==0) c.ans+=mulr+b.mull;
else c.ans+=1ull*mulr*b.mull%ppp;
}else if(!lst){
if(cntl!=len) c.ans+=mulr;
if(b.cntl!=b.len) c.ans+=b.mull;
}
c.ans%=ppp;
c.len=len+b.len;
c.lst=b.lst;
return c;
}
};
node s[270000];
void merge(ui p,const node &h1,const node &h2){//tips: merge不会改变s[p].lim,len等basic信息
memset(s[p].p1,0,s[p].lim+1<<2);
memset(s[p].p2,0,s[p].lim+1<<2);
s[p].cnt=0; s[p].sum=(h1.sum+h2.sum)%ppp;
s[p].mul=1ull*h1.mul*h2.mul%ppp; s[p].lst=h2.lst;
for(ui i=1;i<=h1.lim;i++) s[p].p1[i]+=h1.p1[i];
for(ui i=1;i<=h1.cnt;i++){
ui u=h1.p2[i]; if(u>s[p].lim) s[p].p2[++s[p].cnt]=u;
else s[p].p1[u]++;
}
for(ui i=1;i<=h2.lim;i++) s[p].p1[i]+=h2.p1[i];
for(ui i=1;i<=h2.cnt;i++){
ui u=h2.p2[i]; if(u>s[p].lim) s[p].p2[++s[p].cnt]=u;
else s[p].p1[u]++;
}
s[p].ans=(h1.ans+h2.ans)%ppp;
if(h1.lst==0){
s[p].cntl=h1.cntl; s[p].cntr=h2.cntr;
s[p].mull=h1.mull; s[p].mulr=h2.mulr;
if(h1.cntl==h1.len){
if(h2.cntl==h2.len){
}else{
ui u=h2.cntl;
if(u>s[p].lim) s[p].p2[++s[p].cnt]=u;
else s[p].p1[u]++;
s[p].ans+=h2.mull; s[p].ans%=ppp;
}
}else{
if(h2.cntl==h2.len){
ui u=h1.cntr;
if(u>s[p].lim) s[p].p2[++s[p].cnt]=u;
else s[p].p1[u]++;
s[p].ans+=h1.mulr; s[p].ans%=ppp;
}else{
ui u=h1.cntr;
if(u>s[p].lim) s[p].p2[++s[p].cnt]=u;
else s[p].p1[u]++;
u=h2.cntl;
if(u>s[p].lim) s[p].p2[++s[p].cnt]=u;
else s[p].p1[u]++;
s[p].ans+=h1.mulr; s[p].ans%=ppp;
s[p].ans+=h2.mull; s[p].ans%=ppp;
}
}
}else if(h1.cntl==h1.len){
if(h2.cntl==h2.len){
s[p].ans=0;
s[p].cntl=s[p].cntr=s[p].len;
s[p].mull=s[p].mulr=s[p].mul;
}else{
s[p].ans=h2.ans;
s[p].mull=1ull*h1.mull*h2.mull%ppp;
s[p].mulr=h2.mulr;
s[p].cntl=h1.cntl+h2.cntl;
s[p].cntr=h2.cntr;
}
}else if(h2.cntl==h2.len){
s[p].ans=h1.ans;
s[p].mull=h1.mull; s[p].mulr=1ull*h1.mulr*h2.mulr%ppp;
s[p].cntl=h1.cntl; s[p].cntr=h2.cntr+h1.cntr;
}else{
s[p].mull=h1.mull; s[p].mulr=h2.mulr;
s[p].cntl=h1.cntl; s[p].cntr=h2.cntr;
ui u=h1.cntr+h2.cntl;
if(u>s[p].lim) s[p].p2[++s[p].cnt]=u;
else s[p].p1[u]++;
s[p].ans+=1ull*h1.mulr*h2.mull%ppp;
s[p].ans%=ppp;
}
}
void down(ui p,ui l,ui r){//O(log n + sqrt(len))
ui m=l+r>>1;
if(s[p].tag2!=-1){
s[p<<1].lst=s[p].tag2;
s[p<<1].tag2=s[p].tag2;
memset(s[p<<1].p1,0,s[p<<1].lim+1<<2);
memset(s[p<<1].p2,0,s[p<<1].lim+1<<2);
s[p<<1].cnt=0;
if(s[p<<1].len>1){
if(s[p].tag2==0){//+
s[p<<1].mull=seg2::query(1,1,n,l);
s[p<<1].mulr=seg2::query(1,1,n,m);
s[p<<1].cntl=s[p<<1].cntr=1;
s[p<<1].ans=(s[p<<1].sum+ppp+ppp-s[p<<1].mull-s[p<<1].mulr)%ppp;
s[p<<1].p1[1]=s[p<<1].len-2;
}else{
s[p<<1].mull=s[p<<1].mulr=s[p<<1].mul;
s[p<<1].ans=0;
s[p<<1].cntl=s[p<<1].cntr=s[p<<1].len;
}
}
s[p<<1|1].lst=s[p].tag2;
s[p<<1|1].tag2=s[p].tag2;
s[p<<1|1].cnt=0;
memset(s[p<<1|1].p1,0,s[p<<1|1].lim+1<<2);
memset(s[p<<1|1].p2,0,s[p<<1|1].lim+1<<2);
if(s[p<<1|1].len>1){
if(s[p].tag2==0){//+
s[p<<1|1].mull=seg2::query(1,1,n,m+1);
s[p<<1|1].mulr=seg2::query(1,1,n,r);
s[p<<1|1].cntl=s[p<<1|1].cntr=1;
s[p<<1|1].ans=(s[p<<1|1].sum+ppp+ppp-s[p<<1|1].mull-s[p<<1|1].mulr)%ppp;
s[p<<1|1].p1[1]=s[p<<1|1].len-2;
}else{
s[p<<1|1].mull=s[p<<1|1].mulr=s[p<<1|1].mul;
s[p<<1|1].ans=0;
s[p<<1|1].cntl=s[p<<1|1].cntr=s[p<<1|1].len;
}
}
s[p].tag2=-1;
}
if(s[p].tag1!=-1){
s[p<<1].tag1=s[p].tag1;
init2(s[p<<1].tag1,lg2[s[p<<1].lim]+1);
s[p<<1].mull=pww(s[p<<1].cntl); s[p<<1].mulr=pww(s[p<<1].cntr);
s[p<<1].sum=1ull*s[p].tag1*s[p<<1].len%ppp; s[p<<1].mul=pww(s[p<<1].len);
s[p<<1].ans=0;
for(ui i=1;i<=s[p<<1].lim;i++){
s[p<<1].ans+=1ull*pww(i)*s[p<<1].p1[i]%ppp; s[p<<1].ans%=ppp;
}
for(ui i=1;i<=s[p<<1].cnt;i++){
s[p<<1].ans+=pww(s[p<<1].p2[i]); s[p<<1].ans%=ppp;
}
s[p<<1|1].tag1=s[p].tag1;
s[p<<1|1].mull=pww(s[p<<1|1].cntl); s[p<<1|1].mulr=pww(s[p<<1|1].cntr);
s[p<<1|1].sum=1ull*s[p].tag1*s[p<<1|1].len%ppp; s[p<<1|1].mul=pww(s[p<<1|1].len);
s[p<<1|1].ans=0;
for(ui i=1;i<=s[p<<1|1].lim;i++){
s[p<<1|1].ans+=1ull*pww(i)*s[p<<1|1].p1[i]%ppp; s[p<<1|1].ans%=ppp;
}
for(ui i=1;i<=s[p<<1|1].cnt;i++){
s[p<<1|1].ans+=pww(s[p<<1|1].p2[i]); s[p<<1|1].ans%=ppp;
}
s[p].tag1=-1;
}
}
void build(ui p,ui l,ui r){//O(n)
s[p].lim=sqrt(r-l+1)+1.05; s[p].len=r-l+1;
s[p].p1=nw; nw+=s[p].lim+2; s[p].p2=nw; nw+=s[p].lim+2;
if(l==r){
s[p].ans=0; s[p].sum=s[p].mul=s[p].mull=s[p].mulr=a[l]%ppp;
s[p].cntl=s[p].cntr=1;
s[p].lst=b[l]; return ;
}
ui m=l+r>>1; build(p<<1,l,m); build(p<<1|1,m+1,r);
merge(p,s[p<<1],s[p<<1|1]);
}
void update1(ui p,ui l,ui r,ui x,ui y,ui v){//O(sqrt(n)+log^2n)
if(x>r||y<l) return;
if(x<=l&&r<=y){
s[p].tag1=v; s[p].sum=1ull*s[p].len*v%ppp; s[p].mul=pw(s[p].len);
s[p].ans=0;
for(ui i=1;i<=s[p].lim;i++){
s[p].ans+=1ull*pw(i)*s[p].p1[i]%ppp; s[p].ans%=ppp;
}
for(ui i=1;i<=s[p].cnt;i++){
s[p].ans+=pw(s[p].p2[i]); s[p].ans%=ppp;
}
s[p].mull=pw(s[p].cntl); s[p].mulr=pw(s[p].cntr);
return;
}down(p,l,r);
ui m=l+r>>1;
update1(p<<1,l,m,x,y,v); update1(p<<1|1,m+1,r,x,y,v);
merge(p,s[p<<1],s[p<<1|1]);
}
void update2(ui p,ui l,ui r,ui x,ui y,ui v){//O(sqrt(n)+log^2n)
if(x>r||y<l) return;
if(x<=l&&r<=y){
s[p].tag2=v; s[p].lst=v;
if(l==r) return;
memset(s[p].p1,0,s[p].lim+1<<2); memset(s[p].p2,0,s[p].lim+1<<2);
s[p].cnt=0;
if(v==0){
s[p].cntl=s[p].cntr=1;
s[p].mull=seg2::query(1,1,n,l); s[p].mulr=seg2::query(1,1,n,r);
s[p].ans=(s[p].sum+ppp+ppp-s[p].mull-s[p].mulr)%ppp;
s[p].p1[1]=max(0u,r-l-1);
}else{
s[p].cntl=s[p].cntr=s[p].len; s[p].mull=s[p].mulr=s[p].mul;
s[p].ans=0;
}
return;
}down(p,l,r);
ui m=l+r>>1;
update2(p<<1,l,m,x,y,v); update2(p<<1|1,m+1,r,x,y,v);
merge(p,s[p<<1],s[p<<1|1]);
}
node query(ui p,ui l,ui r,ui x,ui y){
if(x<=l&&r<=y){
return s[p];
}down(p,l,r);
ui m=l+r>>1;
if(m<x) return query(p<<1|1,m+1,r,x,y);
else if(m>=y) return query(p<<1,l,m,x,y);
else return query(p<<1,l,m,x,y)+query(p<<1|1,m+1,r,x,y);
}
}
void upd_num(ui l,ui r,ui v){
seg2::update(1,1,n,l,r,v);
seg1::init(v,9);
seg1::update1(1,1,n,l,r,v);
}
void upd_opt(ui l,ui r,ui v){
seg1::update2(1,1,n,l,r,v);
}
ui qry_ans(ui l,ui r){
seg1::node d=seg1::query(1,1,n,l,r);
ui s=d.getans();
return s;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
cin>>n>>q;
for(ui i=2;i<=n;i++) lg2[i]=lg2[i>>1]+1;
for(ui i=1;i<=n;i++) cin>>a[i];
for(ui i=1;i<=n;i++) a[i]%=ppp;
for(ui i=1;i<n;i++) cin>>b[i];
seg1::build(1,1,n); seg2::build(1,1,n);
while(q--){
ui op,l,r,v; cin>>op>>l>>r;
if(op!=3){
cin>>v; v%=ppp;
}
if(op==1) upd_num(l,r,v);
else if(op==2) upd_opt(l,r,v);
else cout<<qry_ans(l,r)<<'\n';
}
return 0;
}