计蒜客 Trace（2018 ICPC亚洲区域赛网络赛 徐州 G）（线段树）

There's a beach in the first quadrant. And from time to time, there are sea waves. A wave ( xx , yy ) means the wave is a rectangle whose vertexes are ( 00 , 00 ), ( xx , 00 ), ( 00 , yy ), ( xx , yy ). Every time the wave will wash out the trace of former wave in its range and remain its own trace of ( xx , 00 ) -> ( xx , yy ) and ( 00 , yy ) -> ( xx , yy ). Now the toad on the coast wants to know the total length of trace on the coast after n waves. It's guaranteed that a wave will not cover the other completely.

Input

The first line is the number of waves n(n \le 50000)n(n≤50000).

The next nn lines，each contains two numbers xx yy ,( 0 < x0<x , y \le 10000000y≤10000000 )，the ii-th line means the ii-th second there comes a wave of ( xx , yy ), it's guaranteed that when 1 \le i1≤i , j \le nj≤n ，x_i \le x_jxi​≤xj​ and y_i \le y_jyi​≤yj​ don't set up at the same time.

Output

An Integer stands for the answer.

Hint：

As for the sample input, the answer is 3+3+1+1+1+1=103+3+1+1+1+1=10

样例输入复制

3
1 4
4 1
3 3

样例输出复制

10

题目来源

ACM-ICPC 2018 徐州赛区网络预赛

 

题意：有很多个矩形，后一个矩形会覆盖掉前一个矩形，求剩下的周长和。

解题思路：先考虑X，从后往前考虑，对于每个x,y，查询x~MAXN的最大的Y，然后答案更新y-Y即可。画画图就知道这是对的。Y同理。那么直接用线段树查询就好了，记得离散化一下。

 

#include <iostream>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
typedef long long ll;

int treex[MAXN << 2];
int treey[MAXN << 2];
void pushup(int rt)
{
    treex[rt] = max(treex[rt << 1], treex[rt << 1 | 1]);
    treey[rt] = max(treey[rt << 1], treey[rt << 1 | 1]);
}

void updateX(int L, int C, int l, int r, int rt)
{
    if (l == r)
    {
        treex[rt] = max(treex[rt], C);
        return;
    }
    int m = (l + r) / 2;
    if (L <= m)
        updateX(L, C, l, m, rt << 1);
    else
        updateX(L, C, m + 1, r, rt << 1 | 1);
    pushup(rt);
}

void updateY(int L, int C, int l, int r, int rt)
{
    if (l == r)
    {
        treey[rt] = max(treey[rt], C);
        return;
    }
    int m = (l + r) / 2;
    if (L <= m)
        updateY(L, C, l, m, rt << 1);
    else
        updateY(L, C, m + 1, r, rt << 1 | 1);
    pushup(rt);
}

int queryX(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
    {
        return treex[rt];
    }
    int ans = -1;
    int m = (l + r) / 2;
    if (L <= m)
        ans = max(ans, queryX(L, R, l, m, rt << 1));
    if (R > m)
        ans = max(ans, queryX(L, R, m + 1, r, rt << 1 | 1));
    return ans;
}

int queryY(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
    {
        return treey[rt];
    }
    int ans = -1;
    int m = (l + r) / 2;
    if (L <= m)
        ans = max(ans, queryY(L, R, l, m, rt << 1));
    if (R > m)
        ans = max(ans, queryY(L, R, m + 1, r, rt << 1 | 1));
    return ans;
}

vector<pair<int, int>> P;

int sorted[2 * MAXN];
int main()
{
    int N;
    scanf("%d", &N);
    ll ans = 0;
    for (int i = 1; i <= N; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        P.push_back(make_pair(x, y));

        sorted[i] = x;
        sorted[N + i] = y;
    }
    sort(sorted + 1, sorted + 2 * N + 1);
    int cnt = unique(sorted + 1, sorted + 2 * N + 1) - sorted - 1;

    for (int i = N - 1; i >= 0; i--)
    {
        int x = lower_bound(sorted + 1, sorted + cnt + 1, P[i].first) - sorted;
        int y = lower_bound(sorted + 1, sorted + cnt + 1, P[i].second) - sorted;

        ll Y = queryX(x, MAXN, 1, MAXN, 1);
        if (sorted[y] - sorted[Y] >= 0)
        {
            ans += sorted[y] - sorted[Y];
            updateX(x, y, 1, MAXN, 1);
        }

        ll X = queryY(y, MAXN, 1, MAXN, 1);
        if (sorted[x] - sorted[X] >= 0)
        {
            ans += sorted[x] - sorted[X];
            updateY(y, x, 1, MAXN, 1);
        }
    }
    printf("%lld\n", ans);
}