驴蛋蛋在愉快地与STL玩耍
突然间小A跳了出来对驴蛋蛋说,看你与STL玩的很开心啊,那我给你一个大小为N的vector,这个vector上每个位置上是一个set
每次我会在闭区间 [L,R] 中的每个set
小A走了,留下驴蛋蛋一个人外加一个长度为 N 的vector
根据小A的 C&＃43;&＃43;2.33 标准vector可以被视作一个数组,下标从 1 开始,大小不得超过65536
set
小A最多会进行Q 次(不超过 65536)完全符合 C&＃43;&＃43;2.33标准的操作,但如果出现询问时[L,R]区间里不足K个数的情况,你只需要对小A回答−1就好了
分析传说中的毒瘤题&＃xff1f;线段树&＃43;永久延迟标记&＃43;二分&＃43;bitset
空间不够&＃xff0c;被逼写了一次非结构体线段树&＃xff0c;这样只用开两倍了。
bitset以前写到过一次,stl黑科技。bitset的第i位为1表示i这个数在这个结点的集合里。
二分之前先查询一次&＃xff0c;把查询区间的数都染成1。
为助于理解&＃xff0c;把pre数组打印出来了&＃xff0c;二分的原理应该也很明显了吧&＃xff1f;
10000000000
11000000000
11100000000
11110000000
11111000000
11111100000
11111110000
11111111000
11111111100
11111111110
11111111111
#include
using namespace std;
#define N 10010
#define M 65540
#define lc (p<<1)
#define rc (p<<1|1)
struct email
{bitset
}t[M*2];
int n,q,k,ql,qr,op,cnt;
bitset
{t[p].bit[k]&＃61;1;if(ql<&＃61;l&&qr>&＃61;r){t[p].lazy[k]&＃61;1;return ;}int mid&＃61;l&＃43;r>>1;if(ql<&＃61;mid)update(lc,l,mid);if(qr>mid) update(rc,mid&＃43;1,r);
}inline void query(int p,int l,int r)
{if(ql<&＃61;l&&qr>&＃61;r){ans[cnt]|&＃61;t[p].bit;return ;}ans[cnt]|&＃61;t[p].lazy;int mid&＃61;l&＃43;r>>1;if(ql<&＃61;mid)query(lc,l,mid);if(qr>mid) query(rc,mid&＃43;1,r);
}inline int check(int mid)
{tmp&＃61;ans[cnt]&pre[mid];if(tmp.count()>&＃61;k)return 1;return 0;
}inline void solve()
{if(k&＃61;&＃61;0){puts("-1");return ;}cnt&＃43;&＃43;;query(1,1,n);if(ans[cnt].count()
}int main()
{scanf("%d%d",&n,&q);pre[0][0]&＃61;1;for(int i&＃61;1;i
}
京公网安备 11010802041100号