题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1541
题意 求每个等级的星星有多少个
当前这个星星的左下角 有多少个 星星 它的等级就是多少
和它同一水平线的左边的星星 以及 同一竖直线的下边的星星也算在内
思路 因为题目给出的x y 坐标 是按照 以 y 为第一关键词 x 为第二关键词 排序后给出的
那么 对于当前的星星来说，在它之前给出的星星中，都是在它下边的
所以 我们就可以不用管 Y 坐标 只用X 坐标
形成一个序列 就是求这个序列的 所有逆序对的个数
树状数组
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 32000 + 5; const int MOD = 1e9 + 7; int a[maxn]; int sum[maxn]; int lowbit(int x) { return x & (-x); } int Sum(int n) { int ans = 0; while (n > 0) { ans += a[n]; n -= lowbit(n); } return ans; } void add(int x) { while (x <= maxn) { a[x]++; x += lowbit(x); } } int main() { int n; while (~scanf("%d", &n)) { CLR(sum); CLR(a); int x, y; for (int i = 0; i < n; i++) { scanf("%d%d", &x, &y); sum[Sum(++x)]++; add(x); } for (int i = 0; i < n; i++) printf("%d\n", sum[i]); } }转载于:https://www.cnblogs.com/Dup4/p/9433125.html
