LuoguP5356 [Ynoi2017] 由乃打扑克

(Updated: )
oi
,

Description

题目链接：P5356

一个长为 $n$ 的序列 $a$，需要支持 $m$ 次操作，操作有两种：

  1. 查询区间 $[l,r]$ 的第 $k$ 小值。
  2. 区间 $[l,r]$ 加上 $k$。

$1\leq n,m\leq 10^5,-2\times 10^4\leq$ 每次加上的数和原序列的数 $\leq 2\times 10^4$。

Solution

查询第 $k$ 小，直接想到两种方法：

  1. 二分枚举然后再统计次数统计，复杂度 $O(\sqrt{N}log_2V)$
  2. 值域分块，记录前缀和。

第一种方法显然

很遗憾，被我卡掉了。——lxl

但是却可以AC本题

考虑第二种方法区间修改有点困难，所以直接上第一种方法，修改时只要整块打上标记，散块暴力修改即可，加上各种优化：

  1. 二分的边界可以先跑一次求出最大最小值。
  2. 二分判断统计时，最大值也小于等于 $mid$，直接加上块长即可，最小值大于 $mid$，直接跳过即可。
  3. 一颗沉稳的心

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,S=250,M=N/S+10;
int n,m,tot,g[M],mn[M],mx[N];
vector<int> b[M],s[M];
I void B(CI x){s[x]=b[x],sort(s[x].begin(),s[x].end()),mn[x]=*s[x].begin(),mx[x]=*s[x].rbegin();}
I bool check(CI bL,CI bR,CI l,CI r,CI mid,CI k){
    RI i,S=0;if(bL==bR){for(i=l;i<=r;i++) if(b[bL][i]+g[bL]<=mid) S++;return S>=k;}
    for(i=l;i<b[bL].size();i++) if(b[bL][i]+g[bL]<=mid) S++;for(i=0;i<=r;i++) if(b[bR][i]+g[bR]<=mid) S++;
    for(i=bL+1;i<=bR-1;i++) if(mx[i]+g[i]<=mid) S+=b[i].size();
    else if(mn[i]+g[i]<=mid) S+=(upper_bound(s[i].begin(),s[i].end(),mid-g[i])-s[i].begin());return S>=k; 
}
I int Gmn(RI l,RI r){
    RI i,bL=1,bR=1,S=2e9;W(l>=b[bL].size()) l-=b[bL++].size();W(r>=b[bR].size()) r-=b[bR++].size();
    if(bL==bR){for(i=l;i<=r;i++) S=min(S,b[bL][i]+g[bL]);return S;}
    for(i=l;i<b[bL].size();i++) S=min(S,b[bL][i]+g[bL]);for(i=0;i<=r;i++) S=min(S,b[bR][i]+g[bR]);
    for(i=bL+1;i<=bR-1;i++) S=min(S,*s[i].begin()+g[i]);return S;
}
I int Gmx(RI l,RI r){
    RI i,bL=1,bR=1,S=-2e9;W(l>=b[bL].size()) l-=b[bL++].size();W(r>=b[bR].size()) r-=b[bR++].size();
    if(bL==bR){for(i=l;i<=r;i++) S=max(S,b[bL][i]+g[bL]);return S;}
    for(i=l;i<b[bL].size();i++) S=max(S,b[bL][i]+g[bL]);for(i=0;i<=r;i++) S=max(S,b[bR][i]+g[bR]);
    for(i=bL+1;i<=bR-1;i++) S=max(S,*s[i].rbegin()+g[i]);return S;
}
I int Q(RI l,RI r,CI k){
    if(r-l+1<k) return -1;RI i,L=Gmn(l,r),R=Gmx(l,r),S=2e9+1,mid,bL=1,bR=1;W(l>=b[bL].size()) l-=b[bL++].size();W(r>=b[bR].size()) r-=b[bR++].size();
    W(L<=R) check(bL,bR,l,r,mid=(1LL*L+R>>1),k)?(S=mid,R=mid-1):L=mid+1;return S==2e9+1?-1:S;
}
I void U(RI l,RI r,CI k){
    RI i,bL=1,bR=1;W(l>=b[bL].size()) l-=b[bL++].size();W(r>=b[bR].size()) r-=b[bR++].size();
    if(bL==bR){for(i=l;i<=r;i++) b[bL][i]+=k;return B(bL);}
    for(i=l;i<b[bL].size();i++) b[bL][i]+=k;B(bL);for(i=0;i<=r;i++) b[bR][i]+=k;B(bR);
    for(i=bL+1;i<=bR-1;i++) g[i]+=k;
}
int main(){ 
    RI i,x,opt,l,r,k;for(read(n,m),i=0;i<n;i++) read(x),b[i/S+1].push_back(x);tot=(n-1)/S+1;
    for(i=1;i<=tot;i++) B(i);for(i=1;i<=m;i++) if(read(opt,l,r,k),opt==1) writeln(Q(l-1,r-1,k));
    else U(l-1,r-1,k);return 0;
}