2018 China Collegiate Programming Contest Final (CCPC-Final 2018) Topic Link

The thinking of this question is really a step by step approach to the answer, thinking for a long time.

1. Category and Search Sets to Divide Relations into Sets

First of all, when we see the contradiction, the first thing we think about is the category and collection. Of course, because this problem is not compulsory online, we can also directly use the complexity O(N) bipartite graph to complete this processing. We divide so many interrelated points into multiple sets, each of which has one (because there is only one point in the set) or two camps.

Secondly, it is not difficult to think of dealing with the maximum and minimum values of each joint set, but because it is uncertain which camp, if you choose Camp 0 with the node, then all other points are the corresponding camps; if the root node chooses Camp 1, then the other nodes are the anti-selection, so it is maintained. The maximum and minimum values of each state are also collected.

2. Enumeration of minimum (maximum is also possible)

After dealing with this problem and collecting it, we can decompose it (divide and conquer it), we can think of it as a group of sets, we know the maximum and minimum (the maximum and minimum of each set). Now for such a group of disordered intervals, it is very difficult to operate, but if we do one of them. The dimension becomes ordered, so we can look up another dimension. So, the way to deal with this is to sort the minimum values of each set in descending order.

How can we find such an answer? Then we need to control the maximum. We put the maximum into the data structure to maintain it. We traverse the minimum one by one, until there are enough points in it, then we can calculate the answer. The answer is the maximum of the "maximum" in the data structure at this time, then subtract the enumeration at this time. The minimum value to be reached.

In this case, the "maximum" refers to the {minimum, maximum} in the corresponding set (because there are actually two equal sets), and if both of them are put into the data structure, we will take smaller ones, because this will be closer to the lower limit and make the answer smaller.

3. Data Structure Maintenance Maximum (Line Segment Tree)

Here, we just need to maintain the maximum value. We can handle the above and maintain the maximum "maximum value".

 

To sum up:

• First, I deal with the opposition of relations. I use categories and collect them, and then put them into the collection.
• According to each of the camps we collected together, we listed the 0 and 1 camps and distributed different sets.
• Now the set group is processed twice as many as the number of sets to be collected.
• For all sets, we arrange them in descending order of minimum value.
• Enumerate the minimum value from the beginning to the end, and then put the maximum value into the data structure for maintenance.
• If the set is the same and the set is looked up, we put it into the data structure, which should be the minimum "maximum value";
• If it's a collection of different and searched sets, we record the number. When the number put in is equal to the number of searched sets, we need to calculate the answer.

 

My Code:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 2e5 + 7, IIF = 2e9 + 7;
int N, M, root[maxN], team[maxN], cnt, vis[maxN], _UP;
struct Point
{
    int x, y;
    Point(int a=0, int b=0):x(a), y(b) {}
}a[maxN];
int fid(int x)
{
    if(x == root[x]) return x;
    int tmp = root[x];
    root[x] = fid(root[x]);
    team[x] = (team[x] + team[tmp]) & 1;
    return root[x];
}
struct node   //0 is the original state and 1 is the inverted state
{
    int minn, maxx, id;
    node(int a=INF, int b=-INF, int c=0):minn(a), maxx(b), id(c) {}
    friend bool operator < (node e1, node e2) { return e1.minn == e2.minn ? e1.maxx < e2.maxx : e1.minn > e2.minn; }
}t[maxN<<1];
int tree[maxN<<2], in_tree[maxN], in_maxx[maxN];
void buildTree(int rt, int l, int r)
{
    tree[rt] = -INF;
    if(l == r) return;
    int mid = HalF;
    buildTree(Lson); buildTree(Rson);
}
inline void pushup(int rt) { tree[rt] = max(tree[lsn], tree[rsn]); }
void update(int rt, int l, int r, int qx, int val)
{
    if(l == r) { tree[rt] = val; return; }
    int mid = HalF;
    if(qx <= mid) update(Lson, qx, val);
    else update(Rson, qx, val);
    pushup(rt);
}
inline void init()
{
    cnt = _UP = 0;
    for(int i=1; i<=N; i++)
    {
        root[i] = i;
        team[i] = 0;
        vis[i] = 0;
    }
}
int main()
{
    int T; scanf("%d", &T);
    for(int Cas=1; Cas<=T; Cas++)
    {
        scanf("%d%d", &N, &M);
        init();
        bool flag = true;
        for(int i=1, u, v, fa_u, fa_v; i<=M; i++)
        {
            scanf("%d%d", &u, &v);
            if(!flag) continue;
            fa_u = fid(u); fa_v = fid(v);
            if(fa_u != fa_v)
            {
                root[fa_v] = fa_u;
                team[fa_v] = (team[u] + 1 - team[v]) & 1;
            }
            else if(team[u] == team[v]) flag = false;
        }
        for(int i=1, u; i<=N; i++)
        {
            scanf("%d%d", &a[i].x, &a[i].y);
            if(!flag) continue;
            u = fid(i);
            if(!vis[u])
            {
                cnt += 2;
                vis[u] = cnt - 1;
                if(!team[i])
                {
                    t[cnt - 1] = node(a[i].x, a[i].x, ++_UP);
                    t[cnt] = node(a[i].y, a[i].y, _UP);
                }
                else
                {
                    t[cnt - 1] = node(a[i].y, a[i].y, ++_UP);
                    t[cnt] = node(a[i].x, a[i].x, _UP);
                }
                in_tree[_UP] = false;
            }
            else
            {
                if(!team[i])
                {
                    t[vis[u]].minn = min(t[vis[u]].minn, a[i].x);
                    t[vis[u]].maxx = max(t[vis[u]].maxx, a[i].x);
                    t[vis[u] + 1].minn = min(t[vis[u] + 1].minn, a[i].y);
                    t[vis[u] + 1].maxx = max(t[vis[u] + 1].maxx, a[i].y);
                }
                else
                {
                    t[vis[u]].minn = min(t[vis[u]].minn, a[i].y);
                    t[vis[u]].maxx = max(t[vis[u]].maxx, a[i].y);
                    t[vis[u] + 1].minn = min(t[vis[u] + 1].minn, a[i].x);
                    t[vis[u] + 1].maxx = max(t[vis[u] + 1].maxx, a[i].x);
                }
            }
        }
        printf("Case %d: ", Cas);
        if(!flag) { printf("IMPOSSIBLE\n"); continue; }
        buildTree(1, 1, _UP);
        sort(t + 1, t + cnt + 1);
        int sum = 0, _id = 0, ans = IIF;
        for(int i=1; i<=cnt; i++)
        {
            if(sum == _UP)
            {
                if(t[i].maxx < t[in_maxx[t[i].id]].maxx) update(1, 1, _UP, in_tree[t[i].id], t[i].maxx);
                ans = min(ans, tree[1] - t[i].minn);
            }
            else
            {
                if(!in_tree[t[i].id])
                {
                    sum++; in_tree[t[i].id] = ++_id; in_maxx[t[i].id] = i;
                    update(1, 1, _UP, _id, t[i].maxx);
                    if(sum == _UP) ans = min(ans, tree[1] - t[i].minn);
                }
                else if(t[i].maxx < t[in_maxx[t[i].id]].maxx) update(1, 1, _UP, in_tree[t[i].id], t[i].maxx);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}