P5356 由乃打扑克
题面
题解
就是区间加区间 \(k\,\mathrm{th}\)，线段树难以维护，考虑分块，记块长为 \(B\)。
每个块内维护排好序的序列以及有序序列中每个数的实际 \(\mathrm{id}\)，区间修改对于整块直接打 \(\mathrm{tag}\)，对于散块可以用归并排序的方式进行重构，这一部分单次 \(O(B+\frac nB)\)；区间查询需要在外层二分答案，预先将散块部分排序（使用归并），然后整块直接块内二分，可以做到 \(O(B+\frac nB\log B\log A)\)。
视 \(n,m\) 同阶，所以总复杂度 \(O(n(B+\frac{n\log B\log A}B))\)，取 \(B\sim O(\sqrt n\log n)\) 可以近似得到 \(O(n\sqrt n\log n)\) 的复杂度。
如果被卡常，可以在整块二分加剪枝：如果全块都大于给定值或都小于给定值，直接 return 即可。
Code
#include<bits/stdc++.h>
#pragma optimize(2)
#pragma optimize(3)
#pragma optimize("Ofast")
#pragma optimize("inline")
#pragma optimize("unroll-loops")
#pragma optimize("-funroll-loops")
#pragma optimize("inline-functions")
#pragma optimize("no-stack-protector")
#pragma optimize("inline-small-functions")
#pragma optimize("-funsafe-loop-optimizations")
#pragma optimize("inline-functions-called-once")
using namespace std;
typedef pair<int,int>P;
int n,m,a[100005];
const int T=256;
int d[100005],e[100005],f[600];//第d[i]块第e[i]个，第t块第1个编号为f[i]
P b[600][600];
int len[600];
int lazy[600];
void upd(int p,int l,int r,int k){
for(register int i=l;i<=r;i++) a[i]+=k;
for(register int i=1;i<=T;i++){
if(b[p][i].second>=l&&b[p][i].second<=r){
b[p][i].first+=k;
}
}
sort(b[p]+1,b[p]+1+len[p]);
}
void update(int l,int r,int k){
if(d[l]==d[r]){
upd(d[l],l,r,k);
return;
}
upd(d[l],l,f[d[l]+1]-1,k);
upd(d[r],f[d[r]],r,k);
l=d[l]+1; r=d[r]-1;
for(register int i=l;i<=r;i++) lazy[i]+=k;
}
int ll[600],rr[600],ans[600];
int f1(int l,int r,int k){
int cnt=0;
for(register int i=l;i<=r;i++){
if(a[i]+lazy[d[i]]<=k) cnt++;
}
return cnt;
}
int f2(int p,int k){
k-=lazy[p];
if(k>=b[p][len[p]].first) return len[p];
else if(k<b[p][1].first) return 0;
int l=ll[p],r=rr[p];
while(l<=r){
int mid=l+r>>1;
if(b[p][mid].first<=k) l=mid+1;
else r=mid-1;
}
return r;
}
int solve(int l,int r,int k,int ps=2){//[l,r]中<=k的数个数 \
ps=0表示上次个数<k，ps=1表示>=k ps=2不知道
/*
if(ps==0){
for(register int i=1;i<=d[n];i++){
ll[i]=ans[i];
}
}else if(ps==1){
for(register int i=1;i<=d[n];i++){
rr[i]=ans[i];
}
}
*/
if(d[l]==d[r]) return f1(l,r,k);
int cnt=f1(l,f[d[l]+1]-1,k)+f1(f[d[r]],r,k);
l=d[l]+1; r=d[r]-1;
for(register int i=l;i<=r;i++){
if(ps==0) ll[i]=ans[i];
else if(ps==1) rr[i]=ans[i];
cnt+=(ans[i]=f2(i,k));
}
return cnt;
}
int query(int l,int r,int k){
if(r-l+1<k) return -1;
int L=-2000000000,R=2000000000,ps=2;
for(register int i=1;i<=d[n];i++){
ll[i]=1,rr[i]=len[i];
ans[i]=-1;
}
while(L<=R){
int mid=(long long)(L)+R>>1;
if(solve(l,r,mid)<k){
L=mid+1;
ps=0;
}
else{
R=mid-1;
ps=1;
}
}
return L;
}
void print(){
for(register int i=1;i<=d[n];i++){
cout<<"------------\n";
cout<<"对于第"<<i<<"块（"<<f[i]<<"~"<<f[i]+len[i]-1<<"）：\n";
cout<<"a数组：";
for(register int j=f[i];j<=f[i]+len[i]-1;j++) cout<<a[j]<<' '; cout<<'\n';
cout<<"b数组：\n";
for(register int j=1;j<=len[i];j++){
cout<<b[i][j].first<<' '<<b[i][j].second<<'\n';
}
cout<<"lazy="<<lazy[i]<<"\n------------\n";
}
}
inline int read(){
int ans=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-f;
c=getchar_unlocked();
}
while(c>='0'&&c<='9'){
ans=(ans<<3)+(ans<<1)+c-48;
c=getchar_unlocked();
}
return ans*f;
}
inline char readchar(){
bk:
char c=getchar_unlocked();
if(c>32&&c<127) return c;
if(c==EOF) return 0;
goto bk;
}
void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x<10) putchar(x+48);
else{
write(x/10);
putchar(x%10+48);
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
n=read(); m=read();
for(register int i=1;i<=n;i++) a[i]=read();
for(register int i=1;i<=n;i++){
d[i]=(i+T-1)/T;
e[i]=d[i]!=d[i-1]?1:e[i-1]+1;
b[d[i]][e[i]]=P(a[i],i);
if(e[i]==1) f[d[i]]=i;
len[d[i]]++;
}
for(register int i=1;i<=d[n];i++) sort(b[i]+1,b[i]+len[i]+1);
int opt,l,r,k;
while(m--){
opt=read(); l=read(); r=read(); k=read();
if(opt==2) update(l,r,k);
else{
write(query(l,r,k)); putchar(10);
}
}
return 0;
}