ACM-ICPC 2018 徐州赛区网络预赛 Trace【线段树】

题目大意，这个题就是给你若干个点，这些点与坐标轴围成一个矩形，然后后面的矩形可以覆盖前面的矩形，问最后还留在平面中的线段的长度是多少

分析：离散化以后倒过来扫点，比如说求x，就用线段树维护当前 [y,inf]区间内最大的x，即为maxx
那么如果 x>maxx 那么其贡献就位 maxx-x ；并且更新y点的值为x
y同理；

#include <bits/stdc++.h>
using namespace std;
const int maxn = 50050;
const int inf = 0x3f3f3f3f;
typedef long long ll;
struct Point {
    int x, y;
};
Point p[maxn];
int n;
vector<int>vx, vy;
inline int getIDx(int x) { return lower_bound(vx.begin(), vx.end(), x) - vx.begin() ; }
inline int getIDy(int x) { return lower_bound(vy.begin(), vy.end(), x) - vy.begin() ; }

struct Node
{
    int l, r;
    int val;
}node[4 * maxn][2];
void pushup(int root, int k)
{
    node[root][k].val = max(node[root * 2][k].val, node[root * 2 + 1][k].val);
}
void build(int root, int l, int r, int k)
{
    if (l>r)return;
    node[root][k].l = l;
    node[root][k].r = r;
    node[root][k].val = 0;
    if (l == r)return;
    else
    {
        int mid = l + (r - l) / 2;
        build(root * 2, l, mid, k);
        build(root * 2 + 1, mid + 1, r, k);
        pushup(root, k);
    }
}
void update(int root, int pos, int val, int k)
{
    if (node[root][k].l == node[root][k].r)
    {
        node[root][k].val = val;
        return;
    }
    int mid = node[root][k].l + (node[root][k].r - node[root][k].l) / 2;
    if (pos <= mid)update(root * 2, pos, val, k);
    if (pos>mid) update(root * 2 + 1, pos, val, k);
    pushup(root, k);
}
int query(int root, int st, int ed, int k)
{
    int l = node[root][k].l;
    int r = node[root][k].r;
    if (st>r || ed<l)return 0;
    if (st <= l && ed >= r)return node[root][k].val;
    else
    {
        int ans = 0;
        ans = max(ans, query(root * 2, st, ed, k));
        ans = max(ans, query(root * 2 + 1, st, ed, k));
        return ans;
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &p[i].x, &p[i].y);
        vx.push_back(p[i].x);
        vy.push_back(p[i].y);
    }
    vx.push_back(0);
    vy.push_back(0);
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    sort(vy.begin(), vy.end());
    vy.erase(unique(vy.begin(), vy.end()), vy.end());
    ll ansx = 0, ansy = 0;
    build(1, 0, n, 0);
    build(1, 0, n, 1);
    for (int i = n; i >= 1; i--)
    {
        int x = getIDx(p[i].x);
        int y = getIDy(p[i].y);
        int t = query(1, x, n, 0);
        int q = query(1, y, n, 1);
        //cout << " maxx = " << t << " maxy=" << q << endl;
        if (t<y) { ansy += vy[y] - vy[t]; update(1, x, y, 0); }
        if (q<x) { ansx += vx[x] - vx[q]; update(1, y, x, 1); }
    }
    ll allans = ansx + ansy;
    printf("%lld\n", allans);
    return 0;
}