题目链接:https://vijos.org/p/1066

题目描述

永恒和mx正在玩一个即时战略游戏，名字嘛~~~~~~恕本人记性不好，忘了-_-b。

mx在他的基地附近建立了n个战壕，每个战壕都是一个独立的作战单位，射程可以达到无限（“mx不赢定了？！？”永恒ftING...@_@）。

但是，战壕有一个弱点，就是只能攻击它的左下方，说白了就是横纵坐标都不大于它的点（mx：“我的战壕为什么这么菜”ToT）。这样，永恒就可以从别的地方进攻摧毁战壕，从而消灭mx的部队。

战壕都有一个保护范围，同它的攻击范围一样，它可以保护处在它左下方的战壕。所有处于它保护范围的战壕都叫做它的保护对象。这样，永恒就必须找到mx的战壕中保护对象最多的点，从而优先消灭它。

现在，由于永恒没有时间来计算，所以拜托你来完成这个任务：

给出这n个战壕的坐标xi、yi，要你求出保护对象个数为0，1，2……n-1的战壕的个数。

输入格式

第一行，一个正整数n（1<=n<=15000）
接下来n行，每行两个数xi,yi，代表第i个点的坐标
（1<=xi,yi<=32000）
注意：可能包含多重战壕的情况（即有数个点在同一坐标）

输出格式

输出n行，分别代表保护对象为0，1，2……n-1的战壕的个数。

样例输入

5
1 1
5 1
7 1
3 3
5 5

样例输出

1
2
1
1
0

限制

各点2s（算是宽限吧^_^）

解题思路

题意:判断每个点有多少个在该点的左下方，分别统计出个数为0~n-1的点数。
思路:数据很水，直接暴力求解都可以过，有没有更快的的方法呢，当然，树状数组完全可以解决。先把所有点按y从小到大排序，这样就只需要x了，枚举每个点，要统计之前有多少个点的x坐标小于等于该点的x坐标，查询之后就更新到树上去，不然就会导致只考虑x，不考虑y的情况。初学线段树，就利用线段树的方法写了写，感觉还可以。

暴力求解:

/*
*@Author:   lzyws739307453
*@Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
struct edge {
    int x, y;
}e[15005];
int ans[15005], val[15005];
int main() {
    int n;
    scanf("%d", &n);
    memset(ans, 0, sizeof(ans));
    memset(val, 0, sizeof(val));
    for (int i = 0; i < n; i++)
        scanf("%d%d", &e[i].x, &e[i].y);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j && e[i].x >= e[j].x && e[i].y >= e[j].y)
                ans[i]++;
    for (int i = 0; i < n; i++)
        val[ans[i]]++;
    for (int i = 0; i < n; i++)
        printf("%d\n", val[i]);
    return 0;
}

树状数组:

/*
*@Author:   lzyws739307453
*@Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 32005;
int bits[MAXN], ans[MAXN >> 1];
struct edge {
    int x, y;
}e[MAXN >> 1];
bool cmp(edge X, edge Y) {
    if (X.y != Y.y)
        return X.y < Y.y;
    return X.x < Y.x;
}
int lowbit(int x) {
    return x & -x;
}
void Update(int i) {
    while (i < MAXN) {
        bits[i]++;
        i += lowbit(i);
    }
}
int PrefixSum(int i) {
    int cnt = 0;
    while (i > 0) {
        cnt += bits[i];
        i -= lowbit(i);
    }
    return cnt;
}
int main() {
    int n;
    scanf("%d", &n);
    memset(ans, 0, sizeof(ans));
    memset(bits, 0, sizeof(bits));
    for (int i = 0; i < n; i++)
        scanf("%d%d", &e[i].x, &e[i].y);
    sort(e, e + n, cmp);
    for (int i = 0; i < n; i++) {
        ans[PrefixSum(e[i].x)]++;
        Update(e[i].x);
    }
    for (int i = 0; i < n; i++)
        printf("%d\n", ans[i]);
    return 0;
}

线段树:

/*
*@Author:   lzyws739307453
*@Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 32005;
struct edge {
    int x, y;
}e[MAXN >> 1];
struct SegTreeNode {
    int val;
}segTree[MAXN << 2];
int ans[MAXN >> 1];
bool cmp(edge a, edge b) {
    if (a.y != b.y)
        return a.y < b.y;
    return a.x < b.x;
}
int Query(int root, int q, int left, int right) {
    if (q < left)
        return 0;
    if (q >= right)
        return segTree[root].val;
    int mid = left + ((right - left) >> 1);
    return Query(root << 1, q, left, mid) + Query(root << 1 | 1, q, mid + 1, right);
}
void Update(int root, int left, int right, int index) {
    if (left == right) {
        if (left == index)
            segTree[root].val++;
        return ;
    }
    int mid = left + ((right - left) >> 1);
    if (index <= mid)
        Update(root << 1, left, mid, index);
    else Update(root << 1 | 1, mid + 1, right, index);
    segTree[root].val = segTree[root << 1].val + segTree[root << 1 | 1].val;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &e[i].x, &e[i].y);
    sort(e, e + n, cmp);
    for (int i = 0; i < n; i++) {
        ans[Query(1, e[i].x, 1, MAXN)]++;
        Update(1, 1, MAXN, e[i].x);
    }
    for(int i = 0; i < n; i++)
        printf("%d\n", ans[i]);
    return 0;
}