C++(clang++11) 解法, 执行用时: 785ms, 内存消耗: 233184K, 提交时间: 2021-03-19 22:21:53

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define N 100012
#define U 20000012
#define LL long long
int n,m,tot=0,a[N],rt[N],c[U][2],s1[U];LL s[U];
inline void Ins(int &p,int l,int r,int v,int v1)
{
	if(!p)p=++tot;s[p]+=v*v1;s1[p]+=v1;if(l==r)return;int mid=(l+r)>>1;
	(v<=mid)?Ins(c[p][0],l,mid,v,v1):Ins(c[p][1],mid+1,r,v,v1);
}
inline void Add(int x,int v,int v1){for(;x<=n;x+=x&(-x))Ins(rt[x],0,100000,v,v1);}
vector<int>I,D;LL su=0;int sz=0;
int Ask(int l,int r,LL k)
{
	if(l==r)return l;int i,u,mid=(l+r)>>1,o;LL v=su-1ll*(mid+1)*sz;
	for(auto p:I)v+=s[c[p][1]]-1ll*(mid+1)*s1[c[p][1]];for(auto p:D)v-=s[c[p][1]]-1ll*(mid+1)*s1[c[p][1]];
	if(v>=k){for(i=0,u=I.size();i<u;i++)I[i]=c[I[i]][1];for(i=0,u=D.size();i<u;i++)D[i]=c[D[i]][1];return Ask(mid+1,r,k);}
	for(i=0,u=I.size();i<u;i++)o=I[i],su+=s[c[o][1]],sz+=s1[c[o][1]],I[i]=c[o][0];
	for(i=0,u=D.size();i<u;i++)o=D[i],su-=s[c[o][1]],sz-=s1[c[o][1]],D[i]=c[o][0];return Ask(l,mid,k);
}
int main(){
	scanf("%d%d",&n,&m);int i,cm,x,v,l,r,ans;LL K;
	for(i=1;i<=n;i++){scanf("%d",&x);Add(i,x,1);a[i]=x;}
	while(m--)
	{
		scanf("%d",&cm);
		if(cm==0)
		{
			scanf("%d%d%lld",&l,&r,&K);I.clear();D.clear();su=0;sz=0;
			for(;r;r&=(r-1))I.push_back(rt[r]);for(--l;l;l&=(l-1))D.push_back(rt[l]);ans=Ask(0,100000,K);
			if(su<K)printf("-1\n");else printf("%d\n",ans);
		}
		else{scanf("%d%d",&x,&v);Add(x,a[x],-1),Add(x,a[x] = v,1);}
	}return 0;
}