模板太多了，写啥更新啥，顺便当自己的存档
码风很乱，见谅
单点修改树状数组
#include <iostream> #include <cstdio> #include <algorithm> #define ll long long #define rg register #define l() i&-i using namespace std; int n,m,a[500010],tree[500010],c,x,y; inline int lowbit(int x) { return x&(-x); } inline void updata(int x,int k) { for(int i=x;i<=n;i+=lowbit(x)) tree[i]+=k; } inline int query(int x) { int ans=0; for(int i=x;i;i-=lowbit(x)) ans+=tree[i]; return ans; } inline int read() { int x=0,f=1; char ch; while (ch < '0' || ch > '9') {if (ch=='-')f = -1;ch = getchar();} while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();} return f*x; } int main() { n=read(); m=read(); for(int i=1;i<=n;i++) { a[i]=read(); updata(i,a[i]); } for(int i=1;i<=m;i++) { c=read(); if(c==1) { x=read(); y=read(); updata(x,y); } else { x=read(); y=read(); cout<<query(y)-query(x-1)<<endl; } } }
区间修改树状数组
#include <iostream> #include <cstdio> #include <algorithm> #define ll long long #define rg register #define l() i&-i using namespace std; int n,x,y,z,k,tree[500010],a,m,last=0; inline int read() { int x=0,f=1; char ch; while (ch < '0' || ch > '9') {if (ch=='-')f = -1;ch = getchar();} while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();} return f*x; } inline int lowbit(int x) { return x&(-x); } inline void add(int x,int k) { for(int i=x;i<=n;i+=lowbit(i)) tree[i]+=k; } inline long long query(int x) { long long ans=0; for(int i=x;i;i-=lowbit(i)) ans+=tree[i]; return ans; } int main() { n=read(),m=read(); for(int i=1;i<=n;i++) { a=read(); add(i,a-last); last=a; } for(int i=1;i<=m;i++) { cin>>x; if(x==1) { cin>>y>>z>>k; add(y,k); add(z+1,-k); } if(x==2) { cin>>y; cout<<query(y)<<endl; } } }
可持久化线段树（主席树）
#include <iostream> #include <cstdio> #include <algorithm> #define ll long long #define rg register using namespace std; inline int read() { int x=0,f=1; char ch; while (ch < '0' || ch > '9') {if (ch=='-')f = -1;ch = getchar();} while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();} return f*x; } int n,q,m,T[200001],tot,a[200001],b[200001]; struct cym{ int l,r,val; }tree[8000001]; inline int bulid(int l,int r)// 建树操作 { int bj=++tot; tree[bj].val=0; int mid=(l+r)>>1; if(l>r) { tree[bj].l=bulid(l,mid); tree[bj].r=bulid(mid+1,r); } return bj; } inline int change(int pre,int l,int r,int zone)// 修改 { int bj=++tot; tree[bj].l=tree[pre].l; tree[bj].r=tree[pre].r; tree[bj].val=tree[pre].val+1; int mid=(l+r)>>1; if(l<r) { if(zone<=mid) tree[bj].l=change(tree[pre].l,l,mid,zone); else tree[bj].r=change(tree[pre].r,mid+1,r,zone); } return bj; } inline int cx(int from,int to,int l,int r,int k)// 查询 { if(l==r) return l; int x=tree[tree[to].l].val-tree[tree[from].l].val; int mid=(l+r)>>1; if(x>=k) return cx(tree[from].l,tree[to].l,l,mid,k); else return cx(tree[from].r,tree[to].r,mid+1,r,k-x); } int main() { n=read(),q=read(); for(rg int i=1;i<=n;i++) { a[i]=read(); b[i]=a[i]; } sort(b+1,b+n+1);// 排序 m=unique(b+1,b+n+1)-b-1;// 看一共有多少个不重复的元素 T[0]=bulid(1,m);// 把最后一个点建在 主席树数组T[0]的位置 for(rg int i=1;i<=n;i++) { int t=lower_bound(b+1,b+m+1,a[i])-b;// 第一个比a[i] 大的树的位置 T[i]=change(T[i-1],1,m,t); } for(rg int i=1;i<=q;i++) { int l=read(),r=read(),k=read(); int anss=cx(T[l-1],T[r],1,m,k); printf("%d ",b[anss]); } }
ST表
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int MAXN=1e6+10; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int Max[MAXN][21]; int Query(int l,int r) { int k=log2(r-l+1); return max(Max[l][k],Max[r-(1<<k)+1][k]);//把拆出来的区间分别取最值 } int main() { int N=read(),M=read(); for(int i=1;i<=N;i++) Max[i][0]=read(); for(int j=1;j<=21;j++) for(int i=1;i+(1<<j)-1<=N;i++)//注意这里要控制边界 Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);//如果看不懂边界的话建议好好看看图 for(int i=1;i<=M;i++) { int l=read(),r=read(); printf("%d ",Query(l,r)); } return 0; }
Kruskal
/* Kruskal 并查集 结构体存边 luogu P3366 模板 */ #include <iostream> #include <cstdio> #include <algorithm> #define ll long long #define rg register using namespace std; int n,m,ans,now_e,now_v,cnt; inline int read()// 读入优化 { int x=0,f=1; char ch; while (ch < '0' || ch > '9') {if (ch=='-')f = -1;ch = getchar();} while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();} return f*x; } struct Node{ int start,end,power; // start为起始点 // end 为终点 // power 为权值 }edge[2000010];// 存边 int fa[6666];//并查集 int cmp(Node a,Node b) { return a.power<b.power; } inline int find(int x)// 并查集找祖先 { if(x!=fa[x]) { fa[x]=find(fa[x]); } return fa[x]; } /*inline void merge(int x,int y,int n)// 并查集合并 // n用来记录最短路中应该加入哪个点 { int fx=find(x); int fy=find(y); if(fx!=fy) { pre[fx]=fy; sum+=edge[n].power; } }*/ inline void Kruskal() { sort(edge+1,edge+1+m,cmp);// 排序 for(rg int i=1;i<=m;i++) { now_e=find(edge[i].start); now_v=find(edge[i].end); if(now_e==now_v) continue;//若两点联通 就不需要了 ans+=edge[i].power; fa[now_v]=now_e;//合并 if(++cnt==n-1) break;// 边数==点数-1 就结束循环 } } int main() { n=read(),m=read(); for(rg int i=1;i<=n;i++) { fa[i]=i;// 并查集初始化 } for(rg int i=1;i<=m;i++) { edge[i].start=read(); edge[i].end=read(); edge[i].power=read(); } Kruskal(); printf("%d",ans); }
Prim
/* Prim 链式前向星存图 */ #include <iostream> #include <cstdio> #include <algorithm> #define ll long long #define rg register #define inf 0x7ffffff using namespace std; int head[5005],dis[5005],cnt,n,m,tot,now=1,ans; bool vis[5005]; inline int read() { int x=0,f=1; char ch; while (ch < '0' || ch > '9') {if (ch=='-')f = -1;ch = getchar();} while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();} return f*x; } struct Node{ int v,w,next; }e[400010]; inline void add(int u,int v,int w) { e[++cnt].v=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt; } inline int prim() { for(rg int i=2;i<=n;i++) dis[i]=inf; for(rg int i=head[1];i;i=e[i].next) { dis[e[i].v]=min(dis[e[i].v],e[i].w); } while(++tot<n)//最小生成树边数==点数-1 { rg int minn=inf; vis[now]=1;//标记点已经走过 for(rg int i=1;i<=n;i++) { if(!vis[i]&&minn>dis[i]) { minn=dis[i]; now=i; } } ans+=minn; //枚举now的连边，更新dis for(rg int i=head[now];i;i=e[i].next) { rg int v=e[i].v; if(dis[v]>e[i].w&&!vis[v]) { dis[v]=e[i].w; } } } return ans; } int main() { n=read(),m=read(); for(rg int i=1,u,v,w;i<=m;i++) { u=read(),v=read(),w=read(); add(u,v,w),add(v,u,w);//无向图 } printf("%d",prim()); }
稀疏图：Kruskal
稠密图：Prim
Dijkstra
/* Dijkstra 朴素：O(n^2) 堆优化：O((n+m)log^2n) 不可以处理负边权的图 luogu P4799 模板 */ #include <iostream> #include <cstdio> #include <algorithm> #include <queue> #define ll long long #define rg register using namespace std; inline int read() { int x=0,f=1; char ch; while (ch < '0' || ch > '9') {if (ch=='-')f = -1;ch = getchar();} while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();} return f*x; } struct Node{ int v,w,next; }e[500010]; int head[100010],dis[100010],cnt; bool vis[100010]; int n,m,s; inline void add(int u,int v,int dis) { e[++cnt].v=v; e[cnt].w=dis; e[cnt].next=head[u]; head[u]=cnt; } struct node{ int dis;// 值 int pos;// 位置 bool operator <( const node &x)const { return x.dis<dis; } }; // 堆优化 priority_queue<node>q; inline void dij()//名字太长了 容易打错 简写dij { dis[s]=0; q.push((node){0,s}); while(!q.empty()) { node tmp=q.top(); q.pop(); int x=tmp.pos,d=tmp.dis; if(vis[x]) continue; vis[x]=1; for(int i=head[x];i;i=e[i].next) { int y=e[i].v; if(dis[y]>dis[x]+e[i].w) { dis[y]=dis[x]+e[i].w; // if(!vis[y]) //{ q.push(node{dis[y],y}); // } } } } } int main() { n=read(),m=read(),s=read(); for(rg int i=1;i<=n;i++) dis[i]=2147482647;// 尽量赋值大一点 防止答案超过这个数！！！ for(rg int i=1,u,v,d;i<=m;i++) { u=read(),v=read(),d=read(); add(u,v,d); } dij(); for(int i=1;i<=n;i++) printf("%d ",dis[i]); }
倍增版LCA
/* LCA 倍增 */ #include <iostream> #include <cstdio> #include <algorithm> #define ll long long #define rg register using namespace std; inline int read() { int x=0,f=1; char ch; while (ch < '0' || ch > '9') {if (ch=='-')f = -1;ch = getchar();} while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();} return f*x; } struct cym{ int t,nex; }e[1000001]; int depth[500001],fa[500001][22],lg[500001],head[500001],n,m,s; int cnt; inline void add(int x,int y) { e[++cnt].t=y; e[cnt].nex=head[x]; head[x]=cnt; } void dfs(int f,int fath)// f 表示当前的节点，fath 表示他的父亲节点 { depth[f]=depth[fath]+1; fa[f][0]=fath; for(rg int i=1;(1<<i)<=depth[f];i++) fa[f][i]=fa[fa[f][i-1]][i-1];// 核心转移 // f的2^i祖先=f的2^(i-1)的祖先的2(i-1)祖先 //2^i=2^(i-1)+2^(i-1) for(rg int i=head[f];i;i=e[i].nex) if(e[i].t!=fath) dfs(e[i].t,f); } inline int lca(int x,int y) { if(depth[x]<depth[y])// 我们不妨设x的深度>=y的深度 swap(x,y); while(depth[x]>depth[y]) x=fa[x][lg[depth[x]-depth[y]]-1];//先跳到同一深度 if(x==y) return x;// 如果x是y的祖先，那他们的lca就是x for(rg int k=lg[depth[x]]-1;k>=0;k--) { if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k]; } return fa[x][0];//返回父节点 } int main() { n=read(),m=read(),s=read(); for(rg int i=1,x,y;i<=n-1;i++) { x=read(),y=read(); add(x,y); add(y,x); } dfs(s,0); for(rg int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i); // 预处理log2i +1的值 直接调用 for(rg int i=1,x,y;i<=n;i++) { x=read(),y=read(); printf("%d ",lca(x,y)); } }
区间M的最小值（单调队列优化Dp）
#include <iostream> #include <cstdio> #include <algorithm> //#include <windows.h> #define ll long long #define rg register #define ull unsigned long long using namespace std; int n,m; int k,tot,head=1,tail=0; int a[2000009],q[2000009]; inline int read() { int x=0,f=1; char ch; while (ch < '0' || ch > '9') {if (ch=='-')f = -1;ch = getchar();} while (ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();} return f*x; } int main() { n=read(),m=read(); for(rg int i=1;i<=n;i++) a[i]=read(); for(rg int i=1;i<=n;i++) { printf("%d ",a[q[head]]); while(i-q[head]+1>m&&head<=tail) head++; while(a[i]<a[q[tail]]&&head<=tail) tail--; q[++tail]=i; } //system("pause"); return 0; }