Skip to content

线段树

1) 线段树中的优先级： 乘法大于加法(P3373模板),推平大于加法,注意维护两个\(lazytag\)

2) 线段树最重要的是叶节点，有时父节点可以为0,只有叶节点有值，如果有操作将父节点的值分裂，就传递给叶节点。这不是传统线段树，而是利用了线段树的结构，因此注意线段树的灵活性。(P1558)

SP2713 GGS4

这道题用了一个\(_{小技巧}\)

因为数据范围是1e18，最多六次就会得到1,而1和0开平方后还是自身，所以只需要对不等于一的数暴力修改，若区间和小于等于区间长度，则只剩1或0，不需再修改。总的修改次数\(\Theta(6nlogn)\),又因为每次都要查询，用于判断或输出答案，所以\(\Theta(nlogn)\)

总复杂度\(\Theta(6nlogn)\)

P1856 & P5490

扫描线(离散化+线段树）

将每个矩形都离散成边，在加入线段树中。

统计的方式：

用cover和len数组分别记录该区间被覆盖的次数和被覆盖的长度。

如果cover>0，说明至少被全覆盖了一次，len=r-l+1

如果cover==0，说明没有全覆盖，可能是连续的区间。所以继承子节点的信息，直接pushup。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
//#define int long long 
using namespace std;
const int N=2e5+10,INF=1e4;
struct node{
    int i,j,x,y;
}q[N];
struct edge{
    int l;
    int r;
    int z;
    int t;
}e[N];
struct tree{
    int len,cover;
}tre[N];
int n,ans;
bool cmp1(edge a,edge b){
    if(a.z==b.z)return a.t>b.t;
    else return a.z<b.z;
}
bool cmp2(edge a,edge b){
    if(a.z==b.z)return a.t>b.t;
    else a.z>b.z;
}
void pushup(int i,int l,int r){
    if(tre[i].cover>0){
        tre[i].len=r-l+1;
    }else{
        tre[i].len=tre[i<<1].len+tre[i<<1|1].len;
    }
}
void change(int i,int l,int r,int el,int er,int k){
    if(el<=l && r<=er){
        tre[i].cover+=k;
        if(tre[i].cover>0){
            tre[i].len=r-l+1;
        }else{
            tre[i].len=tre[i<<1].len+tre[i<<1|1].len;
        }
        return;
    }
    int mid=l+r>>1;
    if(el<=mid)change(i<<1,l,mid,el,er,k);
    if(er>mid)change(i<<1|1,mid+1,r,el,er,k);
    pushup(i,l,r);
    return;
}

void ins(int i,int l,int r,int el,int er){
    if(el<=l && r<=er){
        tre[i].cover++;
        tre[i].len=r-l+1;
        return;
    }
    //if(l+1==r)return;
    int mid=l+r>>1;
    if(el<=mid)ins(i<<1,l,mid,el,er);
    if(er>mid)ins(i<<1|1,mid+1,r,el,er);
    pushup(i,l,r);
    return;
}
void del(int i,int l,int r,int el,int er){
    if(el<=l && r<=er){
        tre[i].cover--;
        if(tre[i].cover>0)tre[i].len=r-l+1;
        else tre[i].len=tre[i<<1].len+tre[i<<1|1].len;
        return;
    }
    //if(l+1==r)return;
    int mid=l+r>>1;
    if(el<=mid)del(i<<1,l,mid,el,er);
    if(er>mid)del(i<<1|1,mid+1,r,el,er);
    pushup(i,l,r);
    return;
}
int abs1(int a){
    return a>0?a:-a;
}
void build(int i,int l,int r){
    if(l==r){
        tre[i].len=0;
        tre[i].cover=0;
        return;
    }
    int mid=l+r>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    //pushup(i,l,r);
    tre[i].len=0;
    tre[i].cover=0;
    return;
}
void work3(){
    int cnt=0;
    for(int i=1;i<=n;++i){
        e[++cnt].l=q[i].i;
        e[cnt].r=q[i].x;
        e[cnt].z=q[i].j;
        e[cnt].t=1;
        e[++cnt].l=q[i].i;
        e[cnt].r=q[i].x;
        e[cnt].z=q[i].y;
        e[cnt].t=-1;
    }
    sort(e+1,e+cnt+1,cmp1);
    build(1,-INF,INF);
    for(int i=1;i<=cnt;++i){
        int l=e[i].l,r=e[i].r,t=e[i].t;
        int lst=tre[1].len;
        change(1,-INF,INF,l,r-1,t);
        ans+=abs1(lst-tre[1].len);
    }
    //cout<<ans<<endl;
    return;
}
void work4(){
    int cnt=0;
    for(int i=1;i<=n;++i){
        e[++cnt].l=q[i].j;
        e[cnt].r=q[i].y;
        e[cnt].z=q[i].i;
        e[cnt].t=1;
        e[++cnt].l=q[i].j;
        e[cnt].r=q[i].y;
        e[cnt].z=q[i].x;
        e[cnt].t=-1;
    }
    sort(e+1,e+cnt+1,cmp1);
    //memset(tre,0,sizeof tre);
    build(1,-INF,INF);
    for(int i=1;i<=cnt;++i){
        int l=e[i].l,r=e[i].r,t=e[i].t;
        int lst=tre[1].len;
        change(1,-INF,INF,l,r-1,t);     
        ans+=abs1(lst-tre[1].len);
    }

    return;
}
void work1(){
    int cnt=0;
    for(int i=1;i<=n;++i){
        e[++cnt].l=q[i].i;
        e[cnt].r=q[i].x;
        e[cnt].z=q[i].j;
        e[cnt].t=1;
        e[++cnt].l=q[i].i;
        e[cnt].r=q[i].x;
        e[cnt].z=q[i].y;
        e[cnt].t=-1;
    }
    sort(e+1,e+cnt+1,cmp1);
    build(1,-INF,INF);
    for(int i=1;i<=cnt;++i){
        int l=e[i].l,r=e[i].r,t=e[i].t;
        int lst=tre[1].len;
        if(t==1) ins(1,-INF,INF,l,r-1);
        else del(1,-INF,INF,l,r-1);//cout<<lst<<" "<<tre[1].len<<endl;
        ans+=abs1(lst-tre[1].len);
    }
    //cout<<ans<<endl;
    return;
}
void work2(){
    int cnt=0;
    for(int i=1;i<=n;++i){
        e[++cnt].l=q[i].j;
        e[cnt].r=q[i].y;
        e[cnt].z=q[i].i;
        e[cnt].t=1;
        e[++cnt].l=q[i].j;
        e[cnt].r=q[i].y;
        e[cnt].z=q[i].x;
        e[cnt].t=-1;
    }
    sort(e+1,e+cnt+1,cmp1);
    //memset(tre,0,sizeof tre);
    build(1,-INF,INF);
    for(int i=1;i<=cnt;++i){
        int l=e[i].l,r=e[i].r,t=e[i].t;
        int lst=tre[1].len;
        if(t==1) ins(1,-INF,INF,l,r-1);
        else del(1,-INF,INF,l,r-1);

        ans+=abs1(lst-tre[1].len);
    }

    return;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d%d%d",&q[i].i,&q[i].j,&q[i].x,&q[i].y);
    }
    ans=0;
    work3();
    work4();
    printf("%d",ans);
    return 0;
}
/*
2 
0 0 4 4
0 4 4 8

*/
  • 线段树的特点：只有用当前区间时才用pushdown计算值,保证\(O(nlogn)\)；当前区间一定只包含小区间和自己，不会有某个区间的一部分。

