设 (f[j]) 中的 (j) 表示你所选出的数列的已知最大长度限制，而且是只管右限制的最大长度限制。
比如说第一个数右限制是 (4)，那么最大长度限制是 (5)，因为要算上它本身和它右边最多可能的人的个数。
然后如果第二个数是 (9)，那么最大限制依然是 (5)。
如果第二个数是 (1)，那么最大长度限制缩小为 (3)，因为要算上这两个和它右边最多可能多出来的 (1) 个人。
(f[j]) 表示在上述条件下的最大答案。
这样子我们从左往右扫一遍，每次去更新答案，可以发现每次更新的一定是一个区间。以下是原因：
- (f[j]) 是单调递减的。
- (j-f[j]) 是单调递增的。
- 当(j – f[j] – 1 ≤ \text{第 i 个人的右限制}) 时，这个人的右限制满足加入(f[j]) 的条件。
- 当(f[j] ≤ \text{第 i 个人的左限制}) 时，这个人的左限制满足加入(f[j]) 的条件。
因此只需要二分求出每次刚好满足右限制和左限制的位置，卡出来的是一个区间。(f[j]) 用树状数组维护。
#include
#include
#include
#define lowbit(i) (i&-i)
using namespace std;
const int N = 2e5 + 1;
int t, n, a, b, tree[N ], ans, l, r。
void add(int i, int x){
i = n - i;
while(i 0){
ret += tree[i];
i -= lowbit(i);
}
return ret;
}
int main(){
scanf("%d", &t);
while(t--){
ans = 0;
memset(tree + 1, 0, sizeof(int) * n);
scanf("%d", &n);
for(int i = 1; i > 1;
if(ans1 - query(ans1) > 1;
if(query(ans2)
Original: https://www.cnblogs.com/XeRiVO/p/CF1610C.html
Author: XeRiVO
Title: CF1610C-Keshi Is Throwing a Party
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604312/
转载文章受原作者版权保护。转载请注明原作者出处！