md调了5h才调出来恶心坏了没想到这么快就做了第二道Ynoi
据说这题其实不卡常
题面也很清楚，给定两种操作，一种是区间加，一种是询问区间内第 k 小的数的值是多少。
对于区间加，在分块入门系列里面是直接对于修改过的散块进行重排，剩下的直接用 tag 来标记，我也是这么想的，所以我试了一下：
我觉得我写的没有问题，一定是这样做不对所以我换了个思路，直接将当前散块内的整块里的数分为两部分，修改的和没修改的，然后直接暴力修改，用两个队列把两种数给存下来，然后枚举重排，把两个队列里的元素每次都取小的插入排完序的数组内，因为遍历的是有序的数组，所以两个队列里面先进的数肯定比后面的小，这样就解决了区间加的问题。
然后来考虑区间kth，我们不难想到可以二分第 k 小的数的值，然后我们就可以在写个查询区间内小于等于 mid 的数个个数，对于整块，我们再进行二分查找（也可以重载运算符用upper_bound但是我不太会重载，所以没写），然后散块直接暴力。
还有一些小优化，比如如果要是当前的 k 是 1 的话就是直接找最小值，如果是区间长度的话就是直接找区间内最大值，在查询函数二分的时候也是同理，如果最大值都小于 mid 那么可以直接加上块长，如果最小值都大于 mid 可以直接跳过。
code：
#include<bits/stdc++.h>
#define int long long
#define N 300100
using namespace std;
int n,m,b[N],kc,bl[N],tag[N],block;
struct sb{int num,id;}e[N],pp[2100],qq[2100];
inline bool cmp(sb a,sb b){return a.num<b.num;}
inline int read(){int x=0;int f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;}
inline void print(int x){if(x>=10)print(x/10);putchar(x%10+48);}
inline void add(int l,int r,int c)
{
int c1=0,c2=0;
for(int i=(bl[l]-1)*kc+1;i<=bl[l]*kc;i++)
{
if(i>=l&&i<=r)b[i]+=c;//暴力修改原数列
if(e[i].id>=l&&e[i].id<=r)//在区间范围内
qq[++c2]=(sb){e[i].num+c,e[i].id};//用qq存下更新后的
else pp[++c1]=e[i];//否则保持不变
}
int k1=1,k2=1,t=(bl[l]-1)*kc+1;//开始合并
while(t<=bl[l]*kc)
{
if(k1<=c1&&(k2>c2||pp[k1].num<qq[k2].num))e[t++]=pp[k1],k1++;//只要pp还有数，并且比当前的qq要小，就放pp
else e[t++]=qq[k2],k2++;//反之放qq
}
if(bl[l]!=bl[r])//lr不在同一块里的情况
{
c1=0;c2=0;//照常处理
for(int i=(bl[r]-1)*kc+1;i<=bl[r]*kc;i++)
{
if(i>=l&&i<=r)b[i]+=c;
if(e[i].id>=l&&e[i].id<=r)
qq[++c2]=(sb){e[i].num+c,e[i].id};
else pp[++c1]=e[i];
}
k1=1,k2=1,t=(bl[r]-1)*kc+1;
while(t<=bl[r]*kc)
{
if(k1<=c1&&(k2>c2||pp[k1].num<qq[k2].num))e[t++]=pp[k1],k1++;
else e[t++]=qq[k2],k2++;
}
}
for(int i=bl[l]+1;i<bl[r];i++)tag[i]+=c;//直接修改标记
return ;
}
/*inline void add(int l,int r,int c)
{
for(int i=l;i<=min(kc*bl[l],r);i++)b[i]+=c;
for(int i=(bl[l]-1)*kc+1;i<=kc*bl[l];i++)e[i].num=b[i],e[i].id=i;
sort(e+(bl[l]-1)*kc+1,e+kc*bl[l]+1,cmp);
if(bl[l]!=bl[r])
{
for(int i=(bl[r]-1)*kc+1;i<=r;i++)b[i]+=c;
for(int i=(bl[r]-1)*kc+1;i<=min(r,kc*bl[r]);i++)e[i].num=b[i],e[i].id=i;
sort(e+(bl[r]-1)*kc+1,e+min(r,kc*bl[r])+1,cmp);
}
for(int i=bl[l]+1;i<bl[r];i++)tag[i]+=c;
return ;
}*/
inline int ask(int l,int r,int k)//查询序列里面有多少数是小于等于k的
{
int res=0;
for(int i=l;i<=min(bl[l]*kc,r);i++)
if(b[i]+tag[bl[l]]<=k)res++;//暴力查询左散块
if(bl[l]!=bl[r])
for(int i=(bl[r]-1)*kc+1;i<=r;i++)
if(b[i]+tag[bl[r]]<=k)res++;//暴力查询右散块
for(int i=bl[l]+1;i<bl[r];i++)//整块
{
int nl=(i-1)*kc+1,nr=i*kc;//左右边界
if(e[nr].num+tag[i]<=k)//如果要是最大值就比k小
{
res+=nr-nl+1;//直接加块长跳过
continue;
}
if(e[nl].num+tag[i]>k)continue;//最小值都比k大直接跳过
while(nl<nr)//二分查找
{
int mid=(nr+nl)/2+1;
// cout<<mid<<endl;
if(e[mid].num+tag[i]<=k)nl=mid;
else nr=mid-1;
}
if(e[nl].num+tag[i]<=k)res+=nl-(i-1)*kc;//累加小于等于k的数的个数
}
return res;
}
signed main()
{
// freopen("55.in","r",stdin);
// freopen("552.out","w",stdout);
n=read();m=read();
kc=1000;//求出块长
for(int i=1;i<=n;i++)
{
b[i]=e[i].num=read();//存入两个数组
bl[i]=(i-1)/kc+1;//标记当前数属于哪一块
e[i].id=i;//存编号
}
// cout<<"cao"<<endl;
for(int i=1;i<=n;)//从一到n遍历每一个数
{
int j;
for(j=i;bl[j]==bl[i];j++);//只要他俩相等就一直j++；
sort(e+i,e+j,cmp);//最后j的值是当前块多一，所以不用加一
i=j;//替换i值
}
for(int i=1;i<=m;i++)//遍历询问
{
// for(int j=1;j<=n;j++)
// cout<<b[j]<<endl;
// cout<<endl;
int op=read(),l=read(),r=read(),k=read();
if(op==1)//查询操作
{
// for(int j=1;j<=n;j++)
// cout<<tag[bl[j]]<<" ";
// cout<<endl;
int nl=2e9,nr=-2e9;//左右边界极限值
for(int j=l;j<=min(r,bl[l]*kc);j++)//处理左边散块，有可能lr在同一块
{
// cout<<j<<endl;
if(nl>b[j]+tag[bl[l]])nl=b[j]+tag[bl[l]];//对于左端点取最小值
if(nr<b[j]+tag[bl[l]])nr=b[j]+tag[bl[l]];//对于右端点取最大值
}
// cout<<l<<' '<<r<<endl;
// cout<<bl[l]<<" "<<bl[r]<<endl;
if(bl[l]!=bl[r])//不在同一块里
{
for(int j=(bl[r]-1)*kc+1;j<=r;j++)//同理处理nlnr的值
{
// cout<<j<<endl;
if(nl>b[j]+tag[bl[r]])nl=b[j]+tag[bl[r]];
if(nr<b[j]+tag[bl[r]])nr=b[j]+tag[bl[r]];
}
}
for(int j=bl[l]+1;j<bl[r];j++)//处理中间的整块
{
// cout<<"cao"<<endl;
// cout<<"G:"<<e[(j-1)*kc+1].num+tag[j]<<' '<<e[j*kc].num+tag[j]<<endl;
if(nl>e[(j-1)*kc+1].num+tag[j])nl=e[(j-1)*kc+1].num+tag[j];//因为e里面的数都是从小到大排好的
if(nr<e[j*kc].num+tag[j])nr=e[j*kc].num+tag[j];//同上直接找最大值
}
if(k==1)//等于1的情况
{
cout<<nl<<'\n';
continue;
}
if(k==nr-nl+1)//最大值的情况
{
cout<<nr<<'\n';
continue;
}
int ans=-1;
// cout<<"G:"<<nl<<" "<<nr<<endl;
while(nl<=nr)//二分第k小的值
{
// cout<<nl<<" "<<nr<<endl;
int mid=(nr+nl)/2;
// cout<<mid<<endl;
int cao=ask(l,r,mid);
// cout<<"cao:"<<cao<<endl;
if(cao<k)nl=mid+1;
else ans=mid,nr=mid-1;
}
cout<<ans<<'\n';//输出答案
}
else add(l,r,k);
}
return 0;
}
/*
5 3
1 5 4 2 3
1 2 4 2
2 1 4 4
1 2 4 3
4
-1
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
*/
【龙门粗口】