题解 P2801 【教主的魔法】

· · 题解

这其实是一个线段树的裸题，就是要改一下query函数

1.先打一个支持区间修改，查询区间最小值的的普通线段树

2把if(L<=l&&r<=R)return a[cur];改成下面这两句 .

if(L<=l&&r<=R&&a[cur]>=num)return r-l+1;

if(l==r)return a[cur]>=num;

作用：如果本区间最小值比num大，直接把整个区间长度输出，否则继续执行二分（分成了一个点的时候当然要停下）

比普通的分块肯定是要快不少 O2 172MS

#include<iostream>
#include<cstdio>
using namespace std;
inline int read()
{
      int x=0,f=1;
      char ch=getchar();
      while(ch>'9'||ch<'0')
      {
          if(ch=='-')f=-1;
          ch=getchar();
      }
      while(ch<='9'&&ch>='0')
      {
          x=x*10+ch-'0';
          ch=getchar();
      }
      return x*f;
}
int n,m,a[4000001],lazy[4000001],k[1000001],x,y,z;char c;
void buildtree(int l,int r,int cur)
{
     if(l==r)
     {
          a[cur]=k[l];
          return ;
     }
     int mid=(l+r)>>1;
     buildtree(l,mid,cur<<1);
     buildtree(mid+1,r,cur<<1|1);
     a[cur]=min(a[cur<<1],a[cur<<1|1]);
}
void pushdown(int cur)
{
     if(lazy[cur]==0)return;
     lazy[cur<<1]+=lazy[cur];
     lazy[cur<<1|1]+=lazy[cur];
     a[cur<<1]+=lazy[cur];
     a[cur<<1|1]+=lazy[cur];
     lazy[cur]=0;
}
void updata(int l,int r,int L,int R,int cost,int cur)
{
     if(L<=l&&r<=R)
     {
         a[cur]+=cost;
         lazy[cur]+=cost;
         return ;
     }
     int mid=(l+r)>>1;
     pushdown(cur);
     if(L<=mid)updata(l,mid,L,R,cost,cur<<1);
     if(R>=mid+1)updata(mid+1,r,L,R,cost,cur<<1|1);
     a[cur]=min(a[cur<<1],a[cur<<1|1]);
}
int query(int l,int r,int L,int R,int num,int cur)
{
    if(L<=l&&r<=R&&a[cur]>=num)return r-l+1;
    if(l==r)return a[cur]>=num;
    int mid=(l+r)>>1,ans=0;
    pushdown(cur);
    if(L<=mid)ans+=query(l,mid,L,R,num,cur<<1);
    if(R>=mid+1)ans+=query(mid+1,r,L,R,num,cur<<1|1);
    return ans;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)k[i]=read();
    buildtree(1,n,1);
    for(int i=1;i<=m;i++)
    {
         cin>>c;x=read();y=read();z=read();
         if(c=='M')updata(1,n,x,y,z,1);
         if(c=='A')printf("%d\n",query(1,n,x,y,z,1));
    }
    system("pause");
    return 0;
}