线段树+树状数组

线段树大C

树状数组与线段树总结

时间复杂度
虽然它们都是nlogn，但是，你会发现，在查询时，树状数组最坏情况是logn（比如8个数，然后查询8），但是线段树是所有情况都是nlogn，稍慢于树状数组。

空间复杂度

树状数组完胜于线段树，线段树要开2倍到4倍内存（推荐4倍），但是树状数组一倍就够了。

适用范围

线段树之所以存在的理由是因为它能适用于很多方面，不仅仅是区间、单点的查询修改，还有标记等等，可以用于模拟、DP等等，而且空间经过离散化以后也可以相对压缩，所以适用范围线段树更加广一些。

树状数组

树状数组单点修改

模板

#include<bits/stdc++.h>
typedef long long ll;
const long long maxn=5e5+11;
using namespace std;
ll t[maxn],n;//树状数组空间开一倍就够了
ll lowbit(ll x){
    return x & -x;
}
void add(ll x,ll val){
    while(x<=n){
        t[x]+=val;
        x+=lowbit(x);
    }
}
ll getsum(ll x){
    ll sum=0;
    while(x>=1){
        sum+=t[x];
        x-=lowbit(x);
    }
    return sum;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll m;
    cin>>n>>m;
    for(ll i=1,val;i<=n;i++){
        cin>>val;
        add(i,val);
    }
    ll op,val,l,r;
    while(m--){
        cin>>op;
        if(op==1){
            cin>>l>>val;
            add(l,val);
        }
        else if(op==2){
            cin>>l>>r;
            cout<<getsum(r)-getsum(l-1)<<endl;
        }
    }
    return 0;
}

线段树

线段树单点修改

模板

//注意保证l<r及数据的合法性
#include<bits/stdc++.h>
using namespace std;
#define lson l,m,now<<1
#define rson m+1,r,now<<1|1
typedef long long ll;
const long long maxn=5e5+11;
ll t[maxn<<2],ar[maxn]; //线段树得开四倍
void push_up(ll now){
    t[now]=t[now<<1]+t[now<<1|1];
}
void build(ll l,ll r,ll now){
    if(l==r){
        t[now]=ar[l];
        return ;
    }
    ll m=l+((r-l)>>1);//这个操作挺牛逼的,不然我只会写m=(l+r)/2...
    build(lson);build(rson);
    push_up(now);
}

void add(ll x,ll val,ll l,ll r,ll now){
    t[now]+=val;
    if(l==r)  return ;
    ll m=l+((r-l)>>1);
    if(x<=m)  add(x,val,lson);
    else  add(x,val,rson);
}
ll getsum(ll L,ll R,ll l,ll r,ll now){
    if(L<=l && r<=R){
        return t[now];
    }
    ll m=l+((r-l)>>1);
    ll sum=0;
    if(L<=m)  sum+=getsum(L,R,lson);
    if(R>m)  sum+=getsum(L,R,rson);
    return sum;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,m;
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>ar[i];
    }
    build(1,n,1);
    ll op,x,val,r;
    while(m--){
        cin>>op;
        if(op==1){
            cin>>x>>val;
            add(x,val,1,n,1);
        }
        else if(op==2){
            cin>>x>>r;
            cout<<getsum(x,r,1,n,1)<<endl;
        }
    }
    return 0;
}

线段树区间修改

模板

