NOIP模板总结

2022-12-17 07:38:49

NOIP模板总结

　　进考场先打一份缺省源：

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 int main()

 {

     return ;

 }

缺省源

 #include<bits/stdc++.h>

 using namespace std;

 int main()

 {

     int n=;

     while()

     {

         printf("Test %d:\n",++n);

         system("data.exe");

         system("my.exe");

         system("std.exe");

         if(system("fc std.out my.out"))

             puts("WA"),system("pause");

         else puts("AC");

     }

 }

对拍

 # define r(a,b) (rand()*rand()%((b)-(a)+)+(a))

生成随机数

 int read()

 {

     int x=,f=;

     char c=getchar();

     while(!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }

     while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

     return x*f;

 }

快读

　　重启一下电脑看看是哪些盘不清空。

调配置：

　　·工具->编译选项->代码警告->显示最多警告消息;

　　·工具->编译选项->连接器->产生调试信息;

　　·(如果$IDE$右边有奇怪的白色竖线):工具->编辑器属性->基本->右边缘->把勾去掉;

　　·工具->编辑器属性->高亮显示当前行->$Green$;

　　·工具->编辑器属性->显示->字体:$Andalus$->大小$10$;

　　·工具->编辑器属性->语法->预设$Obsidian$;

　　虽然比不上$Vscode$漂亮,但是至少挺清楚的.

　　本来想把数据结构都封装成结构体,后来发现没什么用处还容易错...等联赛完了再弄这些东西吧。

　　前几篇模板都是全套的，大多数还在$OJ$上交过,后面的一些来不及写了只写了主要的函数,但是思路肯定是对的.

图论:

　　关于最小生成树,实测还是$kruscal$比较快,而且内存小,而且代码短.

 for (R k=;k<=n;++k)

     for (R i=;i<=n;++i)

         for (R j=;j<=n;++j)

             g[i][j]=min(g[i][j],g[i][k]+g[k][j]);

floyd

 # include <cstdio>

 # include <iostream>

 # include <queue>

 # include <cstring>

 # define ll long long

 # define R register int

 # define pac(a,b) make_pair(a,b)

 using namespace std;

 const int maxn=;

 const int maxm=;

 int n,m,s,h,firs[maxn],vis[maxn],x,y,z;

 ll d[maxn];

 struct edge

 {

     int too,nex,co;

 }g[maxm<<];

 typedef pair <int,int> pii;

 priority_queue <pii,vector<pii>,greater<pii> >q;

 void add (int x,int y,int z)

 {

     g[++h].nex=firs[x];

     firs[x]=h;

     g[h].too=y;

     g[h].co=z;

 }

 int read()

 {

     int x=;

     char c=getchar();

     while(!isdigit(c)) c=getchar();

     while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

     return x;

 }

 void dij (int s)

 {

     int beg,j;

     memset(d,,sizeof(d));

     d[s]=;

     q.push(pac(,s));

     while(q.size())

     {

         beg=q.top().second;

         q.pop();

         if(vis[beg]) continue;

         vis[beg]=true;

         for (R i=firs[beg];i;i=g[i].nex)

         {

             j=g[i].too;

             if(d[beg]+g[i].co>=d[j]) continue;

             d[j]=d[beg]+g[i].co;

             q.push(pac(d[j],j));

         }

     }

 }

 int main()

 {

     n=read(),m=read(),s=read();

     for (R i=;i<=m;++i)

     {

         x=read(),y=read(),z=read();

         add(x,y,z);

     }

     dij(s);

     for (R i=;i<=n;++i)

         printf("%lld ",d[i]);

     return ;

 }

Heap+dijkstra

 # include <cstdio>

 # include <iostream>

 # include <queue>

 # include <cstring>

 # define ll long long

 # define R register int

 # define pac(a,b) make_pair(a,b)

 using namespace std;

 const int maxn=;

 const int maxm=;

 int n,m,s,h,firs[maxn],vis[maxn],x,y,z;

 ll d[maxn],f[maxn];

 struct edge

 {

     int too,nex,co;

 }g[maxm<<];

 typedef pair <int,int> pii;

 priority_queue <pii,vector<pii>,greater<pii> >q;

 void add (int x,int y,int z)

 {

     g[++h].nex=firs[x];

     firs[x]=h;

     g[h].too=y;

     g[h].co=z;

 }

 int read()

 {

     int x=;

     char c=getchar();

     while(!isdigit(c)) c=getchar();

     while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

     return x;

 }

 void dij (int s)

 {

     int beg,j;

     memset(d,,sizeof(d));

     d[s]=;

     f[s]=;

     q.push(pac(,s));

     while(q.size())

     {

         beg=q.top().second;

         q.pop();

         if(vis[beg]) continue;

         vis[beg]=true;

         for (R i=firs[beg];i;i=g[i].nex)

         {

             j=g[i].too;

             if(d[beg]+g[i].co>d[j]) continue;

             if(d[beg]+g[i].co==d[j]) f[j]+=f[beg];

             else

             {

                 f[j]=f[beg];

                 d[j]=d[beg]+g[i].co;

                 q.push(pac(d[j],j));

             }

         }

     }

 }

 int main()

 {

     n=read(),m=read(),s=read();

     for (R i=;i<=m;++i)

     {

         x=read(),y=read(),z=read();

         add(x,y,z);

     }

     dij(s);

     for (R i=;i<=n;++i)

         printf("%lld ",f[i]);

     return ;

 }

最短路计数

 # include <cstdio>

 # include <iostream>

 # include <queue>

 # include <cstring>

 # define ll long long

 # define R register int

 using namespace std;

 const int maxn=;

 const int maxm=;

 int n,m,s,h,firs[maxn],vis[maxn],x,y,z;

 ll d[maxn],f[maxn];

 struct edge

 {

     int too,nex,co;

 }g[maxm<<];

 queue <int> q;

 void add (int x,int y,int z)

 {

     g[++h].nex=firs[x];

     firs[x]=h;

     g[h].too=y;

     g[h].co=z;

 }

 int read()

 {

     int x=;

     char c=getchar();

     while(!isdigit(c)) c=getchar();

     while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

     return x;

 }

 void spfa (int s)

 {

     int beg,j;

     memset(d,,sizeof(d));

     d[s]=;

     q.push(s);

     while(q.size())

     {

         beg=q.front();

         q.pop();

         vis[beg]=false;

         for (R i=firs[beg];i;i=g[i].nex)

         {

             j=g[i].too;

             if(d[beg]+g[i].co>d[j]) continue;

         d[j]=d[beg]+g[i].co;

         if(!vis[j]) q.push(j),vis[j]=true;

         }

     }

 }

 int main()

 {

     n=read(),m=read(),s=read();

     for (R i=;i<=m;++i)

     {

         x=read(),y=read(),z=read();

         add(x,y,z);

     }

     spfa(s);

     for (R i=;i<=n;++i)

         printf("%lld ",d[i]);

     return ;

 }

spfa

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <queue>

 # define R register int

 # define ll long long

 # define pac(a,b) make_pair(a,b)

 using namespace std;

 const int maxn=;

 const int maxm=;

 int n,m,h,firs[maxn],d[maxn],vis[maxn],x,y,z,ed[maxn];

 struct edge

 {

     int too,nex,co;

 }g[maxm<<];

 typedef pair <int,int> pii;

 priority_queue <pii,vector<pii>,greater<pii> > q;

 void add (int x,int y,int z)

 {

     g[++h].nex=firs[x];

     firs[x]=h;

     g[h].too=y;

     g[h].co=z;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for (R i=;i<=m;++i)

     {

         scanf("%d%d%d",&x,&y,&z);

         add(x,y,z);

         add(y,x,z);

     }

     memset(d,,sizeof(d));

     vis[]=,d[]=;

     q.push(pac(,));

     int j,beg;

     while(q.size())

     {

         beg=q.top().second;

         q.pop();

         if(vis[beg]) continue;

         vis[beg]=true;

         for (R i=firs[beg];i;i=g[i].nex)

         {

             j=g[i].too;

             if(vis[j]) continue;

             d[j]=min(d[j],g[i].co);

             q.push(pac(d[j],j));

         }

     }

     for (R i=;i<=n;++i)

         if(!vis[j])

         {

             printf("orz");

             return ;

         }

     int ans=;

     for (R i=;i<=n;++i)

         ans+=d[i];

     printf("%d",ans);

     return ;

 }

Heap+Prim

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 const int maxm=;

 int n,m,h,f[maxn],z[maxn],S,fx,fy,ans;

 struct ed

 {

     int x,y,z;

 }g[maxm];

 bool cmp (ed a,ed b) { return a.z<b.z; }

 int father (int x) { if(x!=f[x]) return f[x]=father(f[x]); return x; }

 int main()

 {

     scanf("%d%d",&n,&m);

     for (R i=;i<=m;++i)

         scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].z);

     sort(g+,g++m,cmp);

     for (R i=;i<=n;++i)

         f[i]=i,z[i]=;

     S=n;

     for (R i=;i<=m;++i)

     {

         fx=father(g[i].x);

         fy=father(g[i].y);

         if(fx==fy) continue;

         ans+=g[i].z;

         if(z[fx]>z[fy]) z[fx]+=z[fy],f[fy]=fx;

         else z[fy]+=z[fx],f[fx]=fy;

         S--;

     }

     if(S!=) printf("orz");

     else printf("%d",ans);

     return ;

 }

