Panasonic Programming Contest 2021(AtCoder Beginner Contest 231) F Jealous Two

已知问题

1.第一次看题的时候以为可以给任意一人送任意个礼物，且礼物可以重复送，想不出解法。

2.没有注意到N*A[i]=10^14，那么必须开long long才能统计下来。

题解

题目要求对于A的每一个喜欢的礼物，对于B来说都有一些比这些礼物更好的礼物，但是这些B喜欢的礼物里，只能给B送A没有那么喜欢的。

设礼物的两个维度分别为a[i]和b[i]（对a[i]从小到大排序），那么对于每一个a[i]，显然对小A来说，这个礼物之前的礼物都"没有那么喜欢"。

那么，对于小B呢？小B也有一样的要求，问题是候选的礼物里只有小A同意了才能送给小B。换句话讲，小B只能从"小A没那么喜欢"的礼物堆里挑礼物。

而在这个礼物堆中，只能送那些b[j]>=b[i]的给小B。换句话讲，就转化成了动态求逆序对问题。

就用树状数组统计就行。（首先要离散化）

#include
#include
#include
#include
#define int long long
using namespace std;
const int MAXN = 4e5;

struct Point {
	int x, y;

	bool operator <(const Point &another)const {
		if (x == another.x) {
			return y > another.y;
		}
		else return x < another.x;
	}
}p[MAXN];
int vals[MAXN], cnt = 0;

int c[MAXN];

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

void add(int x, int k) {
	while (x <= cnt) {
		c[x] += k;
		x += lowbit(x);
	}
}

int sum(int l, int r) {
	l--;
	int ans = 0;
	while (r) {
		ans += c[r];
		r -= lowbit(r);
	}
	while (l) {
		ans -= c[l];
		l -= lowbit(l);
	}
	return ans;
}

signed main() {
	int n;
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &p[i].x);
		vals[++cnt] = p[i].x;
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &p[i].y);
		vals[++cnt] = p[i].y;
	}
	sort(vals + 1, vals + cnt + 1);
	cnt = unique(vals + 1, vals + cnt + 1) - (vals + 1);

	map valMap;
	for (int i = 1; i <= cnt; i++) {
		valMap[vals[i]] = i;
	}

	for (int i = 1; i <= n; i++) {
		p[i].x = valMap[p[i].x];
		p[i].y = valMap[p[i].y];
	}

	sort(p + 1, p + n + 1);//用x sort

	//二维偏序
	int ans = 0;

	int sameCnt = 0;
	for (int i = 1; i <= n; i++) {
		//printf("p[%d]:(%d,%d)\n", i, p[i].x, p[i].y);

		if (i < n && (p[i].x == p[i + 1].x&&p[i].y == p[i + 1].y)) {
			sameCnt++;
		}
		else {
			if (sameCnt > 0&&(p[i].x!=p[i+1].x||p[i].y!=p[i+1].y)) {
				sameCnt++;
				ans += sameCnt*(sameCnt - 1) / 2;
				sameCnt = 0;
			}
		}

		ans += sum(p[i].y, cnt);
		add(p[i].y, 1);
		//对于每个p[i].x，找y大于等于p[i].y的数量
	}
	ans += n;
	cout << ans << endl;
	return 0;
}

TRANSLATE with x English
Arabic Hebrew Polish
Bulgarian Hindi Portuguese
Catalan Hmong Daw Romanian
Chinese Simplified Hungarian Russian
Chinese Traditional Indonesian Slovak
Czech Italian Slovenian
Danish Japanese Spanish
Dutch Klingon Swedish
English Korean Thai
Estonian Latvian Turkish
Finnish Lithuanian Ukrainian
French Malay Urdu
German Maltese Vietnamese
Greek Norwegian Welsh
Haitian Creole Persian  
Bing Webmaster Portal Back
A题解 数据结构树状数组 常见题型二维偏序

相关

Git--学习笔记（三）远程仓库克隆到本地

全国产化 自主可控 飞腾4核主板

html标签

洛谷P5340 大中锋的游乐场 题解 分层图最短路

学习《Python编程从入门到实践》PDF+代码训练

【OF框架】定义框架标准WebApi，按照规范返回状态信息及数据信息

Windows cmd 启动 tomcat 中文乱码问题

有勇气的牛排博客

ValidateTemplate(Label lb2, boolean iflag) {

C# 十六进制八进制前缀或后缀

[Tools] 多媒体视频处理工具FFmpeg

rocketmq入门笔记

标签