//注意保证l<r及数据的合法性
#include<bits/stdc++.h>
using namespace std;
#define lson l,m,now<<1
#define rson m+1,r,now<<1|1
typedef long long ll;
const long long maxn=5e5+11;
ll t[maxn<<2],ar[maxn],lazy[maxn<<2];//线段树得开四倍
void push_up(ll now){
    t[now]=t[now<<1]+t[now<<1|1];
}
void push_down(ll l,ll r,ll now){
    ll m=l+((r-l)>>1);
    if(lazy[now]){
        t[now<<1]+=lazy[now]*(m-l+1),lazy[now<<1]+=lazy[now];
        t[now<<1|1]+=lazy[now]*(r-m),lazy[now<<1|1]+=lazy[now];
        lazy[now]=0;
    }
}
void build(ll l,ll r,ll now){
    if(l==r){
        t[now]=ar[l];
        return ;
    }
    ll m=l+((r-l)>>1);//这个操作挺牛逼的,不然我只会写m=(l+r)/2...
    build(lson);build(rson);
    push_up(now);
}
void add(ll L,ll R,ll val,ll l,ll r,ll now){
    if(L <= l && r <= R){//因为输入数据的L,R可能超过最大范围
        t[now]+=(r-l+1)*val,lazy[now]+=val;
        return;
    }
    ll m=l+((r-l)>>1);
    push_down(l,r,now);
    if(L<=m) add(L,R,val,lson);
    if(R>m) add(L,R,val,rson);
    push_up(now);
}
ll getsum(ll L,ll R,ll l,ll r,ll now){
    if (L<=l && r<=R)  return t[now];
    ll m=l+((r-l)>>1);
    push_down(l,r,now);
    ll sum=0;
    if(L<=m)  sum=getsum(L,R,lson);
    if(R>m)  sum+=getsum(L,R,rson);
    return sum;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,m;
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>ar[i];
    }
    build(1,n,1);
    ll op,x,val,r;
    while(m--){
        cin>>op;
        if(op==1){
            cin>>x>>r>>val;
            add(x,r,val,1,n,1);
        }
        else if(op==2){
            cin>>x>>r;
            cout<<getsum(x,r,1,n,1)<<endl;
        }
    }
    return 0;
}

线段树扫描线

模板

//没有下放操作，在cnt=1时不会错，cnt=2时会错,即如果求矩形面积的并不会错，求至少覆盖两次的会出错
//线段树每个点代表一个区间，不能用每个点代表一个点
#include<iostream>
#include<algorithm>
using namespace std;
#define Debug(x) cout<<#x<<":"<<x<<endl;
#define lson l,m,now<<1
#define rson m+1,r,now<<1|1
typedef long long ll;
const ll maxn=4e5+11;
struct Line{
    ll x1,x2,y,w;
    bool operator < (const Line& b)  const{
        return y<b.y;
    }
}line[maxn];
ll t[maxn<<2],cnt[maxn<<2],x[maxn],step;
void push_up(ll l,ll r,ll now){
    if(cnt[now])  t[now]=x[r+1]-x[l];
    else  t[now]=t[now<<1]+t[now<<1|1];
}
void update(ll L,ll R,ll val,ll l,ll r,ll now){
    if(L<=l && r<=R){
        cnt[now]+=val;
        push_up(l,r,now);
        return ;
    }
    ll m=l+((r-l)>>1);
    if(L<=m)  update(L,R,val,lson);
    if(R>m)  update(L,R,val,rson);
    push_up(l,r,now);
}
ll pos(ll xi){
    return lower_bound(x+1,x+1+step,xi)-x;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;cin>>n;
    for(ll i=1,x1,y1,x2,y2;i<=n;i++){
        cin>>x1>>y1>>x2>>y2;
        line[(i<<1)-1].x1=x1,line[(i<<1)-1].x2=x2,line[(i<<1)-1].y=y1,line[(i<<1)-1].w=1;
        line[i<<1].x1=x1,line[i<<1].x2=x2,line[i<<1].y=y2,line[i<<1].w=-1;
        x[(i<<1)-1]=x1,x[i<<1]=x2;
    }
    sort(line+1,line+1+2*n);
    sort(x+1,x+1+2*n);
    step=unique(x+1,x+1+2*n)-(x+1);
    ll ans=0;
    for(ll i=1;i<=2*n-1;i++){
        update(pos(line[i].x1),pos(line[i].x2)-1,line[i].w,1,step-1,1);
        ans+=t[1]*(line[i+1].y-line[i].y);
    }
    cout<<ans<<endl;
    return 0;
}

