题解 P5356 【[Ynoi2017]由乃打扑克】
Jμdge
2019-11-14 07:45:01
果然呢， lxl dl 出的题目永远都是调完代码之后还能卡一个晚上的常
做法讲道理是 ynoi 中最水的一批了，思路就是 ： 分块+二分答案+块内二分 ，复杂度是 $\Big(n\log B \Big) + \Big( B+{n\over B}\Big) +\Big( \frac{n}{B} \log B \log MX \Big) $
然后据JZ 姐姐说这玩意儿 B 取 $\sqrt {n\log n }$ 最优，但实际上并不是，实测 B 是要小一些的，大概是初始化的时候常数会大些（也可能是咱的常数大些）
那么接下来最主要的事情就是**卡常**了 kk
>首先一堆卡常的语句就不用说了
>其次我们直接读入的数据直接放到块内，反正留着也没别的用
>还有直接除 bl 得到 pos 要比预处理 pos 快（实锤）
>最后也是最关键的我们查找的时候可以预处理出左右两小块 $l, r$ 范围内的元素，这样两个小块的询问也变成了 $\log $
# Code
```
//by Judge
#define HGS_AK_IOI true
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define Rg register
#define P pair<int,int>
#define fi first
#define se second
#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)
#define open(S) freopen(S".in","r",stdin),freopen(S".out","w",stdout)
using namespace std;
const int inf=2e9+7;
const int M=2e5+23;
typedef int arr[M];
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){ int x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} char sr[1<<21],z[20];int CCF=-1,Z;
inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;}
inline void print(int x,char chr='\n'){
if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr;
} int n,m,bl,mx,na,nb,sum; arr L,R; P f[M],a[M],b[M];
struct Pt{ int sz,L,R,tag;
inline void init(int l,int r){ L=l,R=r,sort(f+l,f+r+1); }
inline void copy(const Pt& b,int l,int r,int s){ tag=b.tag,R=(L=s)-1;
fp(i,b.L,b.R) if(l<=f[i].se&&f[i].se<=r) f[++R]=f[i];
}
inline void add(int l,int r,int k){ na=nb=0;
fp(i,L,R) if(l<=f[i].se&&f[i].se<=r)
a[++na]=f[i],a[na].fi+=k; else b[++nb]=f[i];
merge(a+1,a+1+na,b+1,b+1+nb,f+L);
}
inline int ask(int x){ Rg int l=L,r=R;
while(l<=r){ Rg int mid=(l+r)>>1;
(f[mid].fi+tag<=x)?(l=mid+1):(r=mid-1);
} return r-L+1;
}
}bk[M];
double y,eps=1e-8;
#define pos(x) (int(x*y+eps))
signed main(){ Rg int op,l,r,k,pl,pr;
n=read(),m=read(),bl=pow(n*log(n),0.425),y=1.0/bl,mx=pos(n);
fp(i,1,n) sum+=(f[i].fi=read()),f[i].se=i;
fp(i,0,mx) L[i]=R[i-1]+1,R[i]=(i+1)*bl-1;
R[mx]=n; fp(i,0,mx) bk[i].init(L[i],R[i]);
fp(t,1,m){ op=read(),l=read(),r=read();
k=read(),pl=pos(l),pr=pos(r);
if(op&1){
if(r-l+1<k){ print(-1);continue; }
Rg int ll=0,rr=sum,mid,num;
if(pl==pr){
bk[mx+1].copy(bk[pl],l,r,n+1);
while(ll<=rr){ mid=(ll+rr)>>1;
num=bk[mx+1].ask(mid);
(num>=k)?(rr=mid-1):(ll=mid+1);
}
} else{
bk[mx+1].copy(bk[pl],l,r,n+1);
bk[mx+2].copy(bk[pr],l,r,bk[mx+1].R+1);
while(ll<=rr){ mid=(ll+rr)>>1;
num=bk[mx+1].ask(mid)+bk[mx+2].ask(mid);
for(Rg int i=pl+1;num<k&&i<pr;++i)
num+=bk[i].ask(mid);
(num>=k)?(rr=mid-1):(ll=mid+1);
}
} print(ll);
} else{ sum+=k;
if(pl==pr) bk[pl].add(l,r,k);
else{ fp(i,pl+1,pr-1) bk[i].tag+=k;
bk[pl].add(l,r,k),bk[pr].add(l,r,k);
}
}
} return Ot(),0;
}
```cpp