萌新刚学kdt求助
  • 板块P4148 简单题
  • 楼主OIer_Tan
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/12 16:36
  • 上次更新2024/7/12 17:37:59
查看原帖
萌新刚学kdt求助
700210
OIer_Tan楼主2024/7/12 16:36

RT,全MLE。

#include<bits/stdc++.h>

#ifndef CRT
#define endl '\n' 
#endif

using namespace std ;

typedef long long ll ;
typedef unsigned long long ull ;
typedef long double ld ;

const ll N = 5e5 + 5 ;

struct point
{
	ll x , y , w ;
	point ( const ll & x = 0 , const ll & y = 0 , const ll & w = 0 ) : x ( x ) , y ( y ) , w ( w ) {}
};

struct kdtree
{
	ll idx , root ;
	ll tot , buf [N] ;
	const ld maxsz = 0.72 ;
	struct node
	{
		ll l = 0 , r = 0 ;
		point p ;
		ll sum , size ;
		ll minn [2] , maxn [2] ;
	} nodes [N] ;
	ll add ()
	{
		if ( ! tot )
		{
			return ++ idx ;
		}
		return buf [tot --] ;
	}
	void pushup ( ll u )
	{
		auto &l = nodes [nodes [u].l] , & r = nodes [nodes [u].r] ;
		nodes [u].sum = nodes [u].p.w + l.sum + r.sum ;
		nodes [u].size = l.size + r.size + 1 ;
		nodes [u].minn [0] = min ( { nodes [u].p.x , l.minn [0] , r.minn [0] } ) ;
		nodes [u].maxn [0] = max ( { nodes [u].p.x , l.maxn [0] , r.maxn [0] } ) ;
		nodes [u].minn [1] = min ( { nodes [u].p.x , l.minn [1] , r.minn [1] } ) ;
		nodes [u].maxn [1] = max ( { nodes [u].p.x , l.maxn [1] , r.maxn [1] } ) ;
	}
	point pt [N] ;
	void getseq ( ll u , ll cnt )
	{
		if ( nodes [u].l )
		{
			getseq ( nodes [u].l , cnt ) ;
		}
		buf [++ tot] = u ;
		pt [nodes [nodes [u].l].size + cnt] = nodes [u].p ;
		if ( nodes [u].r )
		{
			getseq ( nodes [u].r , cnt + nodes [nodes [u].l].size + 1 ) ;
		}
	}
	ll rebuild ( ll l , ll r , ll k )
	{
		if ( l > r )
		{
			return 0 ;
		}
		ll mid = l + r >> 1 ;
		ll u = add () ;
		nth_element ( pt + l , pt + mid , pt + r + 1 , [&]( point a , point b ){
			return ( k ? ( a.y < b.y ) : ( a.x < b.x ) ) ;
		}) ;
		nodes [u].p = pt [mid] ;
		nodes [u].l = rebuild ( l , mid - 1 , k ^ 1 ) ;
		nodes [u].r = rebuild ( mid + 1 , r , k ^ 1 ) ;
		pushup ( u ) ;
		return u ;
	}
	void maintain ( ll & u , ll k )
	{
		if ( nodes [u].size * maxsz < nodes [nodes [u].l].size ||
			nodes [u].size * maxsz < nodes [nodes [u].r].size )
		{
			getseq ( u , 0 ) ;
			u = rebuild ( 1 , tot , k ) ;
		}
		return ;
	}
	void insert ( ll & u , point p , ll k )
	{
		if ( ! u )
		{
			u = add () ;
			nodes [u].p = p ;
			pushup ( u ) ;
			return ;
		}
		if ( ( k ? p.y <= nodes [u].p.y : p.x < nodes [u].p.x ) )
		{
			insert ( nodes [u].l , p , k ^ 1 ) ;
		}
		else
		{
			insert ( nodes [u].r , p , k ^ 1 ) ;
		}
		pushup ( u ) ;
		maintain ( u , k ) ;
	}
	bool In ( node t , ll x1 , ll y1 , ll x2 , ll y2 )
	{
		return t.minn [0] >= x1 && t.maxn [0] <= x2 && t.minn [1] >= y1 && t.maxn [1] <= y2 ;	
	}
	bool In ( point p , ll x1 , ll y1 , ll x2 , ll y2 )
	{
		return p.x >= x1 && p.x <= x2 && p.y >= y1 && p.y <= y2 ;
	}
	bool Out ( node t , ll x1, ll y1, ll x2, ll y2 ) 
	{
		return t.maxn[0] < x1 || t.minn [0] > x2 || t.maxn [1] < y1 || t.minn [1] > y2 ;	
	}
	ll query ( ll u , ll x1 , ll y1 , ll x2 , ll y2 )
	{
		if ( In ( nodes [u] , x1 , y1 , x2 , y2 ) )
		{
			return nodes [u].sum ;
		}
		if ( Out ( nodes [u] , x1 , y1 , x2 , y2 ) )
		{
			return 0 ; 
		}
		ll ans = 0 ;
		if ( In ( nodes [u].p , x1 , y1 , x2 , y2 ) )
		{
			ans += nodes [u].p.w ;
		}
		ans += query ( nodes [u].l , x1 , y1 , x2 , y2 ) +
			   query ( nodes [u].r , x1 , y1 , x2 , y2 ) ;
		return ans ;
	}
} tree ;

void init ()
{
	tree.nodes [0].minn [0] = tree.nodes [0].minn [1] = N + 5 ;
	tree.nodes [0].maxn [0] = tree.nodes [0].maxn [1] = -1 ;
	return ;
}

ll n , ans = 0 ;

ll last_ans = 0 ;

int main ()
{
	// freopen ( ".in" , "r" , stdin ) ;
	// freopen ( ".out" , "w" , stdout ) ;
	ios::sync_with_stdio ( 0 ) ;
	cin.tie ( 0 ) ;
	cout.tie ( 0 ) ;
	cin >> n ;
	ll opt ;
	while ( cin >> opt , opt != 3 )
	{
		if ( opt == 1 )
		{
			ll x , y , k ;
			cin >> x >> y >> k ;
			x ^= last_ans ;
			y ^= last_ans ;
			k ^= last_ans ;
			tree.insert ( tree.root , point ( x , y , k ) , 0 ) ;
		}
		else
		{
			ll x1 , y1 , x2 , y2 ;
			cin >> x1 >> y1 >> x2 >> y2 ;
			x1 ^= last_ans , y1 ^= last_ans ;
			x2 ^= last_ans , y2 ^= last_ans ;
			last_ans = tree.query ( tree.root , x1 , y1 , x2 , y2 ) ;
			cout << last_ans << endl ;
		}
	}
	return 0 ;
}
2024/7/12 16:36
加载中...