SP1043 GSS1

线段树。

用结构体tre作为节点维护四个值：

区间和 s，区间最大子段和 t，区间从左端点开始的最大前缀和 l，区间从右端点开始的最大后缀和 r。

    1. 如何合并两个小区间 ls , rs，得到大区间 i 的子段和？

考虑子段和的最大值从何而来：

1）由两个小区间自身内部产生，那么答案就是max(tre[ls].t , tre[rs].t)

2)由两个小区间合并得出，则用到的就是左区间的后缀和加有区间的前缀和，合并出覆盖两个小区间的大区间。欲使其值最大，则取最大前缀后缀和tre[ls].r + tre[rs].l。

因此

tre[i].t=max(max(tre[i<<1].t,tre[i<<1|1].t),tre[i<<1].r+tre[i<<1|1].l);
这里ls=i<<1 ,rs=i<<1|1.
  • 2.如何维护当前节点的最大前缀，后缀和？

当前大区间的前缀和是长短两种情况取max，即左边小区间的最大前缀和的值，和覆盖整个左边小区间和右边小区间的最大前缀和的值 取max。

后缀和同理。

tre[i].l=max(tre[i<<1].l,tre[i<<1].s+tre[i<<1|1].l);

tre[i].r=max(tre[i<<1|1].r,tre[i<<1|1].s+tre[i<<1].r);
最后区间和就是左右区间相加。

不需要修改，只用查询。

具体的看注释和代码吧QwQ

Code Time： 

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
const int N=1e5+10,INF=15007+5;
struct node{
    int l,r,t,s;
    node(){//初始化，防止随机数据造成干扰
        l=-INF,r=-INF,t=-INF,s=-INF;
    }
}tre[N<<2];//别问我为什么先开两倍空间再乘4
int n,m,l,r;
int a[N];
void pushup(int i){
    tre[i].t=max(max(tre[i<<1].t,tre[i<<1|1].t),tre[i<<1].r+tre[i<<1|1].l);
    tre[i].l=max(tre[i<<1].l,tre[i<<1].s+tre[i<<1|1].l);
    tre[i].r=max(tre[i<<1|1].r,tre[i<<1|1].s+tre[i<<1].r);
    tre[i].s=tre[i<<1].s+tre[i<<1|1].s;
    return;
}
void build(int i,int l,int r){//建树
    if(l==r){
        tre[i].t=a[l];
        tre[i].l=a[l];
        tre[i].r=a[l];
        tre[i].s=a[l];
        return;
    }
    int mid=l+r>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    pushup(i);
    return;
}
node query(int i,int l,int r,int el,int er){
    if(el<=l && r<=er){
        return tre[i];
    }
    int mid=l+r>>1;
    node ans=node(),x=node(),y=node();
    if(el<=mid)x=query(i<<1,l,mid,el,er);
    if(er>mid)y=query(i<<1|1,mid+1,r,el,er);

    ans.t=max(max(x.t,y.t),x.r+y.l);//pushup
    ans.l=max(x.l,x.s+y.l);
    ans.r=max(y.r,y.s+x.r);
    ans.s=x.s+y.s;

    return ans;
}
signed main(){
    memset(tre,0,sizeof tre);
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);    
    }
    build(1,1,n);
    scanf("%lld",&m);
    for(int i=1;i<=m;++i){
        scanf("%lld%lld",&l,&r);
        node res=node();
        res=query(1,1,n,l,r);
        printf("%lld\n",res.t);
    }
    return 0;
} 
/*

数据

>>>input
8
-1 2 3 1 -1 1 1 -1
4
1 8
2 7
4 5
3 4
>>>output
7
7
1
4
*/
Orz

CF833B

设\(f[i][j]\)表示前\(i\)个颜色分成\(j\)端的最大贡献，\(col[i][j]\)表示从\(i\)到\(j\)的贡献。

则转移方程：

\[ f[i][j]=\max_{k=0}^{i-1}(f[k][j-1]+col[k+1][i]) \]

这样做复杂度\(O(n^2k)\),肯定爆炸。

由于每次需要枚举\(k\)而耽误时间，所以考虑把上一轮所有的\(f[k][j-1]\)丢进线段树里维护。

用到了去重的常用$_ {trick} $,就是将每个颜色上一次出现的位置记录下来。之后，用线段树的区间加来更新当前的颜色对之前哪些位置由贡献。

线段树中位置\(k\)维护的就是从\(k\)到\(i\)的贡献\(col[k][i]\)加上\(f[k-1][j-1]\)的总贡献。

这样每次只需要取\(query(1,1,n,1,j)\)即可更新\(f[i][j]\).

~~注意线段树的清零操作(lazytag)，我已经被坑的见祖宗了,见注释~~

code time:

#include<iostream>
#include<cstdio>
#include<cstring>
#define ls i<<1
#define rs i<<1|1
#define int long long 
using namespace std;
const int N=4e4+10,K=55;
int f[K][N],pos[N],pre[N],tre[N<<2],tag[N<<2];
int n,k,t;
void pushup(int i){
    tre[i]=max(tre[ls],tre[rs]);
}
void pushdown(int i,int l,int r){
    int k=tag[i];
    if(!k)return;
    tag[ls]+=k;tag[rs]+=k;tre[ls]+=k;tre[rs]+=k;
    tag[i]=0;   
}
void build(int i,int l,int r,int now){
    tag[i]=0;//一定要清零，并且要写在外面
    if(l==r){
        tre[i]=f[now][l-1];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid,now);
    build(rs,mid+1,r,now);
    pushup(i);
}
void change(int i,int l,int r,int el,int er,int k){
    if(el<=l && r<=er){
        tag[i]+=k;tre[i]+=k;
        return;
    }
    pushdown(i,l,r);
    int mid=(l+r)>>1;
    if(el<=mid) change(ls,l,mid,el,er,k);
    if(er>mid) change(rs,mid+1,r,el,er,k);
    pushup(i);
}
int query(int i,int l,int r,int el,int er){
    if(el<=l && r<=er) return tre[i];
    pushdown(i,l,r);
    int mid=(l+r)>>1,ans=0;
    if(el<=mid)ans=max(ans,query(ls,l,mid,el,er));
    if(er>mid)ans=max(ans,query(rs,mid+1,r,el,er));
    return ans;
}
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;++i)scanf("%lld",&t),pre[i]=pos[t]+1,pos[t]=i;
    for(int i=1;i<=k;++i){
        build(1,1,n,i-1);
        for(int j=1;j<=n;++j){
            change(1,1,n,pre[j],j,1);
            f[i][j]=query(1,1,n,1,j);
        }
    }
    printf("%lld",f[k][n]);
}

