BZOJ5442：[Ceoi2018]Global warming

原题传送门
从头开始跑一遍最长上升
从尾开始跑一遍最长下降

把头尾信息综合起来
如何综合，我采用树状数组维护最值，先用二分查找到当前数对应的地方，然后更新

整个代码我用了三只树状数组，麻烦的一点是需要离散化，由于我马力不够一个细节点没处理好wa了一发

Code：

#include <bits/stdc++.h>
#define maxn 200010
#define LL long long
using namespace std;
struct data{
	LL x;
	int id;
}b[maxn], c[maxn];
int p, n, f[maxn], g[maxn], a[maxn], tree1[maxn], tree2[maxn], tree3[maxn], ans, tot;
LL maxx;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

bool cmp1(data x, data y){ return x.x < y.x; }
bool cmp2(data x, data y){ return x.id < y.id; }
int lowbit(int x){ return x & -x; }
void upd(int &x, int y){ if (x < y) x = y; }
void upd1(int x, int y){ for (; x <= p; x += lowbit(x)) upd(tree1[x], y); }
int qry1(int x){ int sum = 0; for (; x; x -= lowbit(x)) upd(sum, tree1[x]); return sum; }
void upd2(int x, int y){ for (; x; x -= lowbit(x)) upd(tree2[x], y); }
int qry2(int x){ int sum = 0; for (; x <= p; x += lowbit(x)) upd(sum, tree2[x]); return sum; }
void upd3(int x, int y){ for (; x <= p; x += lowbit(x)) upd(tree3[x], y); }
int qry3(int x){ int sum = 0; for (; x; x -= lowbit(x)) upd(sum, tree3[x]); return sum; }

int find(LL x){
	if (x < c[1].x) return 1;
	if (x >= c[tot].x) return p + 1;
	int l = 1, r = tot, ans;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (c[mid].x >= x) ans = mid, r = mid - 1; else l = mid + 1;
	}
	return c[ans].x == x ? a[c[ans].id] + 1 : a[c[ans].id];
}

int main(){
	freopen("pa.in", "r", stdin);
	freopen("pa.out", "w", stdout);
	n = read(), maxx = read();
	for (int i = 1; i <= n; ++i) b[i] = (data){read(), i};
	sort(b + 1, b + 1 + n, cmp1);
	b[0].x = b[1].x - 1;
	for (int i = 1; i <= n; ++i)
		if (b[i].x != b[i - 1].x) c[++tot] = b[i];
	for (int i = 1; i <= n; ++i) a[b[i].id] = b[i].x == b[i - 1].x ? p : ++p;
	sort(b + 1, b + 1 + n, cmp2);
	for (int i = 1; i <= n; ++i){
		f[i] = qry1(a[i] - 1) + 1;
		upd1(a[i], f[i]);
	}
	for (int i = n; i; --i){
		g[i] = qry2(a[i] + 1) + 1;
		upd2(a[i], g[i]);
	}
	for (int i = 1; i <= n; ++i){
		int sum = qry3(a[i]) + g[i]; //printf("%d %d %d %d ", f[i], sum, g[i], a[i]);
		upd(ans, sum);
		upd3(find(max(b[i].x - maxx, 0LL)), f[i]);// printf("%d\n", find(max(b[i].x - maxx, 0LL)));
	} //printf("%d\n", find(3));
	printf("%d\n", ans);// printf("%d\n", find(1));
	return 0;
}