自定义头文件
Mars_Dingdang
2020-12-19 16:22:59
## 自定义头文件使用介绍
### 一、代码主体
```cpp
struct Bignum{
int len,s[maxm];
Bignum(){
len=1;
memset(s,0,sizeof(s));
}
Bignum operator =(const char *num){
len=strlen(num);
rep(i,0,len-1) s[i]=(num[len-i-1]^48);
return *this;
}
Bignum operator =(const int num){
char a[maxm];
sprintf(a,"%d",num);
*this = a;
return *this;
}
Bignum(int num){*this = num;}
Bignum(const char *num){*this = num;}
Bignum operator +(const Bignum &a){
Bignum c;
c.len=max(len,a.len)+1;
for(int i=0,x=0;i<c.len;i++){
c.s[i]=s[i]+a.s[i]+x;
x=c.s[i]/10;
c.s[i]%=10;
}
if(c.s[c.len-1]==0) c.len--;
return c;
}
Bignum operator +=(const Bignum &a){
*this = *this + a;
return *this;
}
Bignum operator *(const Bignum &a){
Bignum c;
c.len=len+a.len;
rep(i,0,len-1)
{
rep(j,0,a.len-1)
{
c.s[i+j] += s[i]*a.s[j];
c.s[i+j+1] += c.s[i+j]/10;
c.s[i+j] %= 10;
}
}
if(c.s[c.len-1]==0) c.len--;
return c;
}
Bignum operator *=(const Bignum &a){
*this = *this * a;
return *this;
}
bool operator <(const Bignum &x)const{
if(len!=x.len) return len<x.len;
for(int i=len-1;i>=0;i--)
if(s[i]!=x.s[i]) return s[i]<x.s[i];
return false;
}
bool operator >(const Bignum &x)const{return x<*this;}
bool operator <=(const Bignum &x)const{return !(x<*this);}
bool operator >=(const Bignum &x)const{return !(*this<x);}
bool operator ==(const Bignum &x)const{return !(*this<x||x<*this);}
bool operator !=(const Bignum &x)const{return (*this<x||x<*this);}
};
ostream& operator <<(ostream &out,const Bignum &x){
for(int i=x.len-1;i>=0;i--) cout<<x.s[i];
return out;
}
istream& operator >>(istream &in,Bignum &x){
char num[maxm];
in>>num;
x=num;
return in;
}
class PrimeNumber{
public:
int tot=0,prime[maxn]={0};
bool a[maxn]={0};
inline bool isPrime(int x){
if(x<=1) return 0;
if(x==2) return 1;
else if(!(x&1)) return 0;
for(int i=3;i*i<=x;i+=2)
if(x%i==0) return 0;
return 1;
}
inline void EulerFind(int n){
memset(a,1,sizeof(a));
a[0]=a[1]=false;
for(int i=2;i<=n;i++){
if(a[i]==true){
prime[++tot]=i;
}
for(int j=1;j<=tot;j++){
int t=i*prime[j];
if(t>n) break;
a[t]=false;
if(i%prime[j]==0) break;
}
}
}//欧拉筛
};
class Dijkstra{
private:
struct node{
int w,now;
bool operator <(const node &x)const{
return w>x.w;
}
};
priority_queue<node> q;
public:
struct Edge{
int from,to,w,next;
}e[maxn];
int head[maxn],tot,dis[maxn],s;
bool vis[maxn];
inline void add(int u,int v,int w){
e[++tot].from=u;
e[tot].to=v;
e[tot].w=w;
e[tot].next=head[u];
head[u]=tot;
}
inline void dijkstra(){
memset(dis,0x3f3f3f3f,sizeof(dis));
dis[s]=0;
q.push((node){0,s});
while(!q.empty()){
node x=q.top();q.pop();
int u=x.now;
if(vis[u]) continue; vis[u]=1;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
q.push((node){dis[v],v});
}
}
}
}
};
class KMP{
public:
int n,m;
char a[maxn],b[maxn];
inline void pre(){
n=strlen(a+1);
m=strlen(b+1);
p[1]=0;
now=0;
rep(i,1,m-1){
while(now>0 && b[now+1]!=b[i+1]) now=p[now];
if(b[now+1]==b[i+1]) now++;
p[i+1]=now;
}
}
inline void find(){
now=0;
rep(i,0,n-1){
while(now>0 && b[now+1]!=a[i+1]) now=p[now];
if(b[now+1]==a[i+1]) ++now;
if(now==m){
printf("%d\n",(i+1)-m+1);
now=p[now];
}
}
rep(i,1,m) printf("%d ",p[i]);
}
int p[maxn],now;
};
class ST{
public:
int n,m,a[maxn];
inline void init(){
n=read(),m=read();
rep(i,1,n) a[i]=read();
l[0]=-1;//l[i]= int [log2(i)]
rep(i,1,n)
{
f[i][0]=a[i];
l[i]=l[i>>1]+1;
}
rep(j,1,maxl)
{
for(int i=1;i+(1<<j)-1<=n;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);//Time: O(NlogN)
}
}
inline int query(int x,int y){
int k=l[y-x+1];
return max(f[x][k],f[y-(1<<k)+1][k]);// Time: O(1)
}
private:
#define re register
#define gg (getchar())
inline int read(){
register int x=0,f=1;
re char c=gg;
while(!isdigit(c)){
if(c=='-') f=-1;
c=gg;
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=gg;
}
return x*f;
}
#undef re
#undef gg
int l[maxn],f[maxn][maxl+5];//Memory: O(NlogN)
};
inline long long Pow(int a,int x){
long long ans=1;
while(x){
if(x&1) ans*=a;
a*=a;
x>>=1;
}
return ans;
}
class BinaryIndexTree{
private:
int c[maxn];
inline int lowbit(int x){return x&(-x);}
public:
#define Max(a,b) (a>b?a:b)
int n;
inline void update(int x,int v){
for(;x<=n;x+=lowbit(x)) c[x]+=v;
}
inline int sum(int x) {
int res=0;
for(;x;x-=lowbit(x)) res+=c[x];
return res;
}
#undef Max(a,b)
};
#define re register
#define gg (getchar())
inline ll input(){
register ll x=0,f=1;
re char c=gg;
while(!isdigit(c)){
if(c=='-') f=-1;
c=gg;
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=gg;
}
return x*f;
}
#undef re
#undef gg
struct SegmentTree{
ll add[maxn<<2]={0},sum[maxn<<2]={0},mul[maxn<<2]={0},a[maxn];
inline void pushdown(ll k,ll l,ll r){
if(!add[k] && mul[k]==1) return ;
ll len=r-l+1;
sum[k<<1]=(sum[k<<1]*mul[k]+add[k]*(len-(len>>1)))%mod;
sum[k<<1|1]=(sum[k<<1|1]*mul[k]+add[k]*(len>>1))%mod;
add[k<<1]=(add[k<<1]*mul[k]+add[k])%mod;
add[k<<1|1]=(add[k<<1|1]*mul[k]+add[k])%mod;
(mul[k<<1]*=mul[k])%=mod;
(mul[k<<1|1]*=mul[k])%=mod;
add[k]=0;mul[k]=1;
}
inline void build(ll k,ll l,ll r){
add[k]=0;mul[k]=1;
if(l==r){
sum[k]=a[l]%mod;
return ;
}
ll mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
sum[k]=sum[k<<1]+sum[k<<1|1];sum[k]%=mod;
}
inline void multiply(ll k,ll l,ll r,ll x,ll y,ll v){
pushdown(k,l,r);
if(x<=l&&y>=r){
(sum[k]*=v)%=mod;
(mul[k]*=v)%=mod;
return ;
}
ll mid=(l+r)>>1;
if(x<=mid) multiply(k<<1,l,mid,x,y,v);
if(y>mid) multiply(k<<1|1,mid+1,r,x,y,v);
sum[k]=sum[k<<1]+sum[k<<1|1];sum[k]%=mod;
}
inline void update(ll k,ll l,ll r,ll x,ll y,ll v){
pushdown(k,l,r);
if(l==r){
(sum[k]+=v*(r-l+1))%=mod;
(add[k]+=v)%=mod;
return ;
}
ll mid=(l+r)>>1;
if(x<=mid) update(k<<1,l,mid,x,y,v);
if(y>mid) update(k<<1|1,mid+1,r,x,y,v);
sum[k]=(sum[k<<1]+sum[k<<1|1])%mod;
}
inline ll query(ll k,ll l,ll r,ll x,ll y){
pushdown(k,l,r);
if(x<=l&&y>=r) return sum[k];
ll mid=(l+r)>>1;
ll res=0;
if(x<=mid) (res+=query(k<<1,l,mid,x,y))%=mod;
if(y>mid) (res+=query(k<<1|1,mid+1,r,x,y))%=mod;
return res;
}
};
class MST{
private:
int fa[maxn],n=0,m=0,ans=0;
inline int find(int k){
if(k==fa[k]) return fa[k];
return fa[k]=find(fa[k]);
}
public:
struct node{
int u,v,w;
bool operator <(const node &x)const{
return w<x.w;
}
}a[maxn];
inline void kruskal(){
rep(i,1,n) fa[i]=i;
int cnt=0;
rep(i,1,m)
{
int f1=find(a[i].u);
int f2=find(a[i].v);
if(f1!=f2) {
ans+=a[i].w;
fa[f2]=f1;
cnt++;
if(cnt==n-1) break;
}
}
}
//<------------Kruskal-------------->
const int inf=0x3f3f3f3f;
struct Edge{
int from,to,w,next;
}e[maxn];
int head[maxn],dis[maxn],tot,cnt;
bool vis[maxn];
inline void add(int u,int v,int w){
e[++tot].to=v;
e[tot].w=w;
e[tot].next=head[u];
head[u] = tot;
}
#define mp(x,y) make_pair(x,y)
priority_queue< pair<int,int> > q;
inline int prim(){
q.push(mp(0,1));
while(!q.empty() && cnt<=n-1){
int now=q.top().second;
int w=q.top().first;q.pop();
if(vis[now]) continue;
vis[now]=1;
ans+=w;
cnt++;
for(int i=head[now];i;i=e[i].next){
int x=e[i].to;
if(!vis[x]){
q.push(mp(-e[i].w,x));
}
}
}
return -ans;
}
#undef mp(x,y)
//<-------------prim--------------->
};
#undef rep(ii,aa,bb)
```
### 二、功能介绍
本头文件基本包含了 c++ 常备头文件，如 `iostream`, `cstdio`, `cmath`, `algorithm` 等，可以实现库函数和 STL 的直接调用实现。更进一步地了解可以使用的库函数和 STL 容器请自行百度（由于这些均是已开发头文件）。
STL 容器大致包含了 `vector`, `map`, `queue`, `priority_queue`, `stack`, `string`, `set`等常用模板库。当然也可以自行更改 `Mars.h` 以添加。
接下来重点介绍手写的封装数据结构：
1. 变量（常量）等可直接调用函数：
- 长整型 `ll`;
- 数值范围 `maxm=4000`用于高精位数，`maxn=1e5+5`, `maxl=20`用于 RMQ, `mod=1e9+7`；
- 循环简化 `rep(i,a,b)`；
- 读入优化 `ll input()`；
- 快速幂 `ll Pow(int,int)`;
2. 手写数据结构：
- 高精加法乘法 `Bignum`，包括输入输出流的定义
- 质数 `PrimeNumber` 中包含判断函数 `bool isPrime(int)` $O(\sqrt n)$，以及欧拉筛 `void EulerFind(int)`;
- 最短路 `Dijkstra` 中包含链式前向星连边操作 `add` 与 `dijkstra` 函数，$O((n+m)\log m)$;
- `KMP` 基本函数
- RMQ 问题的 `ST` 中包含初始化 `void init()` 与查询最大值 `int query(int,int)`；
- 树状数组 `BinaryIndexTree` 的单点修改 `void update(int,int)` 和前缀和查询 `int sum(int)`；
- 线段树 `SegmentTree`;
- 最小生成树 `MST` 的 `void kruskal()`, `prim()`。