SP1557 GSS2

~~OrzOrzOrz~~

好题，是GSS1的超级加强。

对于区间去重可以离线将r排序，逐个加入a[i]，计算当前以r为右端点的所有子区间中的最大和，那么它就是最大子段和。

对于每个节点维护四个值：

s 表示当前点的最大子段和

m 表示当前点历史最大

stag 表示当前懒标记

mtag 表示历史最大懒标记

mtag存在的意义： stag在同时遇到许多操作时会将所有操作覆盖成一个操作，而历史最大需要stag中的最大状态，这只用stag表示不出来，所以用一个mtag.

这样，每次查询[l,r]的tre[i].m即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long 
using namespace std;
const int N=2e5+10;
struct node{
    int m,s,mtag,stag;
}tre[N<<2];
struct que{
    int l,r,id;
}q[N];
int n,m;
int pre[N],vis[N<<1],a[N],ans[N];
bool cmp(que a,que b){
    return a.r<b.r;
}
void pushup(int i){
    tre[i].s=max(tre[i<<1].s,tre[i<<1|1].s);
    tre[i].m=max(tre[i<<1].m,tre[i<<1|1].m);
}
void pushdown(int i,int l,int r){

    int ls=i<<1,rs=i<<1|1,mid=l+r>>1;

    tre[ls].m=max(tre[ls].m,tre[ls].s+tre[i].mtag);
    tre[rs].m=max(tre[rs].m,tre[rs].s+tre[i].mtag);

    tre[ls].s+=tre[i].stag;
    tre[rs].s+=tre[i].stag;

    tre[ls].mtag=max(tre[ls].mtag,tre[i].mtag+tre[ls].stag);
    tre[rs].mtag=max(tre[rs].mtag,tre[i].mtag+tre[rs].stag);

    tre[ls].stag+=tre[i].stag;
    tre[rs].stag+=tre[i].stag;

    tre[i].stag=0;
    tre[i].mtag=0;

    return;
}
void add(int i,int l,int r,int el,int er,int k){
    if(el<=l && r<=er){
        tre[i].s+=k;
        tre[i].m=max(tre[i].m,tre[i].s);
        tre[i].stag+=k;
        tre[i].mtag=max(tre[i].mtag,tre[i].stag);
        return;
    }
    pushdown(i,l,r);
    int mid=l+r>>1;
    if(el<=mid)add(i<<1,l,mid,el,er,k);
    if(er>mid)add(i<<1|1,mid+1,r,el,er,k);
    pushup(i);
    return;
}
int query(int i,int l,int r,int el,int er){
    if(el<=l && r<=er){
        return tre[i].m;
    }
    pushdown(i,l,r);
    int mid=l+r>>1,ans=0;
    if(el<=mid)ans=max(ans,query(i<<1,l,mid,el,er));
    if(er>mid)ans=max(ans,query(i<<1|1,mid+1,r,el,er));
    return ans;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
    scanf("%lld",&m);
    for(int i=1;i<=m;++i){
        scanf("%lld%lld",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    for(int i=1;i<=n;++i){
        pre[i]=vis[a[i]+N];
        vis[a[i]+N]=i;
    }
    /*for(int i=1;i<=n;++i){
        cout<<pre[i]<<" ";
    }
    cout<<endl;*/

    for(int i=1,j=1;i<=n;++i){
        int ll=pre[i]+1,rr=i;
        add(1,1,n,ll,rr,a[i]);
        for(j;j<=m && q[j].r<=i;++j){
            ans[q[j].id]=query(1,1,n,q[j].l,q[j].r);
        }
    }
    for(int i=1;i<=m;++i){
        printf("%lld\n",ans[i]);
    }
    return 0;
} 
/*
8
-1 2 3 1 -1 1 1 -1
3
1 2
2 4
1 8
*/
注意下面没有mtag的错误代码: 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long 
using namespace std;
const int N=2e5+10;
struct node{
    int m,s,stag;
}tre[N<<2];
struct que{
    int l,r,id;
}q[N];
int n,m;
int pre[N],vis[N<<1],a[N],ans[N];
bool cmp(que a,que b){
    return a.r<b.r;
}
void pushup(int i){
    tre[i].s=max(tre[i<<1].s,tre[i<<1|1].s);
    tre[i].m=max(tre[i<<1].m,tre[i<<1|1].m);
    tre[i].m=max(tre[i].m,tre[i].s);//
}
void pushdown(int i,int l,int r){

    int ls=i<<1,rs=i<<1|1,mid=l+r>>1;

    tre[ls].m=max(tre[ls].m,tre[ls].s+tre[i].stag);
    tre[rs].m=max(tre[rs].m,tre[rs].s+tre[i].stag);

    tre[ls].s+=tre[i].stag;
    tre[rs].s+=tre[i].stag;

    tre[ls].stag+=tre[i].stag;
    tre[rs].stag+=tre[i].stag;

    tre[i].stag=0;

    return;
}
void add(int i,int l,int r,int el,int er,int k){
    if(el<=l && r<=er){
        tre[i].s+=k;
        tre[i].stag+=k;
        tre[i].m=max(tre[i].m,tre[i].s);
        return;
    }
    pushdown(i,l,r);
    int mid=l+r>>1;
    if(el<=mid)add(i<<1,l,mid,el,er,k);
    if(er>mid)add(i<<1|1,mid+1,r,el,er,k);
    pushup(i);
    return;
}
int query(int i,int l,int r,int el,int er){
    if(el<=l && r<=er){
        return tre[i].m;
    }
    pushdown(i,l,r);
    int mid=l+r>>1,ans=0;
    if(el<=mid)ans=max(ans,query(i<<1,l,mid,el,er));
    if(er>mid)ans=max(ans,query(i<<1|1,mid+1,r,el,er));
    return ans;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
    scanf("%lld",&m);
    for(int i=1;i<=m;++i){
        scanf("%lld%lld",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    for(int i=1;i<=n;++i){
        pre[i]=vis[a[i]+N];
        vis[a[i]+N]=i;
    }
    /*for(int i=1;i<=n;++i){
        cout<<pre[i]<<" ";
    }
    cout<<endl;*/

    for(int i=1,j=1;i<=n;++i){
        int ll=pre[i]+1,rr=i;
        add(1,1,n,ll,rr,a[i]);
        for(j;j<=m && q[j].r<=i;++j){
            ans[q[j].id]=query(1,1,n,q[j].l,q[j].r);
        }
    }
    for(int i=1;i<=m;++i){
        printf("%lld\n",ans[i]);
    }
    return 0;
} 
/*
9
4 -2 -2 3 -1 -4 2 2 -6
4
1 2
1 5
4 9
2 8
*/

P3924

这道题的关键就是，对于每次修改，有效产生贡献的只有叶子节点，所以直接通过深度维护每个叶子节点到根上的概率总和，因为每次修改的数相同，所以直接前缀和累加。开始O（n）求出初始值，每次再加。

P4588

对于每次操作，如果直接逆元肯定不行。

考虑线段树，每次的操作就是单点修改。

注意\(pushup\)一直要\(modM\) 

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
#define ls i<<1
#define rs i<<1|1
using namespace std;
const int N=2e5+10;
int tre[N<<2];
int Q,t,M,op,m;
void pushup(int i){
    tre[i]=(tre[ls]*tre[rs])%M;
}
void build(int i,int l,int r){
    if(l==r){
        tre[i]=1;
        return;
    }
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(i);
}
void change(int i,int l,int r,int pos,int k){
    if(l==r){
        tre[i]=k;
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid)change(ls,l,mid,pos,k);
    else change(rs,mid+1,r,pos,k);
    pushup(i);
}
signed main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&Q,&M);
        build(1,1,Q);
        for(int i=1;i<=Q;++i){
            scanf("%lld%lld",&op,&m);
            if(op==1){
                change(1,1,Q,i,m);
            }else{
                change(1,1,Q,m,1);
            }
            printf("%lld\n",tre[1]%M);
        }
    }
    return 0;
}
~~线段树思维题真多~~

P1712

尺取法线段树。

先将区间从小到大排序，依次右移\(r\).

对于每个区间，用线段树维护当前的区间有哪些重合的地方，如果有一个点重合度\(\geq m\),就右移\(l\)并统计答案。

CF1042D

维护每个端点\(i\)前面有多少个端点\(j\)满足\(sum[i]-sum[j-1]<t\)。

因为每次做完都会加入\(sum[i]\)，所以保证\(sum[j-1],1 \leq j \leq i-1 \(在之前已经求出来了，因此可以权值树状数组维护之前满足条件的端点个数,即\)>sum[i]-t\)的个数。

P5482

细节特多的一道题。

注意每个等式的\(a\)有三种情况：

1) \(a>0\),此时正常讨论 2) \(a=0\),需要特殊讨论，不能除，不然就\(RE\)了. 3) \(a<0\),这是需要将等式反转：\(-x>-\frac{c-b}{a}\),所以新的解\(t=-x\),满足\(-at+b>c\)

