线段树题单

将写一篇比较长的博客来系统的学习下线段树:群友Limit的线段树题单以及线段树分治的某些题单
update:群友Limit的线段树题单two

P3372 【模板】线段树 1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll Tree[N<<4],w[N],lazy[N<<4];
//分别表示该节点的下的权值和是多少,
void pushdown(int u,int l,int r)
{
    int mid=(l+r)>>1;
    Tree[u<<1]+=(mid-l+1)*lazy[u];
    Tree[u<<1|1]+=(r-mid)*lazy[u];
    lazy[u<<1]+=lazy[u];
    lazy[u<<1|1]+=lazy[u];
    lazy[u]=0;
}

void modify(int u,int l,int r,int L,int R,int val)//在[l,r]中更新[L,R].
{
    int mid=(l+r)>>1;
    if(L>r||R<l)    return;
    if(L<=l&&r<=R)    //这个区间信息可以保留.
    {
        lazy[u]+=val;
        Tree[u]+=(r-l+1)*val;
        return;
    }
    pushdown(u,l,r);
    modify(u<<1,l,mid,L,R,val);
    modify(u<<1|1,mid+1,r,L,R,val);
    Tree[u]=Tree[u<<1]+Tree[u<<1|1];
}

ll query(int u,int l,int r,int L,int R)//在[l,r]中查询[L,R].
{
    int mid=(l+r)>>1;
    if(L>r||R<l)    return 0;
    pushdown(u,l,r);
    if(L<=l&&r<=R)    //这个区间信息可以保留.
    {
        return Tree[u];
    }
    return query(u<<1,l,mid,L,R)+query(u<<1|1,mid+1,r,L,R);
}

void build(int u,int l,int r)
{
    if(l==r)
    {
        Tree[u]=w[l];
        return;
    }int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    Tree[u]=Tree[u<<1]+Tree[u<<1|1];
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&w[i]);
    }build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int op,x,y,k;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&x,&y,&k);
            modify(1,1,n,x,y,k);
        }
        else
        {
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

P6492 [COCI2010-2011#6] STEP
吐槽:为什么我的代码如此优美呢?2333

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+50;

struct Tree{
    int l,r,L,R,lans,rans,ans;//l,r表示管辖的范围.L,R表示该节点左右两端的值.ans表示最长的长度.
}tr[N<<2];

void push_up(int u)
{
    int ls=(u<<1),rs=(u<<1|1);
    tr[u].ans=max(tr[ls].ans,tr[rs].ans);
    tr[u].lans=tr[ls].lans;
    tr[u].rans=tr[rs].rans;
    if(tr[ls].R^tr[rs].L)
    {
        tr[u].ans=max(tr[u].ans,tr[ls].rans+tr[rs].lans);
        if(tr[ls].lans==(tr[ls].r-tr[ls].l+1))    tr[u].lans=max(tr[u].lans,tr[ls].lans+tr[rs].lans);
        if(tr[rs].rans==(tr[rs].r-tr[rs].l+1))    tr[u].rans=max(tr[u].rans,tr[rs].rans+tr[ls].rans);
    }
    tr[u].l=tr[ls].l,tr[u].r=tr[rs].r;
    tr[u].L=tr[ls].L,tr[u].R=tr[rs].R;
}

void modify(int u,int pos)//在当前管辖的区间更新某个位子.
{
    int ls=(u<<1),rs=(u<<1|1);
    if(pos>tr[u].r||pos<tr[u].l)    return;
    if(tr[u].l==tr[u].r&&tr[u].l==pos)
    {
        int odd=tr[u].L;
        tr[u].L=tr[u].R=(!odd);
        return;
    }
    modify(ls,pos);
    modify(rs,pos);
    push_up(u);
}

void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u].l=tr[u].r=l;
        tr[u].L=tr[u].R=0;
        tr[u].lans=tr[u].rans=1;
        tr[u].ans=1;return;
    }int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    push_up(u);
}

