题面
驴蛋蛋在愉快地与STL玩耍
突然间小A跳了出来对驴蛋蛋说,看你与STL玩的很开心啊,那我给你一个大小为N的vector,这个vector上每个位置上是一个set<int>,
每次我会在闭区间 [L,R] 中的每个set<int>里插入一个数c,或者询问 [L,R] 区间所有set里所有数拿下来排序之后的严格第K小,现在你还开心吗，红红火火恍恍惚惚韩寒会画红槐花!!!!
小A走了,留下驴蛋蛋一个人外加一个长度为 N 的vector<set<int> >在风中凌乱，你能帮驴蛋蛋解除凌乱吗？
根据小A的 C++2.33 标准vector可以被视作一个数组,下标从 1 开始,大小不得超过65536
set<int>是一个集合,其中的数不得超过 10000 并且会被自动去重
小A最多会进行Q 次(不超过 65536)完全符合 C++2.33标准的操作,但如果出现询问时[L,R]区间里不足K个数的情况,你只需要对小A回答−1就好了
分析
传说中的毒瘤题？线段树+永久延迟标记+二分+bitset
空间不够，被逼写了一次非结构体线段树，这样只用开两倍了。
bitset以前写到过一次,stl黑科技。bitset的第i位为1表示i这个数在这个结点的集合里。
二分之前先查询一次，把查询区间的数都染成1。
为助于理解，把pre数组打印出来了，二分的原理应该也很明显了吧？
10000000000 11000000000 11100000000 11110000000 11111000000 11111100000 11111110000 11111111000 11111111100 11111111110 11111111111
代码
#include<bits/stdc++.h> using namespace std; #define N 10010 #define M 65540 #define lc (p<<1) #define rc (p<<1|1) struct email { bitset<N>lazy,bit; }t[M*2]; int n,q,k,ql,qr,op,cnt; bitset<N>ans[M],pre[N],tmp; inline void update(int p,int l,int r) { t[p].bit[k]=1; if(ql<=l&&qr>=r) { t[p].lazy[k]=1; return ; } int mid=l+r>>1; if(ql<=mid)update(lc,l,mid); if(qr>mid) update(rc,mid+1,r); } inline void query(int p,int l,int r) { if(ql<=l&&qr>=r) { ans[cnt]|=t[p].bit; return ; } ans[cnt]|=t[p].lazy; int mid=l+r>>1; if(ql<=mid)query(lc,l,mid); if(qr>mid) query(rc,mid+1,r); } inline int check(int mid) { tmp=ans[cnt]&pre[mid]; if(tmp.count()>=k)return 1; return 0; } inline void solve() { if(k==0){puts("-1");return ;} cnt++;query(1,1,n); if(ans[cnt].count()<k){puts("-1");return ;} int l=0,r=N-2,ans,mid; while(l<=r) { mid=l+r>>1; if(check(mid))ans=mid,r=mid-1; else l=mid+1; } printf("%d ",ans); } int main() { scanf("%d%d",&n,&q); pre[0][0]=1; for(int i=1;i<N;i++) pre[i]=pre[i-1],pre[i][i]=1; while(q--) { scanf("%d%d%d%d",&op,&ql,&qr,&k); if(op==1)update(1,1,n); else solve(); } return 0; }