#10121. 「一本通 4.2 例 3」与众不同

离线询问最大完美数列长度 这种[L,R]的题目一般都先定R 然后再一个线性递推

设f[i] 表示第i个数为完美序列结尾 开头最大的位置 明显f[]是单调递增的

明显以i结尾完美序列的最大长度就是 i-pos+1

再考虑一个询问[L,R]

对于f[i]>L的情况 就相当于询问区间最大值

特别的 可能最开始几个的f[]

前面几个的最大值为pos-L+1 后面最大值就区间询问RMQ即可

#include
#define il inline
#define ri register int
#define ll long long
#define lowbit(x) x&(-x)
using namespace std;
const int mod=9999991;
const int maxn =2e5+5;
const int maxx =1e6;
int x,n,m;
int st[maxn][20],lg[maxn],last[(maxx<<1)+5],dp[maxn],f[maxn];
void init(){
	lg[0]=-1;
	for(ri i=1;i<=n;i++)
	lg[i]=lg[i>>1]+1;
	for(ri j=1;(1<R)return 0;
	int k=lg[R-L+1];
	return max(st[L][k],st[R-(1<