4⭐树状数组统计ai之前比ai小的数个数

题意：给一个长度为n<5e4的数列，每个数编号从1到n，且无重复。一个四元组(a,b,c,d)，要求a<b<c<d 且 Aa<Ab && Ac<Ad,问数列中这样的四元组有多少个。

思路：关键在于如何统计数列中在ai之前且比ai小的数有多少个。用树状数组统计，代码如下：
for(ll i=1;i<=n;i++) re[i]=sum(ar[i]),add(ar[i],1);
知道这点后，对于四元组中每个b，其四元组个数为(b之前小于b的个数)*(b之后的(c,d)对数)，对于(c,d)对数统计，即倒过来再扫一遍即可。

#include<iostream>
#include<cstring>
typedef long long ll;
const long long maxn=5e4+11;
using namespace std;
ll t[maxn],ar[maxn],markl[maxn],markr[maxn],n;//树状数组空间开一倍就够了
ll lowbit(ll x){
    return x & -x;
}
void add(ll x,ll val){
    while(x<=n){
        t[x]+=val;
        x+=lowbit(x);
    }
}
ll getsum(ll x){
    ll sum=0;
    while(x>=1){
        sum+=t[x];
        x-=lowbit(x);
    }
    return sum;
}
void solve(){
    memset(t,0,sizeof(t));
    for(ll i=1;i<=n;i++){
        markl[i]=getsum(ar[i]);
        add(ar[i],1);
    }
    memset(t,0,sizeof(t));
    memset(markr,0,sizeof(markr));
    for(ll i=n;i>=1;i--){
        markr[i]=n-i-getsum(ar[i])+markr[i+1];
        add(ar[i],1);
    }
    ll ans=0;
    for(ll i=1;i<=n-1;i++){
        ans+=markl[i]*markr[i+1];
    }
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t;cin>>t;
    while(t--){
        cin>>n;
        for(ll i=1;i<=n;i++)  cin>>ar[i];
        solve();
    }
    return 0;
}

线段树基本运用（有另类巧妙做法）

题意 有 t 组数据，每组有 n 张(1<=n<=1e4)覆盖了 区间 [li,ri] 的海报(1<=i<=n,1<=li<=ri<=1e7)，海报会由于张贴顺序先后而被覆盖 问还有多少张海报能够看得见
优质题解

点击查看代码

  

//两种做法
//dfs做法
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const ll maxn=1e5+11;
ll li[maxn],ri[maxn],vis[maxn],ans;
void dfs(ll l,ll r,ll x){
    if(x==0)  return ;
    if(l<=ri[x] && li[x]<=r){
        if(!vis[x]){
            vis[x]=1;ans++;
        }
        if(l<li[x])  dfs(l,li[x]-1,x-1);
        if(r>ri[x])  dfs(ri[x]+1,r,x-1);
    }
    else  dfs(l,r,x-1);
}
void init(){
    memset(vis,0,sizeof(vis));
    ans=0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t;cin>>t;
    while(t--){
        init();
        ll n;cin>>n;
        for(ll i=1;i<=n;i++)  cin>>li[i]>>ri[i];
        dfs(1,1e7,n);
        cout<<ans<<endl;
    }
    return 0;
}


