• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

「狐狸」的模板库

开发技术 开发技术 7个月前 (11-19) 66次浏览

「狐狸」的 模板库

@关于我,会宁狐狸,卑微蒟蒻想要留下些许痕迹

  该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("%lldn",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 }

「狐狸」的模板库


程序员灯塔
转载请注明原文链接:「狐狸」的模板库
喜欢 (0)