LG-P8858 折线 Solution

• LG-P8858 折线 Solution
  • 更好的阅读体验戳此进入
    • 题面
    • Solution
    • 赛时 Code
  • UPD

更好的阅读体验戳此进入

题面

从从 $ (0, 0) $ 到 $ (10^{100}, 10^{100}) $ 的矩形里有正偶数 $ n $ 个整点，需构造一条从 $ (0, 0) $ 到 $ (10^{100}, 10^{100}) $ 的折线，要求其每部分都平行于坐标轴，不能经过给定的整点，需要将整块区域分为包含给定整点数量相等的两块，要最小化其整点。输出合法的折线的整点数，保证一定存在如下直线。

Solution

提供一个 $ O(T n \log n) $ 的线段树上二分做法。

首先我们可以考虑观察一下样例和大样例，不难发现所有答案均在 $ [2, 4] $ 之间，以此可猜想答案一定在此区间中，可以尝试感性证明一下：

首先一个折点的话一定无法将矩形分为两块，所以不合法。

两个折点的话即为通过一条直线将矩形分为两半，这条直线可以水平也可以竖直，所以对于这种情况，我们只需要对 $ x $ 坐标和 $ y $ 坐标分别做一个前缀和，然后分别遍历一遍，如果存在一个点 $ i $ 使 $ sum_i = \dfrac{n}{2} $ 那么显然合法，答案为 $ 2 $。

三个折点的话随便画一下就会发现，最终的情况一定是隔离起来一个左上角或者右下角，如图：

考虑如何维护，显然可以把这个东西按照类似二位偏序或者说二维数点来写，先按照 $ x $ 排序，然后把每一段相同的 $ x $ 的所有 $ y $ 都插到权值线段树里，然后在线段树上二分查找是否存在一个前缀刚好等于 $ \dfrac{n}{2} $。然后再把整个顺序反过来插反过来查，找是否存在一个后缀恰好等于 $ \dfrac{n}{2} $，如果能找到那么显然可以通过隔离出来一段左上角或右下角的角落构造合法折线，答案即为 $ 3 $。

如果以上的判断都不合法的话那么显然最终答案即为 $ 4 $，这个通过我们最开始 “面向数据编程” 得到的性质直接得到，也可以考虑画一下，如图：

显然这个时候我们是可以隔离出来任意数量的整点了，比较好理解，考虑一下如果想更多地包含新的点，将中间那块凸起略移动一下 $ x $ 和 $ y $ 即可，感性理解一下即可。

至此我们便以 $ O(T n \log n) $ 的复杂度解决了这道题，还算比较直观，作为 T1 难度挺合理。

赛时 Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define MAXN (510000)

template< typename T = int >
inline T read(void);

int N;
struct Coord{int x, y;}a[MAXN];
int bucx[MAXN], bucy[MAXN];

class SegTree{
private:
    int tr[MAXN << 2];
    #define LS (p << 1)
    #define RS (LS | 1)
    #define MID ((gl + gr) >> 1)
public:
    void Clear(int p = 1, int gl = 1, int gr = N + 1){
        if(gl == gr)return tr[p] = 0, void();
        Clear(LS, gl, MID);
        Clear(RS, MID + 1, gr);
        tr[p] = 0;
    }
    void Pushup(int p){tr[p] = tr[LS] + tr[RS];}
    void Modify(int idx, int v = 1, int p = 1, int gl = 1, int gr = N + 1){
        if(gl == gr)return tr[p] += v, void();
        if(idx <= MID)Modify(idx, v, LS, gl, MID);
        else Modify(idx, v, RS, MID + 1, gr);
        Pushup(p);
    }
    bool QueryR(int val, int cur = 0, int p = 1, int gl = 1, int gr = N + 1){
        // printf("Querying %d ~ %d, cur = %d\n", gl, gr, cur);
        if(cur + tr[p] == val)return true;
        if(gl == gr)return false;
        if(cur + tr[LS] >= val)return QueryR(val, cur, LS, gl, MID);
        else return QueryR(val, cur + tr[LS], RS, MID + 1, gr);
    }
    bool QueryL(int val, int cur = 0, int p = 1, int gl = 1, int gr = N + 1){
        // printf("Querying %d ~ %d, cur = %d\n", gl, gr, cur);
        if(cur + tr[p] == val)return true;
        if(gl == gr)return false;
        if(cur + tr[RS] >= val)return QueryL(val, cur, RS, MID + 1, gr);
        else return QueryL(val, cur + tr[RS], LS, gl, MID);
    }
}st;

int main(){
    // freopen("ex_line2.in", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int T = read();
    while(T--){
        bool flag(false);
        memset(bucx, 0, sizeof(int) * (N + 10)), memset(bucy, 0, sizeof(int) * (N + 10));
        N = read();
        for(int i = 1; i <= N; ++i)
            a[i].x = read() + 1, a[i].y = read() + 1, bucx[a[i].x]++, bucy[a[i].y]++;
        a[N + 1].x = a[N + 1].y = 0;
        for(int i = 1; i <= N; ++i){
            bucx[i] += bucx[i - 1], bucy[i] += bucy[i - 1];
            if(bucx[i] == N >> 1 || bucy[i] == N >> 1){printf("2\n"), flag = true; break;}
        }if(flag)continue;
        sort(a + 1, a + N + 1, [](const Coord &a, const Coord &b)->bool{return a.x == b.x ? a.y < b.y : a.x < b.x;});
        st.Clear();
        for(int i = N; i >= 1; --i){
            st.Modify(a[i].y);
            while(a[i - 1].x == a[i].x)st.Modify(a[--i].y);
            if(st.QueryR(N / 2)){printf("3\n"), flag = true; break;}
        }if(flag)continue;
        st.Clear();
        for(int i = 1; i <= N; ++i){
            st.Modify(a[i].y);
            while(a[i + 1].x == a[i].x)st.Modify(a[++i].y);
            if(st.QueryL(N / 2)){printf("3\n"), flag = true; break;}
        }if(flag)continue;
        printf("4\n");
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_11_22 初稿

update-2022_11_22 修改了一处细节错误

update-2022_11_23 图片被洛谷墙了，换成了洛谷图床