//线段树做法
#include<iostream>
#include<cstring>
#include<algorithm>
#define lson l,m,now<<1
#define rson m+1,r,now<<1|1
using namespace std;
#define Debug(x) cout<<#x<<":"<<x<<endl;
typedef long long ll;
const ll maxn=3e4+11;
ll t[maxn<<2],vis[maxn<<2],x[maxn<<2],a[maxn<<2],b[maxn<<2],ans,step;
void push_down(ll now){
    if(t[now]){
        t[now<<1]=t[now<<1|1]=t[now];
        t[now]=0;
    }
}
void update(ll L,ll R,ll val,ll l,ll r,ll now){
    if(L<=l && r<=R){
        t[now]=val;return ;
    }
    push_down(now);
    ll m=l+((r-l)>>1);
    if(L<=m) update(L,R,val,lson);
    if(R>m) update(L,R,val,rson);
}
void query(ll l,ll r,ll now){
    if(t[now] && !vis[t[now]]){
        vis[t[now]]=1;ans++;
        return ;
    }
    if(l==r)  return ;
    push_down(now);
    ll m=l+((r-l)>>1);
    query(lson);query(rson);
}
ll pos(ll xi){
    return lower_bound(x+1,x+1+step,xi)-x;
}
void init(){
    memset(vis,0,sizeof(vis));
    memset(t,0,sizeof(t));
}
int main(){
    ll ta;cin>>ta;
    while(ta--){
        init();
        ll n;step=1;cin>>n;
        for(ll i=1;i<=n;i++){
            cin>>a[i]>>b[i];
            if(b[i]-a[i]>1)  x[step++]=a[i]+1;
            x[step++]=a[i];x[step++]=b[i];
        }
        sort(x+1,x+step);
        step=unique(x+1,x+step)-(x+1);
        for(ll i=1;i<=n;i++){
            update(pos(a[i]),pos(b[i]),i,1,step,1);
        }
        ans=0;query(1,step,1);
        cout<<ans<<endl;
    }
    return 0;
}

  

线段树基本运用（有另类巧妙做法）

题意
n个点，m个操作(1<=n,m<=5e4)，m行中每行一个字符c表示操作类型，一个整型数x表示第x个点
D x 表示去掉第x点，Q x表示需输出含 x 的最大连续区间的长度，R x表示还原最后去掉的点

优质题解

线段树灵活运用(1700)

题意
t 组数据(t<=10)，每组第一行一个 n 表示 n 个员工(n<=5e4)，接下来 n-1 行，每行两个整数 u,v 表示 v 是 u 的上司
然后一行 m 表示有 m 个操作(m<=5e4) ， 接下来 m 行 由一个字符 和 整型数构成 ，表示不同操作
C x 表示 输出 第 x 个员工的工作号
T x y 表示 将 第 x 个员工的工作号变为 y (x<=n，0<=y<=1e9)
规定，改变工作时，被改变员工的下属一同变为 y

优质题解
注意用线段树求某点对应区间时，只需要在dfs序时，记录其区间左端点和右端点即可，没必要再拉个深度d数组，再二分找

线段树灵活运用-不确定区间

题意：有n<5e4个花瓶，编号0n-1，有m<5e4次操作，操作1：从a开始放f个花瓶，输出花瓶放置的第一个位置和最后一个位置，操作2：拿掉ab之间的花瓶，输出拿掉的花瓶的数量

思路：由于这题是从a开始放f个花瓶，那么与以往线段树不同的一点是，这个区间的右端点是不确定的，得我们自己确定这个区间的右端点。虽然最容易想到的是在线段树里模拟放置花瓶，但是这肯定是不行的。第一，线段树的一般用法不是这么用的，第二，模拟的细节巨多，耗时，炸心，不可能写出来。那我们的方法就是通过二分查找出这个区间的右端点即可，还有一个点就是还需要找到放置花瓶的起始位置和最后一个位置，剩下的就是基础线段树操作。这道题还是需要线段树较扎实的功底的。

