题解 P2801 【教主的魔法】

fnoi16wjhui · 2018-09-29 20:42:15 · 题解

没有人写线段树么，那我写一个吧

更改可以用线段树区间加法+懒惰标记

查询可以记区间max和min，如果查询的数值小于等于 区间的min，那么就返回区间的数字个数（区间所有的数都 大于等于c）， 如果查询的数值大于 区间的max，那么就返回区间的0（区间所有的数都 小于c）

附代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1100000
using namespace std;
struct node{
    int min1,max1,flag;
}tree[N*4];
int n,q,a[N],l,r,c;
char ch[10];
//快读
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0' or c>'9') f=(c=='-'?-1:f),c=getchar();
    while(c>='0' and c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
inline void update(int p){
    tree[p].max1=max(tree[p<<1].max1,tree[p<<1|1].max1);
    tree[p].min1=min(tree[p<<1].min1,tree[p<<1|1].min1);
}
inline void pushdown(int p){
    if(tree[p].flag){
        tree[p<<1].flag+=tree[p].flag,tree[p<<1|1].flag+=tree[p].flag,
        tree[p<<1].max1+=tree[p].flag,tree[p<<1|1].max1+=tree[p].flag,
        tree[p<<1].min1+=tree[p].flag,tree[p<<1|1].min1+=tree[p].flag,
        tree[p].flag=0;
    }
}
void build(int p,int l,int r){
    if(l==r){tree[p].min1=tree[p].max1=a[l];return ;}
    int mid=(l+r)/2;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    update(p);
}
void add(int p,int l,int r,int ql,int qr,int c){
    if(ql<=l and r<=qr){tree[p].max1+=c,tree[p].min1+=c,tree[p].flag+=c;return ;}
    pushdown(p);
    int mid=(l+r)/2;
    if(ql<=mid) add(p<<1,l,mid,ql,qr,c);
    if(mid<qr) add(p<<1|1,mid+1,r,ql,qr,c);
    update(p);
}
int qeury(int p,int l,int r,int ql,int qr,int c){
//如题解所说
    if(ql<=l and r<=qr and c<=tree[p].min1) return r-l+1;
    if(ql<=l and r<=qr and c>tree[p].max1) return 0;
    pushdown(p);
    int mid=(l+r)/2,ans=0;
    if(ql<=mid) ans+=qeury(p<<1,l,mid,ql,qr,c);
    if(mid<qr) ans+=qeury(p<<1|1,mid+1,r,ql,qr,c);
    update(p);return ans;
}
int main(){
    n=read();q=read();
    for(register int i=1;i<=n;++i) a[i]=read();
    //建树
    build(1,1,n);
    for(register int i=1;i<=q;++i){
        scanf("%s",ch);l=read();r=read();c=read();
        if(ch[0]=='M') add(1,1,n,l,r,c);
        else printf("%d\n",qeury(1,1,n,l,r,c));
    }
    return 0;
}