Balanced Playlist(Codeforces Global Round 5-D)(单调栈二分,树状数组)

题目

CF
有一个长度为 $n$ ($n\le 10^5$)的循环播放歌单，每首歌有一个优秀值 $a_i$ ($a_i\le 10^9$)
听歌时选一首歌开始，如果某一首歌 $x$ 的优秀值的两倍小于当前听过的歌中优秀值最大的，那么会在听完 $x$ 之前停止听歌。
对于每首歌 $i$，求 $c_i$ 表示如果从它开始听，最多听完几首歌，如果有重复的算多首。如果从一个位置开始能无限听下去，那么 $c_i=?1$。

思路

首先我们考虑破环成链，但是这里长度不是 $2?n$ 而是 $3?n$ ，可以观察这组数据:

4
3 2 5 3

5 4 3 6

我们发现对于第4个输出第一次经过2时可以，第二次最大值更新为5就不行了，可以理解为转一圈找最大值，然后又转一圈到最大值前一个(构造数据的话)，于是答案最大为 $2?n?2$ (开始在最大值后，结束在最大值前，2圈)
然后我本来想这样干：
$nex{t}_i$ 表示从 $i$ 开始以 $a_i$ 为 $max$ 值能扩展最远的下标，即 $j\in [i,nex{t}_i]$ 都满足 $\frac{a_i}{2}\le a_j$ 最大的下标，考虑这张图：

我们可以于是我们可以将 $[1,i]$ 的点最远点对 $nex{t}_i$ 取 $min$ 但是这是 $n^2$ 的
这样我们就有几种处理方式：
1.倒着做
于是我们只要取 $nex{t}_i$ 的最小值代表 $i$ 能到这个点最后减一个i再加1即可维护
2.分析单调性
如果记 $pre[next[i]]=i$ ，我们答案就是单调递增的(没有减i)，于是就用滑窗解决即可
而对于 $pre$ 和 $next$ 数组我们可以构建单调栈二分或者树状数组求解

代码

#include<set>
#include<map>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
    bool f=0;int x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define MAXN 300000
#define INF 0x3f3f3f3f
int a[MAXN+5],pre[MAXN+5],S[MAXN+5];
int main(){
    //pre[i]:在i之前满足a[t]/2>a[i]最大tint n=read();for(int i=1;i<=n;i++)a[i]=a[i+n]=a[i+2*n]=read();int tp=0;a[0]=INF;for(int i=1;i<=3*n;i++){
    while(tp&&a[S[tp]]<=a[i]) tp--;S[++tp]=i;int L=0,R=tp+1;while(L+1<R){
    //实现时改了改pre定义int Mid=(L+R)>>1;if(a[S[Mid]]>2*a[i]) L=Mid;else R=Mid;}pre[i]=S[L];//printf("%d ",pre[i]);}//puts("");int p=1;for(int i=1;i<=n;i++){
    while(p<=3*n&&pre[p]<i) p++;//在可选取范围内//printf("%d %d\n",pre[p],i);if(p<=3*n) printf("%d ",p);//i<=pre[p] [i,p-1]else printf("-1 ");}return 0;
}