int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    build(1,1,n);
    while(q--)
    {
        int x;
        scanf("%d",&x);
        modify(1,x);
        printf("%d\n",tr[1].ans);
    }
    return 0;
}

线段树2

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+50;
struct Tree{
    int l,r,mul,add,sum;//当前节点所管辖的左右区间,mul,add延迟标记,区间总和sum.
}tr[N<<2];
int n,m,p,w[N];
void push_down(int u)
{
    tr[u<<1].sum=(tr[u].mul*tr[u<<1].sum+(tr[u].add*(tr[u<<1].r-tr[u<<1].l+1))%p)%p;
    tr[u<<1|1].sum=(tr[u].mul*tr[u<<1|1].sum+(tr[u].add*(tr[u<<1|1].r-tr[u<<1|1].l+1))%p)%p;
    tr[u<<1].mul=(tr[u<<1].mul*tr[u].mul)%p;
    tr[u<<1|1].mul=(tr[u<<1|1].mul*tr[u].mul)%p;
    tr[u<<1].add=(tr[u<<1].add*tr[u].mul+tr[u].add)%p;
    tr[u<<1|1].add=(tr[u<<1|1].add*tr[u].mul+tr[u].add)%p;
    tr[u].add=0,tr[u].mul=1;
}

void push_up(int u)
{
    tr[u].l=tr[u<<1].l;tr[u].r=tr[u<<1|1].r;
    tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
}

void add(int u,int l,int r,int val)
{
    if(r<tr[u].l||l>tr[u].r)    return;
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        tr[u].add+=val;
        tr[u].add%=p;
        tr[u].sum=(tr[u].sum+val*(tr[u].r-tr[u].l+1))%p;
        return;
    }
    push_down(u);
    add(u<<1,l,r,val);
    add(u<<1|1,l,r,val);
    push_up(u);
}

void mul(int u,int l,int r,int val)
{
    if(r<tr[u].l||l>tr[u].r)    return;
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        tr[u].add*=val;
        tr[u].add%=p;
        tr[u].mul*=val;
        tr[u].mul%=p;
        tr[u].sum=(tr[u].sum*val)%p;
        return;
    }
    push_down(u);
    mul(u<<1,l,r,val);
    mul(u<<1|1,l,r,val);
    push_up(u);
}

void build(int u,int l,int r)
{
    tr[u].mul=1;
    if(l==r)
    {
        tr[u].l=tr[u].r=l;
        tr[u].sum=w[l]%p;
        return;
    }int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    push_up(u);
}

int query(int u,int l,int r)
{
    if(r<tr[u].l||l>tr[u].r)    return 0;
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        return tr[u].sum%p;
    }push_down(u);
    return (query(u<<1,l,r)+query(u<<1|1,l,r))%p;
}

signed main()
{
    scanf("%lld%lld%lld",&n,&m,&p);
    for(int i=1;i<=n;i++)    scanf("%lld",&w[i]);
    build(1,1,n);
    while(m--)
    {
        int op,x,y,k;scanf("%lld",&op);
        if(op==1)
        {
            scanf("%lld%lld%lld",&x,&y,&k);
            mul(1,x,y,k);
        }
        else if(op==2)
        {
            scanf("%lld%lld%lld",&x,&y,&k);
            add(1,x,y,k);
        }
        else
        {
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",query(1,x,y));
        }
    }
}

