교육 Codeforces Round 87 (Rated for Div. 2) D. Multiset (트 리 배열)

10350 단어 이분트 리 배열
제목 링크:https://codeforces.ml/contest/1354/problem/D 사고방식: 트 리 그룹 + 이분 트 리 그룹 은 동적 유지보수 접두사 와 데이터 구조 코드 입 니 다.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int s[N];
int c[N];
int n,q;
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int a)
{
	c[x]+=a;
	while(x<=n)
	{
		s[x]+=a;
		x+=lowbit(x);
	}
}
int ask(int x)
{
	int res=0;
	while(x)
	{
		res+=s[x];
		x-=lowbit(x);
	}
	return res;
}
int main()
{
	
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		add(x,1);
	}
	for(int i=1;i<=q;i++)
	{
		int x;
		scanf("%d",&x);
		if(x<0)
		{
			int l=1,r=n;
			while(l<r)
			{
				int mid=(l+r)/2;
				if(ask(mid)>=abs(x))
				{
					r=mid;
				}
				else l=mid+1; 
			}
			add(l,-1);
		}
		else
		{
			add(x,1);
		}
	}
	if(ask(n)==0) printf("0
"
); else { for(int i=1;i<=n;i++) { if(c[i]) { printf("%d
"
,i); break; } } } }

좋은 웹페이지 즐겨찾기