先求出前缀和数组sum[i]：在 $[1,i]$的范围内矩形的面积之和。

然后根据不同做法找到分界点。

$O(R)$ 枚举

直接枚举分界点，判断左右两边的值符合条件时输出答案即可。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

#define x first
#define y second

const int N = 1e6 + 10, mod = 1e9 + 7;

LL sum[N];

void solve()
{
    int R, n;
    cin >> R >> n;
    for(int i = 0; i < n; i ++)
    {
        int l, t, w, h;
        cin >> l >> t >> w >> h;
        sum[l + 1] += h;
        sum[l + w + 1] -= h;
    }
    
    for(int i = 1; i <= R; i ++)
        sum[i] += sum[i - 1];
    for(int i = 1; i <= R; i ++)
        sum[i] += sum[i - 1];
    
    int idx = 0;    
    for(int i = 1; i <= R; i ++)
        if(sum[i] >= sum[R] - sum[i])
        {
            idx = i;
            break;
        }
    
    while(idx < R && sum[idx] == sum[idx + 1])
        idx ++;
    cout << idx << endl;
}

int main()
{
    int t = 1;
    // scanf("%d", &t);
    while(t --)
        solve();
}

$O(R)$ 二分

通过二分枚举分界点，需要注意的是由于我们要找到最右边的符合条件的分界点，所以需要 $2$ 次二分。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

#define x first
#define y second

const int N = 1e6 + 10, mod = 1e9 + 7;

LL sum[N];

void solve()
{
    int R, n;
    cin >> R >> n;
    for(int i = 0; i < n; i ++)
    {
        int l, t, w, h;
        cin >> l >> t >> w >> h;
        sum[l + 1] += h;
        sum[l + w + 1] -= h;
    }
    
    for(int i = 1; i <= R; i ++)
        sum[i] += sum[i - 1];
    for(int i = 1; i <= R; i ++)
        sum[i] += sum[i - 1];
    
    int l = 1, r = R;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(sum[mid] >= sum[R] - sum[mid]) r = mid;
        else l = mid + 1;
    }
    
    LL t = sum[l];
    r = R;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(sum[mid] == t) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
}

int main()
{
    int t = 1;
    // scanf("%d", &t);
    while(t --)
        solve();
}