C++ 解法, 执行用时: 870ms, 内存消耗: 14392K, 提交时间: 2022-04-22 21:16:18

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,ans[100005];
vector<int>pos[100005];
struct info{
	int l,r,id;
	int lb,rb,md;
	ll k;
}d[100005];
struct segt{
	int dat[262200];
	ll sum[262200];
	int tg[262200];
	void push(int i,int l,int r,int x){
		dat[i]=tg[i]=x;
		sum[i]=(ll)(r-l+1)*x;
	}
	void built(int i,int l,int r){
		tg[i]=0;
		if(l==r)sum[i]=dat[i]=l;
		else{
			int m=(l+r)>>1;
			built(i<<1,l,m),built(i<<1|1,m+1,r);
			dat[i]=min(dat[i<<1],dat[i<<1|1]);
			sum[i]=sum[i<<1]+sum[i<<1|1];
		}
	}
	void upd(int i,int l,int r,int a,int b,int x){
		if(r<a||b<l)return;
		if(a<=l&&r<=b){
			push(i,l,r,x);
			return;
		}
		int m=(l+r)>>1;
		if(tg[i]){
			push(i<<1,l,m,tg[i]);
			push(i<<1|1,m+1,r,tg[i]);
			tg[i]=0;
		}
		upd(i<<1,l,m,a,b,x),upd(i<<1|1,m+1,r,a,b,x);
		dat[i]=min(dat[i<<1],dat[i<<1|1]);
		sum[i]=sum[i<<1]+sum[i<<1|1];
	}
	int bs(int i,int l,int r,int w){
		if(dat[i]>w)return -1;
		if(l==r)return l;
		int m=(l+r)>>1;
		if(dat[i<<1|1]<=w)return bs(i<<1|1,m+1,r,w);
		return bs(i<<1,l,m,w);
	}
	ll qry(int i,int l,int r,int a,int b){
		if(r<a||b<l)return 0;
		if(a<=l&&r<=b)return sum[i];
		int m=(l+r)>>1;
		if(tg[i]){
			push(i<<1,l,m,tg[i]);
			push(i<<1|1,m+1,r,tg[i]);
			tg[i]=0;
		}
		return qry(i<<1,l,m,a,b)+qry(i<<1|1,m+1,r,a,b);
	}
}tr;
bool cmp(info a,info b){
	return a.md<b.md;
}
void solve(){
	sort(d+1,d+q+1,cmp);
	int it=0;
	tr.built(1,1,n);
	for(int i=0;i<=n+1;i++){
		for(int j=pos[i].size()-1;j;j--){
			int x=pos[i][j];
			int l=pos[i][j-1]+1,r=min(pos[i][j],n);
			if(l>n)continue;
			int pos=tr.bs(1,1,n,x-1);
			if(pos>=l){
				pos=min(pos,r);
				tr.upd(1,1,n,l,pos,x);
			}
		}
		while(it<q&&d[it+1].md==i){
			it++;
			if(d[it].lb==d[it].rb)continue;
			ll K=(d[it].r-d[it].l+1)*(d[it].r-d[it].l+2)/2;
			int pos=tr.bs(1,1,n,d[it].r);
			if(pos>=d[it].l){
				int L=d[it].l,R=pos;
				K-=(R-L+1)*d[it].r-tr.qry(1,1,n,L,R)+(R-L+1);
			}
			if(K>=d[it].k)d[it].rb=d[it].md;
			else d[it].lb=d[it].md+1;
			d[it].md=(d[it].lb+d[it].rb)/2;
		}
	}
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=0;i<=n+1;i++)pos[i].push_back(0);
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);
		pos[x].push_back(i);
	}
	for(int i=0;i<=n+1;i++)pos[i].push_back(n+1);
	for(int i=1;i<=q;i++){
		int l,r;ll k;
		scanf("%d%d%lld",&l,&r,&k);
		d[i].l=l,d[i].r=r,d[i].id=i,d[i].k=k;
		d[i].lb=0,d[i].rb=r-l+1,d[i].md=(d[i].lb+d[i].rb)/2;
	}
	for(int t=0;t<20;t++)solve();
	for(int i=1;i<=q;i++)ans[d[i].id]=d[i].md;
	for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}