2020CCPC河南省赛 发通知(离散+差分)

学院一共有 n 位学生,用 1 编号。每天,学院都会派遣辅导员给学生发送若干通知,以保证各项措施、活动消息得到落实。
现在,学院要求辅导员发送一条关于光盘行动的通知。对于通知信息,同学们的反应往往各不相同,辅导员预测出第 i 号学生收到通知后会产生 wi 的愉悦度。此外,辅导员还观察到第 i 号学生会在 [ai,bi]时间段内实时查阅通知消息,能够收到这段时间内的所有通知;而其他时间将无法收到通知(愉悦度为 0)。
辅导员会选择在某一时刻发布一次通知消息,他希望在至少有 k 名同学收到通知的前提下,使得同学们的总体愉悦度最大。同学们的总体愉悦度是所有同学愉悦度的异或和。请聪明的你帮助辅导员计算最大的总体愉悦度。

AC代码:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1e6+5;
int a[N],b[N],c[N],d[N],e[N];
vector<int>v;
int get(int x){
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i]>>c[i];
		v.push_back(a[i]);
		v.push_back(b[i]+1);  
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=0;i<n;i++){
		int bg=get(a[i]);
		int ed=get(b[i]+1);
		e[bg]++,e[ed]--;
		d[bg]^=c[i],d[ed]^=c[i];
	}
	int ans=-1;
	for(int i=1;i<=v.size();i++){
		e[i]+=e[i-1];
		d[i]^=d[i-1];
		if(e[i]>=k)ans=max(ans,d[i]);
	}
	cout<<ans<<endl; 
}

 

上一篇:2020CCPC长春


下一篇:树上路径求交