P5356

[Ynoi2017] 由乃打扑克

提供一组 样例。

这题比较好想的一个做法是分块，然后二分答案，然后再在每个块上二分得到排名，零散块每次 Check 的时候都扫一遍。修改的时候直接快速排序来重构零散块。

稍微算一算时间复杂度大概是 $O(\dfrac{n^2}{T}\log T\log n+nT\log n)$。

平衡不会算，随便取个 $T=\sqrt{n}$ 的话大概是 $O(n\sqrt{n}\log^2 n)$。如果 $T=\sqrt{n\log n}$ 的话可能会优秀一点？

没有写这个做法，可能大概率会被卡。

下面直接就是 lxl 的解法了。。。

实际上就是对上面的做法稍微优化一下，我们发现零散块每次 Check 的时候都去扫还是有些浪费，不如直接在 Check 之前就把零散块归并成一个假的块，然后每次 Check 的时候在这个假块上二分就完了。因为是归并，所以这个复杂度有所降低（实际上大概也就是常数稍微好一些）。。。

同样的，我们修改的时候零散块也不用快速排序重构，而是用归并的方法重构，复杂度就少一个 $\log$ 了。。。

这个时候我们取 $T=\sqrt{n}\log n$，最后平衡下来的复杂度就是 $O(n\sqrt{n}\log n)$ 的了。。。

我做这个题的时候犯了几个深必的错误。。。

一个是关于重载运算符的，还有一个是关于这个值域的。

这个二分答案的值域应该在 $[-2\times 10^9,2\times 10^9]$ 而不是 $[-2\times 10^4,2\times 10^4]$。。。实际上就是个读题的问题。。。

还有这个无解要输出 -1。。。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=1e6,M=1e5,L=2e2;

ll n,m,nn,lent;
ll a[N+5],pos[N+5];

struct node{
  ll val,id;
  inline node() {}
  inline node(ll x,ll y):val(x),id(y){}
  inline bool operator<(const node& rhs) const{return val<rhs.val;}
  inline bool operator>(const node& rhs) const{return val>rhs.val;}
  inline bool operator==(const node& rhs) const{return val==rhs.val;}
}t[N+5],t1[N+5],t2[N+5];

struct Block{
  node a[M+5];ll l,r,laz;
}blo[L+5];

inline bool Check(ll x,ll l,ll r,ll k) {
  // printf("Check: x=%lld l=%lld r=%lld k=%lld\n",x,l,r,k);
  ll rk=1;
  ll tmp=lower_bound(t+1,t+lent+1,node(x,0))-t-1;
  // printf("tmp=%lld\n",tmp);
  rk+=tmp;
  for(ll i=pos[l]+1;i<pos[r];i++) {
    ll len=blo[i].r-blo[i].l+1;
    tmp=lower_bound(blo[i].a+1,blo[i].a+len+1
    ,node(x-blo[i].laz,0))-blo[i].a-1;
    rk+=tmp;
  }
  // printf("rk=%lld\n",rk);
  return rk<=k;
}

inline bool Refactor_Cmp(bool op,ll x,ll y) {return op?(x>=y):(x<=y);}

inline void Refactor(ll l,bool op) {
  ll len=blo[pos[l]].r-blo[pos[l]].l+1;
  ll cnt1=0,cnt2=0;
  for(ll i=1;i<=len;i++) {
    ll tmp=blo[pos[l]].a[i].id;
    if(Refactor_Cmp(op,tmp,l)) {t1[++cnt1]=blo[pos[l]].a[i];}
    else {t2[++cnt2]=blo[pos[l]].a[i];}
  }
  ll i=1,j=1,cnt=0;
  while(i<=cnt1&&j<=cnt2) {
    if(t1[i]<t2[j]) {t[++cnt]=t1[i++];}
    else {t[++cnt]=t2[j++];}
  }
  while(i<=cnt1) {t[++cnt]=t1[i++];}
  while(j<=cnt2) {t[++cnt]=t2[j++];}
  for(ll i=1;i<=len;i++) {blo[pos[l]].a[i]=t[i];}
}

inline void Refactor_(ll l,ll r) {
  ll len=blo[pos[l]].r-blo[pos[l]].l+1;
  ll cnt1=0,cnt2=0;
  for(ll i=1;i<=len;i++) {
    ll tmp=blo[pos[l]].a[i].id;
    if(tmp>=l&&tmp<=r) {t1[++cnt1]=blo[pos[l]].a[i];}
    else {t2[++cnt2]=blo[pos[l]].a[i];}
  }
  ll i=1,j=1,cnt=0;
  while(i<=cnt1&&j<=cnt2) {
    if(t1[i]<t2[j]) {t[++cnt]=t1[i++];}
    else {t[++cnt]=t2[j++];}
  }
  while(i<=cnt1) {t[++cnt]=t1[i++];}
  while(j<=cnt2) {t[++cnt]=t2[j++];}
  for(ll i=1;i<=len;i++) {blo[pos[l]].a[i]=t[i];}
}