/*
* @Author: Marhoosh
* @Date:   2021-09-04 21:45:32
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-09-17 15:02:14
*/
#include<iostream>
#include<cstring>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define lson l,m,now<<1
#define rson m+1,r,now<<1|1
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=5e4+11;
ll t[maxn<<2],lazy[maxn<<2],beg,en,ans;
//编号0~N-1
void push_up(ll now){
    t[now]=t[now<<1]+t[now<<1|1];
}
void push_down(ll l,ll r,ll now){
    if(lazy[now]>=0){
        ll m=l+((r-l)>>1);
        t[now<<1]=(m-l+1)*lazy[now];t[now<<1|1]=(r-m)*lazy[now];
        lazy[now<<1]=lazy[now<<1|1]=lazy[now];
        lazy[now]=-1;
    }
}
void build(){
    memset(t,0,sizeof(t));
    memset(lazy,-1,sizeof(lazy));
}
ll get_sum(ll L,ll R,ll l,ll r,ll now){
    if(L<=l && r<=R){
        return t[now];
    }
    push_down(l,r,now);
    ll m=l+((r-l)>>1);
    ll sum=0;
    if(L<=m)  sum+=get_sum(L,R,lson);
    if(R>m)  sum+=get_sum(L,R,rson);
    return sum;
}
void add(ll L,ll R,ll l,ll r,ll now){
    if(L<=l && r<=R){
        t[now]=r-l+1;lazy[now]=1;
        return ;
    }
    push_down(l,r,now);
    ll m=l+((r-l)>>1);
    if(L<=m)  add(L,R,lson);
    if(R>m)  add(L,R,rson);
    push_up(now);
}
void dle(ll L,ll R,ll l,ll r,ll now){
    if(L<=l && r<=R){
        ans+=t[now];t[now]=0;lazy[now]=0;
        return ;
    }
    push_down(l,r,now);
    ll m=l+((r-l)>>1);
    if(L<=m)  dle(L,R,lson);
    if(R>m)  dle(L,R,rson);
    push_up(now);
}
void found_b(ll L,ll R,ll l,ll r,ll now){
    if(t[now]==r-l+1)  return ;
    if(beg!=-1)  return ;
    if(l==r && t[now]==0){
        beg=l;return ;
    }
    push_down(l,r,now);
    ll m=l+((r-l)>>1);
    if(L<=m)  found_b(L,R,lson);
    if(R>m)  found_b(L,R,rson);
}
void found_e(ll L,ll R,ll l,ll r,ll now){
    if(t[now]==r-l+1)  return ;
    if(en!=-1)  return ;
    if(l==r && t[now]==0){
        en=l;return ;
    }
    push_down(l,r,now);
    ll m=l+((r-l)>>1);
    if(R>m)  found_e(L,R,rson);
    if(L<=m)  found_e(L,R,lson);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll ta;cin>>ta;
    while(ta--){
        ll n,m;cin>>n>>m;
        build();
        for(ll i=1,o,a,f;i<=m;i++){
            cin>>o>>a>>f;
            if(o==1){
                ll nn=get_sum(a,n-1,0,n-1,1);
                beg=-1;en=-1;
                found_b(a,n-1,0,n-1,1);found_e(a,n-1,0,n-1,1);
                if(nn==n-a){
                    cout<<"Can not put any one."<<endl;
                    continue;
                }
                if(nn+f>=n-a){
                    add(a,n-1,0,n-1,1);
                    cout<<beg<<" "<<en<<endl;continue;
                }
                ll l=a,r=n-1;
                while(l<r){
                    ll mid=(r+l)>>1;
                    if(get_sum(a,mid,0,n-1,1)+f<=mid-a+1)  r=mid;
                    else  l=mid+1;
                }
                add(a,l,0,n-1,1);
                cout<<beg<<" "<<l<<endl;continue;
            }
            else{
                ans=0;
                dle(a,f,0,n-1,1);
                cout<<ans<<endl;continue;
            }
            
        }
        cout<<endl;
    }
    return 0;
}

线段树-找最近小

The 2021 ICPC Asia Regionals Online Contest A Busiest Computing Nodes
题意：有k<1e5个工厂，从0k-1编号，有n个任务，从0n-1编号，每个任务有一个到达时间和一个处理时间。每个任务到达时，若其任务编号为i，则先从第i%k个工厂开始往后找,i+1%k,i+2%k…..一直找到i-1%k，如果所有工厂都不空闲，则此任务被丢弃，问处理任务最多的工厂是哪些。

点击查看思路

  

