//前天见过这个题的 trick。 //shy,你是我的神!!! //我现在是拜奶龙教教徒了 //为什么是树套树,真是好久没写了。 //忘了怎么写平衡树了,直接线段树嵌套空间爆炸了,我选择伟大的 cdq 分治! #include #include #include int max(int a,int b){return a>b?a:b;} int n,m,q; int a[500001]; struct{ int id,l,r,k,val; }b[1000001]; int ans[500001]; int c[500001]; void add(int x,int y){ for(;x<=n;x+=(x&-x))c[x]=max(c[x],y); } void clear(int x){ for(;x<=n;x+=(x&-x))c[x]=0; } int query(int x){ int res=0; for(;x;x-=(x&-x))res=max(res,c[x]); return res; } void solve(int l,int r){ if(l==r)return; int mid=l+r>>1; solve(l,mid),solve(mid+1,r); std::sort(b+l,b+mid+1,[](const auto&x,const auto&y){return x.id==y.id?x.r>y.r:x.idy.l+y.k:x.id>y.id;}); for(int i=l,j=mid+1;j<=r&&b[j].id;++j){ for(;i<=mid&&!b[i].id&&b[i].r>=b[j].l+b[j].k-1;++i)add(b[i].l,b[i].val); b[j].val=max(b[j].val,query(b[j].r-b[j].k+1)); } for(int i=l;i<=mid&&!b[i].id;++i)clear(b[i].l); } namespace init{ int f[20][500001],dep[500001]; std::vectoredge[500001]; void dfs(int u){ dep[u]=dep[f[0][u]]+1; for(const auto&v:edge[u]) if(v!=f[0][u]) f[0][v]=u,dfs(v); } int lca(int u,int v){ if(dep[u]=dep[v]) u=f[i][u]; if(u==v)return u; for(int i=20;i--;) if(f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v]; return f[0][u]; } int st[20][500001],lg[500001]; int Max(int l,int r){ int k=lg[r-l+1]; return max(st[k][l],st[k][r-(1<>1]+1; scanf("%d",&q),m=0; for(int i=1,l,r,k;i<=q;++i){ scanf("%d%d%d",&l,&r,&k); if(k==1)ans[i]=Max(l,r); else b[++m]={i,l,r-1,k-1,0}; } int top=0; for(int i=1;i=a[i];--top); if(!top)pre[i]=1; else pre[i]=stk[top-1]+1; stk[top++]=i; } top=0; for(int i=n-1;i>=1;--i){ for(;top&&a[stk[top-1]]>=a[i];--top); if(!top)suf[i]=n-1; else suf[i]=stk[top-1]-1; stk[top++]=i; } for(int i=1;iy.k;}); solve(1,m); } } int main(){ freopen("query.in","r",stdin); freopen("query.out","w",stdout); init::main(); for(int i=1;i<=m;++i)if(b[i].id)ans[b[i].id]=b[i].val; for(int i=1;i<=q;++i)printf("%d\n",ans[i]); return 0; }//I love wzh(?