下面那个和这个一样的...
P2023 [AHOI2009] 维护序列

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+50;
struct Tree{
    int l,r,mul,add,sum;//当前节点所管辖的左右区间,mul,add延迟标记,区间总和sum.
}tr[N<<2];
int n,m,p,w[N];
void push_down(int u)
{
    tr[u<<1].sum=(tr[u].mul*tr[u<<1].sum+(tr[u].add*(tr[u<<1].r-tr[u<<1].l+1))%p)%p;
    tr[u<<1|1].sum=(tr[u].mul*tr[u<<1|1].sum+(tr[u].add*(tr[u<<1|1].r-tr[u<<1|1].l+1))%p)%p;
    tr[u<<1].mul=(tr[u<<1].mul*tr[u].mul)%p;
    tr[u<<1|1].mul=(tr[u<<1|1].mul*tr[u].mul)%p;
    tr[u<<1].add=(tr[u<<1].add*tr[u].mul+tr[u].add)%p;
    tr[u<<1|1].add=(tr[u<<1|1].add*tr[u].mul+tr[u].add)%p;
    tr[u].add=0,tr[u].mul=1;
}

void push_up(int u)
{
    tr[u].l=tr[u<<1].l;tr[u].r=tr[u<<1|1].r;
    tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
}

void add(int u,int l,int r,int val)
{
    if(r<tr[u].l||l>tr[u].r)    return;
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        tr[u].add+=val;
        tr[u].add%=p;
        tr[u].sum=(tr[u].sum+val*(tr[u].r-tr[u].l+1))%p;
        return;
    }
    push_down(u);
    add(u<<1,l,r,val);
    add(u<<1|1,l,r,val);
    push_up(u);
}

void mul(int u,int l,int r,int val)
{
    if(r<tr[u].l||l>tr[u].r)    return;
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        tr[u].add*=val;
        tr[u].add%=p;
        tr[u].mul*=val;
        tr[u].mul%=p;
        tr[u].sum=(tr[u].sum*val)%p;
        return;
    }
    push_down(u);
    mul(u<<1,l,r,val);
    mul(u<<1|1,l,r,val);
    push_up(u);
}

void build(int u,int l,int r)
{
    tr[u].mul=1;
    if(l==r)
    {
        tr[u].l=tr[u].r=l;
        tr[u].sum=w[l]%p;
        return;
    }int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    push_up(u);
}

int query(int u,int l,int r)
{
    if(r<tr[u].l||l>tr[u].r)    return 0;
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        return tr[u].sum%p;
    }push_down(u);
    return (query(u<<1,l,r)+query(u<<1|1,l,r))%p;
}

signed main()
{
    scanf("%lld%lld",&n,&p);
    for(int i=1;i<=n;i++)    scanf("%lld",&w[i]);
    build(1,1,n);
    scanf("%lld",&m);
    while(m--)
    {
        int op,x,y,k;scanf("%lld",&op);
        if(op==1)
        {
            scanf("%lld%lld%lld",&x,&y,&k);
            mul(1,x,y,k);
        }
        else if(op==2)
        {
            scanf("%lld%lld%lld",&x,&y,&k);
            add(1,x,y,k);
        }
        else
        {
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",query(1,x,y));
        }
    }
}

P1637 三元上升子序列
这题用树状数组更好写,我主要是练下线段树而已...中间还是出现了小小的bug,我不行i...

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e4+40;
int w[N];
int ls[N];
struct Tree{
    int l,r,sum;
}tr[2][N<<2];//开两颗线段树维护前面有多少比它小的,后面有多少比它大的.

void build(int u,int l,int r,int op)
{
    tr[op][u].sum=0;
    tr[op][u].l=l,tr[op][u].r=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(u<<1,l,mid,op);
    build(u<<1|1,mid+1,r,op);
}

void add(int u,int pos,int val,int op)//使得单点加上多少.
{
    if(pos>tr[op][u].r||pos<tr[op][u].l)    return;
    if(pos==tr[op][u].l&&pos==tr[op][u].r)
    {
        tr[op][u].sum+=val;
        return;
    }
    add(u<<1,pos,val,op);
    add(u<<1|1,pos,val,op);
    tr[op][u].sum=tr[op][u<<1].sum+tr[op][u<<1|1].sum;
}

