题解：P8231 [AGM 2022 资格赛] 农场

· · 题解

思路

仔细读题就会发现，田地里的小麦数不会增加，只会减少。但是如果是一般的题目，肯定是既会增加又会减少的，这题只会减少，其实就是在提示我们，这题可以使用二分，对于每一个询问，我们二分最大能盈利的天数，然后用二维树状数组维护单点加，区间查，可以得到一个 O(QT\log T\cdot\log n\log m)，其中前半部分是二分的复杂度，后半部分是二维树状数组单次修改的时间复杂度。

整体二分

刚才的算法时间复杂度太高了，考虑优化。仔细分析一下，发现刚才的算法低效的原因是对于每一个询问，都要进行二分，且很多次操作都是重复的，那么有没有方法，能同时对全部询问进行二分，有的兄弟有的，这便是我们今天的主题——整体二分。

什么是整体二分？

整体二分，顾名思义，就是对整体进行二分（废话），其实整体二分就是一种针对有多个可以二分的询问，然后二分答案，根据答案的可行性将询问进行分类的一种分治技术。比如对于一组询问，我们猜这些询问的答案都是 mid，然后就根普通的二分一样，将每个询问判断一下，根据该答案是否可行分为两组，然后分别递归求解。

整体二分的具体应用

比如这题，我们就可以用整体二分高效求解，伪代码如下：

定义 solve(l,r,Q) 表示已知答案值域范围为 [l,r]，求解集合 Q 中的所有询问

solve(l,r,Q):
  if(l = r):
     for(遍历 q = 集合 Q 中的询问):
        q.ans=l
     return
  mid = (l + r) / 2
  定义 Q1 表示可行当前答案 mid 可行的询问集合
  定义 Q2 表示可行当前答案 mid 不可行的询问集合
  for(遍历 i = l to mid):
     遍历第 i 天的所有操作并执行
  for(遍历 q = 集合 Q 中的询问)：
     按照答案 mid 是否可行将 q 插入 Q1 或 Q2
  for(遍历 i = l to mid):
     遍历第 i 天的所有操作并撤销
  solve(l,mid,Q1)
  solve(mid+1,r,Q2)

注意这并不是整体二分的标准模版，只是这题这么做比较方便，真正的整体二分模板应该是要将修改和查询同时处理，所以整体二分还可以轻松实现带修，这里就不细讲了。

整体二分的时间复杂度证明

相信大部分新手跟我一样，会以为如果集合 Q 划分得不平均的话会影响整体二分的时间复杂度。但实际上，整体二分的时间复杂度跟 Q 划分没有关系。在这里我用最通俗的话讲明白整体二分的时间复杂度，不推式子，不画递归树，也不用主定理。首先，对于递归的每一层，无论 Q 被怎么划分，每一层询问的总数是不会变的，同理，如果是根据值域进行修改或者查询的，那么修改和查询的总数也是不会变的，这意味着每一层的修改数都是固定的，所以整体二分的时间复杂度就是 O(\log V\cdot N\cdot k)，其中 V 是值域，N 是查询次数（在标准的整体二分中，修改和查询操作统称为查询操作），k 是每次查询的时间复杂度。

代码

#include<bits/stdc++.h>
#define tm hkslakd
#define int long long
using namespace std;
const int maxn=5e4+5;
int n,m,x,y,z,c[505][505],tm,tq,ans[maxn];
int lowbit(int x){return x&-x;}
void add(int x,int y,int v){
    for(int i=x;i<=n;i+=lowbit(i))
    for(int j=y;j<=m;j+=lowbit(j)) c[i][j]+=v;
}
int query(int x,int y){
    int res=0;
    for(int i=x;i;i-=lowbit(i))
    for(int j=y;j;j-=lowbit(j)) res+=c[i][j];
    return res;
}
int qsum(int x1,int y1,int x2,int y2){
    return query(x2,y2)+query(x1-1,y1-1)-
           query(x2,y1-1)-query(x1-1,y2);
}
struct qry{
    int x1,y1,x2,y2,p,id;
}qq[maxn],qq1[maxn],qq2[maxn];
struct mdf{
    int x,y,z;
};
vector<mdf> qm[maxn];
void solve(int l,int r,int ql,int qr){
    if(l==r){
        for(int i=ql;i<=qr;i++) ans[qq[i].id]=l;
        return ;
    }
    int mid=l+r>>1,cnt1=0,cnt2=0;
    for(int i=l;i<=mid;i++){
        for(auto&[x,y,z]:qm[i]) add(x,y,z);
    }
    for(int i=ql;i<=qr;i++){
        int sum=qsum(qq[i].x1,qq[i].y1,qq[i].x2,qq[i].y2);
        if(sum>qq[i].p) qq1[++cnt1]=qq[i];
        else qq2[++cnt2]=qq[i],qq2[cnt2].p-=sum;
    }
    for(int i=l;i<=mid;i++){
        for(auto&[x,y,z]:qm[i]) add(x,y,-z);
    }
    for(int i=ql;i<ql+cnt1;i++) qq[i]=qq1[i-ql+1];
    for(int i=ql+cnt1;i<=qr;i++) qq[i]=qq2[i-ql-cnt1+1];
    solve(l,mid,ql,ql+cnt1-1);
    solve(mid+1,r,ql+cnt1,qr);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        cin>>x;
        add(i,j,x);
    }
    cin>>tq;
    for(int i=1;i<=tq;i++){
        cin>>qq[i].x1>>qq[i].y1>>qq[i].x2>>qq[i].y2>>qq[i].p;
        qq[i].id=i;qq[i].p=qsum(qq[i].x1,qq[i].y1,qq[i].x2,qq[i].y2)-qq[i].p;
    }
    memset(c,0,sizeof c);
    cin>>tm;
    for(int i=1;i<=tm;i++){
        int qwq;cin>>qwq;
        while(qwq--){
            cin>>x>>y>>z;
            qm[i].push_back({x,y,z});
        }
    }
    solve(0,tm+1,1,tq);
    for(int i=1;i<=tq;i++){
        if(ans[i]==0) cout<<0<<' ';
        else if(ans[i]==tm+1) cout<<-1<<' ';
        else cout<<ans[i]-1<<' ';
    }
    return 0;
}