WA 逝怎么回逝呢?
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int SIZE = 316;
const int blocks = ceil((double)N/SIZE);
int n,m,L[blocks+5],R[blocks+5];
int bl[N],sorted[blocks+5][SIZE+5];
int a[N],blk,tag[blocks+5],ptr1,ptr2;
int main(){
scanf("%d%d",&n,&m);blk = ceil((double)n / SIZE);
for(int i = 1;i <= n;i ++)scanf("%d",&a[i]);
for(int i = 1;i <= blk;i ++){
L[i] = R[i-1] + 1;
R[i] = min(n,i * SIZE);
for(int j = L[i];j <= R[i];j ++){
bl[j] = i;
sorted[i][j-L[i]+1] = a[j];
}
sort(sorted[i] + 1,sorted[i]+R[i]-L[i]+1+1);
}
while(m --){
int opt,l,r,k;
scanf("%d%d%d%d",&opt,&l,&r,&k);
if(opt == 1){
int p = bl[l],q = bl[r];
long long l1 = -2147483648ll,r1 = 2147483647ll;
if(k>r-l+1||k<1){
puts("-1");
continue;
}
if(p == q){
long long ans = 0;
while(l1 <= r1){
long long mid = (1ll*l1 + 1ll*r1) >> 1ll;
int tot = 0;
for(int i = l;i <= r;i ++)tot += (1ll*a[i]+tag[p]) <= mid;
if(tot < k)l1 = mid + 1;
else {
ans = mid;
r1 = mid - 1;
}
}
printf("%lld\n",ans);
}else{
long long ans = 0;
while(l1 <= r1){
long long mid = (1ll*l1 + 1ll*r1) >> 1ll;
int tot = 0;
for(int i = l;i <= R[p];i ++)tot += ((1ll*a[i]+tag[p]) <= mid);
for(int i = L[q];i <= r;i ++)tot += ((1ll*a[i]+tag[q]) <= mid);
for(int i = p+1;i <= q-1;i ++)
tot += upper_bound(sorted[i]+1,sorted[i]+(R[i]-L[i]+1)+1,mid-tag[i])-sorted[i]-1;
if(tot < k)l1 = mid + 1;
else {
ans = mid;
r1 = mid - 1;
}
}
printf("%lld\n",ans);
}
}else{
int p = bl[l],q = bl[r];
if(p == q){
for(int i = l;i <= r;i ++){
a[i] += k;
}
memcpy(sorted[p]+1,a+L[p],(R[p]-L[p]+1)*sizeof(int));
sort(sorted[p]+L[p],sorted[p]+R[p]+1);
}else{
for(int i = l;i <= R[p];i ++)a[i] += k;
for(int i = L[q];i <= r;i ++)a[i] += k;
memcpy(sorted[p]+1,a+L[p],(R[p]-L[p]+1)*sizeof(int));
memcpy(sorted[q]+1,a+L[q],(R[q]-L[q]+1)*sizeof(int));
sort(sorted[p]+1,sorted[p]+(R[p]-L[p]+1)+1);
sort(sorted[q]+1,sorted[q]+(R[q]-L[q]+1)+1);
for(int i = p+1;i <= q-1;i ++)tag[i] += k;
}
}
// system("pause");
}
return 0;
} /*
10 10
15 11 -18 12 6 9 14 -2 -10 6
1 2 3 1
2 2 4 -3
1 4 10 7
1 2 2 1
1 8 8 1
2 4 10 4
1 4 10 1
1 7 10 4
2 1 4 -5
1 1 8 4
*/