思路：即找最近小的t，满足arrival_time（记为ta） < t,那么因为这个是最近小，距离是第一优先级，就不能用单调队列那些，因为不是按t排序的。这里就要用到二分查找。查找分为两个区间，一个是[i%k,n-1],另一个是[0,i-1%k]，前者记为a区间，后者记为b区间。先找到a区间的最小值，如果最小值(记为minn)都>ta，则找b区间。否则“先”在a区间的左半区间找，若minn>ta，则找a的右半区间找。即先找每个区间的左区间，左区间没有再找右区间即可。是一个二分的思想。用线段树维护区间最小值即可。我一开始也没想到二分还能这么用，因为我看这道题t不是单调的，但是现在发现距离是单调的，所以查找最近小还是可以用二分。
  

/*
* @Author: Marhoosh
* @Date:   2021-07-22 10:27:29
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-09-20 12:29:16
*/
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define lson l,m,now<<1
#define rson m+1,r,now<<1|1
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=1e5+11;
ll t[maxn<<2],cnt[maxn],maxx;
vector<ll> v;
void push_up(ll now){
    t[now]=min(t[now<<1],t[now<<1|1]);
}
void update(ll L,ll val,ll l,ll r,ll now){
    if(L==l && L==r){t[now]=val;return ;}
    ll m=l+((r-l)>>1);
    if(L<=m)  update(L,val,lson);
    else  update(L,val,rson);
    push_up(now);
}
ll found(ll L,ll R,ll val,ll l,ll r,ll now){
    if(val<t[now])  return -1;
    if(l==r && t[now]<=val){
        return l;
    }  
    if(l==r)  return -1;
    ll m=l+((r-l)>>1);
    ll flag=-1;
    if(L<=m)  flag=found(L,R,val,lson);
    if(flag==-1){
        if(R>m)  return found(L,R,val,rson);
    }
    return flag;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll k,n;cin>>k>>n;
    for(ll i=0,ta,tc;i<n;i++){
        cin>>ta>>tc;
        ll pos=i%k;
        ll flag=found(pos,k-1,ta,0,k-1,1);
        if(flag==-1){
            if(pos==0)  continue;
            ll flagg=found(0,pos-1,ta,0,k-1,1);
            if(flagg==-1)  continue;
            flag=flagg;
        }
        update(flag,ta+tc,0,k-1,1);
        cnt[flag]++;
        if(cnt[flag]>maxx){
            maxx=cnt[flag];v.clear();v.push_back(flag);
        }
        else if(cnt[flag]==maxx)  v.push_back(flag);
    }
    sort(v.begin(),v.end());
    for(auto i=v.begin();i!=v.end();i++){
        if(i==v.end()-1)  cout<<*i;
        else  cout<<*i<<" ";
    }
    return 0;
}

Segment Tree beats 维护一个数列

题意

这里对于100以内的25个质数的维护，可以状态压缩，即用一个int的一位二进制表示改质数是否存在。也就是再拉个线段树维护25个质数。

