「狐狸」的模板库
「狐狸」的 模板库
@关于我，会宁狐狸，卑微蒟蒻想要留下些许痕迹
该blog最早写于2020年是11月18日，距离我退役仅剩16天，很快我将参加最后一场NOIP，然后AFO，被机房遗忘。
我将在此blog中整理一些基础模板，和基础技巧，希望能对未来的学弟学妹有所帮助，作为我曾在这个机房拼搏过的些许痕迹。（点击</>可复制代码）
@常见实用操作
1 #include<bits/stdc++.h>//常见实用技巧 2 #define l long//定义l为long ，使下方l t等价于long t 3 #define int long long//定义int 为 long long 使得下文一切int 等价于long long，但要注意long long main() 错误,所以，下方必须写为signed main() 4 using namespace std; 5 int n,m; 6 template<class T>//模板类型T，该代码仅修饰其下方的第一个函数或变量，作用为创建一个可适用任一类型的模板T 7 T sum(T a,T b){//当调用该函数时，T会自动适应为传入参数的类型，如该程序中，T被自动指定为long long 8 return a+b;//当a，b类型不同时该函数会出错，可以用sum<int>(n,m);强制指定T为long long 9 } 10 void Swap(int &a,int &b){//当写作int a,int b时执行该函数，不会使传入的m，n的值改变 11 l t=b;//但一旦使用了int &a(引用a，b修改a，b时就会修改传入的参数，n,m) 12 b=a,a=t;//例：若定义int &x=n;那么之后每一次对x修改，都会改变n的值 13 } 14 inline int read(){ //快读，读入速度显著快于cin,scanf，但只能读整数 15 int x=0,f=1;char ch=getchar();//x为读入整数的绝对值，f为读入数的符号 16 while(ch<'0'||ch>'9'){//读取符号 17 if(ch=='-') f=-1;ch=getchar();} 18 while(ch>='0'&&ch<='9'){//读取数 19 x=x*10+ch-'0';ch=getchar();} 20 return x*f;//返回数×符号 21 } 22 signed main()//signed本质上与int等价，但此刻int已被替换为long long ,所以需int处需全部写为signed 23 { 24 n=read(),m=read(); 25 cout<<sum(n,m)<<endl; 26 Swap(n,m); 27 cout<<n<<" "<<m<<endl; 28 return 0; 29 }
@线段树系列
壹–区间和查询，区间加减乘修改：
1 #include<bits/stdc++.h>//线段树，区间加减乘查询 2 using namespace std; 3 int n,m,mod; 4 5 inline long long read() { 6 long long x = 0, f = 1;char ch = getchar(); 7 while (ch < '0' || ch > '9') {if (ch == '-')f = -1;ch = getchar();} 8 while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();} 9 return f * x; 10 } 11 12 13 struct tree 14 { 15 #define maxn 100010 16 #define int long long//将int宏定义为了long long 17 #define lson rt*2//左，右儿子索引 18 #define rson rt*2+1 19 #define mid (s[rt].l+s[rt].r)/2 20 int p; 21 int arr[maxn]; 22 struct segment 23 { 24 segment() 25 {sum=0,add=0,mul=1;} 26 int sum,l,r,mul,add; 27 int size(){return r-l+1;} 28 }s[maxn<<2]; 29 void up(int rt) 30 {s[rt].sum=s[lson].sum+s[rson].sum;} 31 void down(int rt){//下传懒标记，先乘后加，先总和后标记 32 s[lson].sum=(s[lson].sum*s[rt].mul+s[rt].add*s[lson].size())%p;//处理总和 33 s[rson].sum=(s[rson].sum*s[rt].mul+s[rt].add*s[rson].size())%p; 34 s[lson].mul=s[lson].mul*s[rt].mul%p;//处理标记 35 s[rson].mul=s[rson].mul*s[rt].mul%p; 36 s[lson].add=(s[lson].add*s[rt].mul+s[rt].add)%p; 37 s[rson].add=(s[rson].add*s[rt].mul+s[rt].add)%p; 38 s[rt].mul=1; 39 s[rt].add=0; 40 } 41 void init(int rt,int ll,int rr)//建树，初始化 42 { 43 s[rt].l=ll,s[rt].r=rr; 44 if(ll==rr) 45 {s[rt].sum=arr[ll];return;} 46 init(lson,ll,mid); 47 init(rson,mid+1,rr); 48 up(rt); 49 } 50 void add(int rt,int ll,int rr,int k)//区间加，add为加法懒标记 51 { 52 if(s[rt].l>=ll&&s[rt].r<=rr) 53 { 54 s[rt].sum=(s[rt].sum+k*s[rt].size())%p; 55 s[rt].add=(s[rt].add+k)%p; 56 return ; 57 } 58 down(rt);//切记下传 59 if(ll<=mid) 60 add(lson,ll,rr,k); 61 if(rr>mid) 62 add(rson,ll,rr,k); 63 up(rt);//切记上传 64 } 65 void mul(int rt,int ll,int rr,int k)//区间乘，mul为乘法懒标记 66 { 67 if(s[rt].l>=ll&&s[rt].r<=rr) 68 { 69 s[rt].sum=(s[rt].sum*k)%p; 70 s[rt].add=s[rt].add*k%p; 71 s[rt].mul=s[rt].mul*k%p; 72 return ; 73 } 74 down(rt); 75 if(ll<=mid) 76 mul(lson,ll,rr,k); 77 if(rr>mid) 78 mul(rson,ll,rr,k); 79 up(rt); 80 } 81 int sum(int rt,int ll,int rr)//求区间和 82 { 83 int ans=0; 84 if(s[rt].l>=ll&&s[rt].r<=rr) 85 return s[rt].sum%p; 86 down(rt); 87 if(ll<=mid) 88 ans=(ans+sum(lson,ll,rr))%p; 89 if(rr>mid) 90 ans=(ans+sum(rson,ll,rr))%p; 91 return ans; 92 } 93 }tree; 94 signed main() 95 { 96 cin>>n>>m>>mod; 97 tree.p=mod; 98 for(int i=1;i<=n;i++) 99 cin>>tree.arr[i]; 100 tree.init(1,1,n);//记住建树，否则段错误 101 while(m--){int opt=read();//读取，调用 102 if(opt==1){int x=read(),y=read(),k=read();tree.mul(1,x,y,k);} 103 if(opt==2){int x=read(),y=read(),k=read();tree.add(1,x,y,k);} 104 if(opt==3){int x=read(),y=read();printf("%lld\n",tree.sum(1,x,y)%mod);}} 105 return 0; 106 }
线段树知识略解
贰–区间最大值查询，单点修改：
1 #include<bits/stdc++.h> 2 using namespace std; 3 long long arr[100010]; 4 struct Tree{ 5 #define mid (s[rt].l+s[rt].r)/2 6 #define lson rt*2 7 #define rson rt*2+1 8 #define maxn 100010 9 #define inf 99999999 10 struct segment{ 11 long long max,l,r; 12 long long size(){return r+l-1;} 13 }s[maxn<<2]; 14 void init(long long rt,long long ll,long long rr){ 15 s[rt].l=ll,s[rt].r=rr; 16 if(ll==rr){ 17 s[rt].max=-inf;return ;} 18 init(lson,ll,mid); 19 init(rson,mid+1,rr); 20 s[rt].max=max(s[lson].max,s[rson].max); 21 } 22 long long query(long long rt,long long ll,long long rr){ 23 if(s[rt].l>=ll&&s[rt].r<=rr) 24 return s[rt].max; 25 long long ans=-inf; 26 if(ll<=mid)ans=max(ans,query(lson,ll,rr)); 27 if(rr>mid)ans=max(ans,query(rson,ll,rr)); 28 return ans; 29 } 30 void change(long long rt,long long ll,long long rr,long long x){ 31 if(s[rt].l>=ll&&s[rt].r<=rr){ 32 s[rt].max=x;return ;} 33 if(ll<=mid) change(lson,ll,rr,x); 34 if(rr>mid) change(rson,ll,rr,x); 35 s[rt].max=max(s[lson].max,s[rson].max); 36 } 37 }tree; 38 int n,m; 39 int main() 40 { 41 cin>>n>>m; 42 tree.init(1,1,n); 43 for(int i=1;i<=n;i++){ 44 int x;cin>>x;tree.change(1,i,i,x); 45 } 46 for(int i=1;i<=m;i++){ 47 int l,r;cin>>l>>r;cout<<tree.query(1,l,r)<<endl; 48 } 49 return 0; 50 }
@ST表，稀疏表
1 #include<bits/stdc++.h>//St表，建表O（logN）查询O（1） 2 using namespace std; 3 int n,m; 4 const int K=30;//K看情况取值，要求K>log(n),空间允许时建议大于2log（n）,但不可过大 5 int st[200010][K]; 6 inline int read() 7 { 8 int x=0,f=1;char ch=getchar(); 9 while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} 10 while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} 11 return x*f; 12 } 13 void init() 14 { 15 for(int k=1;k<=25;k++){ 16 int d=pow(2,k-1); 17 for(int i=1;i<=n;i++){ 18 if(i+d<=n) st[i][k]=max(st[i][k-1],st[i+d][k-1]); 19 } 20 } 21 } 22 int query(int l,int r){ 23 int k=log2(r-l+1); 24 int x=r-pow(2,k)+1; 25 return max(st[l][k],st[x][k]); 26 } 27 int main() 28 { 29 cin>>n>>m; 30 for(int i=1;i<=n;i++) cin>>st[i][0]; 31 init(); 32 for(int i=1;i<=m;i++){ 33 int l,r;cin>>l>>r; 34 cout<<query(l,r)<<endl;} 35 return 0; 36 }
