线段树求调
  • 板块CF474E Pillars
  • 楼主PassName
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/4/18 21:58
  • 上次更新2024/4/19 12:53:05
查看原帖
线段树求调
524911
PassName楼主2024/4/18 21:58

RT

#include <bits/stdc++.h>

#define rint register int
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 5;
const int M = 4e5 + 5;

int n, d;
int a[M], b[M], f[N];
int ans[N], pre[N], cnt;
int maxx;
int id;

struct Node 
{
	int v, pos;//v is max
	bool friend operator < (Node x, Node y)
	{
		return x.v < y.v;
	}	
} t[M * 4];

#define ls p << 1
#define rs p << 1 | 1

void push_up(int p) 
{
	t[p] = max(t[ls], t[rs]);
}

void change(int p, int l, int r, int x, int v, int d) 
{
	if (l == r) 
	{
		if (x > t[p].v) t[p].v = v, t[p].pos = d;
		return ;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) change(ls, l, mid, x, v, d);
	else change(rs, mid + 1, r, x, v, d);
	push_up(p);
}

Node query(int p, int l, int r, int x, int y) 
{
	if (l >= x && r <= y) return t[p];
	int mid = (l + r) >> 1;
	Node res;
	if (x <= mid) res = max(res, query(ls, l, mid, x, y));
	if (y > mid) res = max(res, query(rs, mid + 1, r, x, y));
	return res;
}

void print(int x) 
{
	while (x) 
	{
		ans[++cnt] = x;
		x = pre[x];
	}
	for (rint i = cnt; i >= 1; i--) 
	{
		cout << ans[i] << " ";
	}
}

signed main() 
{
	cin >> n >> d;
	for (rint i = 1; i <= n; i++) 
	{
		cin >> b[i];
		a[i] = b[i];
		b[i + n] = a[i + n] = a[i] - d;
		b[i + 2 * n] = a[i + 2 * n] = a[i] + d;
	}
	sort(b + 1, b + 3 * n + 1);
	int tot = unique(b + 1, b + 3 * n + 1) - b - 1;
	for (rint i = 1; i <= 3 * n; i++) a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
	f[1] = 1;
	change(1, 1, tot, a[1], 1, 1);
	for (rint i = 2; i <= n; i++) 
	{
		Node x, y, z;
		x = query(1, 1, tot, 1, a[i + n]);
		y = query(1, 1, tot, a[i + 2 * n], tot);
		z = max(x, y);
		f[i] = z.v + 1;
		pre[i] = z.pos;
		change(1, 1, tot, a[i], f[i], i);
	}
	for (rint i = 1; i <= n; i++) 
	{
		if (maxx < f[i]) maxx = f[i], id = i;
	}
	cout << maxx << endl;
	print(id);
	return 0;
}

2024/4/18 21:58
加载中...