#include<bits/stdc++.h>
using namespace std;
#define Debug(x)  cout<<#x<<": "<<x<<endl;
#define lson l,m,now<<1
#define rson m+1,r,now<<1|1
typedef long long ll;
const ll maxn=1e5+11;
const ll mo=998244353;
ll t[maxn<<2],rr[maxn<<2],x[maxn],lazy[maxn<<2],ar[111];
ll tmp;
ll is(ll x){
    for(ll i=2;i*i<=x;i++)  if(x%i==0)  return 0;
    return 1;
}
void init(){
    tmp=0;
    for(ll i=2;i<=100;i++){
        if(is(i))  ar[tmp++]=i;
    }
}
ll fy(ll x){//计算x的欧拉值
    ll ans=x;
    for(ll i=0;i<25;i++){
        if(x%ar[i]==0){
            ans=ans*(ar[i]-1)/ar[i];
        }
    }
    return ans;
}
ll wei(ll x){
    ll ans=0;
    for(ll i=0;i<25;i++){
        if(x%ar[i]==0){
            ans=ans|(1<<i);
        }
    }
    return ans;
}
void push_up(ll now){
    t[now]=(t[now<<1]+t[now<<1|1])%mo;
    rr[now]=rr[now<<1]&rr[now<<1|1];
}
void push_down(ll l,ll r,ll now){
    if(lazy[now]>1){
        t[now<<1]=t[now<<1]*lazy[now]%mo;
        lazy[now<<1]=lazy[now<<1]*lazy[now]%mo;
        t[now<<1|1]=t[now<<1|1]*lazy[now]%mo;
        lazy[now<<1|1]=lazy[now<<1|1]*lazy[now]%mo;
        lazy[now]=1;
    }
}
void build(ll l,ll r,ll now){
    lazy[now]=1;
    if(l==r){
        t[now]=fy(x[l]);rr[now]=wei(x[l]);
        return ;
    }
    ll m=l+((r-l)>>1);
    build(lson);build(rson);
    push_up(now);
}
void update(ll L,ll R,ll w,ll val,ll l,ll r,ll now){
    if(L<=l && r<=R && (rr[now]&val)==val){
        t[now]=t[now]*w%mo;lazy[now]=lazy[now]*w%mo;
        return ;
    }
    if(l==r){
        t[now]=t[now]*w;
        for(ll i=0;i<25;i++){
            if(((rr[now]>>i)&1)==0 && ((val>>i)&1)==1){
                t[now]=t[now]*(ar[i]-1)/ar[i];
            }
        }
        t[now]=t[now]%mo;
        rr[now]=rr[now]|val;  
        return ;
    }
    ll m=l+((r-l)>>1);
    push_down(l,r,now);
    if(L<=m)  update(L,R,w,val,lson);
    if(R>m)  update(L,R,w,val,rson);
    push_up(now);
}
ll getsum(ll L,ll R,ll l,ll r,ll now){
    if(L<=l && r<=R)  return t[now];
    ll m=l+((r-l)>>1);
    push_down(l,r,now);
    ll sum=0;
    if(L<=m)  sum=getsum(L,R,lson)%mo;
    if(R>m)  sum=(sum+getsum(L,R,rson))%mo;
    return sum;
}
int main(){
    init();
    ll n,m;cin>>n>>m;
    for(ll i=1;i<=n;i++)  cin>>x[i];
    build(1,n,1);
    for(ll i=1;i<=m;i++){
        ll op,l,r,w;
        cin>>op;
        if(op==0){
            cin>>l>>r>>w;
            if(w==1)  continue;
            update(l,r,w,wei(w),1,n,1);
        }
        if(op==1){
            cin>>l>>r;
            cout<<getsum(l,r,1,n,1)<<endl;
        }
    }
    return 0;
}

线段树灵活运用

Lovers HDU - 6562

n,q < 1e5;

思路：容易想到，维护一个区间和，再维护一个区间的一样长的串的长度，若区间内串长度不一样，则为-1.
按照这种想法，在update的时候，需要串长一样才能更新，这样子复杂度较大，导致TLE。

优化：思考如何做到在一个区间内串长不一样时，照样可以更新呢？

通过公式推导，

这里d1,d2推广到加的前缀和加的后缀，而不是单单一个十进制数字d，是因为lazy的懒惰性（叠加性），必然会使得这个d越来越长。故我们直接推广到d1,d2。

接下来代码方面就不难了。

