LuoguP5356 [Ynoi2017] 由乃打扑克
Description
题目链接：P5356
一个长为 n 的序列 a，需要支持 m 次操作，操作有两种：
- 查询区间 [l,r] 的第 k 小值。
- 区间 [l,r] 加上 k。
1leq n,mleq 10^5,-2times 10^4leq 每次加上的数和原序列的数 leq 2times 10^4。
Solution
查询第 k 小，直接想到两种方法：
- 二分枚举然后再统计次数统计，复杂度 O(sqrt{N}log_2V)
- 值域分块，记录前缀和。
第一种方法显然
很遗憾，被我卡掉了。——lxl
但是却可以AC本题
考虑第二种方法区间修改有点困难，所以直接上第一种方法，修改时只要整块打上标记，散块暴力修改即可，加上各种优化：
- 二分的边界可以先跑一次求出最大最小值。
- 二分判断统计时，最大值也小于等于 mid，直接加上块长即可，最小值大于 mid，直接跳过即可。
- 一颗沉稳的心
Code
代码语言：javascript复制#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 '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;
}