int query(int u,int l,int r,int op)//查询区间答案.
{
    if(l>tr[op][u].r||r<tr[op][u].l)    return 0;
    if(l<=tr[op][u].l&&r>=tr[op][u].r)
    {
        return tr[op][u].sum;
    }return query(u<<1,l,r,op)+query(u<<1|1,l,r,op);
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
        ls[i]=w[i];
    }sort(ls+1,ls+1+n);
    build(1,1,n,0);
    build(1,1,n,1);
    for(int i=1;i<=n;i++)
    {
        w[i]=lower_bound(ls+1,ls+1+n,w[i])-ls;
        add(1,w[i],1,1);
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        add(1,w[i],-1,1);
        if(w[i]>1&&w[i]<n)    ans+=1ll*query(1,1,w[i]-1,0)*query(1,w[i]+1,n,1);
        add(1,w[i],1,0);
    }printf("%lld\n",ans);
    return 0;
}

CF915E Physical Education Lessons
动态开点.

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5e6;
int lazy[N],ls[N],rs[N],sum[N],root,cnt;//线段树节点u的左右两个端点.以及这个端点的权值.
void pushdown(int u,int l,int r)
{
    if(~lazy[u])
    {
        if(!ls[u])    ls[u]=++cnt;
        if(!rs[u])    rs[u]=++cnt;
        int mid=(l+r)>>1;
        sum[ls[u]]=(mid-l+1)*lazy[u];
        sum[rs[u]]=(r-mid)*lazy[u];
        lazy[ls[u]]=lazy[rs[u]]=lazy[u];
        lazy[u]=-1;
    }
}

void modify(int &u,int l,int r,int L,int R,int val)
{
    if(!u)    u=++cnt;
    if(L<=l&&r<=R)
    {
        sum[u]=val*(r-l+1);
        lazy[u]=val;
        return;
    }int mid=(l+r)>>1;
    pushdown(u,l,r);
    if(L<=mid)    modify(ls[u],l,mid,L,R,val);
    if(R>mid)    modify(rs[u],mid+1,r,L,R,val);
    sum[u]=sum[ls[u]]+sum[rs[u]];
}

int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    //我们假设工作日为0,非工作日为1.这样比较方便.
    memset(lazy,-1,sizeof lazy);
    modify(root,1,n,1,n,0);
    while(q--)
    {
        int L,R,k;
        scanf("%d%d%d",&L,&R,&k);
        modify(root,1,n,L,R,2-k);//区间修改成2-k.
        printf("%d\n",n-sum[1]);//输出答案.
    }
    return 0;
}

P3384 【模板】轻重链剖分
树链剖分.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+500;
ll n,m,r,p;
ll w[N];
vector<int>v[N];
ll dep[N],siz[N],dfn[N],f[N];
//跑出深度,子树大小,重儿子,父亲. 
void dfs1(int u,int fa)
{
    siz[u]=1;dep[u]=dep[fa]+1;f[u]=fa;
    int num=v[u].size();
    for(int i=0;i<num;i++)
    {
        int son=v[u][i];
        if(son==fa)    continue;
        dfs1(son,u);
        siz[u]+=siz[son];
        if(siz[son]>siz[dfn[u]])    dfn[u]=son;
    }
}

//跑出每个节点的下标以及处理它们的权值,然后统计重链的起点. 
ll id=0,idx[N],top[N],val[N];
void dfs2(int u,int topf)
{
    idx[u]=++id;
    top[u]=topf;
    val[id]=w[u];
    if(!dfn[u])    return;
    dfs2(dfn[u],topf);
    int num=v[u].size();
    for(int i=0;i<num;i++)
    {
        int son=v[u][i];
        if(idx[son])    continue;
        dfs2(son,son);
    }
}

