基础算法题——牛牛种花（高效、降维、离散化、树状数组）

牛牛种花

题目链接


这道题还是挺有意思的，呵呵。

解题思路

①、高效：利用结构体存储数据。

struct node{
    int x,y,id;
}a[N<<1];

利用 id 来记录每个节点是查询或是种树，若为查询则给予编号（从 1 开始编号），否则置为 0。

②、降维
对存储数据的结构体数组 a 以第一关键字：x 第二关键字：y，进行从小到大的排序，从而达到避免考虑 x 的变化的效果 。

bool cmp(node a,node b){
	if(a.x==b.x)
		return a.y<b.y;
	else
		return a.x<b.x; 
}

③、离散化
通过降维，我们只要考虑变量 y_i 的区间和。但题目中数据范围太大，-10⁹<= y_i <=10⁹。若直接用数组把对应 y_i 下标进行标记，那肯定是会溢出。离散化能够 y_i 的规模缩小并存储起来。

④、树状数组
维护 y_i 的区间和。这里我们注意运用树状数组的起始下标必须为 1，不可从 0 开始维护。

ps：Y，s 的数组大小需要开到 2e5 以上，因为最大需要存储 n+m 个元素。

实现代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int Y[N], ans[N];
int s[N]={0}, cnt;

struct node{
	int x, y, id;
}a[N];

bool cmp(node a, node b){
	if(a.x==b.x) 
		return a.y<b.y;
	return a.x<b.x;
}

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

void add(int k){
	for(; k<=cnt; k+=lowbit(k))
		s[k]++;
	return;
}

int sum(int k){
	int x=0;
	for(; k>0; k-=lowbit(k))
		x += s[k];
	return x;
}

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n+m; i++){
		scanf("%d%d", &a[i].x, &a[i].y);
		Y[i] = a[i].y;
		if(i>n)
			a[i].id=i-n;
		else
			a[i].id=0;
	}
	
	sort(a+1, a+n+m+1, cmp);
	sort(Y+1, Y+n+m+1);
	cnt = unique(Y+1, Y+n+m+1)-Y-1;
	
	for(int i=1; i<=n+m; i++){
		int p = lower_bound(Y+1, Y+cnt+1, a[i].y)-Y;
		if(a[i].id)
			ans[a[i].id] = sum(p);
		else
			add(p);
	}
	
	for(int i=1; i<=m; i++)
		printf("%d\n", ans[i]);
	
	return 0;
}

文章对你有帮助，请留个赞鼓励鼓励我吧：)