Description

JYY 发明了一个新的益智游戏, 该游戏由 A 和 B兩人轮流在一个 \(10^6 \times 10^6\) 的方格棋盘上的网格线交点下棋, 网格线交点的坐标以 \((x, y)\) 表示之,\((0, 0)\) 代表棋盘最左下角的点. 每一个棋子放置的位置不可以与任何其它棋子在同一 \(X\) 坐标或 \(Y\) 坐标上, 棋盘上新增加一个棋子时, 棋盘上的计数器会自动算出以目前棋盘上棋子所能够围成的 “无障碍四方形” 个数. “无障碍四方形” 是指以任意兩个棋子所定义出的四方形内部不含其它棋子, 每下一个棋子后所算出的 “无障碍四方形” 个数即为下该棋子的得分数. 每位下棋者的总分即是该下棋者每个所下棋子的得分数总和. 请写一个程序计算 A 和 B兩位下棋者的累计总分.

Input

第一行输入只有一个整数 \(n\), 代表此盘棋共下了 \(n\) 个棋子.

接下來的 \(n\) 行, 每一行有兩个整数, 依序代表这 \(n\) 个棋子所放置的位置.

Output

请输出兩个整数, 分别代表该盘棋兩位下棋者的累计得分數. 先下棋者 (A) 的分数在前, 后下棋者 (B) 的分数在后, 中间用一个空格隔开.

Sample Input

4
2  3
3  4
1  2
4  1

Sample Output

2  6

Data Range

对于所有数据, 满足:\(1 \leq n \leq 5000\).

Explanation

我不生产题解, 我只是题解的搬运工:http://www.tuicool.com/articles/um2YVv

加入一个点时, 将之前加入的所有点根据当前点分为 \(4\) 个象限, 在四个象限中都能得到一条单调上升或下降的序列 (注意: 这里的单调队列指的是找到一个 \(Y\) 比当前结尾高 (低) 的点就加入, 具体可以考虑什么样的点能和当前点构成无障碍四方形). 这个点添加的贡献就是四个队列中的点数和, 但是还要考虑删除的贡献. (注, 接下来的点都指单调队列中的点) 相邻象限中的四方形不会产生贡献, 考虑相对象限的点. 对于 \(1, 3\) 象限, 枚举在第一象限中的每一个点, 然后在第二象限中找到第一个 \(Y\) 值比枚举点小的点, 在第三象限中找到 X 值比这个点小的点数, 然后在第四象限中找 \(X\) 值比枚举点小的 \(X\) 最大的点, 然后得出 \(Y\) 比他小的数, 两者相减得出答案. 由于 \(X, Y\) 都有单调性, 所以枚举时可以一直向下, 时间效率 \(O(n^2)\).

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 5010;
const int infinit = 0x3f3f3f3f;

struct node {
    int x, y, id;
}; bool operator < (node a, node b) {
    return a.x < b.x;
}

class my_queue
{
public:
    node data[maxn];
    int head, tail, end;
    void init(int now, int flag)
    {
        head = tail = end = 0;
        data[0].x = now;
        data[0].y = flag * infinit;
        return ;
    }
    void push(node a, bool flag)
    {
        if ((a.y < data[end].y) ^ flag)
            data[++end] = a;
        return ;
    }
    void pop_x(int x, bool flag)
    {
        while (head <= end && ((data[head].x < x) ^ flag))
            head += 1;
        if (head > 0)
            head -= 1;
        return ;
    }
    void pop_y(int y, bool flag)
    {
        while (tail <= end && ((data[tail].y < y) ^ flag))
            tail += 1;
        return ;
    }
} que1, que2, que3, que4;

int n;
lli res_f[maxn];
node a[maxn], b[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
        b[i].x = a[i].x, b[i].y = a[i].y;
        a[i].id = b[i].id = i;
    }
    sort(b + 1, b + n + 1);
    lli res = 0;
    for (int i = 1; i <= n; i++) {
        que1.init(a[i].x, 1);
        que2.init(a[i].x, 1);
        que3.init(a[i].x, -1);
        que4.init(a[i].x, -1);
        int k = 0;
        for (k = 1; b[k].x < a[i].x; k++);
        for (int j = k - 1; j >= 1; j--) if (b[j].id < i) {
            if (b[j].y > a[i].y)
                que2.push(b[j], false);
            else
                que3.push(b[j], true);
        }
        for (int j = k + 1; j <= n; j++) if (b[j].id < i) {
            if (b[j].y > a[i].y)
                que1.push(b[j], false);
            else
                que4.push(b[j], true);
        }
        res += que1.end + que2.end + que3.end + que4.end;
        for (int j = 1; j <= que1.end; j++) {
            int x = que1.data[j].x,
                y = que1.data[j].y;
            if (!que3.end)
                break;
            que2.pop_y(y, true);
            int xx = (que2.tail > que2.end) ? (-infinit) : (que2.data[que2.tail].x);
            que3.pop_x(xx, true);
            que4.pop_x(x, false);
            int yy = (que4.data[que4.head].y);
            que3.pop_y(yy, false);
            if (que3.tail <= 0)
                que3.tail += 1;
            res -= max(que3.head - que3.tail + 1, 0);
        }
        que2.head = que2.tail = que3.head = que3.tail = que4.head = que4.tail = 1;
        for (int j = 1; j <= que2.end; j++) {
            int x = que2.data[j].x,
                y = que2.data[j].y;
            if (!que4.end)
                break;
            que1.pop_y(y, true);
            int xx = (que1.tail > que1.end) ? (infinit) : (que1.data[que1.tail].x);
            que4.pop_x(xx, false);
            que3.pop_x(x, true);
            int yy = (que3.data[que3.head].y);
            que4.pop_y(yy, false);
            if (que4.tail <= 0)
                que4.tail += 1;
            res -= max(que4.head - que4.tail + 1, 0);
        }
        res_f[i & 1] += res;
    }
    // Output
    printf("%lld %lld\n", res_f[1], res_f[0]);
    return 0;
}