/*
* @Author: Marhoosh
* @Date:   2021-07-22 10:27:33
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-11-05 17:13:51
*/
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define lson l,m,now<<1
#define rson m+1,r,now<<1|1
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=4e5+11;
const ll mod=1e9+7;
ll sum1[maxn],sum2[maxn],lazy1[maxn],lazy2[maxn],lazylen[maxn];
ll f[maxn];
ll n,m;
void init(){
    f[0]=1;
    for(ll i=1;i<maxn;i++)  f[i]=f[i-1]*10%mod;
}
void push_down(ll l,ll r,ll now){
    if(lazylen[now]){
        ll m=(l+r)>>1;
        ll len=lazylen[now],x=lazy1[now],y=lazy2[now];
        sum1[now<<1]=(sum1[now<<1]*f[len]+y*(m-l+1)+x*sum2[now<<1]%mod*f[len])%mod;
        sum1[now<<1|1]=(sum1[now<<1|1]*f[len]+y*(r-m)+x*sum2[now<<1|1]%mod*f[len])%mod;
        sum2[now<<1]=sum2[now<<1]*f[2*len]%mod;
        sum2[now<<1|1]=sum2[now<<1|1]*f[2*len]%mod;
        lazy1[now<<1]=(lazy1[now<<1]+lazy1[now]*f[lazylen[now<<1]])%mod;
        lazy1[now<<1|1]=(lazy1[now<<1|1]+lazy1[now]*f[lazylen[now<<1|1]])%mod;
        lazy2[now<<1]=(lazy2[now<<1]*f[len]+lazy2[now])%mod;
        lazy2[now<<1|1]=(lazy2[now<<1|1]*f[len]+lazy2[now])%mod;
        lazylen[now<<1]+=lazylen[now];
        lazylen[now<<1|1]+=lazylen[now];
        lazylen[now]=0,lazy1[now]=0,lazy2[now]=0;
    }
}
void push_up(ll now){
    sum1[now]=(sum1[now<<1]+sum1[now<<1|1])%mod;
    sum2[now]=(sum2[now<<1]+sum2[now<<1|1])%mod;
}
void build(ll l,ll r,ll now){
    lazy1[now]=lazy2[now]=lazylen[now]=0;
    if(l==r){
        sum1[now]=0;sum2[now]=1;
        return ;
    }
    ll m=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(now);
}
void update(ll L,ll R,ll d,ll l,ll r,ll now){
    if(L<=l && r<=R){
        sum1[now]=(sum1[now]*f[1]+d*(r-l+1)+d*sum2[now]*f[1])%mod;
        sum2[now]=sum2[now]*f[2]%mod;
        lazy1[now]=(lazy1[now]+d*f[lazylen[now]])%mod;
        lazy2[now]=(lazy2[now]*f[1]+d)%mod;
        lazylen[now]+=1;
        return ;
    }
    ll m=(l+r)>>1;
    push_down(l,r,now);
    if(L<=m)  update(L,R,d,lson);
    if(R>m)  update(L,R,d,rson);
    push_up(now);
}
ll query(ll L,ll R,ll l,ll r,ll now){
    if(L<=l && r<=R)  return  sum1[now];
    ll sum=0;
    ll m=(l+r)>>1;
    push_down(l,r,now);
    if(L<=m)  sum+=query(L,R,lson);
    if(R>m)  sum+=query(L,R,rson);
    return sum%mod;
}
void check(ll l,ll r,ll now){
    cout<<l<<" "<<r<<" "<<sum1[now]<<endl;
    if(l==r){
        return ;
    }
    ll m=(l+r)/2;
    check(lson);
    check(rson);
}
int main(){
    init();
    ll ca;scanf("%lld",&ca);
    ll cas=1;
    while(ca--){
        cout<<"Case "<<cas++<<":"<<endl;
        scanf("%lld%lld",&n,&m);
        build(1,n,1);
        for(ll i=1;i<=m;i++){
            char s[11];scanf("%s",s);
            if(s[0]=='w'){
                ll l,r,d;scanf("%lld%lld%lld",&l,&r,&d);
                update(l,r,d,1,n,1);
            }
            else{
                ll l,r;scanf("%lld%lld",&l,&r);
                printf("%lld\n",query(l,r,1,n,1));
            }
            // Debug(i);
            // check(1,n,1);
            // cout<<endl;
        }
    }
    return 0;
}