题解 P2801 【教主的魔法】

L_M_ · 2018-10-22 20:21:27 · 题解

纪念蒟蒻第一次一遍A的线段树quq

好接下来咱们看看这道题

我一开始其实一眼看是分块（hzwer巨佬的博客里有写分块的做法），但是考虑考虑分块发现我这个蒟蒻根本不会写，于是考虑考虑线段树，哎，发现简单的一

具体讲，写一个维护最小值的线段树，区间加就lazy直接搞，询问的话我们看看如果当前的区间和待询问区间重合并且这段区间的min >= c，那么这段区间就合法，不然就一直二分下去，直到只有一个数为止

复杂度q*logn稳得一批

线段树大法吼哇！

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<climits>
#include<queue>
using namespace std;
#define rg register
#define min(a,b) ((a)>(b)?(b):(a))
int d[4000005],mi[4000005];
inline int read()
{
    int ans = 0,op = 1;
    char ch = getchar();
    while(ch < '0'||ch > '9')
    {
        if(ch == '-') op = -1;
        ch = getchar();
    }
    while(ch >= '0'&&ch <= '9')
    {
        (ans *= 10) += ch - '0';
        ch = getchar();
    }
    return ans * op;
 }
inline void pushdown(int i)
{
    if(d[i])
    {
    d[i << 1] += d[i];
    d[i << 1 | 1] += d[i];
    mi[i << 1] += d[i];
    mi[i << 1 | 1] += d[i];
    d[i] = 0;
    }
}
void adde(rg int i,rg int l,rg int r,rg int ql,rg int qr,rg int delta)
{
    if(l == ql&&r == qr)
    {
        mi[i] += delta;
        d[i] += delta;
        return;
    }
    pushdown(i);
    mi[i] += delta;
    //printf("%d ",mi[i]);
    int mid = l + r >> 1;
    if(qr <= mid) adde(i << 1,l,mid,ql,qr,delta);
    else if(ql > mid) adde(i << 1 | 1,mid + 1,r,ql,qr,delta);
    else
    {
        adde(i << 1,l,mid,ql,mid,delta);
        adde(i << 1 | 1,mid + 1,r,mid + 1,qr,delta);
    }
    mi[i] = min(mi[i << 1],mi[i << 1 | 1]);
    return;
}
int query(rg int i,rg int l,rg int r,int ql,int qr,int c)
{
    //printf("%d %d %d %d %d\n",mi[i],l,r,ql,qr);
    if(l == ql && r == qr && mi[i] >= c) return r - l + 1;
    if(l == r) return mi[i] >= c; 
    pushdown(i);
    int mid = l + r >> 1;
    if(qr <= mid) return query(i << 1,l,mid,ql,qr,c);
    else if(ql > mid) return query(i << 1 | 1,mid + 1,r,ql,qr,c);
    else return query(i << 1,l,mid,ql,mid,c) + query(i << 1 | 1,mid + 1,r,mid + 1,qr,c);
}
int main()
{
    int n = read(),q = read();
    //build(1,1,n);
    //memset(mi,0x3f,sizeof(mi));
    for(int i = 1;i <= n;i++)
    {
        int a = read();
        adde(1,1,n,i,i,a);
        //cout<<endl;
    }
    while(q--)
    {
        char c ;
        cin >> c;
        int l = read(),r = read(),m = read();
        if(c == 'M') adde(1,1,n,l,r,m);
        else printf("%d\n",query(1,1,n,l,r,m));
    }
}