C. Maximal Intersection

선분 n개가 주어진다.

이 중 하나를 뺐을 때 나머지 모든 선분의 교집합의 길이의 최대값을 출력하는 문제.

sqrt decompostion을 썼는데 알고보니 최대값, 최대값 다음값, 최소값, 최소값 다음값 네개만 가지고 있으면 되는 문제였다.

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
 
int n;
pair<int, int> arr[300001];
int min_v[600], max_v[600];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    int siz = sqrt(n);
    fill(min_v, min_v + 599, 2e9);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i].first >> arr[i].second;
        min_v[i / siz] = min(min_v[i / siz], arr[i].second);
        max_v[i / siz] = max(max_v[i / siz], arr[i].first);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        // a[i]를 제외한다면
        int a, b, minv, maxv;
        // 0 ~ i-1, i+1~n-1
        minv = 2e9;
        maxv = 0;
        // l
        a = 0; b = i - 1;
        while (a%siz != 0 && a <= b) {
            minv = min(minv, arr[a].second);
            maxv = max(maxv, arr[a++].first);
        }
        while ((b + 1) % siz != 0 && a <= b) {
            minv = min(minv, arr[b].second);
            maxv = max(maxv, arr[b--].first);
        }
        while (a <= b) {
            minv = min(minv, min_v[a/siz]);
            maxv = max(maxv, max_v[a/siz]);
            a += siz;
        }
        // r
        a = i + 1; b = n - 1;
        while (a%siz != 0 && a <= b) {
            minv = min(minv, arr[a].second);
            maxv = max(maxv, arr[a++].first);
        }
        while ((b + 1) % siz != 0 && a <= b) {
            minv = min(minv, arr[b].second);
            maxv = max(maxv, arr[b--].first);
        }
        while (a <= b) {
            minv = min(minv, min_v[a / siz]);
            maxv = max(maxv, max_v[a / siz]);
            a += siz;
        }
        ans = max(ans, minv - maxv);
    }
    cout << ans;
    return 0;
}