【Ynoi2013】文化课
根号复杂度的线段树
题目大意：
给定一个只包含 $+,\times$ 两种符号的表达式。有三个操作：
- 给定 $l,r,v$，将 $l\sim r$ 位置的操作数全部改成 $v$。
- 给定 $l,r,op$，将 $l\sim r$ 位置的运算符全部改成 $op$。
- 给定 $l,r$，将 $l\sim r$ 位置的操作数以及 $l\sim r-1$ 位置的运算符提取出来，连成一个表达式，求表达式的值。符合四则运算的顺序。
题解：
有趣的一道题，先 STO Juan_feng OTZ
考虑用线段树维护区间信息，并进行合并。
这里采用这样的方式记录：一个操作数后面跟一个运算符组合在一起，作为叶子结点。最后一个操作数后面的符号可以看做加号。
先考虑没有修改操作，我们如何合并两个区间的信息。
我们将由乘号连接的连续区间看成一个连通块。
考虑两个区间的符号是这样的情况：$[\dots+\times \times \dots\times][\times\times\dots\times+\dots]$。这种情况，在合并的时候，左边区间的最右边的连通块和右边区间最左边的连通块需要进行合并。
所以我们记录一个区间的 ans，还需要记录其左、右侧的连通块的答案 leftmul,rightmul。
然后合并的时候，ans=l->ans+r->ans-l.leftmul-r.leftmul+l.leftmul*r.leftmul，表示先减去左右两个连通块的值，再加上它们合并起来的值。
由于我们需要同时多记录 leftmul,rightmul，所以也需要维护这个信息。我们再额外记录 sz,leftlen,rightlen,oper，分别表示每个区间的长度，左边连通块的长度，右边连通块的长度，以及最右侧的符号是什么。
注意，由于每个区间左边没有记录符号，因此 leftlen 至少为 $1$，即最左侧的数自己本身可以为一个连通块。而我们记录了最右边的符号，那么当最右边的符号为加号时，rightlen=0,rightmul=1，表示那边并不能和右边连接成新的连通块。
考虑合并 leftmul 和 rightmul，分经过中点和不经过中点讨论一下即可。leftlen,rightlen 同时更新。
这样就完成了两个区间的信息合并，可以通过没有修改操作的情况。
考虑加上修改操作。
对于整个区间的数值修改，一个长度为 $t$ 的连通块会造成 $v^t$ 的贡献。但是连通块个数很多，显然不能直接更新。
注意到长度相同的连通块的贡献相同，而长度不同的连通块只有 $O(\sqrt {sz})$ 个。那么我们对于一个区间，维护一个大小为 $\sqrt{sz}$ 的桶记录长度不超过 $\sqrt{sz}$ 的连通块分别出现了多少次，再另开一个数组记录长度超过 $\sqrt{sz}$ 的连通块，这个数组的大小也是 $O(\sqrt{sz})$ 的。
那么我们推平整个区间的时候，只需 $O(\sqrt{sz})$ 扫描桶，计算长度不超过 $O(\sqrt{sz})$ 的连通块的贡献，再 $O(\sqrt{sz})$ 扫描数组，计算长度超过 $O(\sqrt{sz})$ 的连通块的贡献即可。然后对这个区间打数值修改标记，需要用时下传即可。
发现一个问题，计算长度较大的连通块的时候，会多出来一个快速幂的 $\log$，需要想办法把它卡下去。
lxl 的 trick：令连通块大小已经从小到大排序，那么 $x^{a}$ 到 $x^b$ 只需要乘上 $x^{b-a}$，需要 $O(\log(b-a))$ 的复杂度。这里 $a>\sqrt{sz}$ 并且所有指数的和不超过 sz，所以复杂度是正确的，不会多 $\log$。具体证明据 lxl 说比较麻烦。
至于如何保证长度较大的连通块始终有序，在合并的时候使用双指针归并即可。
而 leftmul,rightmul 的变化，可以直接用快速幂计算。
合并两个区间的同时，也需要合并桶的信息，这些都可以在 $O(\sqrt{sz})$ 内完成。注意合并经过中点的连通块会使信息产生变化。
对于整个区间的符号修改，如果修改成加号，那么区间的答案变成所有数的和，否则变为所有数的积。所以同时还要对区间维护 sum,mul，表示区间和与区间积。这些信息在区间推平时也容易维护。
修改符号的时候，会对 leftmul,rightmul,leftsum,rightsum 以及桶内信息产生影响。桶内信息暴力修改即可，leftmul,rightmul,leftsum,rightsum 根据符号情况进行变化即可。然后对这个区间打运算符修改标记，需要用时下传即可。
这里如果全局改成加号，那么根据上面所说，leftmul 应该变为最左边那个数。所以我们再记一个区间最左边的数的值就可以了。
至此解决了所有的操作。接下来分析复杂度。
对于任意一个线段树上的操作，在大小为 sz 的结点上的复杂度最多为 $O(\log n+\sqrt{sz})$。
而线段树每层的大小都是上一层的一半，每层只会涉及到 $O(1)$ 个结点的更新。
那么单次操作的复杂度就是 $O(\log^2n+\sqrt{n}+\sqrt{\frac{n}2}+\sqrt{\frac{n}4}+\dots)=O(\log^2 n+\sqrt n)$。
总时间复杂度 $O(m\sqrt n)$，空间复杂度 $O(n)$。
下面的代码并没有优化常数，所以跑得很慢
Update on 2020-3-18
模数改成 $10^9+7$ 了，更新了代码。
Code：
/*
By mrsrz
2019-11-05 ~ 2019-11-06
Update on 2020-03-17
*/
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=1e5+5,md=1e9+7;
inline void upd(int&a){a+=a>>31&md;}
inline int pwr(int a,int b){
int ret=1;
for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;
return ret;
}
struct info{
int leftlen,rightlen,leftmul,rightmul;
int sum,mul;
int ans;bool oper;int sz;
};
inline info merge(const info&a,const info&b){
info r;
r.sz=a.sz+b.sz;
upd(r.sum=a.sum+b.sum-md),r.mul=(LL)a.mul*b.mul%md;
if(a.leftlen==a.sz&&a.oper==1){
r.leftlen=a.sz+b.leftlen;
r.leftmul=(LL)a.mul*b.leftmul%md;
}else{
r.leftlen=a.leftlen;
r.leftmul=a.leftmul;
}
if(b.rightlen==b.sz&&a.oper==1){
r.rightlen=b.sz+a.rightlen;
r.rightmul=(LL)b.mul*a.rightmul%md;
}else{
r.rightlen=b.rightlen;
r.rightmul=b.rightmul;
}
r.oper=b.oper;
if(a.oper==1){
r.ans=((LL)a.ans+b.ans-a.rightmul-b.leftmul+(LL)a.rightmul*b.leftmul+2*md)%md;
}else upd(r.ans=a.ans+b.ans-md);
return r;
}
struct Data{
int leftlen,rightlen,leftmul,rightmul;
// 左连乘区间长度，右连乘区间长度，左连乘积，右连乘积
int sum,mul;// 区间和，区间乘积
int ans;bool oper;// 当前答案、最右边的符号
int tag_num;int tag_oper;// 区间修改数值、符号的标记
int sz,lim;// 区间长度，阈值大小
int*buc;// 记录小于等于阈值的多项式的出现次数
vector<int>vec;// 记录所有大于阈值的多项式，要保证有序
int left_num;//最左边的数
inline void makeLeaf(int _num,bool op){
ans=sum=mul=leftmul=left_num=_num;
leftlen=sz=lim=1;
oper=op;
if(op)rightlen=1,rightmul=_num;else rightmul=1,rightlen=0;
buc=new int[2];
buc[0]=0,buc[1]=1;
tag_num=-1,tag_oper=-1;
}
inline void init(int len){
sz=len,lim=sqrt(sz);
buc=new int[lim+1];
for(int i=0;i<=lim;++i)buc[i]=0;
tag_num=-1,tag_oper=-1;
}
void merge(const Data&a,const Data&b){
upd(sum=a.sum+b.sum-md),mul=(LL)a.mul*b.mul%md;
left_num=a.left_num;
if(a.leftlen==a.sz&&a.oper==1){//左边全是乘号
leftlen=a.sz+b.leftlen;
leftmul=(LL)a.mul*b.leftmul%md;
}else{
leftlen=a.leftlen;
leftmul=a.leftmul;
}
if(b.rightlen==b.sz&&a.oper==1){// 右边全是乘号且左边最后一个为乘号
rightlen=b.sz+a.rightlen;
rightmul=(LL)b.mul*a.rightmul%md;
}else{
rightlen=b.rightlen;
rightmul=b.rightmul;
}
oper=b.oper;
int sublen1=0,sublen2=0,addlen=999999;
if(a.oper==1){
ans=((LL)a.ans+b.ans-a.rightmul-b.leftmul+(LL)a.rightmul*b.leftmul+2*md)%md;
sublen1=a.rightlen,sublen2=b.leftlen;addlen=sublen1+sublen2;
}else upd(ans=a.ans+b.ans-md);
for(int i=0;i<=lim;++i)buc[i]=0;
vec.clear();
if(sublen1&&sublen1<=lim)--buc[sublen1],sublen1=0;
if(sublen2&&sublen2<=lim)--buc[sublen2],sublen2=0;
if(addlen<=lim)++buc[addlen],addlen=999999;
for(int i=1;i<=a.lim;++i)
buc[i]+=a.buc[i];
for(int i=1;i<=b.lim;++i)
buc[i]+=b.buc[i];
int it1=0,it2=0;
for(;it1<a.vec.size()&&it2<b.vec.size();){
int val=(a.vec[it1]<b.vec[it2])?a.vec[it1++]:b.vec[it2++];
if(addlen<val){
vec.push_back(addlen),addlen=999999;
}
if(val==sublen1){
sublen1=0;continue;
}
if(val==sublen2){
sublen2=0;continue;
}
if(val<=lim)++buc[val];else
vec.push_back(val);
}
for(;it1<a.vec.size();){
int val=a.vec[it1++];
if(addlen<val){
vec.push_back(addlen),addlen=999999;
}
if(val==sublen1){
sublen1=0;continue;
}
if(val==sublen2){
sublen2=0;continue;
}
if(val<=lim)++buc[val];else
vec.push_back(val);
}
for(;it2<b.vec.size();){
int val=b.vec[it2++];
if(addlen<val){
vec.push_back(addlen),addlen=999999;
}
if(val==sublen1){
sublen1=0;continue;
}
if(val==sublen2){
sublen2=0;continue;
}
if(val<=lim)++buc[val];else
vec.push_back(val);
}
if(addlen<999999)
vec.push_back(addlen);
}
void putTag_num(int val){
sum=(LL)val*sz%md,mul=pwr(val,sz),left_num=val;
leftmul=pwr(val,leftlen),rightmul=pwr(val,rightlen),ans=0;
int nx=1;
for(int i=1;i<=lim;++i){
nx=(LL)nx*val%md;
ans=(ans+(LL)buc[i]*nx)%md;
}
int lst=lim;
for(int i=0;i<vec.size();++i){
int p=vec[i];
nx=(LL)nx*pwr(val,p-lst)%md,lst=p,upd(ans+=nx-md);
}
tag_num=val;
}
void putTag_op(bool op){
oper=op;tag_oper=op;
if(op==1){//*
for(int i=0;i<=lim;++i)buc[i]=0;vec.clear();
if(sz>lim)vec.push_back(sz);else ++buc[sz];
leftlen=rightlen=sz;
leftmul=rightmul=ans=mul;
}else{//+
for(int i=0;i<=lim;++i)buc[i]=0;vec.clear();
buc[1]=sz;
leftlen=1,rightlen=0;
leftmul=left_num,rightmul=1;
ans=sum;
}
}
inline void pushdown(Data&ls,Data&rs){
if(tag_num!=-1){
ls.putTag_num(tag_num);
rs.putTag_num(tag_num);
tag_num=-1;
}
if(tag_oper!=-1){
ls.putTag_op(tag_oper);
rs.putTag_op(tag_oper);
tag_oper=-1;
}
}
inline info out(){
return(info){
leftlen,rightlen,leftmul,rightmul
,sum,mul
,ans,oper,sz
};
}
}d[N<<2];
int n,m;
int _num[N];int _op[N];
void build(int l,int r,int o){
if(l==r){
d[o].makeLeaf(_num[l],_op[l]);
return;
}
d[o].init(r-l+1);
const int mid=l+r>>1;
build(l,mid,o<<1),build(mid+1,r,o<<1|1);
d[o].merge(d[o<<1],d[o<<1|1]);
}
void modify_num(int l,int r,int o,const int&L,const int&R,const int&val){
if(L<=l&&r<=R)
d[o].putTag_num(val);else{
d[o].pushdown(d[o<<1],d[o<<1|1]);
const int mid=l+r>>1;
if(L<=mid)modify_num(l,mid,o<<1,L,R,val);
if(mid<R)modify_num(mid+1,r,o<<1|1,L,R,val);
d[o].merge(d[o<<1],d[o<<1|1]);
}
}
void modify_op(int l,int r,int o,const int&L,const int&R,const bool&op){
if(L<=l&&r<=R)
d[o].putTag_op(op);else{
d[o].pushdown(d[o<<1],d[o<<1|1]);
const int mid=l+r>>1;
if(L<=mid)modify_op(l,mid,o<<1,L,R,op);
if(mid<R)modify_op(mid+1,r,o<<1|1,L,R,op);
d[o].merge(d[o<<1],d[o<<1|1]);
}
}
info query(int l,int r,int o,const int&L,const int&R){
if(L<=l&&r<=R)return d[o].out();
d[o].pushdown(d[o<<1],d[o<<1|1]);
const int mid=l+r>>1;
if(L<=mid&&mid<R)return merge(query(l,mid,o<<1,L,R),query(mid+1,r,o<<1|1,L,R));
if(L<=mid)return query(l,mid,o<<1,L,R);
return query(mid+1,r,o<<1|1,L,R);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;unsigned x;
for(int i=1;i<=n;++i)cin>>x,_num[i]=x%md;
for(int i=1;i<n;++i)cin>>_op[i];_op[n]=0;
build(1,n,1);
while(m--){
int op,l,r;
cin>>op>>l>>r;
switch(op){
case 1:{
unsigned v;
cin>>v;
modify_num(1,n,1,l,r,v%md);
break;
}
case 2:{
int v;
cin>>v;
modify_op(1,n,1,l,r,v);
break;
}
case 3:{
info ret=query(1,n,1,l,r);
cout<<ret.ans<<'\n';
break;
}
}
}
return 0;
}