[AGM 2022 资格赛] 农场

qwqUwU · 2022-07-28 15:21:09 · 题解

农场题解报告

题意简述

给定 $Q$ 个子矩阵，定义一个子矩阵 “盈利” 当且仅当子矩阵内格子的权之和不小于给定值 $b_i$。给出 $T$ 天，每天发生若干事件形如： - $a_{x,y} \leftarrow a_{x,y}-z

对于每个子矩阵，求出一个时间 t ，满足：

第 t 天结束时该子矩阵仍然 “盈利”。
第 t+1 天结束时该子矩阵不 “盈利”。
若第 T 天结束时仍然盈利，则输出 -1。

题目分析

先评价一下这道题吧。

这道题是一道可以作为整体二分模板题的好题。

个人认为这题整体二分比较直接好想，不像有些题会涉及到值域等略微复杂的东西。

先来讲一下整体二分是什么。

顾名思义，你可以把它理解成若干次二分一起做。

我们先来想一个子问题：

那这道题就有一个很简单的做法：

二分第几次事件后开始不 “盈利” ，利用二维树状数组动态维护单点修改与子矩阵查询。

当然，这里要时刻注意哪些事件做了哪些事件没做。

当然不难证明这里的时间复杂度是 O(\sum p \log n \log m) 的。

那么，当 Q 大起来时，有一种直接的想法是跑 Q 次上述操作。

当然这样时间复杂度是 O(Q \sum p \log n \log m) 的，考虑优化。

一般而言，优化一般会往几个方向：

减少重复/无用操作。（如本题）
提高信息利用率（如 KMP）。

而本题主要旨在减少重复操作。

我们考虑单次操作的时间复杂度瓶颈在哪。

对于每次二分判定，我们都需要来回改变当前当前做到哪个“事件”，以确保能够正确判定。

但消耗如此多的时间只判定一个显得太亏了。

因此我们考虑每次二分都一次性把所有子矩阵分成“仍然盈利”与“不盈利了”两类，然后再分治两边。

这，就是整体二分。

本质上来说，整体二分的本质就是：一次修改，多次判定。

也因此，使用整体二分有以下几个要求：

单词询问二分可解。
支持离线
修改的时间复杂度高，而判定的复杂度低。

关于时间复杂度，你可以把它近似理解成 Q=1 的时间复杂度。

具体一点是 O(( \sum p+Q) \log n \log m)，足矣通过本题。

上代码：

#include<bits/stdc++.h>
#define ll long long
#define lb(x) (x&-x)
#define mid (l+r>>1)
using namespace std;
const int N=510;
const int SUMQ=1e5+10;
const int MAXQ=5e4+10;
const ll INF=1e18;
inline ll read(){
    ll x=0,f=1,c=getchar();
    while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
int n,m,Q,T,tot,ans[MAXQ];
struct Field{
    int x1,y1,x2,y2,id;
    ll k;
}q[MAXQ],q1[MAXQ],q2[MAXQ];
struct Rain{
    int x,y,t;
    ll k;
}rain[SUMQ+N*N];
ll t[N][N];
inline void Insert(int x,int y,ll k){
    for(int i=x+1;i<=n+1;i+=lb(i))
        for(int j=y+1;j<=m+1;j+=lb(j))
            t[i][j]+=k;
}
inline ll query(int x,int y,ll A=0){
    for(int i=x+1;i;i-=lb(i))
        for(int j=y+1;j;j-=lb(j))
            A+=t[i][j];
    return A;
}//这里x,y加一是为了防止x=0或y=0的死循环
inline void solve(int L,int R,int l,int r){
    if(L>R){
        for(int i=l;i<=r;i++)Insert(rain[i].x,rain[i].y,rain[i].k);
        return ;
    }
    if(l==r){
        for(int i=L;i<=R;i++)ans[q[i].id]=rain[l].t;
        Insert(rain[l].x,rain[l].y,rain[l].k);
        return;
    }
    for(int i=l;i<=mid;i++)Insert(rain[i].x,rain[i].y,rain[i].k);
    int top1=0,top2=0;
    for(int i=L;i<=R;i++){
        ll res=query(q[i].x2,q[i].y2)-query(q[i].x2,q[i].y1-1)-query(q[i].x1-1,q[i].y2)+query(q[i].x1-1,q[i].y1-1);
        if(res>=q[i].k)q2[++top2]=q[i];
        else q1[++top1]=q[i];
    }
    for(int i=1;i<=top1;i++)q[L+i-1]=q1[i];
    for(int i=1;i<=top2;i++)q[L+top1+i-1]=q2[i];
    for(int i=l;i<=mid;i++)Insert(rain[i].x,rain[i].y,-rain[i].k);
    solve(L,L+top1-1,l,mid);
    solve(L+top1,R,mid+1,r);
}//整个函数还是挺好理解的，一定要注意每个“事件”是否已经被计算了。
int main(){ 
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            Insert(i,j,read());
    Q=read();
    for(int i=1;i<=Q;i++)q[i]={read(),read(),read(),read(),i,read()};
    T=read();
    for(int i=1;i<=T;i++){
        int q=read();
        for(int j=1;j<=q;j++)
            rain[++tot]={read(),read(),i-1,-read()};//这里i-1是因为当天结束还能盈利才会统计哪一天，而ans出来的是哪次事件结束后就“不盈利”了。
    }
    rain[++tot].t=-1;
    solve(1,Q,0,tot);
    for(int i=1;i<=Q;i++)
        printf("%d ",ans[i]);
    return 0;
}

后记：

有不少题解习惯把“修改”和“询问”放在一起进行二分，我觉得那么写有些难以理解，且我这种写法与他们的写法效率相差也小，因此用了这种直白一点的写法。

总而言之，做整体二分的题目还是要多想想我要二分那些东西，L\sim R 与 l\sim r 到底表达的是什么，切忌一味的对着题解码。

本人也算是整体二分的初学者，如有错误欢迎指出。

That's all.Thanks.

[AGM 2022 资格赛] 农场

农场 题解报告

题意简述

题目分析

后记：

农场题解报告