还有就是需要判断\(x\)和\(t\)的出界情况，如果小于\(-1e6\)，就在树状数组\(1\)的位置加\(1\);如果大于\(1e6\),就不能做任何处理。

再有就是重复删除，每次删除后要打上标记。

~~坑爹毒瘤题~~

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
#define lowbit(x) x&-x
using namespace std;
const int N=2e6+100,M=2e5+10,C=1e6+1,LIM=2e6+1;
struct node{
    int a,b,k,type,res;
}op[M];
int c[N],d[N];
int n,cnt,a,b,k;
char ch[10];
void change1(int x,int k) {
    while(x<=N-1) {
        c[x]+=k;
        x+=lowbit(x);
    }
}
int sum1(int x) {
    int ans=0;
    while(x>0) {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
void change2(int x,int k){
    while(x<=N-1){
        d[x]+=k;
        x+=lowbit(x);
    }
}
int sum2(int x){
    int ans=0;
    while(x>0){
        ans+=d[x];
        x-=lowbit(x);
    }
    return ans;
}
signed main() {
    scanf("%lld",&n);
    for(int i=1; i<=n; ++i) {
        scanf("%s",ch);
        if(ch[0]=='A') {
            ++cnt;
            scanf("%lld%lld%lld",&op[cnt].a,&op[cnt].b,&op[cnt].k);
            a=op[cnt].a,b=op[cnt].b,k=op[cnt].k;
            if(a==0){
                if(b>k){
                    op[cnt].type=0,change1(1,1);// 一定有解
                }else{
                    op[cnt].type=1;//无解
                }
            }else if(a>0){
                int tmp=(k-b)/a;
                if(a*tmp+b<=k)tmp++;
                if(tmp+C<1)op[cnt].type=2,change1(1,1);//一定有解
                else if(tmp+C>LIM)op[cnt].type=3;//一定无解
                else op[cnt].res=tmp+C,op[cnt].type=4,change1(tmp+C,1);
            }else{//a<0
                int tmp=(b-k)/a;
                if(-a*tmp+b<=k)tmp++;
                if(tmp+C<1)op[cnt].type=5,change2(1,1);
                else if(tmp+C>LIM)op[cnt].type=6;
                else op[cnt].res=tmp+C,op[cnt].type=7,change2(tmp+C,1);
            }
        }else if(ch[0]=='D'){
            scanf("%lld",&k);
            if(op[k].type==0 || op[k].type==2)change1(1,-1);
            if(op[k].type==5)change2(1,-1);
            if(op[k].type==4)change1(op[k].res,-1);
            if(op[k].type==7)change2(op[k].res,-1);
            op[k].type=8;//已删除
        }else{
            scanf("%lld",&k);
            int tmp1=sum1(k+C);
            int tmp2=sum2(-k+C);
            printf("%lld\n",tmp1+tmp2);
        }
    }
    return 0;
}

P4243

第一道黑题!

~~虽然只有紫题的难度~~

当看见等差数列，有个常用的小\(_ {Trick}\),就是将等差数列转换成差分数列，即\(b[i]=a[i+1]-a[i]\)，这样，只需要维护连续的相同的值有多少段即可。

每次的\(A\)操作可以看成在\(s-1\)处加上\(a\),在\([s,t-1]\)这一段加上\(b\)，再在最后的\(t+1\)处加上\(-a+b*(t-s)\)即可。

而\(B\)操作复杂，需要\(nlrc,lrc,lc,rc\)分别表示\((l,r),[l,r],[l,r),(l,r]\)的四种情况。

此时，看起来好像只需要\(lrc\),合并时判断一下左右端点是否相等就行了啊。

为什么会需要\(lc,rc,nlrc\)呢？

考虑下面这组数据：

s:0 1 2 4 5 7 9
x: 1 1 2 1 2 2
此时，左右区间的\(lrc\)分别是： 

s:[0 1 2 [4] 5 7 9]
x: [1 1 2] [1 2 2]
ans: [2]    [2]
合并：ans=2+2-(2==1)=4
正确答案=3
我们发现，对于\(4\)，它算了两遍。

所以需要这种合并方式：

s:[0 1 2 )[4 5 7 9]
x: [1 1 2) [1 2 2]
ans: [1)    [2]
合并：ans=3，正确

这解释了另外三个值的必要性。

注意，只有\((...[x]...)\)，即两个区间包含原序列的同一个数,这种情况才能将序列合并后判断\(-1\)，即原数列中有一个数在两个公差相等的等差数列中都有，才能合并成一个等差。

对于每个节点，在修改时用\(push_down\)向下修改\(lval\)和\(rval\),再在回溯时用\(pushup\)维护那四个值即可。

因为本体中的结构体不好清零，清零了也不好合并，所以就不保存直接返回即可。

#include<iostream>
#include<cstdio>
#include<cstring>

#define ls i<<1
#define rs i<<1|1

#define int long long 
using namespace std;
const int N=1e5+10;
int n,q,s,t,a,b;
int v[N],w[N];
char chh[200];
struct node{
    int lc,rc,nlrc,lrc,lval,rval;
}tre[N<<2];

int read1(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9' || ch<'0'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch<='9' && ch>='0'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void write1(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write1(x/10);
    putchar(x%10+'0');
    return;
}
node operator +(const node &a,const node &b){//重要的重载运算符
    node c;

    c.lval=a.lval;
    c.rval=b.rval;

    c.nlrc=a.rc+b.lc-(a.rval==b.lval);//将pushup中的内容搬运到这里即可。
    c.nlrc=min(c.nlrc,min(a.nlrc+b.lc,a.rc+b.nlrc));//其实就是三种情况取min

    c.lc=a.lrc+b.lc-(a.rval==b.lval);//注意，只有[]这种情况才能将序列合并后判断-1，即原数列中有一个数在两个公差相等的等差数列中都有。
    c.lc=min(c.lc,min(a.lc+b.lc,a.lrc+b.nlrc));

    c.rc=a.rc+b.lrc-(a.rval==b.lval);
    c.rc=min(c.rc,min(a.rc+b.rc,a.nlrc+b.lrc));

    c.lrc=a.lrc+b.lrc-(a.rval==b.lval);
    c.lrc=min(c.lrc,min(a.lrc+b.rc,a.lc+b.lrc));

    return c;
}
int tag[N<<2];


void pushdown(int i,int l,int r){
    if(!tag[i])return;//注意1:懒标记为空直接跳过。
    int k=tag[i];
    tag[ls]+=k;
    tag[rs]+=k;
    tre[ls].lval+=k;
    tre[ls].rval+=k;
    tre[rs].lval+=k;
    tre[rs].rval+=k;
    tag[i]=0;
    return;
}
void build(int i,int l,int r){
    if(l>=r){//注意2:不要让l>r
        tre[i].lc=tre[i].rc=tre[i].lrc=1;
        tre[i].lval=tre[i].rval=w[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    tre[i]=tre[ls]+tre[rs];
    return;
}
void change(int i,int l,int r,int el,int er,int k){
    if(el<=l && r<=er){
        tre[i].lval+=k;
        tre[i].rval+=k;
        tag[i]+=k;
        return;
    }
    pushdown(i,l,r);
    int mid=(l+r)>>1;
    if(el<=mid)change(ls,l,mid,el,er,k);
    if(er>mid)change(rs,mid+1,r,el,er,k);
    tre[i]=tre[ls]+tre[rs];
    return;
}
node query(int i,int l,int r,int el,int er){
    if(el<=l && r<=er){
        return tre[i];
    }
    pushdown(i,l,r);
    int mid=(l+r)>>1;
    if(er<=mid)return query(ls,l,mid,el,er);//这里这么写只是因为本体中的结构体不好清零，清零了也不好合并，所以就不保存直接返回。
    else if(el>mid)return query(rs,mid+1,r,el,er);//注意3:不用保存直接返回结构体
    else return query(ls,l,mid,el,mid)+query(rs,mid+1,r,mid+1,er);
}

signed main(){
    //freopen("1558/1.in","r",stdin);
    n=read1();
    for(int i=1;i<=n;++i)v[i]=read1();
    for(int i=1;i<n;++i)w[i]=v[i+1]-v[i];
    build(1,1,n-1);
    q=read1();
    for(int i=1;i<=q;++i){
        scanf("%s",chh);
        if(chh[0]=='A'){
            s=read1(),t=read1(),a=read1(),b=read1();
            if(s != 1) change(1, 1, n-1, s-1, s-1, a); //注意4:不要越界
            if(t != n) change(1, 1, n-1, t, t, -(a+b*(t-s))); 
            if(s != t) change(1, 1, n-1, s, t-1, b);
        }else{

            s=read1(),t=read1();
            if(s==t){//注意5:不要越界
                putchar('1');putchar('\n');
            }else write1(query(1,1,n-1,s,t-1).lrc),putchar('\n');
        }
    }


    return 0;
}
  • 注意:本体代码包含了除历史最大值，优先级之外的所有线段树常用的技巧，包括重载运算符，\(lazytag\)，询问时的左右区间分类讨论以及返回结构体等等。

P4064

对于最小值最大化，我们想到二分。

假设当前枚举的答案为\(mid\)，那么对于每个点，必须要加\(\max(\lceil\frac{mid-a_i}{d}\rceil,0)\)次，那么我们可以贪心地按照右端点从远到近地取。

首先要将区间按左端点从小到大排序。

将所有左端点小于\(i\)的区间丢进优先队列里，按上文要求维护右端点。

如果有当前点未满足条件，并且队列为空或当前区间右端点已经小于\(i\)，说明无法满足条件。否则可以满足。

这样二分即得答案。

注意清零。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define int long long 
#define lowbit(x) (x&-x)
using namespace std;
const int N=4e5+10,INF=0x3f3f3f3f;
int a[N],b[N],c[N],vis[N];
int n,m,T,k,d,minn;
struct query {
    int l,r,id;
} f[N];
struct node{
    int num,r;
    node(int numm,int rr){
        num=numm,r=rr;
    }
    bool operator <(const node &x)const{
        return x.r>r;
    }
};
bool cmp(query a,query b) {
    return a.l<b.l;
}
void add(int x,int d) {
    while(x<=n)c[x]+=d,x+=lowbit(x);
}
int sum(int x){
    int ans=0;
    while(x>0)ans+=c[x],x-=lowbit(x);
    return ans;
}
void init(){
    for(int i=1; i<=n; ++i) add(i,b[i]);
}
void clear1() {
    for(int i=1;i<=m;++i){
        if(vis[i]){
            if(f[i].l>0)add(f[i].l,-d);
            if(f[i].r<n)add(f[i].r+1,d);
            vis[i]=0;
        }
    }
}


bool check(int x) {
    priority_queue<node> q;
    int l=1,cnt=0;
    for(int i=1; i<=n; ++i) {
        if(cnt>k)return false;
        while(f[l].l<=i && l<=m)q.push(node(l,f[l].r)),++l;
        int delta=x-sum(i);
        while(delta>0){
            if(q.empty())return false;
            int tmp=q.top().num;q.pop();
            if(f[tmp].r<i)return false;
            if(f[tmp].l>0)add(f[tmp].l,d);
            if(f[tmp].r<n)add(f[tmp].r+1,-d);
            vis[tmp]=1;
            delta-=d;
            ++cnt;
        }
    }
    return cnt<=k;
}
signed main() {
    scanf("%lld",&T);
    while(T--) {
        memset(c,0,sizeof c);
        scanf("%lld%lld%lld%lld",&n,&m,&k,&d);
        minn=INF;a[0]=0;
        for(int i=1; i<=n; ++i)scanf("%lld",&a[i]),minn=min(minn,a[i]);
        for(int i=1; i<=n; ++i)b[i]=a[i]-a[i-1];
        for(int i=1; i<=m; ++i)scanf("%lld%lld",&f[i].l,&f[i].r),f[i].id=i;
        sort(f+1,f+m+1,cmp);
        int l=minn-1,r=minn+k*d+1,ans=0;
        memset(vis,0,sizeof vis);
        init();
        while(l<r) {
            int mid=l+r>>1;
            if(check(mid)) {
                ans=mid;
                l=mid+1;
            } else r=mid;
            clear1();
        }
        printf("%lld\n",ans);
    }
    return 0;
}
  • 树状数组区间修改&单点查询

对于区间修改并且只有单点查询得题目，可以用树状数组维护差分数列。

~~差分真的强~~

对于已有的差分数列，将\(1 \to i\)所有\(c[i]\)加起来，就得到原数列得\(a[i]\)，而将区间\([l,r]\)加上\(d\)就相当于两个单点修改： 

if(l>0)add(l,d);
if(r<n)add(r+1,-d);
  • 逆序对

许多问题，像将不同全排列中相同的数字两两配对，只能交换一个数字和它相邻的数字的最少步数这种问题，就可以转化成逆序对求解。

P1966

首先是一个贪心性质证明：

对于\(a[],b[]\)排序后，一定是一一对应，即\(a[1]\to b[1],a[2]\to b[2],...,a[n]\to b[n]\)

证明：

假设已经对应好前\(n-2\)组，保证答案最小，此时剩余\(a\)组的\(a,b\),\(b\)组的\(c,d\)

x x x x a b
x x x x c d

那么有两种方式：\((a-c)^2+(b-d)^2\)和\((a-d)^2+(b-c)^2\).

假设第一种最优。

则：

\[ -2ac-2bd<-2ad-2bc\\ ac+bd>ad+bc\\ a(c-d)>b(c-d)\\ 当c<d时有:\\a< b \]

证毕。

那么就转化成将\(a[],b[]\)一一对应的问题；

设\(q[a[i]]=b[i]\)，那么答案应满足\(q[a[i]]=a[i]\),即\(q[i]=i\)

所以问题转化成求将\(q\)数组升序排列的最少交换步数，即逆序对数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#define int long long 
#define lowbit(x) (x&-x)
using namespace std;
const int N=2e5+10,P=1e8-3;
struct node{
    int h,id;
}a[N],b[N];
int p[N],c[N];
int n,m; 
bool cmp(node a,node b){
    return a.h<b.h;
}

void add(int x,int d){
    while(x<=n)c[x]+=d,x+=lowbit(x);
}
int sum(int x){
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
signed main(){
    //freopen("P1966_2.in","r",stdin);
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i].h),a[i].id=i;
    for(int i=1;i<=n;++i)scanf("%lld",&b[i].h),b[i].id=i;
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;++i)p[a[i].id]=b[i].id;
    int ans=0;
    for(int i=n;i>=1;--i){
        ans=(ans+sum(p[i]))%P;
        add(p[i],1);
    }
    printf("%lld",(ans+P)%P);

    return 0;
}

P6186

假设每个数前面比他大的数的个数为\(b[i]\)

需要注意到\(k\)轮冒泡排序的特性是，对于\(b[i]>k\)的情况，全部\(-k\),否则就变为\(0\).

因为每一轮中，每个数之前的最大数\(x\)一定会被移动到比\(x\)大的第一个数\(y\)之前，即这个数之后。

所以所有较小数的\(b[i]\)都会因为有一个最大数移动到所有小数的后面而\(-1\).

而每次移动的最大数一定满足\(b[i]=0\),移动后也不会改变，所以假设每轮的最大数有\(p\)个，每轮冒泡排序的贡献就是\(n-p\).

所以最终答案为： $$\sum_{b[i]>k}(b[i]-k) \=(\sum_{b[i]>k}b[i])-\sum_{b[i]>k}k $$

所以用一个树状数组维护所有\(b[i]\)为\(j\)的数的贡献,询问出\(t_1=sum(n)-sum(k)\)；

一个树状数组维护所有\(b[i]\)为\(j\)的数的个数，询问出\(t_2=sum(n)-sum(k)\)；

最后询问的答案为\(t_2-k* t_1\)

#include<iostream>
#include<cstdio>
#include<cstring>
#define lowbit(x) (x&-x)
#define int long long
using namespace std;
const int N=3e5+10;
int n,m,tmp,t,k;
int a[N],b[N],c[N],d[N];
void add(int* C,int x,int d) {
    if(x==0)return;
    while(x<=n)C[x]+=d,x+=lowbit(x);
}
int sum(int* C,int x) {
    int ans=0;
    while(x>0)ans+=C[x],x-=lowbit(x);
    return ans;
}
signed main() {
    scanf("%lld%lld",&n,&m);
    for(int i=1; i<=n; ++i)scanf("%lld",&a[i]);
    for(int i=1;i<=n;++i) {
        b[i]=i-1-sum(c,a[i]);
        add(c,a[i],1);
    }
    memset(c,0,sizeof c);
    for(int i=1; i<=n; ++i)add(c,b[i],1),add(d,b[i],b[i]);
    for(int i=1; i<=m; ++i) {
        scanf("%lld%lld",&t,&k);
        if(t==1) {
            add(c,b[k],-1),add(d,b[k],-b[k]);add(c,b[k+1],-1),add(d,b[k+1],-b[k+1]);
            if(a[k]<a[k+1])++b[k];else --b[k+1];
            swap(b[k],b[k+1]),swap(a[k],a[k+1]);
            add(c,b[k],1),add(d,b[k],b[k]);add(c,b[k+1],1),add(d,b[k+1],b[k+1]);
        } else {
            if(k>=n) {
                printf("0\n");
                continue;
            }
            int t1=sum(c,n)-sum(c,k),t2=sum(d,n)-sum(d,k);
            printf("%lld\n",t2-k*t1);
        }
    }
    return 0;
}

P1442

很好的线段树+dp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mid ((l+r)>>1)
#define ls i<<1
#define rs i<<1|1
using namespace std;
const int N=2e5+10;
struct plane {
    int l,r,h,kl,kr;
} q[N];
int n,h,x,y,cnt,num,m;
int a[N],tre[N<<2],tag[N<<2],nxtl[N],nxtr[N],f[N][2];
bool cmp(int a,int b) {
    return a<b;
}
bool Cmp(plane a,plane b) {
    return a.h<b.h;
}
void lsh() {
    sort(a+1,a+cnt+1,cmp);
    int tot=unique(a+1,a+cnt+1)-a-1;
    for(int i=1; i<=n+1; ++i) q[i].l=lower_bound(a+1,a+tot+1,q[i].l)-a,q[i].r=lower_bound(a+1,a+tot+1,q[i].r)-a;
    x=q[1].l;
}
void pushup(int i) {
    tre[i]=tre[ls]+tre[rs];
}
void pushdown(int i,int l,int r) {
    int k=tag[i];
    if(!k)return;
    tag[ls]=k;
    tag[rs]=k;
    tre[ls]=(mid-l+1)*k;
    tre[rs]=(r-mid)*k;
    tag[i]=0;
}
void change(int i,int l,int r,int el,int er,int k) {
    if(el<=l && r<=er) {
        tag[i]=k;
        tre[i]=(r-l+1)*k;
        return;
    }
    pushdown(i,l,r);
    if(el<=mid)change(ls,l,mid,el,er,k);
    if(er> mid)change(rs,mid+1,r,el,er,k);
    pushup(i);
}
int query(int i,int l,int r,int pos) {
    if(l==r) return tre[i];
    pushdown(i,l,r);
    if(pos<=mid)return query(ls,l,mid,pos);
    else return query(rs,mid+1,r,pos);
}
int main() {
    scanf("%d%d%d%d",&n,&h,&x,&y);
    cnt=0;
    q[1].l=q[1].r=q[1].kl=q[1].kr=x,q[1].h=y;
    a[++cnt]=x;
    for(int i=2; i<=n+1; ++i)scanf("%d%d%d",&q[i].h,&q[i].l,&q[i].r),a[++cnt]=q[i].kl=q[i].l,a[++cnt]=q[i].kr=q[i].r;
    lsh();
    sort(q+1,q+n+2,Cmp);
    num=1;
    while((q[num].l!=x || q[num].h!=y) && num<n+1) ++num;
    m=n+n+2;
    for(int i=1; i<=n+1; ++i) {
        int L=query(1,1,m,q[i].l),R=query(1,1,m,q[i].r);
        if(q[i].h-q[L].h>h)nxtl[i]=-1;
        else nxtl[i]=L;
        if(q[i].h-q[R].h>h)nxtr[i]=-1;
        else nxtr[i]=R;
        if(q[i].l+1<=q[i].r-1)change(1,1,m,q[i].l+1,q[i].r-1,i);
    }
    memset(f,0x3f,sizeof f);
    f[0][0]=f[0][1]=0;
    for(int i=1; i<=n+1; ++i) {
        if(nxtl[i]!=-1) {
            if(nxtl[i]==0) f[i][0]=q[i].h;
            else f[i][0]=min(f[nxtl[i]][0]+(q[i].kl-q[nxtl[i]].kl),f[nxtl[i]][1]+(q[nxtl[i]].kr-q[i].kl))+q[i].h-q[nxtl[i]].h;
        }
        if(nxtr[i]!=-1) {
            if(nxtr[i]==0) f[i][1]=q[i].h;
            else f[i][1]=min(f[nxtr[i]][0]+(q[i].kr-q[nxtr[i]].kl),f[nxtr[i]][1]+(q[nxtr[i]].kr-q[i].kr))+q[i].h-q[nxtr[i]].h;
        }
    }
    printf("%d",f[num][0]);
    return 0;
}

P2221

对于每个询问，令\(r=r-1\),答案都是: $$ans=\sum_{i=l}^ra[i]* (r-i+1)(i-l+1)\展开得\ ans=-\sum_{i=l}^ra[i]i^2+(r+l)\sum_{i=l}^ra[i]i+(-rl+r-l+1)\sum_{i=l}^ra[i]\ =-s_3+(r+l)s_2+(-rl+r-l+1)s_1 $$

那么\(s_1,s_2,s_3\)都可以用线段树维护。

对于修改，\(s_1\)直接加上区间长乘\(v\),\(s_2,s_3\)需要用前缀和求出\(i\)和\(i^2\)的和，在乘以\(v\)即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#define mid ((l+r)>>1)
#define ls (i<<1)
#define rs (i<<1|1)
#define int long long 
using namespace std;
const int N=2e5+10;
int n,m,L,R,v,ans,res,a;
int s4[N],s5[N];
struct tree{
    int l,r,tag,s1,s2,s3;
    tree(){
        l=r=tag=s1=s2=s3=0;
    }
}tre[N<<2];
char ch[10];
int gcd(int a,int b){
    if(a<b)swap(a,b);
    return !b?a:gcd(b,a%b);
}
tree operator +(const tree a,const tree b){
    tree c=tree();
    c.s1=a.s1+b.s1;
    c.s2=a.s2+b.s2;
    c.s3=a.s3+b.s3;
    c.l=a.l;c.r=b.r;
    c.tag=0;
    return c;
}
void init(){
    for(int i=1;i<=n-1;++i)s4[i]=s4[i-1]+i,s5[i]=s5[i-1]+i*i;
}
void pushup(int i){
    tre[i]=tre[ls]+tre[rs];
}
void pushdown(int i){
    int l=tre[i].l,r=tre[i].r,v=tre[i].tag;
    if(!v)return;
    tre[ls].tag+=v;
    tre[rs].tag+=v;

    tre[ls].s1+=(mid-(l-1))*v;
    tre[ls].s2+=(s4[mid]-s4[l-1])*v;
    tre[ls].s3+=(s5[mid]-s5[l-1])*v;

    tre[rs].s1+=(r-(mid))*v;
    tre[rs].s2+=(s4[r]-s4[mid])*v;
    tre[rs].s3+=(s5[r]-s5[mid])*v;
    tre[i].tag=0;
}
void build(int i,int l,int r){
    tre[i].l=l;tre[i].r=r;
    if(l==r) return;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(i);
}
void change(int i,int el,int er,int v){
    int l=tre[i].l,r=tre[i].r;
    if(el<=l && r<=er){
        tre[i].s1+=(r-(l-1))*v;
        tre[i].s2+=(s4[r]-s4[l-1])*v;
        tre[i].s3+=(s5[r]-s5[l-1])*v;
        tre[i].tag+=v;
        return;
    }
    pushdown(i);
    if(el<=mid)change(ls,el,er,v);
    if(er> mid)change(rs,el,er,v);
    pushup(i);
}
tree query(int i,int el,int er){
    int l=tre[i].l,r=tre[i].r;
    if(el<=l && r<=er) return tre[i];
    pushdown(i);
    if(er<=mid) return query(ls,el,er);
    else if(el>mid) return query(rs,el,er);
    else return query(ls,el,mid)+query(rs,mid+1,er);
}
signed main(){
    scanf("%lld%lld",&n,&m);
    init(); 
    build(1,1,n-1);
    for(int i=1;i<=m;++i){
        scanf("%s",ch);
        if(ch[0]=='C'){
            scanf("%lld%lld%lld",&L,&R,&v);--R;
            if(L<=R) change(1,L,R,v);
        }else{
            scanf("%lld%lld",&L,&R);
            a=(R-L+1);
            if(L==R){
                printf("0/1\n");
                continue;
            }
            --R;
            tree tmp=query(1,L,R);
            ans=2*(-tmp.s3+(R+L)*tmp.s2+(-R*L+R-L+1)*tmp.s1),res=a*(a-1);
            int Gcd=gcd(ans,res);
            printf("%lld/%lld\n",ans/Gcd,res/Gcd);
        }
    }



    return 0;
}

P2572

考虑对于一个区间，维护这些量：

  1. \(l,r\)，表示线段树节点对应的左右端点

  2. \(sum\),表示区间和

  3. \(L[0/1],R[0/1],S[0/1]\),表示\(0/1\)的前缀最大子段，后缀最大子段和最大子段

  4. \(tag,frc\)，表示区间覆盖和反转的\(lazytag\) (\(frc\)是首好听的\(bgm\)，来自《声之形》,~~墙裂推荐~~)

那么\(pushup\)就是最大子段和的方式。

\(pushdown\)注意\(tag\)优先级大于\(frc\),所以覆盖是将\(frc\)清零。

#include<iostream>
#include<cstdio>
#include<cstring>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid (l+r>>1)
using namespace std;
const int N=1e5+10;
struct tree {
    int L[2],S[2],R[2],sum,tag,l,r,frc;
    tree() {
        l=r=sum=frc=L[0]=L[1]=R[0]=R[1]=S[0]=S[1]=0,tag=-1;
    }
} tre[N<<2];
int read1(){
    int x=0;char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
}
void write1(int x){
    if(x>9) write1(x/10);
    putchar(x%10+'0');
}
int n,m,op,l,r;
int a[N];
tree operator +(tree a,tree b) {
    tree c=tree();
    int la=a.l,ra=a.r,lb=b.l,rb=b.r,xa=ra-la+1,xb=rb-lb+1;
    for(int k=0; k<=1; ++k) c.L[k]=(a.L[k]==xa?xa+b.L[k]:a.L[k]),c.R[k]=(b.R[k]==xb?xb+a.R[k]:b.R[k]),c.S[k]=max(max(a.S[k],b.S[k]),a.R[k]+b.L[k]); 
    c.sum=a.sum+b.sum;
    c.l=a.l,c.r=b.r;
    return c;
}
void pushup(int i) {
    tre[i]=tre[ls]+tre[rs];
}
void pushdown(int i) {
    int l=tre[i].l,r=tre[i].r,k=tre[i].tag,v=tre[i].frc;
    if(k!=-1) {
        tre[ls].tag=tre[rs].tag=k;
        tre[ls].frc=tre[rs].frc=0;
        tre[ls].sum=(mid-l+1)*k;
        tre[ls].S[k]=tre[ls].L[k]=tre[ls].R[k]=(mid-l+1);
        tre[ls].S[k^1]=tre[ls].L[k^1]=tre[ls].R[k^1]=0;
        tre[rs].sum=(r-mid)*k;
        tre[rs].S[k]=tre[rs].L[k]=tre[rs].R[k]=(r-mid);
        tre[rs].S[k^1]=tre[rs].L[k^1]=tre[rs].R[k^1]=0;
        tre[i].tag=-1;
    }
    if(v!=0) {
        tre[ls].frc^=v,tre[rs].frc^=v;
        tre[ls].sum=(mid-l+1)-tre[ls].sum;
        swap(tre[ls].L[0],tre[ls].L[1]);
        swap(tre[ls].R[0],tre[ls].R[1]);
        swap(tre[ls].S[0],tre[ls].S[1]);
        tre[rs].sum=(r-mid)-tre[rs].sum;
        swap(tre[rs].L[0],tre[rs].L[1]);
        swap(tre[rs].R[0],tre[rs].R[1]);
        swap(tre[rs].S[0],tre[rs].S[1]);
        tre[i].frc=0;
    }
}
void build(int i,int l,int r) {
    tre[i].l=l,tre[i].r=r,tre[i].tag=-1,tre[i].frc=0;
    if(l==r) {
        tre[i].sum=a[l];
        tre[i].L[a[l]]=tre[i].R[a[l]]=tre[i].S[a[l]]=1;
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(i);
}
void change(int i,int el,int er,int k) {
    int l=tre[i].l,r=tre[i].r;
    if(el<=l && r<=er) {
        tre[i].tag=k,tre[i].frc=0;
        tre[i].sum=(r-l+1)*k;
        tre[i].S[k]=tre[i].L[k]=tre[i].R[k]=(r-l+1);
        tre[i].S[k^1]=tre[i].L[k^1]=tre[i].R[k^1]=0;
        return;
    }
    pushdown(i);
    if(el<=mid) change(ls,el,er,k);
    if(er> mid) change(rs,el,er,k);
    pushup(i);
}
void reverse(int i,int el,int er) {
    int l=tre[i].l,r=tre[i].r;
    if(el<=l && r<=er) {
        tre[i].frc^=1;
        tre[i].sum=(r-l+1)-tre[i].sum;
        swap(tre[i].L[0],tre[i].L[1]);
        swap(tre[i].R[0],tre[i].R[1]);
        swap(tre[i].S[0],tre[i].S[1]);
        return;
    }
    pushdown(i);
    if(el<=mid) reverse(ls,el,er);
    if(er> mid) reverse(rs,el,er);
    pushup(i);
}
tree query(int i,int el,int er) {
    int l=tre[i].l,r=tre[i].r;
    if(el<=l && r<=er) return tre[i];   
    pushdown(i);
    if(er<=mid) return query(ls,el,er);
    else if(el> mid) return query(rs,el,er);
    else return query(ls,el,mid)+query(rs,mid+1,er);
}
int main() {
    //freopen("1.in","r",stdin); 
    n=read1(),m=read1();
    for(int i=1; i<=n; ++i) a[i]=read1();
    build(1,1,n);
    for(int i=1; i<=m; ++i) {
        op=read1(),l=read1(),r=read1(),++l,++r;
        if(op==0) {
            change(1,l,r,0);
        } else if(op==1) {
            change(1,l,r,1);
        } else if(op==2) {
            reverse(1,l,r);
        } else if(op==3) {
            write1(query(1,l,r).sum),putchar('\n');
        } else {
            write1(query(1,l,r).S[1]),putchar('\n');
        }
    }
    return 0;
}