EC R 87 div2 D. Multiset 线段树树状数组二分

LINK：Multiset

主要点一下二分和树状数组找第k大的做法.

线段树的做法是平凡的开一个数组实现就能卡过.

考虑如树状数组何找第k大二分+查询来判定是不优秀的。

考虑树状数组上倍增来做. 考虑从0开始跳定义跳到的节点为前缀和.

那么不断跳累加权值即可.

第三种做法是二分 (其实我最先想到的是类似的做法.

观察到答案最终只要一个数字受到第三个样例的启发考虑维护最大值/最小值.

直接开堆乱搞是不正确的无法衡量之前是否删除当前的最大值了.

考虑二分这个最大值/最小值

这里以最小值为例因为比较好描述那么check 就是看一下<=mid的数字是否都被删掉了.

这样做可以发现满足判定的单调性.

这里用的是第一种做法。

const int MAXN=1000010;

int n,Q;

int sum[MAXN<<2];

inline void insert(int p,int l,int r,int x)

{

	++sum[p];

	if(l==r)return;

	int mid=(l+r)>>1;

	if(x<=mid)insert(zz,l,mid,x);

	else insert(yy,mid+1,r,x);

}

inline int ask(int p,int l,int r,int k)

{

	if(l==r)return l;

	int mid=(l+r)>>1;

	if(sum[zz]>=k)return ask(zz,l,mid,k);

	return ask(yy,mid+1,r,k-sum[zz]);

}

inline void erase(int p,int l,int r,int x)

{

	--sum[p];

	if(l==r)return;

	int mid=(l+r)>>1;

	if(x<=mid)erase(zz,l,mid,x);

	else erase(yy,mid+1,r,x);

}

int main()

{

	freopen("1.in","r",stdin);

	get(n);get(Q);

	rep(1,n,i)insert(1,1,n,read());

	rep(1,Q,i)

	{

		int get(x);

		if(x>0)insert(1,1,n,x);

		else erase(1,1,n,ask(1,1,n,-x));

	}

	if(!sum[1])put(0);

	else put(ask(1,1,n,1));

	return 0;

}

巴特西

EC R 87 div2 D. Multiset 线段树树状数组二分

最新文章

热门文章

巴特西

EC R 87 div2 D. Multiset 线段树 树状数组 二分

最新文章

热门文章

EC R 87 div2 D. Multiset 线段树树状数组二分