莫队+权值线段树
某个区间[l,r]中，最长的值域 连续段长度
让我联想到了旅馆Hotel那题。
类似的做法，我们只要对权值建线段树，同样是维护从l开始的最长连续段lw[]，同理rw[]，以及区间中最大的连续段mw[]
然后依然是类似的up()
inline void up(int k) { lw[k]=lw[k<<1]; rw[k]=rw[k<<1|1]; if(lw[k<<1]==siz[k<<1]) lw[k]+=lw[k<<1|1]; if(rw[k<<1|1]==siz[k<<1|1]) rw[k]+=rw[k<<1]; mw[k]=max(max(mw[k<<1],mw[k<<1|1]),rw[k<<1]+lw[k<<1|1]); }
这样我们只要每次询问维护莫队，然后$O(1)$查下$mw[1]$就得出了答案
时间复杂度$O(n \sqrt {n} logn)$
原文：https://www.cnblogs.com/hzoi-yzh/p/11253067.html