AcWing 2041. 干草堆（差分）

https://www.acwing.com/problem/content/2043/

因为我们前面有k个区间修改 *** 作，最后求出中位数，由于是静态的，所以我们直接使用差分维护就好啦，然后最后求一个前缀和恢复一下修改后的每个位置的值即可

#include
using namespace std;

const int N = 1e6+10;

int a[N];
int n;
int k,A,B;


int main()
{
	cin>>n>>k;
	while(k--) {
		cin>>A>>B;
		a[A]++;
		a[B+1]--;		
	}
	int res = 0;
	for(int i = 1;i <= n; ++i) {
		res += a[i];
		a[i] = res;
	}
	sort(a+1,a+1+n);
	cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714096.html