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

逃离我推掉我的手 2022-12-13 12:43 116阅读 0赞

### 牛牛种花 ###

[题目链接][Link 1]  
![题目1][1]  
![题目2][2]  
这道题还是挺有意思的，呵呵。

--------------------

#### 解题思路 ####

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

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; 
    }

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

④、[树状数组][Link 3]  
维护 yi 的区间和。这里我们注意运用树状数组的起始下标必须为 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;
    }

--------------------

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

[Link 1]: https://ac.nowcoder.com/acm/contest/6013/C
[1]: /images/20221123/faa1df78c8ff4f529cadd41790572be1.png
[2]: /images/20221123/1515d5b087274140b8057a1f63ba2f40.png
[Link 2]: https://blog.csdn.net/Zhengyangxinn/article/details/108997507
[Link 3]: https://blog.csdn.net/Zhengyangxinn/article/details/105205398?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160240221619195264739730%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=160240221619195264739730&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_v2~rank_blog_default-1-105205398.pc_v2_rank_blog_default&utm_term=%E5%B0%8F%E6%9C%8B%E5%8F%8B&spm=1018.2118.3001.4187