cdq+线段树 104pts WA 后四个点
查看原帖
cdq+线段树 104pts WA 后四个点
541568
Linghua_dog楼主2023/6/6 21:18
#include <cstdio>
#include <vector>
#include <algorithm>

#define all(x) x.begin(), x.end()

using namespace std;

const int N = 1e5 + 5;

struct square
{
	long long xl, xr, yl, yr;
	int id;
}s[N];
struct tree
{
	int l, r;
	int num;
	int lz, Lz;
}tr[16 * N];
vector<long long> S;
bool f[N];

int find(long long x){return lower_bound(all(S), x) - S.begin() + 1;}

bool cmp(square a, square b)
{
	return a.id > b.id;
}

bool cmp1(square a, square b)
{
	return a.xl < b.xl;
}

bool cmp2(square a, square b)
{
	return a.xr < b.xr;
}

void pushup(int u)
{
	tr[u].num = max(tr[u << 1].num, tr[u << 1 | 1].num);
}

void pushdown(int x)
{
	tree &u = tr[x], &l = tr[x << 1], &r = tr[x << 1 | 1]; 
	if(~u.Lz)
	{
		l.Lz = r.Lz = 0;
		l.lz = r.lz = 0;
		r.num = l.num = 0;
		u.Lz = -1;
	}
	l.num = max(l.num, u.lz);
	r.num = max(r.num, u.lz);
	l.lz = max(l.lz, u.lz);
	r.lz = max(r.lz, u.lz);
	u.lz = 0;		
}

void build(int u, int l, int r)
{
	tr[u].l = l, tr[u].r = r;
	if(l == r) 
	{
		tr[u].lz = tr[u].num = 0;
		tr[u].Lz = -1;
		return;	
	}
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void modify(int u, int l, int r, int v)
{
	if(tr[u].l >= l && tr[u].r <= r)
	{
		tr[u].num = max(tr[u].num, v);
		tr[u].lz = max(tr[u].lz, v);
		return ;
	} 
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid) modify(u << 1, l, r, v);
	if(r > mid) modify(u << 1 | 1, l, r, v);
	pushup(u);
}

int query(int u, int l, int r)
{
	if(tr[u].l >= l && tr[u].r <= r) return tr[u].num;
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	int ans = 0;
	if(l <= mid) ans = query(u << 1, l, r);
	if(r > mid) ans = max(ans, query(u << 1 | 1, l, r));
	return ans;
}

void cdq(int l, int r)
{
	if(l >= r) return ;
	int mid = l + r >> 1;
	
	cdq(l, mid), cdq(mid + 1, r);
	sort(s + l, s + 1 + mid, cmp1), sort(s + mid + 1, s + 1 + r, cmp2);
	
	for(int j = mid + 1, i = l; j <= r; j++)
	{
		while(i <= mid && s[i].xl <= s[j].xr)
		{
			modify(1, s[i].yl, s[i].yr, s[i].xr);
			i++;
		} 
		
		f[s[j].id] |= (query(1, s[j].yl, s[j].yr) > s[j].xl);
	}
	
	tr[1].num = tr[1].Lz = tr[1].lz = 0, pushdown(1);
}

int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		int a, b;
		scanf("%d%d%d%d", &s[i].xl, &s[i].yl, &a, &b);
		s[i].id = i;
		s[i].yr = s[i].yl + b, s[i].xr = s[i].xl + a;
		S.push_back(s[i].yr), S.push_back(s[i].yl);
	}
	
	sort(all(S));
	S.erase(unique(all(S)), S.end());
	for(int i = 1; i <= n; i++) s[i].yl = find(s[i].yl), s[i].yr = find(s[i].yr);
	
	build(1, 1, S.size() + 2);
	
	sort(s + 1, s + 1 + n, cmp);
	cdq(1, n);
	
	for(int i = 1; i <= n; i++)
	{
		if(f[i]) puts("NE");
		else puts("DA");
	}
}
2023/6/6 21:18
加载中...