全WA求助

#include<bits/stdc++.h>
using namespace std;
int n,m,t,len;
int a[100005],b[100005],c[100005],l[505],r[505],lazy[505],pos[100005];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    //len=200;
    len=sqrt(n);
    t=n/len;
    if(n%len!=0)
    {
        t++;
    }
    for(int i=1;i<=t;i++)
    {
        l[i]=(i-1)*len+1;
        r[i]=i*len;
    }
    if(r[t]>n)
    {
        r[t]=n;
    }
    for(int i=1;i<=t;i++)
    {
        sort(b+l[i],b+r[i]+1);
        for(int j=l[i];j<=r[i];j++)
        {
            pos[j]=i;
        }
    }
    while(m--)
    {
        int opt,x,y,k;
        cin>>opt>>x>>y>>k;
        if(opt==1)
        {
            if(k>y-x+1)
            {
                cout<<-1<<endl;
            }
            else if(pos[x]==pos[y])
            {
                for(int i=x;i<=y;i++)
                {
                    c[i]=a[i];
                }
                sort(c+x,c+y+1);
                cout<<c[x+k-1]+lazy[pos[x]]<<endl;
            }
            else
            {
                int L=2147483647,R=-2147483647,mid;
                for(int i=pos[x];i<=pos[y];i++)
                {
                    L=min(L,b[l[i]]+lazy[i]);
                    R=max(R,b[r[i]]+lazy[i]);
                }
                while(L<=R)
                {
                    int s=0,S=0;
                    mid=(L+R)/2;
                    //cout<<L<<" "<<R<<" "<<mid<<" ";
                    for(int i=x;i<=r[pos[x]];i++)
                    {
                        if(a[i]+lazy[pos[x]]<mid)
                        {
                            s++;
                        }
                        if(a[i]+lazy[pos[x]]<=mid)
                        {
                            S++;
                        }
                    }
                    for(int i=pos[x]+1;i<=pos[y]-1;i++)
                    {
                        if(b[r[i]]+lazy[i]<=mid)
                        {
                            S+=r[i]-l[i]+1;
                            continue;
                        }
                        if(b[l[i]]+lazy[i]>mid)
                        {
                            continue;
                        }
                        int ql=l[i],qr=r[i];
                        while(ql<=qr)
                        {
                            int Mid=(ql+qr)/2;
                            if(b[Mid]+lazy[i]<=mid&&b[Mid+1]+lazy[i]>mid)
                            {
                                S+=Mid-l[i]+1;
                                break;
                            }
                            if(b[Mid]+lazy[i]<mid)
                            {
                                ql=Mid+1;
                            }
                            else
                            {
                                qr=Mid-1;
                            }
                        }
                    }
                    for(int i=pos[x]+1;i<=pos[y]-1;i++)
                    {
                        if(b[r[i]]+lazy[i]<mid)
                        {
                            s+=r[i]-l[i]+1;
                            continue;
                        }
                        if(b[l[i]]+lazy[i]>=mid)
                        {
                            continue;
                        }
                        int ql=l[i],qr=r[i];
                        while(ql<=qr)
                        {
                            int Mid=(ql+qr)/2;
                            if(b[Mid]+lazy[i]<mid&&b[Mid+1]+lazy[i]>=mid)
                            {
                                s+=Mid-l[i]+1;
                                break;
                            }
                            if(b[Mid]+lazy[i]<mid)
                            {
                                ql=Mid+1;
                            }
                            else
                            {
                                qr=Mid-1;
                            }
                        }
                    }
                    for(int i=l[pos[y]];i<=y;i++)
                    {
                        if(a[i]+lazy[pos[y]]<mid)
                        {
                            s++;
                        }
                        if(a[i]+lazy[pos[y]]<=mid)
                        {
                            S++;
                        }
                    }
                    //cout<<s<<" "<<S<<endl;
                    if(s<=k-1&&S>=k)
                    {
                        cout<<mid<<endl;
                        break;
                    }
                    else if(s>k-1)
                    {
                        R=mid-1;
                    }
                    else
                    {
                        L=mid+1;
                    }
                }
            }
        }
        else
        {
            if(pos[x]==pos[y])
            {
                for(int i=l[pos[x]];i<=r[pos[x]];i++)
                {
                    b[i]=a[i];
                }
                for(int i=x;i<=y;i++)
                {
                    a[i]+=k;
                    b[i]+=k;
                }
                sort(b+l[pos[x]],b+r[pos[x]]+1);
            }
            else
            {
                for(int i=l[pos[x]];i<=r[pos[x]];i++)
                {
                    b[i]=a[i];
                }
                for(int i=x;i<=r[pos[x]];i++)
                {
                    a[i]+=k;
                    b[i]+=k;
                }
                sort(b+l[pos[x]],b+r[pos[x]]+1);
                for(int i=pos[x]+1;i<=pos[y]-1;i++)
                {
                    lazy[i]+=k;
                }
                for(int i=l[pos[y]];i<=r[pos[y]];i++)
                {
                    b[i]=a[i];
                }
                for(int i=l[pos[y]];i<=y;i++)
                {
                    a[i]+=k;
                    b[i]+=k;
                }
                sort(b+l[pos[x]],b+r[pos[x]]+1);
            }
        }
    }
}