DLUTOJ -1234: Zeratul与塔防游戏(二分+线段树+贪心)

题解

维护长为m的树状数组，先将n次区间修改维护到数组上。

二分答案为q，每次判断需要升级的次数，是否小于k。

我们从左到右遍历塔i，类似manacher/扩展kmp算法一样更新一个当前最右端点nowr，

其实是贪心的思想，代表当前存在一个防御塔能更新到nowr，

对于不需要更新的点i，跳过即可；

需要更新点i的时候，我们就对[i,nowr]区间进行区间更新，显然是最优的。

最大化最小值，二分经典题型，就是check(mid)需要动一动脑筋。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e4+10;
ll bit0[maxn],bit1[maxn],tmp0[maxn],tmp1[maxn],n,m,k;
int range[maxn],nowr;
int lowbit(int x)
{
  return x&(-x);
}
void add(ll *b,int i,ll x)
{
    while(i<=m)
    {
     b[i]+=x;
     i+=lowbit(i);
    }
}
ll sum(ll *b,int i)
{
   ll ans=0;
   while(i>0)
   {
    ans+=b[i];
    i-=lowbit(i);
   }
   return ans;
}
ll ask(ll *bit1,ll *bit0,int l,int r)
{
   ll res=0;
   res+=sum(bit0,r)+sum(bit1,r)*r;
   res-=sum(bit0,l-1)+sum(bit1,l-1)*(l-1);
   return res;
}
void jia(ll *bit1,ll *bit0,int l,int r,ll a)
{
     add(bit0,l,-a*(l-1));
     add(bit1,l,a);
     add(bit0,r+1,a*r);
     add(bit1,r+1,-a);
}
bool check(ll mid)
{
    ll num=0;
    nowr=0;
    for(int i=1;i<=m;++i)
    {
        tmp0[i]=bit0[i];
        tmp1[i]=bit1[i];
    }
    for(int i=1;i<=m;++i)
    {
        ll q=ask(tmp1,tmp0,i,i);
        nowr=max(nowr,range[i]);//当前能到的最右 
        if(q>=mid)continue;
        if(nowr<i)return 0;
        num+=mid-q;
	    jia(tmp1,tmp0,i,nowr,mid-q);
        if(num>k)return 0;
    }
    return 1;
}
ll erfen(ll l,ll r)
{
    while(r-l>1)
    {
        ll mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    return l;
}
int main()
{
  scanf("%lld%lld%lld",&n,&m,&k);
  for(int i=0;i<n;++i)
  {
     int l,r,a;
     scanf("%d%d%d",&l,&r,&a);
     jia(bit1,bit0,l,r,a);
     range[l]=max(range[l],r);
  }
  printf("%lld\n",erfen(0,1e18));
  return 0;
}