花园 3 / Garden 3 JOI Final 2026

[JOI Final 2026] 花园 3 / Garden 3

有一个长 $H$ 宽 $W$ 的矩形花园。

有 $n$ 次操作。

第 $i$ 次操作会将矩形范围 $U_i\le x\le D_i,L_i\le y\le R_i$ 的 $(x,y)$ 的点权 $+C_i$，初始时所有点权均为 $0$。

给定常数 $X$，每次修改后，求面积最小的矩形的面积使得其可以覆盖所有点权 $\ge X$ 的点。

$H,W\le 10^9,n\le 2\times10^5$；

$C_i\le 10^9,X\le 2\times 10^{14}$。

这题需要仔细分析就能轻松写出。

首先将求面积转化为求出 $\ge X$ 的点中 $x$ 坐标和 $y$ 坐标最小/最大的坐标是多少。

显然这四个本质相同，因此只考虑求出 $x$ 坐标最小的。

然后由于答案必然越来越小，因此可以考虑扫描线，枚举 $x$ 坐标，并确定那一段区间的答案会是他。

先将坐标离散化，同时使用线段树维护区间 $+$ 区间 $\max$，当矩形出现或消失时对线段树进行更改。

不妨设枚举到了 $x$，那么由于答案越来越小，因此维护一个变量 $t$ 表示最后一个没有确定答案的询问是谁。

对于 $x$，我们可以不断执行以下过程：

• 求出线段树上的最大值，如果 $<X$ 则退出；
• 一段区间内的答案必然是 $x$，我们要找出这个区间；
• 于是我们应该维护目前被加入线段树的所有矩形的编号，并找到最大的；
• 这个可以使用 set 维护；
• 那么设最大编号为 $T$，那么区间 $[T,t]$ 内的答案都是 $x$；
• 接着令 $t\leftarrow T-1$，同时在线段树和 set 中删除 $T$。

这样就可以求出所有区间的答案了。

其余同理。

#include <bits/stdc++.h>
using namespace std;
const int N=400010;
int ans[N],n,m,L[N],R[N],am[N],ss,c[N],p[N],np[N],R2[N],len[N];
struct node{int x,y;}q[N];
int get(int x){return lower_bound(am+1,am+1+ss,x)-am;}
int nn;
void clear(int n){nn=n;for(int i=1;i<=n;i++)c[i]=0;}
void add(int x,int y){for(int i=x;i<=nn;i+=(i&-i))c[i]+=y;}
int query(int x){int cnt=0;for(int i=x;i>=1;i-=(i&-i))cnt+=c[i];return cnt;}
int query(int l,int r){return l>r?0:query(r)-query(l-1);}
vector<node>v[N],V[N];
set<int>S;
using pii=pair<int,int>;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",L+i,R+i),am[++ss]=L[i],am[++ss]=R[i],len[i]=R[i]-L[i];
    sort(am+1,am+1+ss);ss=unique(am+1,am+1+ss)-am-1; 
    for(int i=1;i<=n;i++)L[i]=get(L[i]),R[i]=get(R[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&q[i].x,&q[i].y);
    for(int i=1;i<=n;i++)p[i]=i;
    sort(p+1,p+1+n,[](int x,int y){return L[x]==L[y]?R[x]<R[y]:L[x]<L[y];});
    for(int i=1;i<=n;i++)np[p[i]]=i;
    for(int i=1;i<=m;i++)if(len[q[i].x]>=q[i].y)
        V[np[q[i].x]-1].push_back({get(am[L[q[i].x]]+q[i].y),i});
    for(int i=1;i<=n;i++)v[np[i]].push_back({R[i],1});
    clear(ss);
    for(int i=1;i<=n;i++){
        for(node j:v[i])add(j.x,j.y);
        for(node j:V[i])ans[j.y]+=query(j.x,ss);
    }
    priority_queue<pii,vector<pii>,greater<pii>>q1,q2;
    R2[1]=-1;
    for(int i=1;i<n;i++)R2[i+1]=max(R2[i],R[p[i]]);
    for(int i=1;i<=n;i++){
        q1.push({am[R[i]]-am[L[i]],np[i]});
        q2.push({am[R2[np[i]]]-am[L[i]],np[i]});
    }
    ss=0;
    for(int i=1;i<=m;i++)am[++ss]=q[i].y;
    sort(am+1,am+1+ss);ss=unique(am+1,am+1+ss)-am-1;
    for(int i=1;i<=ss;i++)v[i].clear();
    for(int i=1;i<=m;i++)if(len[q[i].x]>=q[i].y)
        v[get(q[i].y)].push_back({q[i].x,i});
    S.insert(n+1);
    clear(n);
    for(int i=1;i<=n;i++)add(i,1);
    for(int i=1;i<=ss;i++){
        while(!q1.empty()){
            pii t=q1.top();
            int x=t.second,y=t.first;
            if(y>=am[i])break;
            q1.pop();
            add(x,-1);
        }
        while(!q2.empty()){
            pii t=q2.top();
            int x=t.second,y=t.first;
            if(y>=am[i])break;
            q2.pop();
            S.insert(x);
        }
        for(node j:v[i]){
            int x=j.x,id=j.y;
            int t=*S.upper_bound(np[x]);
            ans[id]+=query(np[x]+1,t-1);
        }
    }
    for(int i=1;i<=m;i++)ans[i]++;
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}