各种算法的模板整理
蒟蒻的模板 可能不是很好
============================================================
基础类
- 快速排序【2018.3.10】
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int M=1e6+10;
namespace QSort{
int size;
template <class T>
void swap(T &a,T &b){T t=a;a=b;b=t;}
template <class T>
void Qsort(T a,T b,T *c)
{
if(a==b) return;
T mid=(a+b)/2;
T val=c[mid];
T i=a-1,j=b+1;
while(1)
{
do i++;while(c[i]<val);
do j--;while(c[j]>val);
if(i>=j) break;
swap(c[i],c[j]);
}
Qsort(a,j,c);
Qsort(j+1,b,c);
}
}
using namespace QSort;
int x[M];
void init(){
scanf("%d",&size);
for(int i=1;i<=size;i++)scanf("%d",&x[i]);
}
void out(){
Qsort(1,size,x);
for(int i=1;i<=size;i++)printf("%d ",x[i]);
}
int main(){
init();
out();
return 0;
}
- 归并排序 【2018.3.10】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1e6+10;
namespace GSort{
int size;
template <class T>
void Gsort(T a,T b,T *c,T *d)
{
if(a==b) return;
T mid=(a+b)/2;
Gsort(a,mid,c,d);
Gsort(mid+1,b,c,d);
int f=a,f1=a,f2=mid+1;
while(f1<=mid&&f2<=b){
if(d[f1]<d[f2])c[f++]=d[f1++];
else c[f++]=d[f2++];
}
for(T i=f1;i<=mid;i++)c[f++]=d[i];
for(T i=f2;i<=b;i++) c[f++]=d[i];
for(T i=a;i<=b;i++) d[i] =c[i];
}
}
using namespace GSort;
int td[M],x[M];
void init(){
scanf("%d",&size);
for(int i=1;i<=size;i++)scanf("%d",&x[i]);
}
void out(){
Gsort(1,size,td,x);
for(int i=1;i<=size;i++)printf("%d ",x[i]);
}
int main(){
init();
out();
return 0;
}
图论
- 最小生成树-Kruskal【2018.3.12】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=2e5+10,N=5010;
int n,m;
struct ss{
int from,to,val;
ss(int a=0,int b=0,int c=0):from(a),to(b),val(c){}
bool operator <(ss a)const{return val<a.val;}
}g[M];
struct ufs{
int f[N];
int find(int a){return f[a]==a?a:f[a]=find(f[a]);}
void init(){for(int i=1;i<=n;i++)f[i]=i;}
void uni(int a,int b){f[a]=b;}
}uf;
void readin(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d%d",&g[i].from,&g[i].to,&g[i].val);
}
int Kruskal(){
sort(g+1,g+m+1);
uf.init();
int tot=0,ans=0;
for(int i=1;i<=m;i++){
int a=uf.find(g[i].from),b=uf.find(g[i].to);
if(a==b) continue;
uf.uni(a,b);
tot++;ans+=g[i].val;
if(tot==n-1) break;
}
return ans;
}
int main()
{
readin();
printf("%d
",Kruskal());
return 0;
}Before 风格
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1e5+10;
struct ss{
int from,to,cap;
bool operator <(ss a)const{return cap<a.cap;}
}g[M<<1];
int f[M];
int n,m;
int find(int a){return f[a]==a?a:f[a]=find(f[a]);}
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) f[i]=i;
}
int main()
{
init();
for(int i=1;i<=m;i++){
scanf("%d%d%d",&g[i].from,&g[i].to,&g[i].cap);
}
sort(g+1,g+m+1);
int tot=0,ans=0;
for(int i=1;i<=m;i++){
int f1=find(g[i].from),f2=find(g[i].to);
if(f1==f2) continue;
f[f1]=f2;
ans+=g[i].cap;tot++;
if(tot==n-1) break;
}
printf("%d
",ans);
return 0;
}- 最大流-Dinic 【2018.3.13】
- 前向星存图(链表)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1e5+10;
int n,m,s,t;
struct ss{
int to,last,cap;
ss(int a=0,int b=0,int c=0):to(a),last(b),cap(c){}
}g[M<<1];
int head[M],cnt=1;
void add(int a,int b,int c){
g[++cnt]=ss(b,head[a],c);head[a]=cnt;
g[++cnt]=ss(a,head[b],0);head[b]=cnt;
}
int dep[M],cur[M],que[M],p,q;
int bfs(){
memset(dep,0,sizeof(dep));
dep[s]=1;que[p=q=1]=s;
for(;p<=q;p++){
int now=que[p];
for(int i=head[now];i;i=g[i].last){
if(!dep[g[i].to]&&g[i].cap>0){
dep[g[i].to]=dep[now]+1;
que[++q]=g[i].to;
}
}
}
return dep[t];
}
int dfs(int a,int cap){
if(a==t||cap<0) return cap;
int tot=0;
if(!cur[a]) cur[a]=head[a];
for(int &i=cur[a];i;i=g[i].last){
if(g[i].cap>0&&dep[g[i].to]==dep[a]+1){
int now=dfs(g[i].to,min(g[i].cap,cap));
tot+=now;cap-=now;
g[i].cap-=now;g[i^1].cap+=now;
if(cap<=0) break;
}
}
return tot;
}
const int inf=0x7fffffff;
int maxflow(){
int ans=0;
while(bfs()){
memset(cur,0,sizeof(cur));
ans+=dfs(s,inf);
}
return ans;
}
int a,b,c;
void readin(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
}
int main()
{
readin();
printf("%d
",maxflow());
return 0;
}- 邻接表存图(vector)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
const int M=6e5+10,N=1010,inf=0x7fffffff;
int cal[N],que[N],p,q,dep[N],cnt=1;
int n,m,st,en,ans;
struct ss{
int to,cap;
ss(int a=0,int b=0):to(a),cap(b){}
}g[M];
vector <int> vec[N];
void add(int a,int b,int c){
g[++cnt]=ss(b,c);vec[a].push_back(cnt);
g[++cnt]=ss(a,0);vec[b].push_back(cnt);
}
int bfs(){
memset(dep,0,sizeof(dep));
dep[st]=1;que[p=q=1]=st;
for(;p<=q;p++){
int now=que[p];
for(int i=0;i<(int)vec[now].size();i++){
int t=vec[now][i];
if(!dep[g[t].to]&&g[t].cap){
dep[g[t].to]=dep[now]+1;
que[++q]=g[t].to;
}
}
}
return dep[en];
}
int dfs(int a,int cap){
if(a==en||!cap) return cap;
int tot=0;
for(int &i=cal[a];i<vec[a].size();i++){
int t=vec[a][i];
if(dep[g[t].to]==dep[a]+1&&g[t].cap){
int now=dfs(g[t].to,min(cap,g[t].cap));
g[t].cap-=now;g[t^1].cap+=now;
tot+=now;
cap-=now;
if(!cap) break;
}
}
return tot;
}
int a,b,c;
int read(){
int x=0;char ch=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') {
x=(x<<3)+(x<<1)+ch-'0';ch=getchar();
}
return x;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&st,&en);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
while(bfs()){
memset(cal,0,sizeof(cal));
int now;
while(now=dfs(st,inf)) ans+=now;
}
printf("%d
",ans);
return 0;
}- 并查集【2018.3.15】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=2e5+10;
namespace BCJ{
template <class T>
struct bcj{
T f[M];
T find(T a){return f[a]==a?a:f[a]=find(f[a]);}
T operator [](T a){return find(a);}
void clear(){memset(f,0,sizeof(f));}
void init(T a){for(T i=0;i<=a;i++)f[i]=i;}
};
void merge(bcj <int> &a,int t1,int t2){
int f1=a[t1],f2=a[t2];
if(f1==f2) return;
a.f[f1]=f2;
}
}
using namespace BCJ;
bcj <int> f;
int n,m,a,b,c;
int main()
{
scanf("%d%d",&n,&m);
f.init(n);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
switch(a){
case 1:{
merge(f,b,c);
break;
}
case 2:{
if(f[b]==f[c]) printf("Y
");
else printf("N
");
break;
}
}
}
return 0;
}- 并查集【以前的风格】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=2e5+10;
int n,m;
int f[M];
int find(int a){return f[a]==a?a:f[a]=find(f[a]);}
void init(){for(int i=1;i<=n;i++)f[i]=i;}
int cao,a,b;
int main(){
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=m;i++){
scanf("%d%d%d",&cao,&a,&b);
int p1=find(a),p2=find(b);
if(cao==2){
if(p1==p2) printf("Y
");
else printf("N
");
}else{
f[p1]=p2;
}
}
return 0;
}LCA【2018.3.19】
Tarjan离线算法
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=5e5+10;
struct ss{
int to,last;
ss(int a=0,int b=0):to(a),last(b){}
}g[M<<1];
struct que{
int to,last,lca;
que(int a=0,int b=0,int c=0):to(a),last(b),lca(c){}
}q[M<<1];
int headg[M],headq[M],n,m,root,a,b;
int cnt,tot=1;
int f[M];
int find(int a){return f[a]==a?a:f[a]=find(f[a]);}
void add1(int a,int b){
g[++cnt]=ss(b,headg[a]);headg[a]=cnt;
g[++cnt]=ss(a,headg[b]);headg[b]=cnt;
}
void add2(int a,int b){
q[++tot]=que(b,headq[a]);headq[a]=tot;
q[++tot]=que(a,headq[b]);headq[b]=tot;
}
bool vis[M];
void dfs(int a){
f[a]=a;vis[f[a]]=1;
for(int i=headg[a];i;i=g[i].last){
if(vis[g[i].to]) continue;
dfs(g[i].to);f[g[i].to]=a;
}
for(int i=headq[a];i;i=q[i].last){
if(vis[q[i].to]){
q[i^1].lca=q[i].lca=find(q[i].to);
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&root);
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
add1(a,b);
}
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
add2(a,b);
}
dfs(root);
for(int i=1;i<=m;i++)printf("%d
",q[i<<1].lca);
return 0;
}- 倍增的在线算法
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=5e5+10;
int n,m,root;
int f[M][22];
struct ss{
int to,last;
ss(int a=0,int b=0):to(a),last(b){}
}g[M<<1];
int head[M],cnt;
void add(int a,int b){
g[++cnt]=ss(b,head[a]);head[a]=cnt;
g[++cnt]=ss(a,head[b]);head[b]=cnt;
}
int dep[M];
void dfs(int a,int fa,int dp){
dep[a]=dp;
f[a][0]=fa;
for(int i=1;i<=21;i++){f[a][i]=f[f[a][i-1]][i-1];}
for(int i=head[a];i;i=g[i].last){
if(g[i].to==fa) continue;
dfs(g[i].to,a,dp+1);
}
}
void swap(int &a,int &b){a^=b^=a^=b;}
int lca(int a,int b){
if(dep[a]<dep[b]) swap(a,b);
for(int i=21;i>=0;i--){
if(dep[f[a][i]]>=dep[b]){
a=f[a][i];
}
}
if(a==b) return a;
for(int i=21;i>=0;i--){
if(f[a][i]!=f[b][i]){
a=f[a][i];
b=f[b][i];
}
}
return f[a][0];
}
int a,b;
int main()
{
scanf("%d%d%d",&n,&m,&root);
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
add(a,b);
}
dfs(root,0,1);
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
printf("%d
",lca(a,b));
}
return 0;
}- 最小费用最大流SPFA【2018.3.31】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1e5+10;
const int inf=0x7fffffff;
int n,m,s,t;
struct ss{
int to,last,cap,cost;
ss(int a=0,int b=0,int c=0,int d=0):to(a),last(b),cap(c),cost(d){}
}g[M<<1];
int head[M],cnt=1;
void add(int a,int b,int c,int d){
g[++cnt]=ss(b,head[a],c,d);head[a]=cnt;
g[++cnt]=ss(a,head[b],0,-d);head[b]=cnt;
}
int dis[M],que[M],p,q,flow[M],from[M],pos[M];
bool used[M];
bool bfs(){
for(int i=1;i<=n;i++){
used[i]=flow[i]=from[i]=0;
dis[i]=inf;
}
used[s]=1;flow[s]=inf;dis[s]=0;
que[p=q=1]=s;
for(;p<=q;p++){
int now=que[p];
used[now]=0;
for(int i=head[now];i;i=g[i].last){
if(dis[g[i].to]>dis[now]+g[i].cost&&g[i].cap>0){
dis[g[i].to]=dis[now]+g[i].cost;
from[g[i].to]=now;pos[g[i].to]=i;
flow[g[i].to]=min(flow[now],g[i].cap);
if(!used[g[i].to]){
used[g[i].to]=1;
que[++q]=g[i].to;
if(dis[que[(p+1)]]>dis[que[q]])
swap(que[(p+1)],que[q]);
}
}
}
}
if(dis[t]==inf) return 0;return 1;
}
void work(){
int mc=0,mf=0;
while(bfs()){
mc+=flow[t]*dis[t];
mf+=flow[t];
for(int i=t;i;i=from[i]){
g[pos[i]].cap-=flow[t];
g[pos[i]^1].cap+=flow[t];
}
}
printf("%d %d
",mf,mc);
}
int a,b,c,d;
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&a,&b,&c,&d);
add(a,b,c,d);
}
work();
return 0;
}数据结构
- 堆（大根和小根）【2018.3.13】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1e6+10;
#define MIN
/*
MIN 从小到大：小根堆
MAX 从大到小：大根堆
*/
#include<iostream>
namespace Heap{
template <class T>
struct HEAP{
T heap[M];int sze;
#ifdef MIN
/*Min*/
void insert(T a){
heap[++sze]=a;
int fa=sze>>1,now=sze;
while(fa){
if(heap[fa]>heap[now]) swap(heap[fa],heap[now]);
now=fa;fa=now>>1;
}
}
void pop(){
heap[1]=heap[sze];sze--;
int son=2,now=1;
while(son<=sze){
if(son+1<=sze&&heap[son+1]<heap[son]) son++;
if(heap[now]<heap[son]) break;
else swap(heap[now],heap[son]);
now=son,son=now<<1;
}
}
#endif
#ifndef MIN
#ifdef MAX
/*Max*/
void insert(T a){
heap[++sze]=a;
int fa=sze>>1,now=sze;
while(fa){
if(heap[fa]<heap[now]) swap(heap[fa],heap[now]);
now=fa;fa=now>>1;
}
}
void pop(){
heap[1]=heap[sze];sze--;
int son=2,now=1;
while(son<=sze){
if(son+1<=sze&&heap[son+1]>heap[son]) son++;
if(heap[now]>heap[son]) break;
else swap(heap[now],heap[son]);
now=son,son=now<<1;
}
}
#endif
#endif
T top(){return heap[1];}
void out(T *a,int begin,int end){for(int i=begin;i<=end;i++) a[i]=top(),pop();}
int size(){return sze;}
void sort(T *a,int begin,int end){
for(int i=begin;i<=end;i++){insert(a[i]);}
out(a,begin,end);
}
void clear(){memset(heap,0,sizeof(heap));sze=0;}
};
}
using namespace Heap;
HEAP <int> hp;
/*Luogu P1177排序*/
int n,x[M];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&x[i]);}
hp.sort(x,1,n);
for(int i=1;i<=n;i++) printf("%d ",x[i]);
return 0;
}
/*Luogu P3378 堆*/
int n,cao,b;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&cao);
switch(cao){
case 1:{
scanf("%d",&b);
hp.insert(b);
break;
}
case 2:{
printf("%d
",hp.top());
break;
}
case 3:{
hp.pop();
break;
}
}
}
return 0;
}- 树状数组(全)【2018.3.16】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=5e5+10;
namespace BITTREE{
int lowbit(int a){return (a&(-a));}
/*普通的树状数组*/
template <class T>
struct bit_tree{
T f[M];
int sze;
int size(){return sze;}
void add_pos(int p,T a){
for(int i=p;i<=sze;i+=lowbit(i))f[i]+=a;
}
void add_area(int l,int r,T a){
add_pos(l,a);add_pos(r+1,-a);
}
T query_pos(int p){
T ans=0;
for(int i=p;i;i-=lowbit(i)) ans+=f[i];
return ans;
}
T query_area(int l,int r){
T ans=query_pos(r)-query_pos(l-1);
return ans;
}
void clear(){memset(f,0,sizeof(f));}
bit_tree(int a=1){if(!a)clear();}
T operator [](int a){return query_pos(a);sze=0;}
};
/*树组树组维护区间最大值*/
template <class T>
struct max_tree{
T maxv[M],v[M];
int sze;
int size(){return sze;}
T max_area(int l,int r){
T ans=0;
while(l<=r){
ans=max(ans,v[r]);r--;
for(;r-lowbit(r)>=l;r-=lowbit(r)) ans=max(ans,maxv[r]);
}
return ans;
}
T change_pos(int p,T a){
v[p]=a;
for(int i=p;i<=sze;i+=lowbit(i)){
maxv[i]=v[i];
for(int j=1;j<lowbit(i);j<<=1) maxv[i]=max(maxv[i],maxv[i-j]);
}
}
T operator [](int a){return v[a];}
T operator ()(int a,int b){return max_area(a,b);}
void init(int p){
for(int i=p;i<=sze;i+=lowbit(i)) maxv[i]=max(maxv[i],v[p]);
}
void clear(){memset(maxv,0,sizeof(maxv));memset(v,0,sizeof(v));sze=0;}
};
/*二维树状数组*/
template <class T>
struct two_bit{
T f[2000][2000];
int sze1,sze2;
void add_pos(int a,int b,T v){
for(int i=a;i<=sze1;i+=lowbit(i))
for(int j=b;j<=sze2;j+=lowbit(j))
f[i][j]+=v;
}
T query_pos(int a,int b){
T ans=0;
for(int i=a;i;i-=lowbit(i))
for(int j=b;j;j-=lowbit(j))
ans+=f[i][j];
return ans;
}
void add_area(int x1,int y1,int x2,int y2){
add_pos(x1,y1,1);
add_pos(x1,y2+1,-1);
add_pos(x2+1,y1,-1);
add_pos(x2+1,y2+1,1);
}
T operator ()(int a,int b){return query_pos(a,b);}
void clear(){memset(f,0,sizeof(f));sze1=sze2=0;}
};
}
using namespace BITTREE;
/*Luogu P3368*/
//bit_tree <int> tr;
//int m,a,b,c,d;
//int main()
//{
// scanf("%d%d",&tr.sze,&m);
// for(int i=1;i<=tr.sze;i++){
// scanf("%d",&a);
// tr.add_area(i,i,a);
// }
// for(int i=1;i<=m;i++){
// scanf("%d%d",&a,&b);
// if(a==1){
// scanf("%d%d",&c,&d);
// tr.add_area(b,c,d);
// }else{
// printf("%d
",tr[b]);
// }
// }
// return 0;
//}
/*Luogu P3374*/
//bit_tree <int> tr;
//int m,a,b,c,d;
//int main()
//{
// scanf("%d%d",&tr.sze,&m);
// for(int i=1;i<=tr.sze;i++){
// scanf("%d",&a);
// tr.add_pos(i,a);
// }
// for(int i=1;i<=m;i++){
// scanf("%d%d%d",&a,&b,&c);
// if(a==1){
// tr.add_pos(b,c);
// }else{
// printf("%d
",tr.query_area(b,c));
// }
// }
// return 0;
//}
/*HDU1754*/
//max_tree <int> tr2;
//int n,m,a,b;
//char cao[2];
//int main(){
// while(scanf("%d%d",&n,&m)==2){
// tr2.sze=n;
// for(int i=1;i<=n;i++){
// scanf("%d",&a);
// tr2.v[i]=a;
// tr2.init(i);
// }
// for(int i=1;i<=m;i++){
// scanf("%s%d%d",cao,&a,&b);
// if(cao[0]=='Q'){
// printf("%d
",tr2(a,b));
// }else{
// tr2.change_pos(a,b);
// }
// }
// tr2.clear();
// }
// return 0;
//}
/*POJ2155*/
//int T,t1,t2,t3,t4,n,m;
//char cao[5];
//two_bit <int> tr;
//int main()
//{
// scanf("%d",&T);
// while(T--){
// tr.clear();
// scanf("%d%d",&n,&m);
// tr.sze1=tr.sze2=n;
// for(int i=1;i<=m;i++){
// scanf("%s",cao);
// if(cao[0]=='C'){
// scanf("%d%d%d%d",&t1,&t2,&t3,&t4);
// tr.add_area(t1,t2,t3,t4);
// }else{
// scanf("%d%d",&t1,&t2);
// printf("%d
",tr(t1,t2)&1);
// }
// }
// printf("
");
// }
// return 0;
//}- 线段树1【2018.3.16】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1e5+10;
namespace Segment_tree{
template <class T>
struct segment_tree{
int sze;
T sumv[M<<2],v[M],lazy[M<<2];
void pushup(int o){sumv[o]=sumv[o<<1]+sumv[o<<1|1];}
void pushdown(int o,int l,int r){
if(!lazy[o]) return;
int mid=l+r>>1;
lazy[o<<1]+=lazy[o];lazy[o<<1|1]+=lazy[o];
sumv[o<<1]+=lazy[o]*(mid-l+1);
sumv[o<<1|1]+=lazy[o]*(r-mid);
lazy[o]=0;
}
void build(int o,int l,int r){
lazy[o]=0;
if(l==r){sumv[o]=v[l];return;}
int mid=l+r>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pushup(o);
}
void init(){build(1,1,sze);}
void add_area(int o,int l,int r,int L,int R,T val){
if(L<=l&&r<=R){
lazy[o]+=val;sumv[o]+=(r-l+1)*val;
return;
}
pushdown(o,l,r);
int mid=l+r>>1;
if(L<=mid) add_area(o<<1,l,mid,L,R,val);
if(R>mid) add_area(o<<1|1,mid+1,r,L,R,val);
pushup(o);
}
T query_area(int o,int l,int r,int L,int R){
if(L<=l&&r<=R){return sumv[o];}
pushdown(o,l,r);
int mid=l+r>>1;
T ans=0;
if(L<=mid) ans+=query_area(o<<1,l,mid,L,R);
if(R>mid) ans+=query_area(o<<1|1,mid+1,r,L,R);
pushup(o);
return ans;
}
void add_pos(int o,int l,int r,int pos,T val){
if(l==r){sumv[o]+=val;return;}
pushdown(o,l,r);
int mid=l+r>>1;
if(pos<=mid) add_pos(o<<1,l,mid,pos,val);
else add_pos(o<<1|1,mid+1,r,pos,val);
pushup(o);
}
T query_pos(int o,int l,int r,int pos){
if(l==r){return sumv[o];}
pushdown(o,l,r);
int mid=l+r>>1;
T ans=0;
if(pos<=mid) ans=query_pos(o<<1,l,mid,pos);
else ans=query_pos(o<<1|1,mid+1,r,pos);
pushup(o);
return ans;
}
void clear(){
memset(v,0,sizeof(v));
memset(sumv,0,sizeof(sumv));
}
T get_area(int a,int b){return query_area(1,1,sze,a,b);}
void up_area(int a,int b,T c){add_area(1,1,sze,a,b,c);}
T get_pos (int a){return query_pos(1,1,sze,a);}
void up_pos (int a,T b){add_pos(1,1,sze,a,b);}
T operator ()(int a,int b){return get_area(a,b);}
T operator ()(int a){return get_pos(a);}
};
}
#define ll long long
using namespace Segment_tree;
segment_tree <ll> tr;
int m,cao,x,y;
ll k;
/*Luogu P3372*/
int main()
{
scanf("%d%d",&tr.sze,&m);
for(int i=1;i<=tr.sze;i++) scanf("%d",&tr.v[i]);
tr.init();
for(int i=1;i<=m;i++){
scanf("%d%d%d",&cao,&x,&y);
if(cao==1){
scanf("%lld",&k);
tr.up_area(x,y,k);
}else{
printf("%lld
",tr(x,y));
}
}
return 0;
}- RMQ算法【2018.3.20】
//#include<cstdio>
//#include<cstring>
//#include<algorithm>
//
//using namespace std;
//const int M=1e5+10,Log=17;
//#define MIN
//namespace RMQ{
//#ifdef MIN
//template <class T>
// T ck(T a,T b){return a<b?a:b;}
//#endif
//#ifndef MIN
//#ifdef MAX
//template <class T>
// T ck(T a,T b){return a<b?b:a;}
//#endif
//#endif
//template <class T>
// struct rmq{
// T rmq[M][Log];
// int sze;
// int &size(){return sze;}
// T &operator [](int a){return rmq[a][0];}
// void init(){
// for(int i=1;(1<<i)<=sze;i++){
// for(int j=1;j+(1<<i)-1<=sze;j++){
// rmq[j][i]=ck(rmq[j][i-1],rmq[j+(1<<(i-1))][i-1]);
// }
// }
// }
// T query(int l,int r){
// if(l>r) swap(l,r);
// int k=0;
// while(1<<(k+1)<=r-l+1) k++;
// return ck(rmq[l][k],rmq[r-(1<<k)+1][k]);
// }
// T operator ()(int l,int r){return query(l,r);}
// };
//}
//using namespace RMQ;
//rmq <int> sta;
//int main()
//{
// scanf("%d",&sta.size());
// for(int i=1;i<=sta.size();i++){scanf("%d",&sta[i]);}
// sta.init();
// int m,l,r;
// scanf("%d",&m);
// for(int i=1;i<=m;i++){
// scanf("%d%d",&l,&r);
// printf("%d
",sta(l,r));
// }
// return 0;
//}
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1e5+10,Log=17;
namespace RMQ{
template <class T>
//class==typename
struct rmq{
T rmq[M][Log];
int sze;
int &size(){return sze;}
T &operator [](int a){return rmq[a][0];}
template <typename Comp>
void init(Comp ck){
for(int i=1;(1<<i)<=sze;i++){
for(int j=1;j+(1<<i)-1<=sze;j++){
rmq[j][i]=ck(rmq[j][i-1],rmq[j+(1<<(i-1))][i-1]);
}
}
}
template <typename Comp>
T query(int l,int r,Comp ck){
if(l>r) swap(l,r);
int k=0;
while(1<<(k+1)<=r-l+1) k++;
return ck(rmq[l][k],rmq[r-(1<<k)+1][k]);
}
template <typename Comp>
T operator ()(int l,int r,Comp ck){return query(l,r,ck);}
};
}
using namespace RMQ;
int mi(int a,int b){return a<b?a:b;}
rmq <int> sta;
int main()
{
scanf("%d",&sta.size());
for(int i=1;i<=sta.size();i++){scanf("%d",&sta[i]);}
sta.init(mi);
int m,l,r;
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&l,&r);
printf("%d
",sta(l,r,mi));
}
return 0;
}- 树链剖分【2018.3.31】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1e5+10;
int n,m,root,p;
struct ss{
int to,last;
ss(int a=0,int b=0):to(a),last(b){}
}g[M<<1];
int head[M],cnt;
void add(int a,int b){
g[++cnt]=ss(b,head[a]);head[a]=cnt;
g[++cnt]=ss(a,head[b]);head[b]=cnt;
}
int dep[M],f[M],son[M],sze[M],num[M],top[M],rf[M],val[M],tim;
void dfs1(int a,int fa,int dp){
f[a]=fa;dep[a]=dp;sze[a]=1;
for(int i=head[a];i;i=g[i].last){
if(g[i].to==fa) continue;
dfs1(g[i].to,a,dp+1);
sze[a]+=sze[g[i].to];
if(!son[a]||sze[g[i].to]>sze[son[a]]) son[a]=g[i].to;
}
}
void dfs2(int a,int b){
num[a]=++tim;rf[tim]=a;top[a]=b;
if(!son[a]) return;
dfs2(son[a],b);
for(int i=head[a];i;i=g[i].last){
if(g[i].to==f[a]||g[i].to==son[a]) continue;
dfs2(g[i].to,g[i].to);
}
}
int sumv[M<<2],lazy[M<<2];
void pushup(int o){sumv[o]=(sumv[o<<1]+sumv[o<<1|1])%p;}
int pushdown(int o,int l,int r){
if(!lazy[o]) return (l+r)>>1;
lazy[o<<1]+=lazy[o];lazy[o<<1|1]+=lazy[o];
lazy[o<<1]%=p;lazy[o<<1|1]%=p;
int mid=l+r>>1;
sumv[o<<1]+=lazy[o]*(mid-l+1);sumv[o<<1]%=p;
sumv[o<<1|1]+=lazy[o]*(r-mid);sumv[o<<1|1]%=p;
lazy[o]=0;
return mid;
}
void build(int o,int l,int r){
if(l==r){sumv[o]=val[rf[l]]%p;return;}
int mid=l+r>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pushup(o);
}
int query(int o,int l,int r,int L,int R){
if(L<=l&&r<=R) return sumv[o]%p;
int mid=pushdown(o,l,r),ans=0;
if(L<=mid) ans=query(o<<1,l,mid,L,R);
if(R> mid) ans=(ans+query(o<<1|1,mid+1,r,L,R))%p;
pushup(o);
return ans;
}
void update(int o,int l,int r,int L,int R,int v){
if(L<=l&&r<=R){
sumv[o]=(sumv[o]+v*(r-l+1)%p)%p;
lazy[o]=(lazy[o]+v)%p;
return;
}
int mid=pushdown(o,l,r);
if(L<=mid) update(o<<1,l,mid,L,R,v);
if(R> mid) update(o<<1|1,mid+1,r,L,R,v);
pushup(o);
}
void add1(int a,int v){update(1,1,tim,num[a],num[a]+sze[a]-1,v);}
int ask1(int a){return query(1,1,tim,num[a],num[a]+sze[a]-1);}
void add2(int a,int b,int v){
while(top[a]!=top[b]){
if(dep[top[a]]<dep[top[b]]) swap(a,b);
update(1,1,tim,num[top[a]],num[a],v);
a=f[top[a]];
}
if(dep[a]>dep[b]) swap(a,b);
update(1,1,tim,num[a],num[b],v);
}
int ask2(int a,int b){
int ans=0;
while(top[a]!=top[b]){
if(dep[top[a]]<dep[top[b]]) swap(a,b);
ans=(ans+query(1,1,tim,num[top[a]],num[a]))%p;
a=f[top[a]];
}
if(dep[a]>dep[b]) swap(a,b);
return (ans+query(1,1,tim,num[a],num[b]))%p;
}
int cao,a,b,c;
int main()
{
scanf("%d%d%d%d",&n,&m,&root,&p);
for(int i=1;i<=n;i++) scanf("%d",&val[i]);
for(int i=1;i<n;i++){scanf("%d%d",&a,&b);add(a,b);}
dfs1(root,0,1);dfs2(root,root);
build(1,1,tim);
for(int i=1;i<=m;i++){
scanf("%d",&cao);
switch(cao){
case 1:{
scanf("%d%d%d",&a,&b,&c);c%=p;
add2(a,b,c);
break;
}
case 2:{
scanf("%d%d",&a,&b);
printf("%d
",ask2(a,b));
break;
}
case 3:{
scanf("%d%d",&a,&b);b%=p;
add1(a,b);
break;
}
case 4:{
scanf("%d",&a);
printf("%d
",ask1(a));
break;
}
}
}
return 0;
}字符串
- 后缀数组【2018.3.16】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1e6+500;
int cnt[M],y[M<<1],sa[M<<1],rak[M<<1],A=256;
char str[M<<1];
int main()
{
scanf("%s",str);
int len=strlen(str);
for(int i=0;i<len;i++) cnt[rak[i]=str[i]]++;
for(int i=1;i<255;i++) cnt[i]+=cnt[i-1];
for(int i=len-1;i>=0;i--) sa[--cnt[rak[i]]]=i;
for(int w=1;w<=len;w<<=1){
memset(cnt,0,sizeof(cnt));int p=0;
for(int i=len-w;i<len;i++) y[p++]=i;
for(int i=0;i<len;i++) if(sa[i]>=w) y[p++]=sa[i]-w;
for(int i=0;i<len;i++) cnt[rak[y[i]]]++;
for(int i=1;i<A;i++) cnt[i]+=cnt[i-1];
for(int i=len-1;i>=0;i--) sa[--cnt[rak[y[i]]]]=y[i];
swap(y,rak);p=1;
for(int i=0;i<len;i++){
if(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+w]==y[sa[i]+w]) rak[sa[i]]=p-1;
else rak[sa[i]]=p++;
}
if(p>len) break;A=p;
}
for(int i=0;i<len;i++){rak[sa[i]]=i;printf("%d ",sa[i]+1);}
return 0;
}- kmp算法【2018.3.29】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1e6+10;
struct kmp{
bool flag;
int fail[M];
char s1[M],s2[M];
void getfail(char *str,int *f){
int len=strlen(str);
f[0]=f[1]=0;
for(int i=1;i<=len;i++){
int j=f[i];
while(j&&str[i]!=str[j])j=f[j];
if(str[i]==str[j]) f[i+1]=j+1;
else f[i+1]=0;
}
}
void find(char *a,char *b,int *f){
int l1=strlen(a),l2=strlen(b);
getfail(b,f);int j=0;
for(int i=0;i<l1;i++){
while(j&&a[i]!=b[j])j=f[j];
if(a[i]==b[j])j++;
if(j==l2){printf("%d
",i-l2+2);}
}
if(flag)for(int i=1;i<=l2;i++){printf("%d ",f[i]);}
}
void init(){if(!flag)scanf("%*d%*d");scanf("%s%s",s1,s2);}
void work(){find(s1,s2,fail);}
}K;
int main()
{
K.flag=1;
K.init();
K.work();
return 0;
}
数论
- 卢卡斯定理(求组合数&&阶乘取模)【2018.3.16】
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int M=1e5+10;
ll ny[M],pow[M];//ny为预处理逆元
int n,m,p,T;
ll lucas(int a,int b){
if(a<b) return 0;
if(a<p) return pow[a]*ny[b]*ny[a-b]%p;
return lucas(a/p,b/p)*lucas(a%p,b%p)%p;
}
int main()
{
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&p);
ny[0]=ny[1]=pow[0]=pow[1]=1ll;
for(int i=2;i<=n+m;i++) pow[i]=1ll*pow[i-1]*i%p;
for(int i=2;i<=n+m;i++) ny[i]=1ll*(p-p/i)*ny[p%i]%p;
for(int i=2;i<=n+m;i++) ny[i]=1ll*ny[i-1]*ny[i]%p;
printf("%lld
",lucas(n+m,m));
}
return 0;
}- 线性基【2018.3.16】
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int M=60;
ll a,p[M];
void insert(ll a){
for(int i=55;i>=0;i--){
if(!((a>>i)&1ll)) continue;
if(!p[i]){p[i]=a;return;}
a^=p[i];
}
}
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a);
insert(a);
}
ll ans=0;
for(int i=55;i>=0;i--){
ans=max(ans,ans^p[i]);
}
printf("%lld
",ans);
return 0;
}
- FFT快速傅里叶变换【2018.3.31】
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define db double
#define com Complex
using namespace std;
int n,m;
const int M=3e6+10;
const db pi=acos(-1);
struct Complex{
db x,y;
com(db a=0,db b=0):x(a),y(b){}
com operator +(com a){return com(x+a.x,y+a.y);}
com operator -(com a){return com(x-a.x,y-a.y);}
com operator /(db a){return com(x/a ,y/a );}
com operator !( ){return com(x ,-y );}
com operator *(com a){return com(x*a.x-y*a.y,x*a.y+y*a.x);}
}a[M],b[M];
void swap(com &a,com &b){com t=a;a=b;b=t;}
void FFT(com *a,int tot,int f){
int mid=tot>>1,i,j,k;
for(i=1,j=mid;i<tot-1;i++){
if(i<j) swap(a[i],a[j]);
for(k=mid;j>=k;j-=k,k>>=1);
if(j<k) j+=k;
}
for(i=2;i<=tot;i<<=1){
mid=i>>1;
com wn=com(cos(2*pi/i),f*sin(2*pi/i));
for(j=0;j<tot;j+=i){
com w=com(1,0),x,y;
for(k=j;k<j+mid;k++,w=w*wn){
x=a[k],y=w*a[k+mid];
a[k]=x+y;a[k+mid]=x-y;
}
}
}
}
void work(){
int k=1;for(;k<=n+m;k<<=1);
FFT(a,k,1);FFT(b,k,1);
for(int i=0;i<=k;i++) a[i]=a[i]*b[i];
FFT(a,k,-1);
for(int i=0;i<=n+m;i++)
printf("%d ",int(a[i].x/k+0.5));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++) scanf("%lf",&a[i].x);
for(int i=0;i<=m;i++) scanf("%lf",&b[i].x);
work();
return 0;
}计算几何
模板【2018.3.26】 传送门
- 旋转卡(qia3)壳(ke2) + 凸包 POJ2079 【2018.3.26】
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define db double
using namespace std;
const int M=1e5+1;
int n,m;
struct point{
db x,y;
point(db a=0,db b=0):x(a),y(b){}
void in(){scanf("%lf%lf",&x,&y);}
bool operator <(point a)const{return x<a.x||(x==a.x&&y<a.y);}
}pp[M],ans[M];
point operator -(point a,point b){return point(a.x-b.x,a.y-b.y);}
bool cmp(point a,point b){return (a.y<b.y)||(a.y==b.y&&a.x<b.x);}
db cross(point a,point b){return a.x*b.y-a.y*b.x;}
void convexhull(){
sort(pp,pp+n);
m=0;
for(int i=0;i<n;i++){
while(m>1&&cross(ans[m-1]-ans[m-2],pp[i]-ans[m-2])<=0) m--;
ans[m++]=pp[i];
}
int k=m;
for(int i=n-2;i>=0;i--){
while(m>k&&cross(ans[m-1]-ans[m-2],pp[i]-ans[m-2])<=0) m--;
ans[m++]=pp[i];
}
if(n>1)m--;
}
db area(point a,point b,point c){return cross(b-a,c-a);}
db rotcap(){
db zans=0;
int p=1,q=2;
for(int i=0;i<m;i++){
while(fabs(area(ans[(q+1)%m],ans[i],ans[p]))>fabs(area(ans[q],ans[i],ans[p]))) q=(q+1)%m;
zans=max(zans,fabs(area(ans[q],ans[i],ans[p])));
while(fabs(area(ans[(p+1)%m],ans[i],ans[q]))>fabs(area(ans[p],ans[i],ans[q]))) p=(p+1)%m;
zans=max(zans,fabs(area(ans[p],ans[i],ans[q])));
}
return zans/2;
}
int main()
{
while(scanf("%d",&n)==1&&n>0){
for(int i=0;i<n;i++) pp[i].in();
convexhull();
printf("%.2lf
",rotcap());
}
return 0;
}