[BZOJ3594][Scoi2014]方伯伯的玉米田（DP+树状数组优化）

一个结论：每一次拔高玉米的区间的右端点一定是 n $n$。
正确性：如果凭空将 [x,n] $[x,n]$的玉米高度加 1 $1$，那么最长不降子序列的长度一定会增加。所以当 r<n $r<n$时，操作区间 [l,n] $[l,n]$绝对比 [l,r] $[l,r]$优。
根据这个结论，可以设一个状态定义：
f[i][j] $f[i][j]$表示到了第 i $i$个玉米，拔了 j $j$次，以 i $i$为结尾的最长不降子序列长度。
转移：

f[i][j]=1+maxai+j≥ah+k and j≥k{f[h][k]} $$f[i][j]=1+\underset{a_i+j\ge a_h+k\text{ and }j\ge k}{max}\{f[h][k]\}$$

也就是说，由于上面的结论得到，拔高后第 i $i$ 个玉米的高度为 ai+j $a_i+j$ ，第 h $h$ 个玉米的高度为 ah+k $a_h+k$ ，同时区间 [i,n] $[i,n]$ 被拔高的次数不能是负数。可以由上面两点限制得出转移条件。
还是不足以通过。由于转移条件的特殊性（是 Ax≥Ay and Bx≥By $A_x\ge A_y\text{ and }{B}_x\ge B_y$ 的形式），所以可以使用二维树状数组优化。
具体地，第一维是 ai+j $a_i+j$ ，第二维是 j $j$ （考虑到第二维 j $j$ 可能为 0 $0$ ，因此下标要加 1 $1$ ），每计算出一个 f[i][j] $f[i][j]$ 就将其存入树状数组。
这时候，为了避免 f[i][j] $f[i][j]$ 从 f[i][<j] $f[i][<j]$ 转移，枚举 f $f$ 的第二维要从 K $K$ 到 0 $0$ 倒着枚举。
复杂度 O(nKlogalogK) $O(nK\log a\log K)$ 。
代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
#define Rof(i, a, b) for (i = a; i >= b; i--)
#define Pos(x, k) for (; x <= k; x += x & -x)
#define Neg(x) for (; x; x -= x & -x)
using namespace std;
inline int read()
{
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
const int N = 1e4 + 5, M = 555;
int n, K, a[N], f[N][M], T[N][M], ans;
void change(int x, int y, int v)
{
    Pos(x, 7371)
    {
        int z = y;
        Pos(z, 512) T[x][z] = max(T[x][z], v);
    }
}
int ask(int x, int y)
{
    int res = 0;
    Neg(x)
    {
        int z = y;
        Neg(z) res = max(res, T[x][z]);
    }
    return res;
}
int main()
{
    int i, j;
    n = read(); K = read();
    For (i, 1, n) a[i] = read();
    For (i, 1, n) Rof (j, K, 0)
    {
        ans = max(ans, f[i][j] = ask(a[i] + j, j + 1) + 1);
        change(a[i] + j, j + 1, f[i][j]);
    }
    cout << ans << endl;
    return 0;
}