inline void Reorg(ll l,ll r) {
  ll len1=blo[pos[l]].r-blo[pos[l]].l+1;
  ll len2=blo[pos[r]].r-blo[pos[r]].l+1;
  ll cnt1=0,cnt2=0;
  for(ll i=1;i<=len1;i++) {
    if(blo[pos[l]].a[i].id>=l) {
      t1[++cnt1]=blo[pos[l]].a[i];
      t1[cnt1].val+=blo[pos[l]].laz;
    }
  }
  for(ll i=1;i<=len2;i++) {
    if(blo[pos[r]].a[i].id<=r) {
      t2[++cnt2]=blo[pos[r]].a[i];
      t2[cnt2].val+=blo[pos[r]].laz;
    }
  }
  ll i=1,j=1,cnt=0;
  while(i<=cnt1&&j<=cnt2) {
    if(t1[i]<t2[j]) {t[++cnt]=t1[i++];}
    else {t[++cnt]=t2[j++];}
  }
  while(i<=cnt1) {t[++cnt]=t1[i++];}
  while(j<=cnt2) {t[++cnt]=t2[j++];}
  lent=cnt;
}

inline void Reorg_(ll l,ll r) {
  ll cnt=0,len=blo[pos[l]].r-blo[pos[l]].l+1;
  for(ll i=1;i<=len;i++) {
    if(blo[pos[l]].a[i].id>=l&&blo[pos[l]].a[i].id<=r) {
      t[++cnt]=blo[pos[l]].a[i];t[cnt].val+=blo[pos[l]].laz;
    }
  }
  lent=cnt;
}

int main() {

  n=read();m=read();
  // nn=max(1ll,(ll)sqrt(n));
  nn=max(1ll,(ll)sqrt(n)*(ll)log(n));
  // nn=2ll;
  // printf("nn=%lld\n",nn);
  for(ll i=1;i<=n;i++) {a[i]=read();}
  for(ll i=1,cnt=1;i<=n;i+=nn,cnt++) {
    // printf("i=%lld cnt=%lld\n",i,cnt);
    blo[cnt].l=i;blo[cnt].r=i+nn-1;if(blo[cnt].r>n) blo[cnt].r=n;
    // printf("l=%lld r=%lld\n",blo[cnt].l,blo[cnt].r);
    for(ll j=blo[cnt].l,k=1;j<=blo[cnt].r;j++,k++) {
      blo[cnt].a[k].val=a[j];blo[cnt].a[k].id=j;pos[j]=cnt;
    }
    ll len=blo[cnt].r-blo[cnt].l+1;
    sort(blo[cnt].a+1,blo[cnt].a+len+1);
    // for(ll j=1;j<=len;j++) {
    //   printf("a[%lld].val=%lld a[%lld].id=%lld\n"
    //   ,j,blo[cnt].a[j].val,j,blo[cnt].a[j].id);
    // }
  }

  while(m--) {
    ll op,l,r,k;
    op=read();l=read();r=read();k=read();
    if(op==1) {
      if(k>r-l+1) {writeln(-1);continue;}
      if(pos[l]!=pos[r]) Reorg(l,r);
      else Reorg_(l,r);
      // for(ll i=1;i<=lent;i++) {
      //   printf("t[%lld].val=%lld t[%lld].id=%lld\n",i,t[i].val,i,t[i].id);
      // }
      ll lp=-2e9,rp=2e9;
      while(lp<rp) {
        ll mid=(lp+rp+1)>>1;
        if(Check(mid,l,r,k)) lp=mid;
        else rp=mid-1;
      }
      writeln(lp);
    }
    if(op==2) {
      if(pos[l]!=pos[r]) {
        if(l==blo[pos[l]].l) {blo[pos[l]].laz+=k;}
        else {
          ll len=blo[pos[l]].r-blo[pos[l]].l+1;
          for(ll i=1;i<=len;i++) {
            if(blo[pos[l]].a[i].id>=l) {
              blo[pos[l]].a[i].val+=k;
            }
          }
          Refactor(l,1);
        }
        if(r==blo[pos[r]].r) {blo[pos[r]].laz+=k;}
        else {
          ll len=blo[pos[r]].r-blo[pos[r]].l+1;
          for(ll i=1;i<=len;i++) {
            if(blo[pos[r]].a[i].id<=r) {
              blo[pos[r]].a[i].val+=k;
            }
          }
          Refactor(r,0);
        }
      }
      else {
        ll len=blo[pos[l]].r-blo[pos[l]].l+1;
        for(ll i=1;i<=len;i++) {
          if(blo[pos[l]].a[i].id>=l&&blo[pos[l]].a[i].id<=r) {
            blo[pos[l]].a[i].val+=k;
          }
        }
        Refactor_(l,r);
      }
      for(ll i=pos[l]+1;i<pos[r];i++) {blo[i].laz+=k;}
    }
  }

  return 0;
}