//写一份有线段树区间修改,区间求和功能的树. 
struct Tree{
    ll l,r,len,sum,lazy;
}tr[N<<2];
void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void pushdown(int u)
{
    tr[u<<1].sum=(tr[u<<1].sum+tr[u].lazy*tr[u<<1].len%p)%p;
    tr[u<<1|1].sum=(tr[u<<1|1].sum+tr[u].lazy*tr[u<<1|1].len%p)%p;
    tr[u<<1].lazy=(tr[u<<1].lazy+tr[u].lazy)%p;
    tr[u<<1|1].lazy=(tr[u<<1|1].lazy+tr[u].lazy)%p;
    tr[u].lazy=0;
}
void build(int u,int l,int r)
{
    tr[u].len=(r-l+1);tr[u].l=l;tr[u].r=r;
    if(l==r)
    {
        tr[u].l=tr[u].r=l;
        tr[u].sum=val[l];
        return;
    }int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

void add(int u,int L,int R,int k)
{
    if(tr[u].r<L||R<tr[u].l)    return;
    if(L<=tr[u].l&&tr[u].r<=R)
    {
        tr[u].sum=(tr[u].sum+k*(tr[u].len)%p)%p;
        tr[u].lazy=(tr[u].lazy+k)%p;
        return;
    }pushdown(u);
    add(u<<1,L,R,k);
    add(u<<1|1,L,R,k);
    pushup(u);
}

ll query(int u,int L,int R)
{
    if(tr[u].r<L||R<tr[u].l)    return 0;
    if(L<=tr[u].l&&tr[u].r<=R)    return tr[u].sum%p;
    pushdown(u);
    return (query(u<<1,L,R)+query(u<<1|1,L,R))%p;
}

//实现v->u的修改以及查询操作.
void Treeadd(int x,int y,int k)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])    swap(x,y);
        add(1,idx[top[x]],idx[x],k);
        x=f[top[x]];
    }
    if(dep[x]>dep[y])    swap(x,y);
    add(1,idx[x],idx[y],k);
}

ll Treesum(int x,int y)
{
    ll ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])    swap(x,y);
        ans=(ans+query(1,idx[top[x]],idx[x]))%p;
        x=f[top[x]];
    }
    if(dep[x]>dep[y])    swap(x,y);
    ans=(ans+query(1,idx[x],idx[y]))%p;
    return ans;
}

int main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&r,&p);
    for(int i=1;i<=n;i++)    scanf("%lld",&w[i]);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }    
    dfs1(r,r);
    dfs2(r,r);
    build(1,1,n);
    while(m--)
    {
        int op,x,y,z;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&x,&y,&z);
            Treeadd(x,y,z%p);
        }
        else if(op==2)
        {
            scanf("%d%d",&x,&y);
            printf("%lld\n",Treesum(x,y));
        }
        else if(op==3)
        {
            scanf("%d%d",&x,&z);
            add(1,idx[x],idx[x]+siz[x]-1,z%p);
        }
        else
        {
            scanf("%d",&x);
            printf("%lld\n",query(1,idx[x],idx[x]+siz[x]-1));
        }
    }
    return 0;    
}

P1531 I Hate It
简单的单点修改和区间查询吧..

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+500;
struct Tree{
    int l,r,ans;
}tr[N<<2];
int w[N];
void pushup(int u)
{
    tr[u].ans=max(tr[u<<1].ans,tr[u<<1|1].ans);
}

void modify(int u,int l,int r,int val)
{
    if(tr[u].r<l||tr[u].l>r)    return;
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        tr[u].ans=max(tr[u].ans,val);
        return;
    }
    modify(u<<1,l,r,val);
    modify(u<<1|1,l,r,val);
    pushup(u);
}

int query(int u,int l,int r)
{
    if(tr[u].r<l||tr[u].l>r)    return 0;
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        return tr[u].ans;
    }return max(query(u<<1,l,r),query(u<<1|1,l,r));
}

