有个疑问
  • 板块CF19D Points
  • 楼主bps321
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/1/1 14:29
  • 上次更新2024/1/1 18:18:35
查看原帖
有个疑问
540569
bps321楼主2024/1/1 14:29
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#define il inline
#define rg register
using namespace std;

const int N = 200000+10;

struct data
{
	string s;
	int x,y;
}a[N];
int n;

int dx[N],dy[N],totx, toty;
unordered_map<int,int>tx,ty;

struct segment_tree
{
	int l,r;
	int maxy;
	set<int>y;
}t[N*4];

struct pir
{
	int x,y;
};

il void build( int i, int l, int r )
{

	t[i].l = l, t[i].r = r;
	if( l == r )	return;
	
	rg int mid = (l+r)>>1;
	build( i<<1, l, mid );
	build( i<<1|1, mid+1, r );
}
il void upd1( int i, int x, int y )
{
	rg int l = t[i].l, r = t[i].r;
	if( l == r && r == x )
	{
		t[i].maxy = max(t[i].maxy ,y );
		t[i].y.insert( y );
		return;
	}
	rg int mid = (l+r)>>1;
	if( l <= x && x <= mid )	upd1( i<<1, x, y );
	else	upd1( i<<1|1, x,y );
	t[i].maxy = max(t[i<<1].maxy ,t[i<<1|1].maxy );
}
il void upd2( int i, int x, int y )
{
	rg int l = t[i].l, r = t[i].r;
	if( l == r && r == x )
	{
		t[i].y.erase( y );
		if( t[i].y.empty() )	t[i].maxy = 0;
		else	t[i].maxy = *t[i].y.rbegin();
		return;
	}
	rg int mid = (l+r)>>1;
	if( l <= x && x <= mid )	upd2( i<<1, x, y );
	else	upd2( i<<1|1, x,y );
	t[i].maxy = max(t[i<<1].maxy ,t[i<<1|1].maxy );
}
il pir query( int i, int x, int y )
{
	rg pir res;
	res.x = -1;
	res.y = -1;
	if( t[i].maxy <= y )	return res;
	
	rg int l = t[i].l, r = t[i].r;
//	if( r < x+1 )	return res;
	
	if( l == r )
	{
		if( t[i].y.size() && t[i].y.upper_bound( y ) != t[i].y.end() )
		{
			res.x = t[i].l;
			res.y = *t[i].y.upper_bound( y );
			return res;
		}
		else	return res;
	}
	
	rg int mid = (l+r)>>1;
	if( x+1 <= mid )	res = query( i<<1, x, y );
	if( res.x != -1 )	return res;
	res = query( i<<1|1, x, y );
	return res;
}

il int rd()
{
	rg int x = 0, f = 1;
	rg char ch = getchar();
	
	while( !isdigit( ch ) )
	{
		if( ch == '-' )	f = -1;
		ch = getchar();
	}
	while( isdigit( ch ) )
	{
		x = x*10+ch-'0';
		ch = getchar();
	}
	
	return x*f;
}
il string rds()
{
	rg string res = "";
	rg char ch = getchar();
	
	while( !( ch >= 'a' && ch <= 'z' ) )	ch = getchar();
	while( ch >= 'a' && ch <= 'z'  )
	{
		res += ch;
		ch = getchar();
	}
	
	return res;
}
signed main()
{
	n = rd();
	for( int i = 1; i <= n; i++ )
	{
		a[i].s = rds();
		a[i].x = rd();
		a[i].y = rd();
		dx[++totx] = a[i].x;
		dy[++toty] = a[i].y;
	}
	sort( dx+1, dx+totx+1 );
	totx = unique( dx+1, dx+totx+1 )-dx-1;
	for( int i = 1; i <= totx; i++ )	tx[ dx[i] ] = i;
	sort( dy+1, dy+toty+1 );
	toty = unique( dy+1, dy+toty+1 )-dy-1;
	for( int i = 1; i <= toty; i++ )	ty[ dy[i] ] = i;

	build( 1,1,totx );
	for( int i = 1; i <= n; i++ )
	{
		if( a[i].s == "add" )
			upd1( 1,tx[ a[i].x ], ty[ a[i].y ] );
		if( a[i].s == "find" )
		{
			rg pir tmp = query( 1, tx[ a[i].x ], ty[ a[i].y ] );
			if( tmp.x == -1 )	printf("-1\n");
			else	printf("%d %d\n",dx[tmp.x],dy[tmp.y]);
		}
		if( a[i].s == "remove" )
			upd2( 1, tx[ a[i].x ], ty[ a[i].y ] );
	}
	
	return 0;
}

第84行去掉就AC了,求大佬解释

2024/1/1 14:29
加载中...