题意：给定一个n首歌的播放列表，第i首的值为a[i]，听完第i首会回到第1首
现在从每首开始往下，记录听过的最大值，如果当前听的值严格小于听过最大值的一半则停止
问从每首歌开始往下听能听几首，不会停止则输出-1
n<=1e5，1<=a[i]<=1e9
思路：会D不会C，D的写法还奇渣无比……
因为是环形所以先复制粘贴一遍，然后按a[i]从大到小排个序
对于每个出发点now，设在now之后且离now最近的值比他a[now]的点为nxt，在到达nxt之前其听过的最大值一定为a[now]
如果在now后面的最小值*2>=now后面的最大值则ans[now]=-1
如果now能到达nxt则答案即为ans[nxt]+nxt-now
否则可以二分出第一个不合法的点last，答案即为last-now
对于nxt集合用set维护，对于二分找到第一个不合法的点应该可以在线段树上二分做到一个log，我懒直接外面二分了，两个log
赛场上WA了一发，后面用自己的数据调出来了，今天一看和官方数据一样……我与出题人心意相通
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned int uint; 5 typedef unsigned long long ull; 6 typedef pair<int,int> PII; 7 typedef pair<ll,ll> Pll; 8 typedef vector<int> VI; 9 typedef vector<PII> VII; 10 //typedef pair<ll,ll>P; 11 #define N 200010 12 #define M 200010 13 #define fi first 14 #define se second 15 #define MP make_pair 16 #define pb push_back 17 #define pi acos(-1) 18 #define mem(a,b) memset(a,b,sizeof(a)) 19 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++) 20 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--) 21 #define lowbit(x) x&(-x) 22 #define Rand (rand()*(1<<16)+rand()) 23 #define id(x) ((x)<=B?(x):m-n/(x)+1) 24 #define ls p<<1 25 #define rs p<<1|1 26 27 const ll MOD=1e9+7,inv2=(MOD+1)/2; 28 double eps=1e-6; 29 int INF=1e9; 30 int dx[4]={-1,1,0,0}; 31 int dy[4]={0,0,-1,1}; 32 33 int read() 34 { 35 int v=0,f=1; 36 char c=getchar(); 37 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 38 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 39 return v*f; 40 } 41 42 set<int>S; 43 int t[N<<2],c[N],ans[N],s[N],b[N]; 44 45 struct node 46 { 47 int x,y; 48 }a[N]; 49 50 bool cmp(node a,node b) 51 { 52 if(a.x!=b.x) return a.x>b.x; 53 return a.y<b.y; 54 } 55 void pushup(int p) 56 { 57 t[p]=min(t[ls],t[rs]); 58 } 59 60 void build(int l,int r,int p) 61 { 62 if(l==r) 63 { 64 t[p]=c[l]; 65 return; 66 } 67 int mid=(l+r)>>1; 68 build(l,mid,ls); 69 build(mid+1,r,rs); 70 pushup(p); 71 } 72 73 int query(int l,int r,int x,int y,int p) 74 { 75 if(x<=l&&r<=y) return t[p]; 76 int mid=(l+r)>>1; 77 int res=INF; 78 if(x<=mid) res=min(res,query(l,mid,x,y,ls)); 79 if(y>mid) res=min(res,query(mid+1,r,x,y,rs)); 80 return res; 81 } 82 83 int main() 84 { 85 //freopen("1.in","r",stdin); 86 int n=read(); 87 int m=n*2; 88 rep(i,1,n) 89 { 90 a[i].x=read(); 91 a[i].y=i; 92 } 93 rep(i,1,n) c[i]=a[i].x; 94 rep(i,n+1,m) c[i]=c[i-n]; 95 rep(i,n+1,m) 96 { 97 a[i].x=a[i-n].x; 98 a[i].y=i; 99 } 100 sort(a+1,a+m+1,cmp); 101 build(1,m,1); 102 int i=a[1].y,mx=a[1].x,s=0; 103 while(1) 104 { 105 i++; 106 if(i==n+1) i=1; 107 s++; 108 if(c[i]*2<mx) 109 { 110 ans[a[1].y]=s; 111 break; 112 } 113 if(s>n) 114 { 115 ans[a[1].y]=-1; 116 break; 117 } 118 } 119 b[m+1]=0; 120 per(i,m,1) b[i]=max(b[i+1],c[i]); 121 //printf("s=%d\n",s); 122 S.clear(); 123 S.insert(a[1].y); 124 int mn=a[1].y; 125 rep(i,2,m) 126 { 127 //if(a[i].y<=n) 128 129 int now=a[i].y,res; 130 if(now>n) 131 { 132 ans[now]=ans[now-n]; 133 //mn=min(mn,a[i].y); 134 S.insert(now); 135 continue; 136 } 137 res=query(1,m,now,m,1); 138 if(res*2>=b[now]) 139 { 140 ans[now]=-1; 141 S.insert(now); 142 continue; 143 } 144 set<int>::iterator it=S.upper_bound(now); 145 //set<int>::iterator it=S.lower_bound(now); 146 int nxt=(*it); 147 if(nxt<now&&nxt<=n) nxt+=n; 148 //printf("i=%d now=%d nxt=%d\n",i,now,nxt); 149 res=query(1,m,now,nxt,1); 150 if(res*2>=a[i].x) 151 { 152 if(ans[nxt]==-1) ans[now]=-1; 153 else ans[now]=ans[nxt]+nxt-now; 154 } 155 else 156 { 157 int p; 158 if(a[i].x%2==0) p=a[i].x/2; 159 else p=a[i].x/2+1; 160 int l=now,r=nxt,last=l; 161 while(l<=r) 162 { 163 int mid=(l+r)>>1; 164 int res=query(1,m,now,mid,1); 165 if(res<p){last=mid; r=mid-1;} 166 else l=mid+1; 167 } 168 ans[a[i].y]=last-now; 169 } 170 171 S.insert(now); 172 } 173 rep(i,1,n) printf("%d ",ans[i]); 174 return 0; 175 }