四方喝彩 题解

· · 题解

实际上除了封锁操作以外都是模板题的内容，所以我们直接考虑如何处理操作 3。

考虑将所有的封锁操作拆成两个操作（第 k 次的封锁操作以及第 k+x 次操作后的解除封锁操作）。同时对于线段树的每个节点，我们将原来的维护区间和改为维护区间内所有未封锁位置的和以及封锁位置的和，另外再维护区间内未封锁位置个数以及这整个区间是否被封锁（类似于扫描线）。于是我们可以实时维护出每个位置是否被封锁，并据此来进行加法和乘法操作的修改。

这里需要注意一些细节，就是在所有的加法和乘法的操作以及相应标记下传时，如果相应节点整段区间被标记为封锁，那么就不应该对区间和以及标记进行修改，而在其他情况下则需要进行相应的区间和以及标记的修改。以及具体进行封锁和解除封锁时需要根据相应情况进行维护（比如在解除封锁部分，叶节点和非叶节点的维护就不同，以及对相应节点封锁时需要下传标记以保证解除封锁时维护的正确性）。

显然此时复杂度容易证明还是 O(n\log n)（n,m 同阶），考虑如何证明正确性。

可以发现在封锁操作执行前，所有相应需要封锁的节点的祖先标记均已下传，因此在此之前的操作内容已经全部传到这个节点，只需要再进行标记即可。而对于所有的解除封锁操作，在相应时段内的所有操作的标记也已经下传，而根据我们对标记下传部分的修改，相应的效果不会被传到该节点（相当于消去了这个时段内加法和乘法操作对这个区间的影响）。由此我们证明了这个做法的正确性。

#include<bits/stdc++.h>
#define p 1000000007
using namespace std;
int lw[200005],la[200005];
int fl[200005],fr[200005];
int n,m,a[200005];
struct xds{
    int x,fx,len,bj[2],f;
};
#define ls(w) (w<<1)
#define rs(w) (ls(w)^1)
xds tree[800005];
int dr()
{
    int xx=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')xx=(xx<<1)+(xx<<3)+ch-'0',ch=getchar();
    return xx;
}
void u(int w)
{
    if(tree[w].f==0)
    {
        tree[w].x=(tree[ls(w)].x+tree[rs(w)].x)%p,tree[w].fx=(tree[ls(w)].fx+tree[rs(w)].fx)%p;
        tree[w].len=tree[ls(w)].len+tree[rs(w)].len;
    }
}
void d(int w)
{
    if(tree[w].bj[1]!=1)
    {
        int x=tree[w].bj[1];tree[w].bj[1]=1;
        tree[ls(w)].x=1ll*tree[ls(w)].x*x%p,tree[rs(w)].x=1ll*tree[rs(w)].x*x%p;
        if(tree[ls(w)].f==0)tree[ls(w)].bj[0]=1ll*tree[ls(w)].bj[0]*x%p,tree[ls(w)].bj[1]=1ll*tree[ls(w)].bj[1]*x%p;
        if(tree[rs(w)].f==0)tree[rs(w)].bj[0]=1ll*tree[rs(w)].bj[0]*x%p,tree[rs(w)].bj[1]=1ll*tree[rs(w)].bj[1]*x%p;
    }
    if(tree[w].bj[0]!=0)
    {
        int x=tree[w].bj[0];tree[w].bj[0]=0;
        tree[ls(w)].x=(tree[ls(w)].x+1ll*tree[ls(w)].len*x)%p,tree[rs(w)].x=(tree[rs(w)].x+1ll*tree[rs(w)].len*x)%p;
        if(tree[ls(w)].f==0)tree[ls(w)].bj[0]=(tree[ls(w)].bj[0]+x)%p;
        if(tree[rs(w)].f==0)tree[rs(w)].bj[0]=(tree[rs(w)].bj[0]+x)%p;
    }
}
void csh(int w,int l,int r)
{
    tree[w].bj[1]=1;
    if(l==r)
    {
        tree[w].x=a[l],tree[w].len=1;
        return;
    }
    int mid=(l+r)>>1;
    csh(ls(w),l,mid),csh(rs(w),mid+1,r);
    u(w);
}
void xg_1(int w,int L,int R,int l,int r,int x)
{
    if(tree[w].f)return;
    if(L<=l&&r<=R)
    {
        tree[w].x=(tree[w].x+1ll*tree[w].len*x)%p;
        tree[w].bj[0]=(tree[w].bj[0]+x)%p;
        return;
    }
    d(w);
    int mid=(l+r)>>1;
    if(L<=mid)xg_1(ls(w),L,R,l,mid,x);
    if(R>mid)xg_1(rs(w),L,R,mid+1,r,x);
    u(w);
}
void xg_2(int w,int L,int R,int l,int r,int x)
{
    if(tree[w].f)return;
    if(L<=l&&r<=R)
    {
        tree[w].x=1ll*tree[w].x*x%p;
        tree[w].bj[0]=1ll*tree[w].bj[0]*x%p,tree[w].bj[1]=1ll*tree[w].bj[1]*x%p;
        return;
    }
    d(w);
    int mid=(l+r)>>1;
    if(L<=mid)xg_2(ls(w),L,R,l,mid,x);
    if(R>mid)xg_2(rs(w),L,R,mid+1,r,x);
    u(w);
}
void xg_3(int w,int L,int R,int l,int r)
{
    if(L<=l&&r<=R)
    {
        if(l!=r)d(w);
        if(tree[w].f==0)tree[w].fx=(tree[w].fx+tree[w].x)%p,tree[w].x=0,tree[w].len=0;
        ++tree[w].f;
        return;
    }
    d(w);
    int mid=(l+r)>>1;
    if(L<=mid)xg_3(ls(w),L,R,l,mid);
    if(R>mid)xg_3(rs(w),L,R,mid+1,r);
    u(w);
}
void xg_4(int w,int L,int R,int l,int r)
{
    if(L<=l&&r<=R)
    {
        --tree[w].f;
        if(tree[w].f==0)
        {
            if(l==r)swap(tree[w].x,tree[w].fx),tree[w].len=1;
            else u(w);
        }
        return;
    }
    d(w);
    int mid=(l+r)>>1;
    if(L<=mid)xg_4(ls(w),L,R,l,mid);
    if(R>mid)xg_4(rs(w),L,R,mid+1,r);
    u(w);
}
int cx(int w,int L,int R,int l,int r)
{
    if(L<=l&&r<=R)return (tree[w].x+tree[w].fx)%p;
    d(w);
    int mid=(l+r)>>1,x=0;
    if(L<=mid)x+=cx(ls(w),L,R,l,mid);
    if(R>mid)x+=cx(rs(w),L,R,mid+1,r);
    return x%p;
}
int main()
{
    n=dr(),m=dr();
    for(int i=1;i<=n;i++)a[i]=dr();
    csh(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int opt=dr(),l=dr(),r=dr();
        if(opt<=3)
        {
            int x=dr();
            if(opt==1)xg_1(1,l,r,1,n,x);
            if(opt==2)xg_2(1,l,r,1,n,x);
            if(opt==3)
            {
                xg_3(1,fl[i]=l,fr[i]=r,1,n);
                int k=i+x;la[i]=lw[k],lw[k]=i;
            }
        }
        else printf("%d\n",cx(1,l,r,1,n));
        for(int j=lw[i];j;j=la[j])xg_4(1,fl[j],fr[j],1,n);
    }
}