Kruskal

     差分约束其实还是最短路，考的主要是一些建图：

         如果给出的式子有的是小于有的是大于，要先移项后再做；

     举个栗子：a[i]-a[j]<=c -> a[i]<=a[j]+c

     可以认为做一遍最短路后a[j]向a[i]连一条边权为c的边无法更新dis[i],所以连边后跑最短路;

     如果图不保证联通可以加一个虚点向其他所有点连边,边权视情况而定.

     一些基本的性质题目可能不说,但是自己要记得写:a[i]全为正时,s[i]>s[i-],etc...

     求最大值跑最短路,最小值跑最长路.

     如果有负权边就只能用spfa,无解一般表现为又负环或者正环,用spfa判断.

     虽然很假,但是考场上要是真的不会做了可以考虑"梦想spfa",即运行时间过长时直接认为是负环.

     板子就不写了,和最短路差不多的.

差分约束

 bool spfa()

 {

     memset(d,0x3f,sizeof(d));

     int j,beg;

     while (q.size()) q.pop();

     q.push();

     d[]=;

     while (q.size())

     {

         beg=q.front();

         q.pop();

         vis[beg]=;

         for (int i=firs[beg];i;i=g[i].nex)

         {

             j=g[i].too;

             if(d[j]>d[beg]+g[i].co)

             {

                 d[j]=d[beg]+g[i].co;

                 s[j]=s[beg]+;

                 if(s[j]>=n) return ;

                 if(!vis[j])

                 {

                     vis[j]=;

                     q.push(j);

                 }

             }

         }

     }

     return ;

 }

 判断负环的方法很多，有时dfs的确实快，但是那个的复杂度根本不对，所以建议还是写这个。普通的spfa也有两种写法，一种是记录到每个点的最短路经过了几个点，还有一种是记录每个点入队几次，也许两者一起用是最好的吧，这里给出第一种做法。

spfa判负环

 void init()

 {

     for (R i=;i<=n;++i) lg[i]=lg[i>>]+;

 }

 void dfs (int x)

 {

     int j;

     for (R i=firs[x];i;i=g[i].nex)

     {

         j=g[i].too;

         if(dep[j]) continue;

         dep[j]=dep[x];

         f[j][]=x;

         for (R k=;k<=lg[ dep[j] ];++k)

             f[j][k]=f[ f[j][k-] ][k-];

         dfs(j);

     }

 }

 int lca (int x,int y)

 {

     if(dep[x]>dep[y]) swap(x,y);

     for (R i=lg[ dep[y] ];i>=;--i)

         if(dep[y]-(<<i)>=dep[x]) y=f[y][i];

     if(x==y) return x;

     for (R i=lg[ dep[x] ];i>=;--i)

     {

         if(f[x][i]=f[y][i]) continue;

         x=f[x][i];

         y=f[y][i];

     }

     return f[x][];

 }

