1265. 数星星
摘要
Title: 1265. 数星星
Tag: 树状数组
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1265. 数星星
-
题意
见原题
-
思路
题意为，求第i个点前面，存在多少个点，x,y坐标都小于等于它
一个典型的树状数组动态求前缀和的问题
思路就是，固定一个坐标系，枚举另一个坐标系，用树状数组来求小于等于它的数有多少个 -
代码
ps: 关键在于：
- 存的是什么数作为下标（有关tr数组开多大）
- 下标一定不能为0！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47'''
Author: NEFU AB-IN
Date: 2022-03-26 16:29:22
FilePath: \ACM\Acwing\1265.py
LastEditTime: 2022-03-26 16:34:12
'''
from collections import Counter
N = int(4e4 + 10)
tr, a = [0] * N, []
def lowbit(x):
return x & -x
def add(x, d):
while x < N:
tr[x] += d
x += lowbit(x)
def query(x):
res = 0
while x:
res += tr[x]
x -= lowbit(x)
return res
n = int(input())
for i in range(n):
x, y = map(int, input().split())
x += 1
y += 1
a.append([x, y])
a.sort()
a = [0, *a]
d = Counter()
for i in range(1, n + 1):
d[query(a[i][1])] += 1
add(a[i][1], 1)
for i in range(n):
print(d[i])