为了节省写数据结构的时间
方便建立多个相同的数据结构，准备把许多数据结构用结构体封装一下来用
链式前向星
namespace lsq {
typedef int lsqxx;
struct lq {
struct lqbz {
lsqxx v,w,nxt;
} e[1000005];
lsqxx h[1000005],cnt;
inline void add(lsqxx u,lsqxx v,lsqxx w=1) {
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=h[u];
h[u]=cnt;
}
void erase() {cnt=0;memset(h,0,sizeof(h));return;}
#define F(z,u) for(int j=z.h[u],v=z.e[j].v,w=z.e[j].w;j;j=z.e[j].nxt,v=z.e[j].v,w=z.e[j].w)
};
};
使用以下方法建立链式前向星
lq x;
使用以下方法遍历
F(x,u)//x为建立的结构体变量名 u为开始遍历的点
{
}
在循环中使用变量 $v$ $w$
获取终点的编号以及边权的值
线段树
线段树基础
struct x_trees{
struct{
int l,r,sum,lan;
}t[2000005];
void build(int k,int l,int r)
{
t[k].l=l;t[k].r=r;
if(l==r) return;
int mid=l+r>>1;
build(k<<1,l,mid);
build((k<<1)+1,mid+1,r);
}
};
区间最大值
继承基础的代码，懒标记还没写，下次补上
struct max_x_trees:public x_trees{
void add(int k,int x,int y)
{
if(t[k].l>x||t[k].r<x) return;
if(t[k].l==t[k].r)
{
t[k].sum=y;
return;
}
add(k<<1,x,y);
add((k<<1)+1,x,y);
t[k].sum=max(t[k<<1].sum,t[(k<<1)+1].sum);
}
int ask(int k,int x,int y)
{
if(t[k].l>y||t[k].r<x) return 0;
if(t[k].l>=x&&t[k].r<=y) return t[k].sum;
return max(ask(k<<1,x,y),ask((k<<1)+1,x,y));
}
};
区间和
继续继承~
struct sum_x_trees:public x_trees{
void down(int k)
{
t[k<<1].lan+=t[k].lan;
t[k<<1].sum+=(t[k<<1].r-t[k<<1].l+1)*t[k].lan;
t[(k<<1)+1].lan+=t[k].lan;
t[(k<<1)+1].sum+=(t[(k<<1)+1].r-t[(k<<1)+1].l+1)*t[k].lan;
t[k].lan=0;
}
void add(int k,int x,int y,int z)
{
if(t[k].l>y||t[k].r<x) return;
if(t[k].l>=x&&t[k].r<=y)
{
t[k].sum+=(t[k].r-t[k].l+1)*z;
t[k].lan+=z;
return;
}
down(k);
add(k<<1,x,y,z);
add((k<<1)+1,x,y,z);
t[k].sum=t[k<<1].sum+t[(k<<1)+1].sum;
}
int ask(int k,int x,int y)
{
if(t[k].l>y||t[k].r<x) return 0;
if(t[k].l>=x&&t[k].r<=y) return t[k].sum;
down(k);
return ask(k<<1,x,y)+ask((k<<1)+1,x,y);
}
};
树链剖分
struct cut_tree:public sum_x_trees{
struct d{
int num;
int fa,d,big,siz;
int xh,top;
}e[100005];
int fxh[100005],cntx;
typedef int lsqxx;
struct lq {
struct lqbz {
lsqxx v,nxt;
}e[200005];
lsqxx h[100005],cnt;
void add(lsqxx u,lsqxx v) {
e[++cnt].v=v;
e[cnt].nxt=h[u];
h[u]=cnt;
}
#define F(z,u) for(int j=z.h[u],v=z.e[j].v;j;j=z.e[j].nxt,v=z.e[j].v)
};
int start[100005];
void dfs1(int t)
{
e[t].siz=1;
F(q,t)
{
if(e[t].fa==v) continue;
e[v].d=e[t].d+1;
e[v].fa=t;
dfs1(v);
e[t].siz+=e[v].siz;
if(e[e[t].big].siz<e[v].siz)
e[t].big=v;
}
}
void dfs2(int t)
{
if(!t) return;
e[t].xh=++cntx;
trees.add(1,cntx,cntx,e[t].num);
fxh[cntx]=t;
if(e[e[t].fa].big==t) e[t].top=e[e[t].fa].top;
else e[t].top=t;
dfs2(e[t].big);
F(q,t)
{
if(e[t].fa==v) continue;
if(e[t].big==v) continue;
dfs2(v);
}
}
void reset(int n,int root)
{
for(int i=1;i<=n;i++)
e[i].num=start[i];
e[root].fa=root;
e[root].d=1;
dfs1(root);
dfs2(root);
}
void change_line(int x,int y,int z)
{
if(e[e[x].top].d<e[e[y].top].d) swap(x,y);
if(e[e[x].top].d==e[e[y].top].d&&e[x].d<e[y].d) swap(x,y);
if(e[x].top!=e[y].top)
{
trees.add(1,e[e[x].top].xh,e[x].xh,z);
change_line(e[e[x].top].fa,y,z);
}
else
{
trees.add(1,e[y].xh,e[x].xh,z);
}
}
int search_line(int x,int y)
{
if(e[e[x].top].d<e[e[y].top].d) swap(x,y);
if(e[e[x].top].d==e[e[y].top].d&&e[x].d<e[y].d) swap(x,y);
if(e[x].top!=e[y].top)
{
return (trees.ask(1,e[e[x].top].xh,e[x].xh)+
search_line(e[e[x].top].fa,y));
}
else
{
return trees.ask(1,e[y].xh,e[x].xh);
}
}
void change_tree(int x,int y)
{
trees.add(1,e[x].xh,e[x].siz+e[x].xh-1,y);
}
int search_tree(int x)
{
return trees.ask(1,e[x].xh,e[x].xh+e[x].siz-1);
}
};
需要区间和 $sum_x_trees$ 作为前置
需要线段树基础的 $x_trees$ 作为前前置
初始值放入 $start$ 数组
在 $lq$ 中放入边(需调用两次建立双向边)
使用 $reset$ 初始化(包括两个DFS)
二维线段树
基础中的基础
struct double_x_tree{
struct {
int l1,r1,l2,r2;
int sum;
int lan;
}t[2000005];
int _a_[2005][2005];
};
支持矩阵区间和的修改，查询
struct double_add_x_tree{
void build(int k,int x1,int y1,int x2,int y2)
{
t[k].l1=x1;t[k].r1=y1;
t[k].l2=x2;t[k].r2=y2;
if(x1==x2&&y1==y2)
{
t[k].sum=_a_[x1][y1];
return;
}
int midx=x1+x2>>1,midy=y1+y2>>1;
if(x1==x2)
{
build((k<<2)-2+0,x1,y1,x2,midy);
build((k<<2)-2+1,x1,midy+1,x2,y2);
t[k].sum=t[(k<<2)-2+0].sum+t[(k<<2)-2+1].sum;
}
else if(y1==y2)
{
build((k<<2)-2+0,x1,y1,midx,y2);
build((k<<2)-2+1,midx+1,y1,x2,y2);
t[k].sum=t[(k<<2)-2+0].sum+t[(k<<2)-2+1].sum;
}
else
{
build((k<<2)-2+0,x1,y1,midx,midy);
build((k<<2)-2+1,midx+1,y1,x2,midy);
build((k<<2)-2+2,x1,midy+1,midx,y2);
build((k<<2)-2+3,midx+1,midy+1,x2,y2);
t[k].sum=t[(k<<2)-2+0].sum+
t[(k<<2)-2+1].sum+
t[(k<<2)-2+2].sum+
t[(k<<2)-2+3].sum;
}
}
void down(int k)
{
t[(k<<2)-2+0].sum+=t[k].lan*(t[(k<<2)-2+0].l2-t[(k<<2)-2+0].l1+1)*(t[(k<<2)-2+0].r2-t[(k<<2)-2+0].r1+1);
t[(k<<2)-2+1].sum+=t[k].lan*(t[(k<<2)-2+1].l2-t[(k<<2)-2+1].l1+1)*(t[(k<<2)-2+1].r2-t[(k<<2)-2+1].r1+1);
t[(k<<2)-2+2].sum+=t[k].lan*(t[(k<<2)-2+2].l2-t[(k<<2)-2+2].l1+1)*(t[(k<<2)-2+2].r2-t[(k<<2)-2+2].r1+1);
t[(k<<2)-2+3].sum+=t[k].lan*(t[(k<<2)-2+3].l2-t[(k<<2)-2+3].l1+1)*(t[(k<<2)-2+3].r2-t[(k<<2)-2+3].r1+1);
t[(k<<2)-2+0].lan+=t[k].lan;
t[(k<<2)-2+1].lan+=t[k].lan;
t[(k<<2)-2+2].lan+=t[k].lan;
t[(k<<2)-2+3].lan+=t[k].lan;
t[k].lan=0;
}
void add(int k,int x1,int y1,int x2,int y2,int z)
{
if(t[k].l1>x2||t[k].l2<x1||t[k].r1>y2||t[k].r2<y1) return;
if(t[k].l1>=x1&&t[k].l2<=x2&&t[k].r1>=y1&&t[k].r2<=y2)
{
t[k].sum+=z*((t[k].l2-t[k].l1+1)*(t[k].r2-t[k].r1+1));
t[k].lan+=z;
return;
}
down(k);
add((k<<2)-2+0,x1,y1,x2,y2,z);
add((k<<2)-2+1,x1,y1,x2,y2,z);
add((k<<2)-2+2,x1,y1,x2,y2,z);
add((k<<2)-2+3,x1,y1,x2,y2,z);
t[k].sum=t[(k<<2)-2+0].sum+
t[(k<<2)-2+1].sum+
t[(k<<2)-2+2].sum+
t[(k<<2)-2+3].sum;
}
int ask(int k,int x1,int y1,int x2,int y2)
{
if(t[k].l1>x2||t[k].l2<x1||t[k].r1>y2||t[k].r2<y1) return 0;
if(t[k].l1>=x1&&t[k].l2<=x2&&t[k].r1>=y1&&t[k].r2<=y2)
return t[k].sum;
down(k);
return ask((k<<2)-2+0,x1,y1,x2,y2)+
ask((k<<2)-2+1,x1,y1,x2,y2)+
ask((k<<2)-2+2,x1,y1,x2,y2)+
ask((k<<2)-2+3,x1,y1,x2,y2);
}
};
最大流
namespace ISAP{
int n,m,s,t;
int cur[100005];
namespace lsq {
typedef int lsqxx;
struct lq {
struct lqbz {
lsqxx v,w,nxt;
} e[1000005];
lsqxx h[100005],cnt=1;
inline void add(lsqxx u,lsqxx v,lsqxx w=1) {
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=h[u];
h[u]=cnt;
}
#define F(z,u) for(int j=cur[u],v=z.e[j].v,w=z.e[j].w;j;j=z.e[j].nxt,v=z.e[j].v,w=z.e[j].w,cur[u]=j)
}q;
};using namespace lsq;
int d[205],gap[205];
int dfs(int u=s,int in=INT_MAX)
{
if(u==t) return in;
int out=0;
F(q,u)
{
if(d[u]>d[v]&&w)
{
int nt=dfs(v,min(w,in));
in-=nt;out+=nt;
q.e[j].w-=nt;q.e[j^1].w+=nt;
if(!in) return out;
}
}
--gap[d[u]];
if(!gap[d[u]]) d[s]=n+1;
++d[u];
++gap[d[u]];
return out;
}
int ISAP()
{
int ans=0;
gap[0]=n;
while(d[s]<n)
memcpy(cur,q.h,sizeof(q.h)),ans+=dfs();
return ans;
}
}
using namespace ISAP;
带有当前弧优化和gas优化
Other
输出数组
#define cs(dt,n,m) \
for(int i=1;i<=n;i++)\
{\
for(int j=1;j<=n;j++)\
printf("%d ",dt[i][j]);\
cout<<endl;\
}
可以输出一个数组矩阵
矩阵
可以实现矩阵加法，矩阵乘法，矩阵快速幂
支持cin cout 读入输出
namespace matrixs{
#define X 100
#define Y 100
typedef long long ll;
ll matrix_mod=INT_MAX;
void change_mod(ll x){matrix_mod=x;return;}
inline ll reads()
{
char ch=getchar();int f=1,ans=0;
for(;!isdigit(ch);ch=getchar()) ch=='-'?f=-1:f=1;
for(;isdigit(ch);ch=getchar()) ans=(ans<<3)+(ans<<1)+(ch&15);
return f*ans;
}
template<size_t N=X,size_t M=Y>
struct matrix{
ll a[N+5][M+5];
int n=N,m=M;
matrix(){memset(a,0,sizeof(a));}
matrix(int x,int y,bool one=0)
{
n=x;m=y;memset(a,0,sizeof(a));
if(one) g(n) a[i][i]=1;
}
void read()
{
f(i,1,n)
f(j,1,m)
a[i][j]=reads();
}
void print()
{
ios::sync_with_stdio(false);
f(i,1,n)
{
f(j,1,m) cout<<a[i][j]<<" ";
cout<<'\n';
}
ios::sync_with_stdio(true);
}
friend matrix operator +(matrix x,matrix y)
{
matrix<> ans(x.n,x.m);
f(i,1,x.n) f(j,1,x.m)
ans.a[i][j]=(x.a[i][j]+y.a[i][j])%matrix_mod;
return ans;
}
friend matrix operator *(matrix x,matrix y)
{
matrix<> ans(x.n,y.m);
f(i,1,x.n) f(j,1,y.m) f(k,1,x.m)
ans.a[i][j]=(ans.a[i][j]+x.a[i][k]*y.a[k][j])%matrix_mod;
return ans;
}
friend matrix operator ^(matrix x,ll y)
{
matrix<> ans(x.n,x.m,true);
while(y>0)
{
if(y&1) ans=ans*x;
x=x*x;y>>=1;
}
return ans;
}
};
ostream &operator <<(ostream &out,matrix<> &x){x.print();return out;}
istream &operator >>(istream &in, matrix<> &x){x.read(); return in; }
}using namespace matrixs;
高精度 -by mori
# 商业转载请联系作者获得授权，非商业转载请注明出处。
# For commercial use, please contact the author for authorization. For non-commercial use, please indicate the source.
# 协议(License)：署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)
# 作者(Author)：Mori
# 链接(URL)：https://lsoi.top/356.html
# 来源(Source)：LSOI-BLOG
#define N 2048
typedef bitset<N> Bint;
bool operator <(const Bint &a,const Bint &b){
for (int i=a.size()-1;i>=0;--i)
if (a[i]!=b[i])return a[i]<b[i];
return 0;
}
bool operator >(const Bint &a,const Bint &b){return b<a;}
bool operator <=(const Bint &a,const Bint &b){return !(b<a);}
bool operator >=(const Bint &a,const Bint &b){return !(a<b);}
Bint operator +(const Bint &a,const Bint &b){return b.any()?(a^b)+((a&b)<<1):a;}
Bint& operator +=(Bint &a,const Bint &b){return a=a+b;}
Bint operator -(const Bint &a){return Bint(1)+~a;}
//Bint operator -(const Bint &a,const Bint &b){return a+(-b);}
Bint operator -(const Bint &a,const Bint &b){return b.any()?(a^b)-((~a&b)<<1):a;}
Bint& operator -=(Bint &a,const Bint &b){return a=a-b;}
Bint operator *(Bint a,Bint b){
Bint r(0);
for (;b.any();b>>=1,a<<=1)
if (b[0])r+=a;
return r;
}
Bint& operator *=(Bint &a,const Bint &b){return a=a*b;}
pair<Bint,Bint> divide(Bint a,const Bint &b){
Bint c=0; int i=0;
while (b<<(i+1)<=a)++i;
for (;i>=0;--i)
if (a>=(b<<i))a-=b<<i,c.set(i,1);
return make_pair(c,a);
}
Bint operator /(const Bint &a,const Bint &b){return divide(a,b).first;}
Bint& operator /=(Bint &a,const Bint &b){return a=a/b;}
Bint operator %(const Bint &a,const Bint &b){return divide(a,b).second;}
Bint& operator %=(Bint &a,const Bint &b){return a=a%b;}
inline void read(Bint &x){
char ch;int bo=0; x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar());
if (bo)x=-x;
}
inline void print(Bint x){
vector<Bint> v;
if (x==0)printf("0");
for (Bint y=1;y<=x;y*=10)v.push_back(y);
for (int i=v.size()-1;i>=0;--i){
int t=0;
while (x>=(v[i]<<2))x-=v[i]<<2,t+=4;
while (x>=(v[i]<<1))x-=v[i]<<1,t+=2;
while (x>=v[i])x-=v[i],++t;
printf("%d",t);
}
printf("\n");
}
01Trie
template<size_t siz=100005,size_t zw=30,size_t minads=0>
class O1tree{
private:
struct trees{
int to[2];
int cnt;
}t[siz];
int cnt=1;
//ads:如果带负数，权值 +ads
//w:log2(w) w is 值域
int ads=minads,w=zw;
public:
//插入一个数字
inline void add(int num)
{
num+=ads;
int u=1;
ff(i,w,0)
{
int v=(num>>i)&1;
if(!t[u].to[v]) t[u].to[v]=++cnt;
u=t[u].to[v];
t[u].cnt++;
}
}
//删除一个数字
inline void del(int num)
{
num+=ads;
int u=1;
ff(i,w,0)
{
int v=(num>>i)&1;
u=t[u].to[v];
t[u].cnt--;
}
}
//查询x这个数的排名
inline int kth(int num)
{
num+=ads;
int u=1,ans=1;
ff(i,w,0)
{
int v=(num>>i)&1;
if(v) ans+=t[t[u].to[0]].cnt;
u=t[u].to[v];
}
return ans;
}
//查询排名为x的数
inline int ask(int k)
{
int u=1,ans=0;
ff(i,w,0)
{
if(k<=t[t[u].to[0]].cnt)
u=t[u].to[0];
else
k-=t[t[u].to[0]].cnt,
ans|=(1<<i),
u=t[u].to[1];
}
return ans-ads;
}
};
笛卡尔树
template<size_t siz=10000005>
struct Dicar_tree{
struct dicar{
int l,r;
int w;
}t[siz];
stack<int>s;
//插入一个节点
void add(int k,int w)
{
t[k].w=w;
if(s.empty()) {s.push(k);return;}
while((!s.empty())&&(t[s.top()].w>w))
{
t[k].l=s.top();
s.pop();
}
if(!s.empty())
t[s.top()].r=k;
s.push(k);
}
};
蔡勒公式
int getweekday(int YYYY,int MM,int DD)
{
int a,b,c,d;
a=YYYY/100;b=YYYY%100;c=MM;d=DD;
return (a/4-a*2+b+b/4+(13*(c+1))/5+d-1)%7;
}