Comet OJ - Contest #16 小 C 的可重集（随机二分）（线段树）

本文主要是介绍Comet OJ - Contest #16 小 C 的可重集（随机二分）（线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

秀儿操作！我们每次随一个区间，考虑求出 $\ge$ 它的区间个数
注意到左端点固定区间大小随右端点递增，于是 $\ge$ 一个区间的是一个前缀
如果个数 $\ge k$ 那么可以给每一个左端点的区间钦定一个上界，否则可以钦定一个下界
这样的期望次数是 $\log n$ 的，相当于每次 $b a n$ 掉一部分
于是问题变成了对于给定区间，对每一个左端点求前缀的终止位置使得这个前缀 $\ge$ 给点区间
这个位置单调，于是我们可以 $two\ pointer$ 扫一下，线段树维护值域

#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
typedef long long ll;
template <typename T> T read(){T cnt=0, f=1; char ch=0;while(!isdigit(ch)){ ch=getchar(); if(ch=='-') f=-1; }while(isdigit(ch)) cnt=cnt*10+(ch-'0'), ch=getchar();return cnt*f;
}
std::mt19937 rn(time(0));
std::uniform_int_distribution<int> rnd(0,(int)1e9);
int gi(){ return read<int>(); }
ll gl(){ return read<ll>(); }
cs int N = 1e5 + 50;
int n, a[N]; ll k;
int lim[N];
namespace SGT{cs int M = 1<<17;int c[M<<1|5]; bool les[M<<1|5];void clr(){ memset(c,0,sizeof(c));memset(les,0,sizeof(les));}void pushup(int x){c[x]=c[x<<1]|c[x<<1|1];les[x]=les[x<<1]|(!c[x<<1]&&les[x<<1|1]);}void add(int x, int v){if(!x) return;c[x+=M]+=v; les[x]=c[x]<0;for(x>>=1;x;x>>=1) pushup(x);}
}
ll work(int l, int r){SGT::clr(); ll ct = 0;for(int i=l; i<=r; i++) SGT::add(a[i],1);for(int i=1; i<=n; i++){lim[i]=max(i-1,lim[i-1]);while(!SGT::les[1]&&lim[i]<=n) SGT::add(a[++lim[i]],-1);if(i<=lim[i]) SGT::add(a[i],1);ct += (ll)lim[i]-i;} return ct;
}
int main(){n=gi(), k=(ll)n*(n+1)/2-gl()+1;for(int i=1; i<=n; i++) a[i]=gi();static int st[N]; int tp=0; static int L[N], R[N];for(int i=1; i<=n; i++)st[++tp]=i, L[i]=i, R[i]=n;int T = 80;while(T--){int c=st[rnd(rn)%tp+1];int t=L[c]+rnd(rn)%(R[c]-L[c]+1);if(work(c,t)>=k) for(int i=1; i<=tp; i++) R[st[i]]=min(R[st[i]],lim[st[i]]-1);else for(int i=1; i<=tp; i++)L[st[i]]=max(L[st[i]],lim[st[i]]);int ct=0; for(int i=1; i<=tp; i++) if(L[st[i]]<=R[st[i]]) st[++ct]=st[i]; tp=ct; if(tp==1&&L[st[1]]==R[st[1]]) break;}int l=st[1], r=R[st[1]];sort(a+l,a+r+1);for(int i=l; i<=r; i++) cout<<a[i]<<" ";return 0;
}