CF-12D Ball 题解

题目大意

在一个舞会上，有许多女士，每个女士有三个属性（b，l，r），如果存在其他的女士三项属性都比她要高，那么她就会选择死亡。问有多少人会死亡。

解题思路

这道题可以用线段树做，也可以用树状数组做，线段树太麻烦了，还是用树状数组写吧。

（其实是线段树不是很会。。

按b的大小来从大到小排序，记录下位置，以这个位置为下标构造树状数组，数组的值为r的值。

然后按l的大小从大到小排序，就已经确定一个属性了。

剩下的关系就通过线段树来判断。

（网上好像还有用map做的，代码不长，看不懂。。

完整代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 5e5 + 5;
int t[N], n;
struct it{
	int id;
	int b;
	int l;
	int r;
}p[N];

int lowbit(int x) {
	return x & -x;
}

void modify(int pos,int x) {//单点修改
	while (pos <= n) {
		t[pos] = max(t[pos], x);
		pos += lowbit(pos);
	}
}

int findmax(int pos) {//查询区间的最大值
	int M = -1e9;
	while (pos) {
		M = max(M, t[pos]);
		pos -= lowbit(pos);
	}
	return M;
}

int cmp1(it a, it b) {
	return a.b > b.b;
}

int cmp2(it a, it b) {
	return a.l > b.l;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		scanf("%d", &p[i].b);
    /*使用cin超时了，如果要使用cin的话
    需要加上ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	换行用"\n"
	原理自行百度*/
	for (int i = 1; i <= n; i++)
		scanf("%d", &p[i].l);
	for (int i = 1; i <= n; i++)
		scanf("%d", &p[i].r);
	sort(p + 1, p + 1 + n, cmp1);//按x从大到小
	int cnt = 1;
	for (int i = 1; i <= n; i++) {//记录树状数组下标
		if (p[i].b == p[i - 1].b)	p[i].id = p[i - 1].id;//判重
		else p[i].id = ++cnt;
	}
	sort(p + 1, p + 1 + n, cmp2);//按y从大到小
	int j,ans = 0;
	for (int i = 1; i <= n;) {
		for (j = i; j <= n && p[j].l == p[i].l; j++) {
			if (findmax(p[j].id - 1) > p[j].r)	ans++;
            //比她b要大的人中，如果存在最大值比她自己的r大的话，答案加一
		}
		for (j = i; j <= n && p[j].l == p[i].l; j++)
			modify(p[j].id, p[j].r);
		i = j;
	}
	cout << ans << endl;
}