UESTC 1584 Washi与Sonochi的约定 树状数组+排序

Washi与Sonochi的约定

Source

17暑假前集训-数据结构专题 By AutSky_JadeK

2017 UESTC Training for Data Structures

UESTC 1584 Washi与Sonochi的约定

My Solution

题意：在二维平面上，某个点的rank被定义为x坐标不大于其x坐标，且y坐标不大于其y坐标的怪物的数量。
（不含其自身），要求输出n行，每行一个整数，分别代表rank为0~n^1的怪物数量。

树状数组+排序
把所有的坐标读入之后，
按照x为第优先级，y为第二优先级，都是从小到大排序，
只从从0~n-1扫一遍，
此时(i时)树状数组里的点的x值，都不比val[i].x大，//这题所有坐标都不同
所以get(val[i].y)即可得到，所有x坐标不大于vali，且y坐标小于vali的坐标(点)的个数，
然后把val[i].y插入到树状数组里。
扫一遍即可得到所有答案。
复杂度 O(nlogn)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 8;

struct p{
    int x, y;
}val[MAXN];

inline bool cmp(const p &a, const p &b)
{
    if(a.x != b.x) return a.x < b.x;
    else return a.y < b.y;
}

int _rank[MAXN];

//
int Tree[MAXN + 8];
inline int lowbit(int x)
{
    return (x & -x);
}
inline void add(int x, int value)
{
    for(int i = x; i < MAXN; i += lowbit(i)){
        Tree[i] += value;
    }
}
inline int get(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i)){
        res += Tree[i];
    }
    return res;
}

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int n, i;
    scanf("%d", &n);
    for(i = 0; i < n; i++){
        scanf("%d%d", &val[i].x, &val[i].y);
    }
    //!害怕，"输入的坐标两两不同"，为什么不去掉这句话呢，Y^_^Y
    sort(val, val + n, cmp);
    for(i = 0; i < n; i++){
        _rank[get(val[i].y)]++;
        add(val[i].y, 1);
    }
    for(i = 0; i < n; i++){
        printf("%dn", _rank[i]);
    }



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx