题解：P5356 [Ynoi Easy Round 2017] 由乃打扑克

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
int n,m;
int st[100005],ed[1000005];
int cnt[100005];
long long add[100005],maxx[100005],minn[100005],a[100005],b[100005],kk[100005];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int block=sqrt(n);
	int t=n/block;
	if(n%block) t++;
	for(int i=1;i<=t;i++){
		st[i]=(i-1)*block+1;
		ed[i]=i*block;
	}
	ed[t]=n;
	for(int i=1;i<=n;i++){
		cnt[i]=(i-1)/block+1;
	}
	for(int i=1;i<=t;i++){
		minn[i]=INT_MAX,maxx[i]=-INT_MAX;
		for(int j=st[i];j<=ed[i];j++){
			b[j]=a[j];
			minn[i]=min(minn[i],a[j]);
			maxx[i]=max(maxx[i],a[j]);
		}
		sort(b+st[i],b+ed[i]+1);
	}
	while(m--){
		int op,l,r,k;
		cin>>op>>l>>r>>k;
		if(op==1){
			if(k<=0||k>(r-l+1)){
				cout<<-1<<endl;
				continue;
			}
			if(cnt[l]==cnt[r]){
				for(int i=l;i<=r;i++){
					kk[i]=a[i]+add[cnt[i]];
				}
				sort(kk+l,kk+r+1);
				cout<<kk[l+k-1]<<endl;
			}
			else{
				long long tmin=INT_MAX,tmax=-INT_MAX;
				for(int i=l;i<=ed[cnt[l]];i++){
					tmin=min(tmin,a[i]+add[cnt[i]]);
					tmax=max(tmax,a[i]+add[cnt[i]]);
				}
				for(int i=st[cnt[r]];i<=r;i++){
					tmin=min(tmin,a[i]+add[cnt[i]]);
					tmax=max(tmax,a[i]+add[cnt[i]]);
				}
				for(int i=cnt[l]+1;i<=cnt[r]-1;i++){
					tmin=min(tmin,minn[i]);
					tmax=max(tmax,maxx[i]);
				}
                if(k==1){
    				cout<<tmin<<endl;
    				continue;
    			}
    			if(k==(r-l+1)){
    				cout<<tmax<<endl;
    				continue;
    			}
				long long tl=tmin,tr=tmax,qans=-1;
				while(tl<=tr){
					long long mid=(tl+tr)>>1,ans1=0;
					for(int i=l;i<=ed[cnt[l]];i++){
						if(a[i]+add[cnt[i]]<=mid) ans1++;
					}
					for(int i=st[cnt[r]];i<=r;i++){
						if(a[i]+add[cnt[i]]<=mid) ans1++;
					}
					for(int i=cnt[l]+1;i<=cnt[r]-1;i++){
						if(mid>=minn[i]){
							if(mid<maxx[i]){
								int t=upper_bound(b+st[i],b+ed[i]+1,mid-add[i])-b;
								ans1+=t-st[i];								
							}
                            else{
                                ans1+=ed[i]-st[i]+1;
                            }
						}
					}
					if(ans1>=k) tr=mid-1,qans=mid;
					else tl=mid+1;	
				}
				cout<<qans<<endl;				
			}
		}
		else{
			if(cnt[l]==cnt[r]){
				for(int i=l;i<=r;i++){
					a[i]+=k;
				}
				minn[cnt[l]]=INT_MAX,maxx[cnt[l]]=-INT_MAX;
				for(int i=st[cnt[l]];i<=ed[cnt[l]];i++){
					minn[cnt[l]]=min(minn[cnt[l]],a[i]+add[cnt[l]]);
					maxx[cnt[l]]=max(maxx[cnt[l]],a[i]+add[cnt[l]]);
					b[i]=a[i];
				}
				sort(b+st[cnt[l]],b+ed[cnt[r]]+1);
			}
			else{
				for(int i=l;i<=ed[cnt[l]];i++){
					a[i]+=k;
				}
				minn[cnt[l]]=INT_MAX,maxx[cnt[l]]=-INT_MAX;
				for(int i=st[cnt[l]];i<=ed[cnt[l]];i++){
					minn[cnt[l]]=min(minn[cnt[l]],a[i]+add[cnt[i]]);
					maxx[cnt[l]]=max(maxx[cnt[l]],a[i]+add[cnt[i]]);
					b[i]=a[i];
				}
				sort(b+st[cnt[l]],b+ed[cnt[l]]+1);
				for(int i=st[cnt[r]];i<=r;i++){
					a[i]+=k;
				}
				minn[cnt[r]]=INT_MAX,maxx[cnt[r]]=-INT_MAX;
				for(int i=st[cnt[r]];i<=ed[cnt[r]];i++){
					minn[cnt[r]]=min(minn[cnt[r]],a[i]+add[cnt[i]]);
					maxx[cnt[r]]=max(maxx[cnt[r]],a[i]+add[cnt[i]]);
					b[i]=a[i];
				}
				sort(b+st[cnt[r]],b+ed[cnt[r]]+1);
				for(int i=cnt[l]+1;i<=cnt[r]-1;i++){
					add[i]+=k;
					minn[i]+=k;
					maxx[i]+=k;
				}				
			}
		}
	}
	return 0;
}