官方题解 | Farm

E. Farm

substask 20 pt

可以发现直接暴力时间复杂度为 $O(N\times M\times Q)$，TLE，剪枝（或记忆化搜索）即可。

Subtask 45 pt

考虑使用 $\mathtt{vector}$，每次查询时查找之前每次操作 $1$ 播下的种子即可。

45 pt Code

#include <iostream>
#include <vector>
using namespace std;

struct Seed {
    int x, y;
    int t; // 成熟时间 = 播种时间 + k
    bool picked; // 是否已被采摘
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, Q;
    cin >> N >> M >> Q;

    vector<Seed> seeds;
    int current_time = 0;

    for (int i = 0; i < Q; ++i) {
        int op;
        cin >> op;
        current_time++; // 每次操作时间 +1

        if (op == 1) {
            int x, y, k;
            cin >> x >> y >> k;
            seeds.push_back({x, y, current_time + k, false});
        } else {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;

            int count = 0;
            for (auto& seed : seeds) {
                if (!seed.picked && 
                    seed.x >= x1 && seed.x <= x2 && 
                    seed.y >= y1 && seed.y <= y2 && 
                    seed.t <= current_time) {
                    count++;
                    seed.picked = true; // 标记为已采摘
                }
            }
            cout << count << '\n';
        }
    }

    return 0;
}

时间复杂度：$O(Q^2)$

备注：由于一些原因，对于特殊性质 B 依旧可以通过，因此应当正常得分 30 pt。

Subtask 10 pt（特殊性质 B 正解）

可以发现每次操作 $1$ 中的 $k$ 为 $1$，因此可以直接在每次查询时直接查询每个 $1$ 操作并删除。

Subtask 100 pt

由于存在二维数区间点数问题，我们考虑 K-D Tree 或平衡树。以下为 K-D Tree 解法：

分析 $2$ 种操作的处理：

• 播种操作：将种子信息（坐标 $(x,y)$ 的成熟时间 $t$ 为当前时间加 $k$）插入到 K-D Tree 中。
• 采摘操作：查询矩形区域内所有成熟时间 $\le$​ 当前时间的蔬菜，并标记为已采摘。

但是这样的时间复杂度极限下可能达到 $O(Q^2)$，我们考虑剪枝。

• 每个节点存储子树的最小或最大 $(x,y)$ 坐标和时间信息，用于快速剪枝。
• 使用 lazy tag 表示蔬菜是否已被采摘。
• 在查询时，根据这些信息可以快速跳过不满足条件的子树。

这样我们的时间复杂度为 $O(N\sqrt N)$，大约为 $8\times10^7$。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct pt{
    int x,y,t;
};
struct node{
    int x,y,t,minx,maxx,miny,maxy,mint,maxt,sz;
    bool vis;
    node *l,*r;
    node(pt p){
        x = p.x;
        y = p.y;
        t = p.t;
        minx = maxx = x;
        miny = maxy = y;
        mint = maxt = t;
        sz = 1;
        vis = 0;
        l = r = NULL;
    }
    void change(){
        if(vis){
            minx = miny = mint = 0x3f3f3f3f;
            maxx = maxy = maxt = -0x3f3f3f3f;
            sz = 0;
        }else{
            minx = maxx = x;
            miny = maxy = y;
            mint = maxt = t;
            sz = 1;
        }
        if(l && l -> sz > 0){
            minx = min(minx,l -> minx);
            maxx = max(maxx,l -> maxx);
            miny = min(miny,l -> miny);
            maxy = max(maxy,l -> maxy);
            mint = min(mint,l -> mint);
            maxt = max(maxt,l -> maxt);
            sz += l -> sz;
        }
        if(r && r -> sz > 0){
            minx = min(minx,r -> minx);
            maxx = max(maxx,r -> maxx);
            miny = min(miny,r -> miny);
            maxy = max(maxy,r -> maxy);
            mint = min(mint,r -> mint);
            maxt = max(maxt,r -> maxt);
            sz += r -> sz;
        }
    }
};
node *upd(node *nd,pt p,int dep = 0){
    if(nd == NULL) return new node(p);
    if(dep % 2 == 0){
        if(p.x < nd -> x) nd -> l = upd(nd -> l,p,dep + 1);
        else nd -> r = upd(nd -> r,p,dep + 1);
    }else{
        if(p.y < nd -> y) nd -> l = upd(nd -> l,p,dep + 1);
        else nd -> r = upd(nd -> r,p,dep + 1);
    }
    nd -> change();
    return nd;
}
int query(node *nd,int x1,int x2,int y1,int y2,int cur){
    if(nd == NULL || nd -> sz == 0) return 0;
    if(nd -> maxx < x1 || nd -> minx > x2 || nd -> maxy < y1 || nd -> miny > y2) return 0;
    if(nd -> mint > cur) return 0;
    int cnt = 0;
    if(!nd -> vis){
        if(nd -> x >= x1 && nd -> x <= x2 && nd -> y >= y1 && nd -> y <= y2 && nd -> t <= cur){
            cnt++;
            nd -> vis = 1;
        }
    }
    cnt += query(nd -> l,x1,x2,y1,y2,cur);
    cnt += query(nd -> r,x1,x2,y1,y2,cur);
    nd -> change();
    return cnt;
}
signed main(){
    int n,m,q; cin >> n >> m >> q;
    node *root = NULL;
    for(int i = 1;i <= q;i++){
        int op; cin >> op;
        if(op == 1){
            int x,y,k; cin >> x >> y >> k;
            root = upd(root,{x,y,i + k});
        }else{
            int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
            cout << query(root,x1,x2,y1,y2,i) << "\n";
        }
    }
    return 0;
}

时间复杂度：$O(N\sqrt N)$