Luogu传送门
并不需要复杂的 DS(
考虑对于两个点 \(x,y\ (x < y)\),什么情况下才能使它们都有贡献。
第一个条件:
\[a_x < a_y \]这个比较显然吧,就不多说了。
第二个条件:
\[x - a_x \leq y - a_y \]解释一下,\(x - a_x\) 表示在坐标 \(x\) 之前要删掉多少个数才能使 \(x = a_x\),显然对于 \(x,y\ (x < y)\), \(x\) 前删掉的数的个数必须小于等于 \(y\) 之前删掉的数的个数。
同时,我们稍微推一下这个不等式,发现它也满足:
\[x < y \]所以 \(x < y\) 这个条件我们就不需要处理了。
推出上面这两个条件之后怎么做呢?
不难发现,这其实就是一个二维偏序问题,于是我们就可以愉快的用 lower_bound
或 树状数组来解决它啦。
注意:
- 上面的两个条件中一个是小于号,另一个是小于等于号(其实这样反而更简单了),而我们计算出来的序列中可能会有大量相等的数,具体怎么写见代码吧。
- 我们计算出的数列中会有许多 0,所以在树状数组的实现过程中要特判。
(这里使用的树状数组)
#include <bits/stdc++.h> using namespace std; namespace IO{ inline int read(){ int x = 0; char ch = getchar(); while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); return x; } template <typename T> inline void write(T x){ if(x > 9) write(x / 10); putchar(x % 10 + '0'); } } using namespace IO; const int N = 2e5 + 10; struct node{ int x, y; bool operator < (const node &b) const{ return x != b.x ? x < b.x : y < b.y; } }a[N]; int n, cnt, ans; struct BIT{ int c[N]; inline void add(int x, int y){ if(x < 0) return; for(; x <= n; x += x & (-x)) c[x] = max(c[x], y); } inline int query(int x){ if(x <= 0) return 0; int res = 0; for(; x; x -= x & (-x)) res = max(res, c[x]); return res; } }c; int main(){ n = read(); for(int i = 1; i <= n; ++i){ int t = read(); if(i - t >= 0) a[++cnt] = (node){i - t, t}; } sort(a + 1, a + 1 + cnt); for(int i = 1; i <= cnt; ++i){ int len = c.query(a[i].y - 1); c.add(a[i].y, len + 1); ans = max(ans, len + 1); } write(ans), puts(""); return 0; }\[\_EOF\_ \]