倍增求LCA

 # include <cstdio>

 # include <iostream>

 # define R register int

 using namespace std;

 int n,m,h,firs[maxn],r[maxn],c[maxn],x,y;

 struct edge

 {

     略去.

 };

 void dfs (int x)

 {

     int j,t;

     for (R &i=firs[x];i;i=g[i].nex) //这个&是优化时间复杂度的精髓所在啊！

     {

         if(vis[i]) continue;

         j=g[i].too;

         vis[i]=true;

         t=i;

         dfs(j);

         sta[++top]=t; //因为之前加过取地址符，所以i可能变了 ：（

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for (R i=;i<=m;++i)

     {

         scanf("%d%d",&x,&y);

         r[x]++,c[y]++;

         add(x,y);

     }

     for (R i=;i<=n;++i)

         if(r[i]!=c[i])

         {

             printf("NO");

             return ;

         }

     for (R i=;i<=n;++i) //图中可能有一些孤立点，但是因为欧拉回路的关键是边所以没有关系

         if(firs[i])

         {

             dfs(i);

             break;

         }

     for (R i=Top;i>=;--i) printf("%d ",sta[i]);

     return ;

 }

欧拉回路-有向图

 # include <cstdio>

 # include <iostream>

 # define R register int

 using namespace std;

 int n,m,h,firs[maxn],r[maxn],c[maxn],x,y;

 struct edge

 {

     略去.

 };

 void dfs (int x)

 {

     int j,ID;

     for (R &i=firs[x];i;i=g[i].nex) //这个&是优化时间复杂度的精髓所在啊！

     {

         ID=g[i].id;

         if(ID<) ID=-ID;

         if(vis[ ID ]) continue;

         j=g[i].too;

         vis[ ID ]=true;

         dfs(j);

         sta[++top]=ID; //因为之前加过取地址符，所以i可能变了 ：（

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for (R i=;i<=m;++i)

     {

         scanf("%d%d",&x,&y);

         d[x]++,d[y]++;

         add(x,y,i);

         add(y,x,-i);

     }

     for (R i=;i<=n;++i)

         if(d[i]%)

         {

             printf("NO");

             return ;

         }

     for (R i=;i<=n;++i) //图中可能有一些孤立点，但是因为欧拉回路的关键是边所以没有关系

         if(firs[i])

         {

             dfs(i);

             break;

         }

     for (R i=Top;i>=;--i) printf("%d ",sta[i]);

     return ;

 }

欧拉回路-无向图

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <cmath>

 # include <algorithm>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 const int maxm=;

 int n,m,x,y,h,firs[maxn],d[maxn],f[maxn],z[maxn],od[maxn];

 struct edge

 {

     int too,nex;

 }g[maxm<<];

 int father (int x) { if(x!=f[x]) return f[x]=father(f[x]); return x; }

 inline void uni (int x,int y)

 {

     int fx=father(x);

     int fy=father(y);

     if(fx==fy) return ;

     if(z[fx]>z[fy]) f[fy]=fx,z[fx]+=z[fy];

     else f[fx]=fy,z[fy]+=z[fx];

 }

 int main()

 {

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         h=;

         memset(d,,sizeof(d));

         memset(firs,,sizeof(firs));

         memset(od,,sizeof(od));

         for (R i=;i<=n;++i) f[i]=i,z[i]=;

         for (R i=;i<=m;++i)

         {

             scanf("%d%d",&x,&y);

             d[x]++,d[y]++;

             uni(x,y);

         }

         for (R i=;i<=n;++i) f[i]=father(i);

         for (R i=;i<=n;++i) if(d[i]&) od[ f[i] ]++;

         int ans=;

         for (R i=;i<=n;++i)

             if(f[i]==i&&z[i]!=) ans+=max(,od[i]/);

         printf("%d\n",ans);

     }

     return ;

 }

有向图最少笔画数

 欧拉道路就是把每条边不重不漏的经过一次的道路啦。

 无向图：.图连通；

        .有0/2个奇点；

 有向图：：图连通；

        ：所有点的入度出度均相等或一点的入度比出度大一，一点入度比出度小一。

欧拉道路相关

 void dfs (int x,int f)

 {

     id[x]=low[x]=++cnt;

     int j,son_cnt=;

     for (R i=firs[x];i;i=g[i].nex)

     {

         j=g[i].too;

         if(!id[j])

         {

             dfs(j,x);

             son_cnt++;

             low[x]=min(low[x],low[j]);

             if(low[j]>=id[x]) cutt[x]=true;

         }

         else low[x]=min(low[x],id[j]);

     }

     if(f==&&son_cnt>=) cutt[x]=true;

 }

Tarjan-割点

 void dfs (int x,int las)

 {

     id[x]=low[x]=++cnt;

     int j,son_cnt=;

     for (R i=firs[x];i;i=g[i].nex)

     {

         if(i==(las^)) continue;

         j=g[i].too;

         if(!id[j])

         {

             dfs(j,i);

             low[x]=min(low[x],low[j]);

             if(low[j]>id[x]) g[i].t=t[i^].t=;

         }

         else

             low[x]=min(low[x],id[j]);

     }

 }

Tarjan-桥

 void dfs (int x)

 {

     id[x]=low[x]=++cnt;

     vis[x]=true;

     sta[++Top]=x;

     int j;

     for (R i=firs[x];i;i=g[i].nex)

     {

         j=g[i].too;

         if(!id[j])

         {

             dfs(j);

             low[x]=min(low[x],low[j]);

         }

         else if(vis[j]) low[x]=min(low[x],id[j]);

     }

     if(low[x]==id[x])

     {

         col[x]=++bp;

         vis[x]=;

         while(sta[Top]!=x)

         {

             col[ sta[Top] ]=bp;

             vis[ sta[Top] ]=;

             Top--;

         }

         Top--;

     }

 }

Tarjan-强连通

 找出桥后删掉所有的桥，每个联通块就是一个边双。

Tarjan-边双

 void dfs(int x,int f)

 {

     id[x]=low[x]=++cnt;

     int j,sz=,k;

     for (R i=firs[x];i;i=g[i].nex)

     {

         j=g[i].too;

         if(!id[j])

         {

             sz++,sta[++Top]=i;

             dfs(j,x);

             low[x]=min(low[j],low[x]);

             if(low[j]>=id[x])

             {

                 v[x]=true;

                 bp++;

                 do

                 {

                     k=sta[Top];

                     if(col[ g[k].fro ]!=bp)

                     {

                         col[ g[k].fro ]=bp;

                         v_dcc[bp].push_back(g[k].fro);

                         siz[bp]++;

                     }

                     if(col[ g[k].too ]!=bp)

                     {

                         col[ g[k].too ]=bp;

                         v_dcc[bp].push_back(g[k].too);

                         siz[bp]++;

                     }

                     Top--;

                 }while(k!=i);

             }

         }else low[x]=min(low[x],id[j]);

     }

     if(f==&&sz<=) v[x]=false;

 }

Tarjan-点双

dp优化:

　　注意矩阵乘法时一定要把$k$写在最外层循环，因为每次访问的内存连续所以可以快很多,真的快很多！

 struct mat

 {

     int n,m;

     ll a[maxn][maxn];

     void init()

     {

         memset(a,,sizeof(a));

         for (R i=;i<;++i)

             a[i][i]=;

     }

     void cler() { memset(a,,sizeof(a)); }

     mat operator *  (const mat &a) const

     {

         mat c;

         c.cler();

         for (R k=;k<a.m;++k)

             for (R i=;i<this->n;++i)

                 for (R j=;j<this->m;++j)

                     c.a[i][j]=(c.a[i][j]+this->a[i][k]*a.a[k][j]%m)%m;

         c.n=n;

         c.m=a.m;

         return c;

     }

 };

 mat qui (mat a,int p)

 {

     mat ans;

     ans.init();

     ans.n=ans.m=;

     while(p)

     {

         if(p&) ans=ans*a;

         a=a*a;

         p>>=;

     }

     return ans;

 }

矩阵快速幂

 ll X (int i) { return ; }

 ll Y (int i) { return ; }

 ll K (int i) { return ; }

 ll B (int i) { return ; }

 double KK (int a,int b) {    if(X(b)==X(a)) return ; return (double)(Y(b,j)-Y(a,j))/(X(b)-X(a));    }

 struct xq

 {

     int q[maxn];

     int h,t;

     void ins (int i)

     {

         int a,b,c;

         if(h<t) a=q[t-],b=q[t],c=i;

         while(h<t&&KK(a,b)>KK(a,c))

         {

             t--;

             if(h<t) a=q[t-],b=q[t],c=i;

         }

         q[++t]=i;

     }

     void del (int i)

     {

         int a,b;

         if(h<t) a=q[h],b=q[h+];

         while(h<t&&KK(a,b)<K(i))

         {

             h++;

             if(h<t) a=q[h],b=q[h+];

         }

     }

     void init() { h=,t=; }

     int firs () { return q[h]; }

 }q;

基于单调队列的斜率优化

数论算法:

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 ll a,b,p;

 int main()

 {

     scanf("%lld%lld%lld",&a,&b,&p);

     ll s=;

     while(b)

     {

         if(b&1LL) s=s*a%p;

         a=a*a%p;

         b=b>>;

     }

     printf("%lld\n",s%p);

     return ;

 }

快速幂

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 ll a,b,p;

 int main()

 {

     scanf("%lld%lld%lld",&a,&b,&p);

     ll s=;

     while(b)

     {

         if(b&1LL) s=s+a%p;

         a=a+a%p;

         b=b>>;

     }

     printf("%lld\n",s%p);

     return ;

 }

快速加

 int ad (int a,int b)

 {

     a+=b;

     if(a>=p) a-=p;

     return a;

 }

加法取模优化

 inv[]=;

 for (R i=;i<=n;++i)

     inv[i]=(mod-mod/i)*inv[mod%i]%mod;

线性求逆元

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 int f[maxn],pri[maxn],h;

 void sieve()

 {

     f[]=;

     for (R i=;i<=n;++i)

     {

         if(!f[i]) pri[++h]=i;

         for (R j=;j<=h&&i*pri[j]<=n;++j)

         {

             f[ i*pri[j] ]=;

             if(i%pri[j]==) break;

         }

     }

 }

 int main()

 {

     return ;

 }

线性筛素数

 void sdiv (int x)

 {

     for (R i=;i*i<=n;++i)

     {

         if(x%i==) p[++h]=i;

         while(x%i==) c[h]++,x/=i;

     }

     if(x!=) p[h]=x,c[h]=;

 }

根号时间分解质因数

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 int f[maxn],pri[maxn],h,m[maxn],a[maxn];

 void ldiv (int x)

 {

     int cnt=;

     while(x!=)

     {

         a[++cnt]=m[x];

         x/=m[x];

     }

 }

 void sieve()

 {

     f[]=;

     for (R i=;i<=n;++i)

     {

         if(!f[i]) pri[++h]=i,m[i]=i;

         for (R j=;j<=h&&i*pri[j]<=n;++j)

         {

             f[ i*pri[j] ]=;

             m[ i*pri[j] ]=pri[j];

             if(i%pri[j]==) break;

         }

     }

 }

 int main()

 {

     sieve();

     return ;

 }

log时间分解质因数

 f[]=,phi[]=;

 for(re int i=;i<=n;i++)

 {

     if(!f[i]) p[++p[]]=i,phi[i]=i-;

     for(re int j=;j<=p[]&&p[j]*i<=n;j++)

     {

         f[p[j]*i]=;

         if(i%p[j]==)

         {

             phi[p[j]*i]=phi[i]*p[j];

             break;

         }

         phi[p[j]*i]=phi[i]*(p[j]-);

     }

 }

 这个是抄的asuldb的.

欧拉筛

 int gcd (int a,int b) { return b?gcd(b,a%b):a; }

gcd

 int gcd (int a,int b)

 {

     int p=;

     if(a<b) swap(a,b);

     while(a&&b)

     {

         if(a%==&&b%==) p*=,a/=,b/=;

         else if(a%&&b%==) b/=;

         else if(a%==&&b%) a/=;

         else a-=b;

         if(a<b) swap(a,b);

     }

     return p*a;

 }

Stein算法求gcd

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # define R register int

 using namespace std;

 const int maxn=;

 const int base=1e8;

 char c[maxn];

 struct big

 {

     int a[maxn];

     int len;

     void write()

     {

         printf("%d",a[len]);

         for (R i=len-;i>=;--i)

             printf("%08d",a[i]);

         if(len==) printf("");

     }

     void div()

     {

         int mod=;

         for (R i=len;i>=;--i)

         {

             a[i]+=mod*base;

             mod=a[i]%;

             a[i]/=;

         }

         while (a[ len ]==&&len) len--;

     }

     void clear()

     {

         memset(a,,sizeof(a));

         len=;

     }

     void mul()

     {

         for (R i=;i<=len;++i)

             a[i]*=;

         for (R i=;i<=len+;++i)

             a[i+]+=a[i]/base,a[i]%=base;

         len++;

         while (a[ len ]==&&len) len--;

     }

     bool operator < (const big &b) const

     {

         if(b.len!=len) return len<b.len;

         for (R i=len;i>=;--i)

             if(b.a[i]==a[i]) continue;

             else return a[i]<b.a[i];

         return false;

     }

     void read()

     {

         scanf("%s",c+);

         int l=strlen(c+);

         len=l/+((l%)?:);

         int x=,pos=;

         for (R i=;i<=l;++i)

         {

             x=x*+c[i]-'';

             if(i%==l%)

             {

                 a[ len-pos ]=x;

                 pos++;

                 x=;

             }

         }

         if(x) a[len-pos]=x;

     }

 }A,B;

 void sub()

 {

     for (R i=;i<=B.len;++i)

     {

         A.a[i]-=B.a[i];

         if(A.a[i]<) A.a[i]+=base,A.a[i+]--;

     }

     while (A.a[ A.len ]==&&A.len) A.len--;

 }

 void gcd ()

 {

     int cnt=;

     if(A<B) swap(A,B);

     while (A.len&&B.len)

     {

         if(A.a[]%==&&B.a[]%==) cnt++,A.div(),B.div();

         else if (A.a[]%&&B.a[]%==) B.div();

         else if (A.a[]%==&&B.a[]%) A.div();

         else sub();

         if(A<B) swap(A,B);

     }

     for (R i=;i<=cnt;++i)

         A.mul();

     A.write();

 }

 int main()

 {

     A.read();

     B.read();

        gcd();

     return ;

 }

压位高精实现Stein算法

 void exgcd (int a,int b,int &x,int &y)

 {

     if(b==)

     {

         x=,y=;

         return;

     }

     exgcd(b,a%b,y,x);

     y-=a/b*x;

 }

exgcd

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 int a[maxn],b[maxn];

 char c[maxn];

 int main()

 {

     scanf("%s",c+);

     a[]=strlen(c+);

     for (R i=;i<=a[];++i)

         a[i]=c[ a[]-i+ ]-'';

     scanf("%s",c+);

     b[]=strlen(c+);

     for (R i=;i<=b[];++i)

         b[i]=c[ b[]-i+ ]-'';

     a[]=max(a[],b[])+;

     for (R i=;i<=a[];++i)

     {

         a[i]+=b[i];

         a[i+]+=a[i]/;

         a[i]%=;

     }

     while(a[ a[] ]==&&a[]) a[]--;

     for (R i=a[];i>=;--i)

         printf("%d",a[i]);

     if(a[]==) printf("");

     return ;

 }

高精度加法

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 int a[maxn],b[maxn];

 char c[maxn];

 bool smaller ()

 {

     if(a[]!=b[]) return a[]<b[];

     for (R i=a[];i>=;--i)

         if(a[i]!=b[i]) return a[i]<b[i];

     return false;

 }

 void chan()

 {

     int n=max(a[],b[]);

     for (R i=;i<=n;++i)

         swap(a[i],b[i]);

 }

 int main()

 {

     scanf("%s",c+);

     a[]=strlen(c+);

     for (R i=;i<=a[];++i)

         a[i]=c[ a[]-i+ ]-'';

     scanf("%s",c+);

     b[]=strlen(c+);

     for (R i=;i<=b[];++i)

         b[i]=c[ b[]-i+ ]-'';

     if(smaller())

     {

         printf("-");

         chan();

     }

     for (R i=;i<=a[];++i)

     {

         a[i]-=b[i];

         if(a[i]<) a[i]+=,a[i+]--;

     }

     while(a[ a[] ]==&&a[]) a[]--;

     for (R i=a[];i>=;--i)

         printf("%d",a[i]);

     if(a[]==) printf("");

     return ;

 }

高精度减法

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 int a[maxn],b[maxn],d[maxn];

 char c[maxn];

 int main()

 {

     scanf("%s",c+);

     a[]=strlen(c+);

     for (R i=;i<=a[];++i)

         a[i]=c[ a[]-i+ ]-'';

     scanf("%s",c+);

     b[]=strlen(c+);

     for (R i=;i<=b[];++i)

         b[i]=c[ b[]-i+ ]-'';

     d[]=a[]+b[]+;

     for (R i=;i<=a[];++i)

         for (R j=;j<=b[];++j)

             d[i+j-]+=a[i]*b[j];

     for (R i=;i<=d[];++i)

     {

         d[i+]+=d[i]/;

         d[i]%=;

     }

     while(d[ d[] ]==&&d[]) d[]--;

     for (R i=d[];i>=;--i)

         printf("%d",d[i]);

     if(d[]==) printf("");

     return ;

 }

高精度乘法

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # include <map>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 int T,n,m,a[maxn],sta[maxn],Top;

 char c[maxn];

 map <char,int> m1;

 map <int,char> m2;

 int main() //模m取余，逆序输出，除法退位位时注意上一位的余数乘n即可

 {

     scanf("%d",&T);

     for (R i=;i<=;++i)

         m1[ i+'' ]=i,m2[i]=i+'';

     for (R i=;i<=;++i)

         m1[i-+'A']=i,m2[i]=i-+'A';

     for (R i=;i<=;++i)

         m1[i-+'a']=i,m2[i]=i-+'a';

     while (T--)

     {

         scanf("%d%d",&n,&m);

         scanf("%s",c+);

         a[]=strlen(c+);

         Top=;

         for (R i=;i<=a[];++i)

             a[a[]-i+]=m1[ c[i] ];

         printf("%d ",n);

         for (R i=a[];i>=;--i)

             printf("%c",m2[ a[i] ]);

         printf("\n");

         while(a[])

         {

             int r=;

             for (R i=a[];i>=;--i)

             {

                 a[i]=r*n+a[i];

                 r=a[i]%m;

                 a[i]/=m;

             }

             sta[++Top]=r;

             while(a[ a[] ]==&&a[]) a[]--;

         }

         printf("%d ",m);

         for (R i=Top;i>=;--i)

             printf("%c",m2[ sta[i] ]);

         printf("\n\n");

     }

 }

高精度n进制转m进制

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 int a[maxn],b;

 char c[maxn];

 int main()

 {

     scanf("%s",c+);

     a[]=strlen(c+);

     for (R i=;i<=a[];++i)

         a[i]=c[ a[]-i+ ]-'';

     scanf("%d",&b);

     ll r=;

     for (R i=a[];i>=;--i)

     {

         a[i]+=r*;

         r=a[i]%b;

         a[i]/=b;

     }

     while(a[ a[] ]==&&a[]) a[]--;

     for (R i=a[];i>=;--i)

         printf("%d",a[i]);

     if(a[]==) printf("");

     printf("\n%lld",r);

     return ;

 }

高精度除法+取模

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 int T;

 ll f[],inv[];

 ll n,m,p;

 ll c(ll n,ll m)

 {

     if(n<m) return ;

     return (f[n]*inv[m]%p)*inv[n-m]%p;

 }

 ll lucas(ll n,ll m)

 {

     if(m==)

         return ;

     else

         return (ll)lucas(n/p,m/p)*c(n%p,m%p)%p;

 }

 ll quick_pow(ll x,ll c)

 {

     ll s=;

     while (c)

     {

         if(c&) s=s*x%p;

         x=x*x%p;

         c=c>>;

     }

     return s%p;

 }

 void init()

 {

     f[]=inv[]=;

     for (int i=;i<p;++i)

     {

         f[i]=f[i-]*i%p;

         inv[i]=quick_pow(f[i],p-);

     }

 }

 int main()

 {

     scanf("%d",&T);

     while (T--)

     {

         scanf("%lld%lld%lld",&n,&m,&p);

         init();

         printf("%lld\n",lucas(n+m,m));

     }

     return ;

 }

Lucas

 # include <cstdio>

 # include <iostream>

 # define R register int

 # define ll long long

 using namespace std;

 ll n,m,p;

 int h;

 ll a[];

 ll pr[],po[];

 ll ans=;

 ll qui (ll a,ll b,ll p)

 {

     ll s=;

     while (b)

     {

         if(b&1LL) s=s*a%p;

         a=a*a%p;

         b=b>>1LL;

     }

     return s;

 }

 void ex_gcd (ll a,ll b,ll &x,ll &y)

 {

     if(!b) { x=1LL,y=0LL; return ; }

     ex_gcd(b,a%b,y,x);

     y-=a/b*x;

 }

 ll inv (ll a,ll p)

 {

     ll x,y;

     ex_gcd(a,p,x,y);

     return (x%p+p)%p;

 }

 ll crt ()

 {

     ll ans=;

     ll x,y,m,pri;

     for (R i=;i<=h;++i)

     {

         pri=po[i];

         m=p/pri;

         m%=pri;

         ex_gcd(m,pri,x,y);

         x=(x%pri+pri)%pri;

         m=p/pri;

         x=x*m%p;

         ans=(ans+x*a[i])%p;

     }

     return ans;

 }

 ll fac (ll n,ll Pr,ll Po)

 {

     if(n==) return ;

     ll ans=;

     for (R i=;i<=Po;++i)

         if(i%Pr) ans=ans*i%Po;

     ans=qui(ans,n/Po,Po);

     for (R i=;i<=n%Po;++i)

         if(i%Pr) ans=ans*i%Po;

     return ans*fac(n/Pr,Pr,Po)%Po;

 }

 ll C (ll n,ll m,ll Pr,ll Po)

 {

     if(m>n) return ;

     ll t=;

     ll a=fac(n,Pr,Po),b=fac(m,Pr,Po),c=fac(n-m,Pr,Po);

     for (ll i=n;i;i/=Pr) t+=i/Pr;

     for (ll i=m;i;i/=Pr) t-=i/Pr;

     for (ll i=n-m;i;i/=Pr) t-=i/Pr;

     return qui(Pr,t,Po)*a*inv(b,Po)%Po*inv(c,Po)%Po;

 }

 ll Lucas (ll n,ll m)

 {

     for (R i=;i<=h;++i)

         a[i]=C(n,m,pr[i],po[i])%p;

     return crt();

 }

 void div (ll p)

 {

     for (R i=;i*i<=p;++i)

     {

         if(p%i==)

         {

             ++h;

             pr[h]=i;

             po[h]=;

             while (p%i==) po[h]*=i,p/=i;

         }

     }

     if(p>) pr[++h]=p,po[h]=p;

 }

 int main()

 {

     scanf("%lld%lld",&n,&m);

     scanf("%lld",&p),div(p);

     printf("%lld",Lucas(n,m));

     return ;

 }

Exlucas

 # include <cstdio>

 # include <iostream>

 # define ll long long

 # define R register int

 using namespace std;

 const int maxn=;

 int n,f;

 ll m[maxn],c[maxn],m1,m2,c1,c2,I,g,x,y;

 inline char gc() {

     static char buf[],*p1,*p2;

     return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;

 }

 ll read() {

     ll x=;

     char c=gc();

     while(!isdigit(c)) c=gc();

     while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=gc();

     return x;

 }

 ll gcd (ll a,ll b) { return b?gcd(b,a%b):a; }

 void exgcd (ll a,ll b,ll &x,ll &y)

 {

     if(b==)

     {

         x=,y=;

         return ;

     }

     exgcd(b,a%b,y,x);

     y-=a/b*x;

 }

 ll inv (ll a,ll b)

 {

     ll x,y;

     exgcd(a,b,x,y);

     x=(x%b+b)%b;

     if(!x) x+=b;

     return x;

 }

 ll mul (ll a,ll b,ll p)

 {

     ll s=;

     a=(a%p+p)%p;

     b=(b%p+p)%p;

     while (b)

     {

         if(b&1LL) s=(s+a)%p;

         a=(a+a)%p;

         b=b>>1LL;

     }

     return s%p;

 }

 int main()

 {

     scanf("%d",&n);

     f=;

     for (R i=;i<=n;++i)

         m[i]=read(),c[i]=read();

     for (R i=;i<=n;++i)

     {

         m1=m[],m2=m[i],c1=c[],c2=c[i];

         exgcd(m1,m2,x,y);

         g=gcd(m1,m2);

         ll t=m[i]/g;

         x=mul(x,(c2-c1)/g,t);

         x=(x%t+t)%t;

         c[]=(c[]+mul(m[],x,m[]*t))%(m[]*t);

         m[]*=t;

     }

     printf("%lld",(c[]%m[]+m[])%m[]);

     return ;

 }

Excrt

数据结构

 # include <cstdio>

 # include <iostream>

 # define R register int

 using namespace std;

 int c[]={},n;

 void add (int x,int v)

 {

     for (R i=x;i<=n;i+=(i&(-i))) c[i]+=v;

 }

 int ask (int x)

 {

     int S=;

     for (R i=x;i;i-=(i&(-i))) S+=c[i];

     return S;

 }

 int main()

 {

     int m,x,a,b,v;

     scanf("%d%d",&n,&m);

     for (R i=;i<=n;i++)

     {

         scanf("%d",&v);

         add(i,v);

     }

     for (R i=;i<=m;i++)

     {

         scanf("%d%d%d",&x,&a,&b);

         if(x==)

             add(a,b);

         if(x==)

             printf("%d\n",ask(b)-ask(a-));

     }

     return ;

 }

树状数组单点加区间求和

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 int n,m,x,y;

 ll k,now,last=;

 ll t[]={};

 ll S=;

 int xx;

 void add (int x,ll y)

 {

     for (R i=x;i<=n;i+=(i&(-i))) t[i]+=y;

 }

 ll ask (int x)

 {

     ll S=;

     for (R i=x;i;i-=(i&(-i))) S+=t[i];

     return S;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for (int i=;i<=n;i++)

     {

         scanf("%lld",&now);

         add(i,now-last);

         last=now;

     }

     for (int i=;i<=m;i++)

     {

         scanf("%d",&xx);

         if(xx==)

         {

             scanf("%d%d",&x,&y);

             scanf("%lld",&k);

             add(x,k);

             add(y+,-k);

         }

         if (xx==)

         {

             scanf("%d",&x);

             printf("%lld\n",ask(x));

         }

     }

     return ;

 }

树状数组区间加单点查询

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 int m,n,op,x,y,opt;

 ll a[]={},k,s1,s2;

 ll c[]={},c1[]={};

 void add (ll *t,int pos,ll v)

 {

     for (R i=pos;i<=n;i+=(i&(-i)))

         t[i]+=v;

 }

 ll ask (ll *t,int pos)

 {

     ll ans=;

     for (R i=pos;i;i-=(i&(-i)))

         ans+=t[i];

     return ans;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for (R i=;i<=n;++i)

     {

         scanf("%lld",&a[i]);

         add(c,i,a[i]-a[i-]);

         add(c1,i,(i-)*(a[i]-a[i-]));

     }

     for (R i=;i<=m;++i)

     {

         scanf("%d",&opt);

         if (op==)

         {

             scanf("%d%d%lld",&x,&y,&k);

             add(c,x,k);

             add(c,y+,-k);

             add(c1,x,k*(x-));

             add(c1,y+,-k*y);

         }

         if (op==)

         {

             scanf("%d%d",&x,&y);

             s1=(x-)*ask(c,x-)-ask(c1,x-);

             s2=y*ask(c,y)-ask(c1,y);

             printf("%lld\n",s2-s1);

         }

     }

     return ;

 }

树状数组区间加区间查询

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # define R register int

 # define lowbit(x) (x&(-x))

 using namespace std;

 const int maxn=;

 int a,b,c,d,n,m,s1,s2,s3,s4,v;

 string st;

 int c1[maxn][maxn],c2[maxn][maxn],c3[maxn][maxn],c4[maxn][maxn];

 inline void add(int x,int y,int v)

 {

     for (R i=x;i<=n;i+=lowbit(i))

         for (R j=y;j<=m;j+=lowbit(j))

         {

             c1[i][j]+=v;

             c2[i][j]+=v*x;

             c3[i][j]+=v*y;

             c4[i][j]+=v*x*y;

         }

 }

 inline int ask(int x,int y)

 {

     int ans=;

     for (R i=x;i;i-=lowbit(i))

         for (R j=y;j;j-=lowbit(j))

         {

             ans+=(x+)*(y+)*c1[i][j];

             ans-=(y+)*c2[i][j];

             ans-=(x+)*c3[i][j];

             ans+=c4[i][j];

         }

     return ans;

 }

 int main()

 {

     scanf("X %d %d",&n,&m);

     while (cin>>st)

     {

         if(st[]=='L') scanf("%d%d%d%d%d",&a,&b,&c,&d,&v);

         else    scanf("%d%d%d%d",&a,&b,&c,&d);

         if(st[]=='L')

         {

             add(a,b,v);

             add(a,d+,-v);

             add(c+,b,-v);

             add(c+,d+,v);

         }

         else

             printf("%d\n",ask(c,d)-ask(c,b-)-ask(a-,d)+ask(a-,b-));

     }

     return ;

 }

二维树状数组区间加区间查询

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define LL long long

 # define nl (n<<)

 # define nr (n<<|)

 using namespace std;

 const int maxn=;

 int n,m,opt,x,y;

 LL k,t[maxn<<],delta[maxn<<];

 void pushdown (int n,int l,int r)

 {

     int mid=(l+r)>>;

     LL x=delta[n];

     delta[nl]+=x;

     delta[nr]+=x;

     delta[n]=;

     t[nl]+=(mid-l+)*x;

     t[nr]+=(r-mid)*x;

 }

 void build (int n,int l,int r)

 {

     if(l==r)

     {

         scanf("%lld",&t[n]);

         return;

     }

     int mid=(l+r)>>;

     build(nl,l,mid);

     build(nr,mid+,r);

     t[n]=t[nl]+t[nr];

 }

 void add (int n,int l,int r,int ll,int rr,LL v)

 {

     if(ll<=l&&r<=rr)

     {

         delta[n]+=v;

         t[n]+=(r-l+)*v;

         return;

     }

     int mid=(l+r)>>;

     if(delta[n]) pushdown(n,l,r);

     if(ll<=mid) add(nl,l,mid,ll,rr,v);

     if(rr>mid)  add(nr,mid+,r,ll,rr,v);

     t[n]=t[nl]+t[nr];

 }

 LL ask (int n,int l,int r,int ll,int rr)

 {

     if(ll<=l&&r<=rr)

         return t[n];

     if(delta[n]) pushdown(n,l,r);

     int mid=(l+r)>>;

     LL ans=;

     if(ll<=mid) ans=ans+ask(nl,l,mid,ll,rr);

     if(rr>mid)  ans=ans+ask(nr,mid+,r,ll,rr);

     return ans;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     build(,,n);

     for (R i=;i<=m;++i)

     {

         scanf("%d",&opt);

         if(opt==)

         {

             scanf("%d%d%lld",&x,&y,&k);

             add(,,n,x,y,k);

         }

         else

         {

             scanf("%d%d",&x,&y);

             printf("%lld\n",ask(,,n,x,y));

         }

     }

     return ;

 }

线段树区间加区间求和

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define nl (n<<)

 # define nr (n<<|)

 using namespace std;

 const int maxn=;

 int z,x,y,n,m,r,p,a[maxn],h,firs[maxn],dep[maxn],f[maxn],siz[maxn],son[maxn],id[maxn];

 int cnt,top[maxn],c[maxn],t[maxn<<],delta[maxn<<];

 struct edge

 {

     int too,nex;

 }g[maxn<<];

 int read ()

 {

     int x=,f=;

     char c=getchar();

     while (!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }

     while (isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

     return x*f;

 }

 void add_ed (int x,int y)

 {

     g[++h].nex=firs[x];

     g[h].too=y;

     firs[x]=h;

 }

 void dfs1 (int x)

 {

     siz[x]=;

     int j,maxx=;

     for (R i=firs[x];i;i=g[i].nex)

     {

         j=g[i].too;

         if(dep[j]) continue;

         dep[j]=dep[x]+;

         dfs1(j);

         f[j]=x;

         siz[x]+=siz[j];

         if(siz[j]>maxx) maxx=siz[j],son[x]=j;

     }

 }

 void dfs2 (int x,int Tp)

 {

     int j;

     id[x]=++cnt;

     c[cnt]=a[x];

     top[x]=Tp;

     if(!son[x]) return;

     dfs2(son[x],Tp);

     for (R i=firs[x];i;i=g[i].nex)

     {

         j=g[i].too;

         if(j==f[x]||j==son[x]) continue;

         dfs2(j,j);

     }

 }

 void build (int n,int l,int r)

 {

     if(l==r)

         t[n]=c[l]%p;

     else

     {

         int mid=(l+r)>>;

         build(nl,l,mid);

         build(nr,mid+,r);

         t[n]=(t[nl]+t[nr])%p;

     }

 }

 void pushdown (int n,int l,int r)

 {

     int mid=(l+r)>>,x=delta[n];

     delta[n]=;

     delta[nl]+=x;

     delta[nr]+=x;

     t[nl]=(t[nl]+1LL*x*(mid-l+)%p)%p;

     t[nr]=(t[nr]+1LL*x*(r-mid)%p)%p;

 }

 void add (int n,int l,int r,int ll,int rr,int z)

 {

     if(ll<=l&&r<=rr)

     {

         delta[n]+=z;

         t[n]=(t[n]+1LL*z*(r-l+)%p)%p;

         return;

     }

     int mid=(l+r)>>;

     if(delta[n]) pushdown(n,l,r);

     if(ll<=mid) add(nl,l,mid,ll,rr,z);

     if(rr>mid) add(nr,mid+,r,ll,rr,z);

     t[n]=(t[nl]+t[nr])%p;

 }

 int ask (int n,int l,int r,int ll,int rr)

 {

     if(ll<=l&&r<=rr) return t[n];

     int mid=(l+r)>>,ans=;

     if(delta[n]) pushdown(n,l,r);

     if(ll<=mid) ans=(ans+ask(nl,l,mid,ll,rr))%p;

     if(rr>mid) ans=(ans+ask(nr,mid+,r,ll,rr))%p;

     return ans;

 }

 void add_link (int x,int y,int z)

 {

     z%=p;

     while(top[x]!=top[y])

     {

         if(dep[ top[x] ]>dep[ top[y] ]) swap(x,y);

         add(,,n,id[ top[y] ],id[y],z);

         y=f[ top[y] ];

     }

     if(dep[x]>dep[y]) swap(x,y);

     add(,,n,id[x],id[y],z);

 }

 int ask_link (int x,int y)

 {

     int ans=;

     while(top[x]!=top[y])

     {

         if(dep[ top[x] ]>dep[ top[y] ]) swap(x,y);

         ans=(ans+ask(,,n,id[ top[y] ],id[y]))%p;

         y=f[ top[y] ];

     }

     if(dep[x]>dep[y]) swap(x,y);

     ans=(ans+ask(,,n,id[x],id[y]))%p;

     return ans;

 }

 void add_st (int x,int z)

 {

     z%=p;

     add(,,n,id[x],id[x]+siz[x]-,z);

 }

 int ask_st (int x)

 {

     return ask(,,n,id[x],id[x]+siz[x]-);

 }

 int main()

 {

     n=read(),m=read(),r=read(),p=read();

     for (R i=;i<=n;++i) a[i]=read();

     for (R i=;i<n;++i)

     {

         scanf("%d%d",&x,&y);

         add_ed(x,y);

         add_ed(y,x);

     }

     dep[r]=;

     dfs1(r);

     dfs2(r,r);

     build(,,n);

     for (R i=;i<=m;++i)

     {

         int opt=read();

         if(opt==)

         {

             x=read(),y=read(),z=read();

             add_link(x,y,z);

         }

         else if(opt==)

         {

             x=read(),y=read();

             printf("%d\n",ask_link(x,y));

         }

         else if(opt==)

         {

             x=read(),y=read();

             add_st(x,y);

         }

         else

     {

         x=read();

         printf("%d\n",ask_st(x));

         }

     }

     return ;

 }

树链剖分

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <cmath>

 #define R register int

 #define ll long long

 using namespace std;

 const int maxn=;

 int f[maxn]={},z[maxn],n;

 int father(int x)

 {

     if (f[x]!=x) return f[x]=father(f[x]);

     return x;

 }

 void Union(int x, int y)

 {

     x=f(x);

     y=ff(y);

     if (x==y) return;

     if(z[x]>z[y]) z[x]+=z[y],f[y]=x;

     else z[y]+=z[x],f[x]=y;

 }

 void init()

 {

     for (int i = ; i <= n; i++)

         f[i]=i,z[i]=;

 }

 int main()

 {

     scanf("%d", &n);

     init();

     return ;

 }

并查集

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # include <cstdlib>

 # define R register int

 # define ll long long

 # define inf 

 using namespace std;

 const int maxn=;

 int n,opt,x;

 struct node

 {

     int n,r,s,v;

     node *ch[];

     void in (int x)

     {

         n=s=;

         v=x;

         r=rand();

         ch[]=ch[]=NULL;

     }

     void update ()

     {

         s=n;

         if(ch[]) s+=ch[]->s;

         if(ch[]) s+=ch[]->s;

     }

     int cmp (int x)

     {

         if(x==v) return -;

         return x>v;

     }

 }*roo,pool[maxn];

 node *newnode ()

 {

     static int cnt=;

     return &pool[++cnt];

 }

 void rotate (node *&n,int d)

 {

     node *k=n->ch[d];

     n->ch[d]=k->ch[d^];

     k->ch[d^]=n;

     n->update();

     k->update();

     n=k;

 }

 void ins (node *&n,int x)

 {

     if(!n) n=newnode(),n->in(x);

     else

     {

         int d=n->cmp(x);

         if(d==-) n->n++;

         else

         {

             ins(n->ch[d],x);

             if(n->ch[d]->r > n->r) rotate(n,d);

         }

         n->update();

     }

 }

 void del (node *&n,int x)

 {

     if(!n) return;

     int d=n->cmp(x);

     if(d==-)

     {

         if(n->n > ) --n->n;

         else if(!n->ch[]) n=n->ch[];

         else if(!n->ch[]) n=n->ch[];

         else

         {

             int f=(n->ch[]->r > n->ch[]->r)?:;

             rotate(n,f);

             del(n->ch[f^],x);

         }

     }else del(n->ch[d],x);

     if(n) n->update();

 }

 int ask_key (node *&n,int x)

 {

     if(!n) return ;

     if(n->v==x) return (n->ch[]?n->ch[]->s:)+;

     if(n->v<x) return (n->ch[]?n->ch[]->s:)+n->n+ask_key(n->ch[],x);

     return ask_key(n->ch[],x);

 }

 int ask_value (node *&n,int x)

 {

     if(!n||n->s<x||x<=) return ;

     int s=n->ch[]?n->ch[]->s:;

     if(s<x&&x<=s+n->n) return n->v;

     if(s>=x) return ask_value(n->ch[],x);

     return ask_value(n->ch[],x-s-n->n);

 }

 int lef (node *&n,int x)

 {

     if(!n) return -inf;

     if(n->v >= x) return lef(n->ch[],x);

     return max(n->v,lef(n->ch[],x));

 }

 int rig (node *&n,int x)

 {

     if(!n) return inf;

     if (n->v <= x) return rig(n->ch[], x);

     return min(n->v,rig(n->ch[], x));

 }

 int main()

 {

     scanf("%d",&n);

     for (R i=;i<=n;++i)

     {

         scanf("%d%d",&opt,&x);

         if(opt==) ins(roo,x);

         else if(opt==) del(roo,x);

         else if(opt==) printf("%d\n",ask_key(roo,x));

         else if(opt==) printf("%d\n",ask_value(roo,x));

         else if(opt==) printf("%d\n",lef(roo,x));

         else printf("%d\n",rig(roo,x));

     }

     return ;

 }

Treap

 # include <cstdio>

 # include <iostream>

 # include <queue>

 # include <cstring>

 # include <string>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 int n,m,x,y,roo;

 struct node

 {

     int delta,ch[],f,siz;

 }t[maxn];

 int read();

 inline void update (int id)

 {

     t[id].siz=t[ t[id].ch[] ].siz+t[ t[id].ch[] ].siz+;

 }

 inline void lin (int x,int f,int d)

 {

     t[x].f=f;

     t[f].ch[d]=x;

 }

 int build (int l,int r)

 {

     if(l>r) return ;

     int mid=(l+r)>>;

     lin(build(l,mid-),mid,);

     lin(build(mid+,r),mid,);

     t[mid].delta=;

     update(mid);

     return mid;

 }

 inline void pushdown (int n)

 {

     t[n].delta=;

     t[ t[n].ch[] ].delta^=;

     t[ t[n].ch[] ].delta^=;

     swap(t[n].ch[],t[n].ch[]);

 }

 void write (int x)

 {

     if(!x) return;

     if(t[x].delta) pushdown(x);

     write(t[x].ch[]);

     if(x!=&&x!=n+) printf("%d ",x-);

     write(t[x].ch[]);

 }

 inline int D (int x)

 {

     return x==t[ t[x].f ].ch[];

 }

 void rotate (int x)

 {

     int f=t[x].f;

     if(f==roo) roo=x;

     int g=t[f].f;

     int mf=D(x),gf=D(f);

     int k=t[x].ch[mf^];

     lin(k,f,mf),lin(f,x,mf^),lin(x,g,gf);

     update(f),update(x);

 }

 void splay (int x,int g)

 {

     while(t[x].f!=g)

     {

         if(t[ t[x].f ].f==g) rotate(x);

         else if(D(x)==D(t[x].f)) rotate(t[x].f),rotate(x);

         else rotate(x),rotate(x);

     }

     update(x);

 }

 inline int find (int x)

 {

     int no=roo;

     x--;

     if(t[no].delta) pushdown(no);

     while (t[ t[no].ch[] ].siz!=x)

     {

         if(t[ t[no].ch[] ].siz<x)

             x-=t[ t[no].ch[] ].siz+,no=t[no].ch[];

         else no=t[no].ch[];

         if(t[no].delta) pushdown(no);

     }

     return no;

 }

 int main()

 {

     n=read(),m=read();

     roo=build(,n+);

     while(m--)

     {

         x=read(),y=read();

         x=find(x);

         splay(x,);

         y=find(y+);

         splay(y,roo);

         t[ t[y].ch[] ].delta^=;

     }

     write(roo);

     return ;

 }

 inline int read()

 {

     int x=;

     char c=getchar();

     while (!isdigit(c)) c=getchar();

     while (isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

     return x;

 }

Splay

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # include <cstdlib>

 # include <queue>

 # include <ctime>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 int n,m,v[maxn],h,f[maxn],x,y,k,Q,pos[maxn];

 char s[];

 struct node

 {

     int n,v,s,r;

     node *ch[];

     void in (int x)

     {

         n=s=;

         v=x;

         r=rand();

         ch[]=ch[]=NULL;

     }

     int cmp (int x)

     {

         if(x==v) return -;

         return x>v;

     }

     void update()

     {

         s=n;

         if(ch[]) s+=ch[]->s;

         if(ch[]) s+=ch[]->s;

     }

 }*roo[maxn],pool[maxn*];

 node *q[maxn];

 inline int read();

 node *newnode();

 void ins (node *&node,int x);

 inline void mer (int x,int y);

 void rotate (node *&n,int d);

 int father (int x);

 int ask (node *&n,int k);

 void write (int x)

 {

     if(x<) putchar('-'),write(-x);

     else

     {

         if(x>=) write(x/);

         putchar(x%+'');

     }

 }

 int main()

 {

     srand(time());

     n=read(),m=read();

     for (R i=;i<=n;++i)

         x=read(),f[i]=i,ins(roo[i],x),pos[x]=i;

     for (R i=;i<=m;++i)

     {

         x=read(),y=read();

         if(x==||y==) continue;

         mer(x,y);

     }

     Q=read();

     int ans=;

     while (Q--)

     {

         scanf("%s",s);

         x=read(),y=read();

         if(s[]=='Q')

         {

             x=father(x);

             if(roo[x]->s<y) ans=-;

             else ans=pos[ ask(roo[x],y) ];

             write(ans);

             putchar('\n');

         }

         else

         {

             mer(x,y);

             if(x==||y==) continue;

         }

     }

     return ;

 }

 inline int read()

 {

     int x=;

     char c=getchar();

     while(!isdigit(c)) c=getchar();

     while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

     return x;

 }

 int father (int x) { if(x!=f[x]) return f[x]=father(f[x]); return x; }

 node *newnode()

 {

     static int cnt=;

     return &pool[++cnt];

 }

 void ins (node *&n,int x)

 {

     if(!n) n=newnode(),n->in(x);

     else

     {

         int d=n->cmp(x);

         if(d==-) ++n->n;

         else

         {

             ins(n->ch[d],x);

             if(n->ch[d]->r > n->r) rotate(n,d);

         }

         n->update();

     }

 }

 void rotate (node *&n,int d) // rotate n->ch[d] to n

 {

     node *k=n->ch[d];

     n->ch[d]=k->ch[d^];

     k->ch[d^]=n;

     n->update();

     k->update();

     n=k;

 }

 inline void mer (int x,int y)

 {

     if(roo[x]->s<roo[y]->s) swap(x,y);

     x=father(x);

     y=father(y);

     if(x==y) return;

     f[y]=x;

     int h=,t=;

     q[++t]=roo[y];

     node *k;

     while(h<=t)

     {

         k=q[h];

         ins(roo[x],k->v);

         if(k->ch[]) q[++t]=k->ch[];

         if(k->ch[]) q[++t]=k->ch[];

         h++;

     }

     roo[y]=roo[x];

 }

 int ask (node *&n,int k)

 {

     if(!n||k<||n->s<k) return ;

     int s=n->ch[]?n->ch[]->s:;

     if(s<k&&k<=n->n+s) return n->v;

     if(s<k) return ask(n->ch[],k-n->n-s);

     return ask(n->ch[],k);

 }

启发式合并-Treap

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 int n,m,t[maxn<<],ch[maxn<<][],v[maxn],roo[maxn],nod_cnt,l,r,k,true_value[maxn];

 struct node { int p,v; } a[maxn];

 bool cmp (node a,node b)

 {

     return a.v<b.v;

 }

 int build (int l,int r)

 {

     int id=++nod_cnt;

     if(l==r)

         return id;

     int mid=(l+r)>>;

     ch[id][]=build(l,mid);

     ch[id][]=build(mid+,r);

     return id;

 }

 int ins (int las,int l,int r,int pos,int v)

 {

     int id=++nod_cnt;

     if(l==r)

     {

         t[id]=t[las]+v;

         return id;

     }

     int mid=(l+r)>>;

     ch[id][]=ch[las][];

     ch[id][]=ch[las][];

     if(pos<=mid) ch[id][]=ins(ch[las][],l,mid,pos,v);

     else ch[id][]=ins(ch[las][],mid+,r,pos,v);

     t[id]=t[ ch[id][] ]+t[ ch[id][] ];

     return id;

 }

 int ask (int a,int b,int l,int r,int k)

 {

     if(l==r) return l;

     int mid=(l+r)>>,x;

     x=t[ ch[b][] ]-t[ ch[a][] ];

     if(x>=k) return ask(ch[a][],ch[b][],l,mid,k);

     return ask(ch[a][],ch[b][],mid+,r,k-x);

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for (R i=;i<=n;++i)

         scanf("%d",&a[i].v),a[i].p=i;

     sort(a+,a++n,cmp);

     int cnt=;

     a[].v=a[].v+;

     for (R i=;i<=n;++i)

     {

         if(a[i].v!=a[i-].v) cnt++;

         v[ a[i].p ]=cnt;

         true_value[cnt]=a[i].v;

     }

     roo[]=build(,n);

     for (R i=;i<=n;++i)

         roo[i]=ins(roo[i-],,n,v[i],);

     for (R i=;i<=m;++i)

     {

         scanf("%d%d%d",&l,&r,&k);

         if(l>r) swap(l,r);

         int x=ask(roo[l-],roo[r],,n,k);

         printf("%d\n",true_value[x]);

     }

     return ;

 }

 //又名根路径可持久化函数式权值线段树

主席树

 # include <cstdio>

 # include <iostream>

 # include <cmath>

 # define R register int

 using namespace std;

 const int maxn=;

 int l,r,c,opt,n,siz;

 int a[maxn],b[maxn],delta[maxn];

 void add (int l,int r,int v)

 {

     if(b[l]==b[r])

     {

         for (R i=l;i<=r;++i)

             a[i]+=v;

     }

     else

     {

         if(b[l]*siz-l>l-(+b[l]*siz-siz))

         {

             for (R i=+b[l]*siz-siz;i<l;++i) a[i]-=v;

             delta[ b[l] ]+=v;

         }

         else

             for (R i=l;i<=b[l]*siz;++i) a[i]+=v;

         for (R i=b[l]+;i<=b[r]-;++i) delta[i]+=v;

         if(b[r]*siz-r>r-(+b[r]*siz-siz))

             for (R i=+b[r]*siz-siz;i<=r;++i) a[i]+=v;

         else

         {

             for (R i=r+;i<=b[r]*siz;++i) a[i]-=v;

             delta[ b[r] ]+=v;

         }

     }

 }

 int main()

 {

     scanf("%d",&n);

     for (R i=;i<=n;++i) scanf("%d",&a[i]);

     siz=sqrt(n);

     for (R i=;i<=n;++i) b[i]=(i-)/siz+;

     for (R i=;i<=n;++i)

     {

         scanf("%d%d%d%d",&opt,&l,&r,&c);

         if(opt==)

             add(l,r,c);

         else

             printf("%d\n",a[r]+delta[ b[r] ]);

     }

     return ;

 }

分块-区间加单点查询

 # include <cstdio>

 # include <iostream>

 # include <cmath>

 # include <algorithm>

 # define R register int

 # define ll long long

 # define P(i) sort(a++siz*(i-),a++min(siz*i,n),cmp)

 using namespace std;

 const int maxn=;

 int id,n,siz,opt,l,r,c,ans;

 ll delta[maxn];

 struct dig

 {

     int b,k;

     ll v;

 }a[maxn];

 bool cmp (dig a,dig b) { return a.v<b.v; }

 void add (int l,int r,ll c)

 {

     if(a[l].b==a[r].b)

     {

         id=a[l].b;

         for (R i=+siz*(id-);i<=min(id*siz,n);++i)

             if(a[i].k>=l&&a[i].k<=r) a[i].v+=c;

         P(a[l].b);

     }

     else

     {

         id=a[l].b;

         for (R i=+siz*(id-);i<=min(siz*id,n);++i)

             if(a[i].k>=l&&a[i].k<=r)

                 a[i].v+=c;

         P(id);

         for (R i=a[l].b+;i<=a[r].b-;++i) delta[i]+=c;

         id=a[r].b;

         for (R i=+siz*(id-);i<=min(siz*id,n);++i)

             if(a[i].k>=l&&a[i].k<=r)

                 a[i].v+=c;

         P(id);

     }

 }

 int check (int x,ll c)

 {

     int l=+siz*(x-),r=min(n,siz*x),mid,ans=siz*(x-);

     while (l<=r)

     {

         mid=r+((l-r)>>);

         if(a[mid].v+delta[ a[mid].b ]<c)

             l=mid+,ans=max(ans,mid);

         else

             r=mid-;

     }

     return ans-siz*(x-);

 }

 int ask (int l,int r,ll c)

 {

     int ans=,id;

     if(a[l].b==a[r].b)

     {

         id=a[l].b;

         for (R i=+siz*(id-);i<=min(siz*id,n);++i)

             if(a[i].k>=l&&a[i].k<=r&&a[i].v+delta[ a[i].b ]<c)

                 ans++;

     }

     else

     {

         id=a[l].b;

         for (R i=+siz*(id-);i<=min(siz*id,n);++i)

             if(a[i].k>=l&&a[i].k<=r&&a[i].v+delta[ a[i].b ]<c)

                 ans++;

         for (R i=a[l].b+;i<=a[r].b-;++i)

             ans+=check(i,c);

         id=a[r].b;

         for (R i=+siz*(id-);i<=min(siz*id,n);++i)

             if(a[i].k>=l&&a[i].k<=r&&a[i].v+delta[ a[i].b ]<c)

                 ans++;

     }

     return ans;

 }

 int main()

 {

     scanf("%d",&n);

     siz=sqrt(n);

     for (R i=;i<=n;++i)

     {

         scanf("%lld",&a[i].v);

         a[i].k=i;

         a[i].b=(i-)/siz+;

     }

     for (R i=;i<=a[n].b;++i) P(i);

     for (R i=;i<=n;++i)

     {

         scanf("%d%d%d%d",&opt,&l,&r,&c);

         if(opt)

         {

             ans=ask(l,r,1LL*c*c);

             printf("%d\n",ans);

         }

         else

             add(l,r,c);

     }

     return ;

 }

分块-区间加区间排名

 # include <cstdio>

 # include <iostream>

 # include <cmath>

 # include <algorithm>

 # define R register int

 using namespace std;

 const int maxn=;

 int n,b[maxn],opt,l,r,c,siz;

 long long a[maxn],delta[maxn],s[maxn];

 void add (int l,int r,int c)

 {

     if(b[l]==b[r]) for (R i=l;i<=r;++i) a[i]+=c,s[ b[i] ]+=c;

     else

     {

         for (R i=l;i<=siz*b[l];++i) a[i]+=c,s[ b[i] ]+=c;

         for (R i=b[l]+;i<=b[r]-;++i) delta[i]+=c,s[i]+=siz*c;

         for (R i=+siz*(b[r]-);i<=r;++i) a[i]+=c,s[ b[i] ]+=c;

     }

 }

 int ask (int l,int r,int mod)

 {

     long long ans=;

     if(b[l]==b[r]) for (R i=l;i<=r;++i) ans=(ans+a[i]+delta[ b[i] ])%mod;

     else

     {

         for (R i=l;i<=siz*b[l];++i) ans=(ans+a[i]+delta[ b[i] ])%mod;

         for (R i=b[l]+;i<=b[r]-;++i) ans=(ans+s[i])%mod;

         for (R i=+siz*(b[r]-);i<=r;++i) ans=(ans+a[i]+delta[ b[i] ])%mod;

     }

     return ans%mod;

 }

 int main()

 {

     scanf("%d",&n);

     siz=sqrt(n);

     for (R i=;i<=n;++i) scanf("%lld",&a[i]);

     for (R i=;i<=n;++i) b[i]=(i-)/siz+,s[ b[i] ]+=a[i];

     for (R i=;i<=n;++i)

     {

         scanf("%d%d%d%d",&opt,&l,&r,&c);

         if(opt) printf("%d\n",ask(l,r,c+));

         else add(l,r,c);

     }

     return ;

 }

分块-区间加区间查询

 void init()

 {

     for (R i=;i<=n;++i)

         st[i][]=read();

     for (R k=;k<=lg[n];++k)

         for (R i=;i+(<<k)-<=n;++i)

             st[i][k]=max(st[i][k-],st[i+(<<(k-))][k-]);

 }

 int ask (int a,int b)

 {

     int k=lg[b-a+];

     return max(st[a][k],st[b-(<<k)+][k]);

 }

st表

制胡窜

　　好像$NOIP$从来没有考过真正的字符串算法啊，最多也就是读入输出，不过还是总结一下，反正会的也不多。那么就按照一本通的顺序好了。

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 # define ULL unsigned long long

 using namespace std;

 const int maxn=;

 const int base=;

 ULL po[maxn],Hash[maxn];

 char c[maxn];

 int n;

 ULL div_Hash (int l,int r) //获取子串的Hashֵ值

 {

     return Hash[r]-Hash[l]*po[r-l+];

 }

 int main()

 {

     scanf("%s",c+);

     n=strlen(c+);

     po[]=;

     for (R i=;i<=n;++i) po[i]=po[i-]*base;

     for (R i=;i<=n;++i) Hash[i]=Hash[i-]*base+c[i];

     return ;

 }

Hash-自然溢出

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 # define ULL unsigned long long

 # define mod 

 using namespace std;

 const int maxn=;

 const int base=;

 ll po[maxn],Hash[maxn];

 char c[maxn];

 int n;

 ll div_Hash (int l,int r) //获取子串的Hashֵ值

 {

     return ((Hash[r]-Hash[l]*po[r-l+])%mod+mod)%mod;

 }

 int main()

 {

     scanf("%s",c+);

     n=strlen(c+);

     po[]=;

     for (R i=;i<=n;++i) po[i]=(po[i-]*base)%mod;

     for (R i=;i<=n;++i) Hash[i]=(Hash[i-]*base+c[i])%mod;

     return ;

 }

Hash-模大质数

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 const int mod=;

 const int maxn=;

 int h,n,p1=,ans,p2=,a[maxn],v[maxn],firs[mod+],nex[mod+];

 bool que (int x)

 {

     int hash=x;

     while (hash>mod) hash-=mod;

     for (R i=firs[hash];i;i=nex[i])

         if(v[i]==x) return true;

     return false;

 }

 void add (int x)

 {

     int hash=x;

     while (hash>mod) hash-=mod;

     v[++h]=x;

     nex[h]=firs[hash];

     firs[hash]=h;

 }

 void del (int x)

 {

     int hash=x;

     while (hash>mod) hash-=mod;

     for (R i=firs[hash];i;i=nex[i])

         if(v[i]==x)

         {

             v[i]=-;

             return ;

         }

 }

 int main()

 {

     return ;

 }

哈希表

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 char s[maxn],t[maxn];

 int p[maxn],ls,lt,j;

 int main()

 {

     scanf("%s",s+);

     scanf("%s",t+);

     ls=strlen(s+);

     lt=strlen(t+);

     p[]=;

     for (R i=;i<=lt;++i)

     {

         j=p[i-];

         while(j&&t[i]!=t[j+]) j=p[j];

         if(t[i]==t[j+]) p[i]=j+;

         else p[i]=;

     }

     j=;

     for (R i=;i<ls;++i)

     {

         while(j&&a[i+]!=b[j+]) j=p[j];

         if(a[i+]==b[i+]) j++;

         if(j==lt) ans++;

     }

     return ;

 }

kmp

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=*;

 int n,cnt,h,a[];

 struct Trie_01

 {

     int ch[maxn][];

     int vis[maxn];

     void clear()

     {

         memset(ch,,sizeof(ch));

         memset(vis,,sizeof(vis));

     }

     void insert()

     {

         int x=;

         for (R i=;i<=;++i)

         {

             if(!ch[x][ a[i] ])

                 ch[ x ][ a[i] ]=++cnt;

             x=ch[x][ a[i] ];

         }

         vis[x]++;

     }

     int find()

     {

         int ans=,x=;

         for (R i=;i<=;++i)

         {

             if(ch[x][ a[i]^ ])

             {

                 ans=ans<<|;

                 x=ch[x][ a[i]^ ];

             }

             else x=ch[x][ a[i] ];

         }

         return ans;

     }

 }t;

 void spilt (int x)

 {

     h=;

     while(x) a[++h]=x,x/=;

     for (R i=;i<=h/;++i) swap(a[i],a[h-i+]);

 }

 int main()

 {

     return ;

 }

0-1Trie

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 int n,cnt,len;

 char c[maxn];

 struct Trie_char

 {

     int ch[maxn][];

     int vis[maxn];

     void clear()

     {

         memset(ch,,sizeof(ch));

         memset(vis,,sizeof(vis));

     }

     void insert()

     {

         int x=,n;

         for (R i=;i<=len;++i)

         {

             n=c[i]-'a';

             if(!ch[x][ no ])

                 ch[ x ][ no ]=++cnt;

             x=ch[x][ no ];

         }

         vis[x]++;

     }

     bool find()

     {

         int no,x=;

         for (R i=;i<=len;++i)

         {

             no=a[i]-'a';

             if(!ch[x][no]) return false;

             x=ch[x][no];

         }

         return vis[x];

     }

 }t;

 int main()

 {

     scanf("%s",c+);

     len=strlen(c+);

     return ;

 }

char-Trie

其它：

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 int n,l,r;

 ll m,a[maxn],ans,x;

 ll lef[<<],rig[<<];

 void dfs (int x,int l,int r,int col,ll S)

 {

     if(x==r+)

     {

         if(col==) lef[ ++lef[] ]=S;

         else rig[ ++rig[] ]=S;

         return ;

     }

     dfs(x+,l,r,col,S+a[x]);

     dfs(x+,l,r,col,S);

 }

 int main()

 {

     scanf("%d%lld",&n,&m);

     for (R i=;i<=n;++i)

         scanf("%lld",&a[i]);

     int mid=n/;

     dfs(,,mid,,);

     dfs(mid+,mid+,n,,);

     sort(lef+,lef+lef[]+);

     sort(rig+,rig+rig[]+);

     l=-;

     r=rig[];

     for (R i=;i<=lef[];++i)

     {

         x=lef[i];

         while(r&&x+rig[r]>m) r--;

         if(l==-) l=r;

         while(l&&x+rig[l]<=m) l--;

         ans+=(r-l);

     }

     printf("%lld",ans);

     return ;

 }

meet in the middle

 int find_lef (int x) //x的前驱

 {

     int l=,r=n,mid,ans=;

     while(l<=r)

     {

         mid=(l+r)>>;

         if(a[mid]<x)

             ans=max(ans,mid),l=mid+;

         else

             r=mid-;

     }

     return ans;

 }

 int find_rig (int x) //x的后继

 {

     int l=,r=n,mid,ans=n;

     while(l<=r)

     {

         mid=(l+r)>>;

         if(a[mid]>x)

             ans=min(ans,mid),r=mid-;

         else

             l=mid+;

     }

     return ans;

 }

二分法

 double open_up () //开口朝上的函数

 {

     double l=-inf,r=inf,lmid,rmid;

     while(r-l>=eps)

     {

         lmid=l+(l+r)/3.0;

         rmid=r-(l+r)/3.0;

         if(f(lmid)>f(rmid))

             l=lmid;

         else

             r=rmid;

     }

     return f(l);

 }

 double open_down()//开口朝下的函数

 {

     double l=-inf,r=inf,lmid,rmid;

     while(r-l>=eps)

     {

         lmid=l+(l+r)/3.0;

         rmid=r-(l+r)/3.0;

         if(f(lmid)<f(rmid))

             l=lmid;

         else

             r=rmid;

     }

     return f(l);

 }

三分

建议:

　　1.每道题做完后可以开着$O_2$测一下,可能能查出来一些内存方面或者是局部变量忘记清零这样的错误.

　　2.多组数据的题一定要记得清空数组,可以把所有定义的数组都先清空再看哪些是不必要的,定义了$STL$的队列一定要用$q.pop()$清空,千万不要用$q.front()$.所有的变量也都要清为初始状态,注意初始状态不一定是$0$!

　　这里还有$asuldb$的模板库:https://35178.blog.luogu.org/noip-qian-di-ban-zi-men

　　最大值赋得不够大:$memset$一个 $int$ 数组全为 $1$ 还是比 $10^9$ 小的,可以记录$-1$作为初始状态或是直接用$ll$.

　　离线处理询问后忘了调回原来的顺序:记录$id$,处理完后重排序;

　　奇妙的$CE$:用命令行编译可以彻底杜绝此类问题,注意编译之前另存一份,防止被编译没了.

　　不要用英语单词做变量名,不要用除了$n,m,k,x,y,a,b,c,t$之外的单个字母做变量名.

　　树链剖分时不要用top做变量名.

码农公寓

相关文章