void build(int u,int l,int r)
{
    tr[u].l=l;tr[u].r=r;
    if(l==r)
    {
        tr[u].ans=w[l];
        return;
    }int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)    scanf("%d",&w[i]);    
    build(1,1,n);
    while(m--)
    {
        char a;int b,c;    
        cin>>a>>b>>c;
        if(a=='Q')
        {
            printf("%d\n",query(1,b,c));    
        }
        else
        {
            modify(1,b,b,c);
        }
    }    
    return 0;
}

P1276 校门外的树(增强版)
比模板还是多了些操作的...不错的题.

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int ans1=0,ans2=0;
struct Tree{
    int l,r,len,val;//1表示原来那颗大树,0表示没树苗,2表示有树苗,-1表示这个节点不能全部包括. 
}tr[N<<2];

void cut(int u,int l,int r)
{
    if(tr[u].l>r||tr[u].r<l)    return;
    if(tr[u].val!=-1)    tr[u<<1].val=tr[u<<1|1].val=tr[u].val;
    if(l<=tr[u].l&&tr[u].r<=r&&tr[u].val!=-1)
    {
        if(tr[u].val==1)    tr[u].val=0;
        if(tr[u].val==2)
        {
            ans1-=tr[u].len;
            ans2+=tr[u].len;
            tr[u].val=0;
        }
        return;
    }
    cut(u<<1,l,r);
    cut(u<<1|1,l,r);
    if(tr[u<<1].val!=tr[u<<1|1].val) tr[u].val=-1;
    else tr[u].val=tr[u<<1].val;
}

void plant(int u,int l,int r)
{
    if(tr[u].l>r||tr[u].r<l)    return;
    if(tr[u].val!=-1)    tr[u<<1].val=tr[u<<1|1].val=tr[u].val;
    if(l<=tr[u].l&&tr[u].r<=r&&tr[u].val!=-1)
    {
        if(tr[u].val==0)    ans1+=tr[u].len,tr[u].val=2;
        return;
    }
    plant(u<<1,l,r);
    plant(u<<1|1,l,r);
    if(tr[u<<1].val!=tr[u<<1|1].val) tr[u].val=-1;
    else tr[u].val=tr[u<<1].val;
}

void build(int u,int l,int r)
{
    tr[u].l=l,tr[u].r=r,tr[u].val=1,tr[u].len=(r-l+1);
    if(l==r)    return;
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);n++;
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        b++,c++;
        if(a==0)    cut(1,b,c);
        else        plant(1,b,c);
    }printf("%d\n%d\n",ans1,ans2);//校门外留下的树苗数目 种上又被拔掉的树苗数目
    return 0;
}

P1438 无聊的数列
真的菜,区间修改的线段树还是可以打出bug?

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+500;
typedef long long ll;
ll a[N],w[N];
struct Tree{
    ll l,r,len,sum,lazy;
}tr[N<<2];
void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void pushdown(int u)
{
    tr[u<<1].lazy+=tr[u].lazy;
    tr[u<<1|1].lazy+=tr[u].lazy;
    tr[u<<1].sum+=tr[u].lazy*tr[u<<1].len;
    tr[u<<1|1].sum+=tr[u].lazy*tr[u<<1|1].len;
    tr[u].lazy=0;
}

void add(int u,int l,int r,int val)
{
    if(l>tr[u].r||r<tr[u].l)    return;
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        tr[u].lazy+=val;
        tr[u].sum+=tr[u].len*val;
        return;
    }pushdown(u);
    add(u<<1,l,r,val);
    add(u<<1|1,l,r,val);
    pushup(u);
}

ll query(int u,int l,int r)
{
    if(l>tr[u].r||r<tr[u].l)    return 0;
    pushdown(u);
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        return tr[u].sum;
    }
    return query(u<<1,l,r)+query(u<<1|1,l,r);
}

