模板
pzc2004
2020-11-15 20:48:09
用来存储各种模板
# 快读（getchar）
``` cpp
template <class T>
inline void read(T &x)
{
x= 0;
char c= getchar();
while(!isdigit(c)) c= getchar();
while(isdigit(c)) x= x * 10 + (c & 15), c= getchar();
}
```
# 手写bitset
``` cpp
namespace BitsetByMyself
{
#define belong(x) ((x) >> 6)
template <int SIZE>
struct Bitset
{
int len;
int size;
unsigned long long val[belong(SIZE - 1) + 1];
inline Bitset(int size= 0) : size(size) { len= belong(size - 1) + 1, memset(val, 0, 8 * len); } //构造函数
inline bool operator[](int x) const { return (val[belong(x)] >> (x & 63)) & 1; } //获取第x位的值
inline void set(int x) { val[belong(x)]|= 1ull << (x & 63); } //将第x位设置为1
inline void reset(int x) { val[belong(x)]&= UINT64_MAX ^ (1ull << (x & 63)); } //将第x位设置为0
inline void set(int x, bool y) { y ? set(x) : reset(x); } //将第x位设置为y
inline void flip(int x) { val[belong(x)]^= 1ull << (x & 63); } //翻转第x位
inline Bitset operator&(const Bitset &a) const //按位与
{
Bitset ans(min(size, a.size));
for(int i= 0; i < ans.len; i++) ans.val[i]= val[i] & a.val[i];
return ans;
}
inline Bitset operator|(const Bitset &a) const //按位或
{
Bitset ans(min(size, a.size));
for(int i= 0; i < ans.len; i++) ans.val[i]= val[i] | a.val[i];
return ans;
}
inline Bitset operator^(const Bitset &a) const //按位异或
{
Bitset ans(min(size, a.size));
for(int i= 0; i < ans.len; i++) ans.val[i]= val[i] ^ a.val[i];
return ans;
}
inline void operator&=(const Bitset &a) //按位与并赋值
{
for(int i= 0; i < a.len; i++) val[i]&= a.val[i];
}
inline void operator|=(const Bitset &a) //按位或并赋值
{
for(int i= 0; i < a.len; i++) val[i]|= a.val[i];
}
inline void operator^=(const Bitset &a) //按位异或并赋值
{
for(int i= 0; i < a.len; i++) val[i]^= a.val[i];
}
inline void get(Bitset &a, int l, int r) //获取[l,r]区间内的所有位，赋值给a
{
a= Bitset(r - l + 1);
if(belong(l) == belong(r))
{
a.val[0]= val[belong(l)] >> (l & 63);
a.val[0]&= ((1ull << (r - l)) - 1) | (1ull << (r - l));
}
else
{
int x= belong(l) + 1, y= belong(r) - 1;
a.val[0]= val[belong(l)] >> (l & 63);
for(int i= x, j= 0; i <= y; i++, j++)
{
a.val[j]|= val[i] << ((64 - (l & 63) - 1)) << 1;
a.val[j + 1]= val[i] >> (l & 63);
}
if((l & 63) > (r & 63))
a.val[a.len - 1]|= (val[belong(r)] & (((1ull << (r & 63)) - 1) | (1ull << (r & 63)))) << ((64 - (l & 63) - 1)) << 1;
else
a.val[a.len - 2]|= val[belong(r)] << ((64 - (l & 63) - 1)) << 1, a.val[a.len - 1]= (val[belong(r)] & (((1ull << (r & 63)) - 1) | (1ull << (r & 63)))) >> (l & 63);
}
}
};
#undef belong
} // namespace BitsetByMyself
```