题解 P2801 【教主的魔法】

· · 题解

不知道为什么上面说这题线段树做不了啊

看了这题一眼线段树，正好还是qbxt不确定能不能用线段树+lazy做的那种问题，然后做了做，线段树确实可做啊

总的思路就是：

维护区间min

修改就是区间修改+lazy标记（不要忘记回推），询问的时候如果区间被询问区间包含并且最小值大于等于c，那么这段区间里的人全是身高符合要求的

我永远喜欢线段树

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,l,r) for(int i=l;i>=r;--i)
#define mid ((l+r)>>1)
#define ls (x<<1)
#define rs ((x<<1)|1)
using namespace std;
inline int read()
{
    char c;
    bool t=0;
    int a=0;
    while((c=getchar())==' '||c=='\n'||c=='\r');
    if(c=='-')
    {
        t=1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        a*=10;
        a+=(c-'0');
        c=getchar();
    }
    return a*(t?-1:1);
}
int n,q,minn[4000010],lazy[4000010],ans;
void build(int l,int r,int x)
{
    if(l==r)
     minn[x]=read();
    else
    {
        build(l,mid,ls);
        build(mid+1,r,rs);
        minn[x]=min(minn[ls],minn[rs]);
    }
}
void down(int x)
{
    minn[ls]+=lazy[x];
    lazy[ls]+=lazy[x];
    minn[rs]+=lazy[x];
    lazy[rs]+=lazy[x];
    lazy[x]=0;
}
void ask(int l,int r,int x,int ll,int rr,int k)
{
    if(ll<=l&&r<=rr&&minn[x]>=k)
    {
        ans+=r-l+1;
        return;
    }
    if(l==r)
     return;
    if(lazy[x])
     down(x);
    if(ll<=mid)
     ask(l,mid,ls,ll,rr,k);
    if(mid<rr)
     ask(mid+1,r,rs,ll,rr,k);
}
void modify(int l,int r,int x,int ll,int rr,int k)
{
    if(ll<=l&&r<=rr)
    {
        minn[x]+=k;
        lazy[x]+=k;
        return;
    }
    if(lazy[x])
     down(x);
    if(ll<=mid)
     modify(l,mid,ls,ll,rr,k);
    if(mid<rr)
     modify(mid+1,r,rs,ll,rr,k);
    minn[x]=min(minn[ls],minn[rs]);
}
int main()
{
    char c;
    int tx,ty,tz;
    n=read();q=read();
    build(1,n,1);
    rep(i,1,q)
    {
        while((c=getchar())==' '||c=='\n'||c=='\r');
        tx=read();ty=read();tz=read();
        if(c=='M')
        {
            modify(1,n,1,tx,ty,tz);
        }
        else if(c=='A')
        {
            ans=0;
            ask(1,n,1,tx,ty,tz);
            printf("%d\n",ans);
        }
    }
    return 0;
}