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

2019yyy · 2025-12-04 21:12:10 · 题解

整体二分板子。

考虑 q=1 的时候我们要怎么做？答案是二分答案，用一个二维树状数组维护矩形和这种东西。

现在 q 大一些，套一个整体二分就可以了。

注意无解的判法，我的判法是在最后加上一个时间为 -1 的修改，这样跑完前面所有还不行就会跑到最后这个无解的修改上。

#include<bits/stdc++.h>
using namespace std;
namespace MyGO{
    #define int long long
    bool NagasakiSoyo;
    const int INF=0x3f3f3f3f3f3f3f3f;
    struct BitArr{
        int lowbit(int x){ return (x&(-x)); }
        int tr[510][510],N,M;
        void init(int n,int m){
            N=n;M=m;
            for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) tr[i][j]=0;
        }
        void modify(int x,int y,int v){
            if(x==0 or y==0) return ;
            for(int i=x;i<=N;i+=lowbit(i)){
                for(int j=y;j<=M;j+=lowbit(j)){
                    tr[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+=tr[i][j];
                }
            }
            return res;
        }
    } ba;
    struct Query{ int x,y,xx,yy,v,id; } q[110000];
    struct Modi{ int x,y,v,t; } Q[110000];
    int ans[110000];
    void solve(int l,int r,vector<Query> qr){
        if(l>r or qr.empty()) return ;
        if(l==r){
            for(auto p:qr) ans[p.id]=Q[l].t;
            return ;
        }
        int mid=(l+r)>>1;
        for(int i=l;i<=mid;i++) ba.modify(Q[i].x,Q[i].y,-Q[i].v);
        vector<Query> q1,q2;
        for(auto p:qr){
            int x=p.x,y=p.y,xx=p.xx,yy=p.yy;
            int t=ba.query(x,y)-ba.query(xx-1,y)-ba.query(x,yy-1)+ba.query(xx-1,yy-1);
            if(t>=p.v) q2.push_back(p);
            else q1.push_back(p);
        }
        solve(mid+1,r,q2);
        for(int i=l;i<=mid;i++) ba.modify(Q[i].x,Q[i].y,Q[i].v);
        solve(l,mid,q1);
    }
    bool ChihayaAnon;
    void main(){
        cerr<<((&NagasakiSoyo)-(&ChihayaAnon))/1048576.0<<'\n';
        // freopen("P8231.in","r",stdin);
        // freopen("P8231.out","w",stdout);

        int n,m;cin>>n>>m;ba.init(n,m);
        for(int i=1;i<=n;i++) for(int j=1,v;j<=m;j++) cin>>v,ba.modify(i,j,v);
        int K;cin>>K;vector<Query> qr;
        for(int i=1;i<=K;i++) cin>>q[i].xx>>q[i].yy>>q[i].x>>q[i].y>>q[i].v,q[i].id=i,ans[i]=-1,qr.push_back(q[i]);
        int T,cnT=0;cin>>T;
        for(int i=1;i<=T;i++){
            int p;cin>>p;
            for(int j=1;j<=p;j++){
                cnT++;
                cin>>Q[cnT].x>>Q[cnT].y>>Q[cnT].v;Q[cnT].t=i-1;
            }
        }
        Q[++cnT].t=-1;
        solve(0,cnT,qr);
        for(int i=1;i<=K;i++) cout<<ans[i]<<" ";
        cout<<'\n';
        cerr<<1.0*clock()/CLOCKS_PER_SEC*1000.0<<'\n';
    }
    #undef int
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    MyGO::main();
    return 0;
}