开放原子开发者工作坊

有问题，找副连，无聊的时候当然也可以找他啦。小W找到了他的叔叔——东厂厂长——宇宙超级无敌老WS yy。他们叔侄两个商量之后决定用弹弓打破社区里的一些窗户，但是弹弓每秒只能彻底打破一扇窗户。而且如果某户窗户的主人回来了的话，他们就不能进行破坏了（不然会死得很惨的）。因为有的人装的玻璃好，有的人装的玻璃差，有的人装的玻璃高，有的人装的玻璃矮，所以你不能要求他们叔侄两个打破不同的窗户获得的快乐值必须相同。现在他们想知道在能活着的情况下能够获得的最大快乐值。

贪心+数据结构，先按照欢乐值排序，维护一个时间序列，每次将一个窗户放进最晚的空格中，如果不行就放弃

这里用了ZKW线段树，其实原解是并查集？！！

“

非常 显 然，只有 n 以 内 的 时间 是有用的。

那 么 我 们 可以 将 窗 户 按照 欢乐值 降序排列，然后用 并查 集 维护 每 个 位置 它 左 边 最近的一 个没 有被使 用的位置。

”

好吧可能我太水了

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct W{ int t,v; } w[200010];
inline bool operator < (W a,W b){ return a.v>b.v; }
int n,M=1,s[600010]; long long ans=0;
int fpr(int x){
	if(x>n) x=n+1;
	for(x+=M;x;x>>=1)
		if((x&1)&&(s[x^1])){
			for(--x;x<=M;x=(s[x<<1|1]?x<<1|1:x<<1));
			return x-M;
		}
	return -1;
}
void remove(int x){ for(x+=M;x;x>>=1) s[x]--; }
int main(){
	scanf("%d",&n);
	while(M<=n) M<<=1; --M; 
	for(int i=M+1;i<=M+n;++i) s[i]=1;
	for(int i=M;i;--i) s[i]=s[i<<1]+s[i<<1|1];
	for(int i=1;i<=n;++i){
		scanf("%d%d",&w[i].t,&w[i].v);
		if(!w[i].t||w[i].v<=0){ n--; i--; }
		else ++w[i].t;
	}
	sort(w+1,w+1+n); 
	for(int i=1;i<=n;++i){
		int p=fpr(w[i].t);
		if(~p){ ans+=w[i].v; remove(p); }
	}
	printf("%lld\n",ans);
}