void build(int u,int l,int r)
{
    tr[u].l=l,tr[u].r=r,tr[u].len=r-l+1;
    tr[u].lazy=0;
    if(l==r)
    {
        tr[u].sum=w[l];
        return;
    }int mid=(r+l)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        if(i==1)    w[i]=a[i];
        else        w[i]=a[i]-a[i-1];
    }build(1,1,n);
    while(m--)
    {
        int op;int l,r,k,d;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d%d",&l,&r,&k,&d);
            add(1,l,l,k);
            add(1,l+1,r,d);
            add(1,r+1,r+1,-(k+(r-l)*d));
        }
        else
        {
            int p;scanf("%d",&p);
            printf("%lld\n",query(1,1,p));
        }
    }
    return 0;
}

P1471 方差
不难,但是也是值得学习的一题.

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+500;
struct Tree{
    int l,r,len;
    double sum;
    double lazy;
}_tr[N<<2],__tr[N<<2];//一个维护区间和,另外一个维护区间平方和.

double w[N];

void pushup(int u)
{
    _tr[u].sum=_tr[u<<1].sum+_tr[u<<1|1].sum;
    __tr[u].sum=__tr[u<<1].sum+__tr[u<<1|1].sum;
}

void pushdown(int u)
{
    __tr[u<<1].lazy+=__tr[u].lazy;
    __tr[u<<1|1].lazy+=__tr[u].lazy;
    __tr[u<<1].sum+=_tr[u<<1].sum*2*__tr[u].lazy+__tr[u<<1].len*__tr[u].lazy*__tr[u].lazy;
    __tr[u<<1|1].sum+=_tr[u<<1|1].sum*2*__tr[u].lazy+__tr[u<<1|1].len*__tr[u].lazy*__tr[u].lazy;
    _tr[u<<1].lazy+=_tr[u].lazy;
    _tr[u<<1|1].lazy+=_tr[u].lazy;
    _tr[u<<1].sum+=_tr[u].lazy*_tr[u<<1].len;
    _tr[u<<1|1].sum+=_tr[u].lazy*_tr[u<<1|1].len;
    _tr[u].lazy=__tr[u].lazy=0;
}

void add(int u,int l,int r,double val)
{
    if(l>_tr[u].r||r<_tr[u].l)    return;
    if(_tr[u].l>=l&&_tr[u].r<=r)
    {
        __tr[u].lazy+=val;
        __tr[u].sum+=_tr[u].sum*2*val+_tr[u].len*val*val;
        _tr[u].lazy+=val;
        _tr[u].sum+=val*_tr[u].len;
        return;
    }pushdown(u);
    add(u<<1,l,r,val);
    add(u<<1|1,l,r,val);
    pushup(u);
}

double query(Tree tree[],int u,int l,int r)
{
    if(l>tree[u].r||r<tree[u].l)    return 0;
    if(l<=tree[u].l&&tree[u].r<=r)  return tree[u].sum;
    pushdown(u);
    return query(tree,u<<1,l,r)+query(tree,u<<1|1,l,r);
}

void build(int u,int l,int r)
{
    _tr[u].l=l,_tr[u].r=r;
    __tr[u].l=l,__tr[u].r=r;
    _tr[u].len=__tr[u].len=(r-l+1);
    _tr[u].lazy=__tr[u].lazy=0;
    if(l==r)
    {
        _tr[u].sum=w[l];
        __tr[u].sum=w[l]*w[l];
        return;
    }int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)   scanf("%lf",&w[i]);
    build(1,1,n);
    int op,x,y;
    double k;
    while(m--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%lf",&x,&y,&k);
            add(1,x,y,k);
        }
        else if(op==2)
        {
            scanf("%d%d",&x,&y);
            printf("%.4f\n",query(_tr,1,x,y)/(y-x+1));
        }
        else
        {
            scanf("%d%d",&x,&y);
            double age=query(_tr,1,x,y)/(y-x+1);
            printf("%.4f\n",fabs(age*age-query(__tr,1,x,y)/(y-x+1)));
        }
    }
    return 0;
}