以下是本蒟蒻认为的NOIP范围内的所有模板，自认为写的又好懂又好记。按照基本算法->基本数据结构->数学->高级数据结构->图论的顺序编排，提供所有OJ模板题链接和代码。希望能帮助大家。
目录
快速幂||取余运算
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
LL a,b,p;
inline LL power(LL a,LL b,LL p){
LL ans=1%p;
for(;b;b>>=1){
if(b&1)ans=ans*a%p;
a=a*a%p;
}
return ans;
}
int main(){
a=read<LL>();b=read<LL>();p=read<LL>();
printf("%lld^%lld mod %lld=%lld
",a,b,p,power(a,b,p));
return 0;
}
三分法
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=20;
#define eps 1e-6
int n;
double l,r,a[maxn];
inline double power(double a,int b){
double ans=1.0;
for(;b;b>>=1){
if(b&1)ans=ans*a;
a=a*a;
}
return ans;
}
inline double calc(double x){
double ans=0.0;
for(register int i=n;i>=0;--i){
ans+=power(x,i)*a[i];
}
return ans;
}
inline void solve(void){
while(r-l>=eps){
double K=(r-l)/3.0;
double lmid=l+K,rmid=r-K;
if(calc(lmid)<calc(rmid))l=lmid;
else r=rmid;
}
}
int main(){
n=read<int>();scanf("%lf%lf",&l,&r);
for(register int i=n;i>=0;--i){
scanf("%lf",a+i);
}
solve();
printf("%.5lf",l);
return 0;
}
ST表
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=1e5+5;
int n,m,a[maxn];
int f[maxn][25];
inline void init(void){
for(register int i=1;i<=n;++i)f[i][0]=a[i];
for(register int j=1;j<=20;++j){
for(register int i=1;i<=n-(1<<j)+1;++i){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
}
int main(){
n=read<int>();m=read<int>();
for(register int i=1;i<=n;++i){
a[i]=read<int>();
}
init();
while(m--){
int l=read<int>(),r=read<int>();
if(l>r)swap(l,r);
int k=log2(r-l+1);
printf("%d
",max(f[l][k],f[r-(1<<k)+1][k]));
}
return 0;
}
字符串哈希
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int base=131,maxn=10005;
int n;
unsigned long long a[maxn];
char str[1005];
inline unsigned long long Hash(void){
int len=strlen(str+1);unsigned long long ret=0;
for(register int i=1;i<=len;++i){
ret=ret*base+str[i]-'a'+1;
}
return ret;
}
int main(){
n=read<int>();
for(register int i=1;i<=n;++i){
scanf("%s",str+1);
a[i]=Hash();
}
sort(a+1,a+n+1);
printf("%d
",unique(a+1,a+n+1)-a-1);
return 0;
}
KMP字符串匹配
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=1000005;
char s1[maxn],s2[maxn];
int len1,len2,nxt[maxn],now,f[maxn];
int main(){
scanf("%s",s2+1);len2=strlen(s2+1);
scanf("%s",s1+1);len1=strlen(s1+1);//我习惯把小串称为s1串
now=0;
for(register int i=2;i<=len1;++i){
while(now&&s1[i]!=s1[now+1])now=nxt[now];
if(s1[i]==s1[now+1])++now;
nxt[i]=now;
}
now=0;
for(register int i=1;i<=len2;++i){
if(now&&(now==len1||s2[i]!=s1[now+1]))now=nxt[now];
if(s2[i]==s1[now+1])++now;
f[i]=now;
if(f[i]==len1)printf("%d
",i-len1+1);
}
for(register int i=1;i<=len1;++i)printf("%d ",nxt[i]);
puts("");
return 0;
}
manacher算法
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=11000005;
int n,hw[maxn<<1],ans;
char str[maxn],s[maxn<<1];
inline void change(void){
s[0]=s[1]='#';
for(register int i=0;i<n;++i){
s[i*2+2]=str[i];
s[i*2+3]='#';
}
n=n*2+2;
s[n]=0;
}
inline void manacher(void){
int maxright=0,mid=0;
for(register int i=1;i<n;++i){
if(i<maxright)
hw[i]=min(hw[mid*2-i],maxright-i);
else hw[i]=1;
while(s[i+hw[i]]==s[i-hw[i]])++hw[i];
if(hw[i]+i>maxright){
maxright=hw[i]+i;mid=i;
}
}
}
int main(){
scanf("%s",str);
n=strlen(str);
change();
manacher();
for(register int i=0;i<n;++i)ans=max(ans,hw[i]);
cout<<ans-1<<endl;
return 0;
}
Trie
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#define LL long long
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=1000005;
int trie[maxn][30],cnt[maxn*30],tot=1;
inline void Insert(char s[]){
int p=1,len=strlen(s);
for(register int i=0;i<len;++i){
if(!trie[p][s[i]-'a'+1])trie[p][s[i]-'a'+1]=++tot;
p=trie[p][s[i]-'a'+1];
cnt[p]++;
}
return;
}
inline int query(char s[]){
int p=1,len=strlen(s);
for(register int i=0;i<len;++i){
if(!trie[p][s[i]-'a'+1])return 0;
p=trie[p][s[i]-'a'+1];
}
return cnt[p];
}
int main(){
char ch[15];
while(gets(ch)){
if(ch[0]==NULL)break;
Insert(ch);
}
while(gets(ch)){
printf("%d
",query(ch));
}
return 0;
}
线性筛素数
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=10000005;
int n,m;
bool is_prime[maxn];
int priN,primes[maxn];
inline void find(void){
mem(is_prime,true);
is_prime[1]=false;
for(register int i=2;i<=n;++i){
if(is_prime[i])primes[++priN]=i;
for(register int j=1;j<=priN;++j){
if(i*primes[j]>n)break;
is_prime[i*primes[j]]=false;
if(i%primes[j]==0)break;
}
}
}
int main(){
n=read<int>();m=read<int>();
find();
while(m--){
int x=read<int>();
if(is_prime[x])puts("Yes");
else puts("No");
}
return 0;
}
裴蜀定理
//首先这道题让我明白了裴蜀定理可以扩展到多个数的情况
//for example：设d=gcd(a,b,c),则ax+by+cz=k有整数解当且仅当d|k
//那这道题就求个gcd就好了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=30;
int n,a[maxn],d;
inline int gcd(int a,int b){
if(!b)return a;
return gcd(b,a%b);
}
int main(){
n=read<int>();
for(register int i=1;i<=n;++i)a[i]=read<int>(),d=gcd(abs(a[i]),d);//要把负数变成正数！
cout<<d<<endl;
return 0;
}
扩展欧几里得算法
洛谷模板 （其实这不是一道裸的模板，但和模板差不了多少。）
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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 a,b;
inline int exgcd(int a,int b,int &x,int &y){
if(b==0){x=1;y=0;return a;}
int d=exgcd(b,a%b,x,y);
int z=x;x=y;y=z-y*(a/b);
return d;
}
int main(){
a=read<int>();b=read<int>();
int x=0,y=0;
exgcd(a,b,x,y);
cout<<(x%b+b)%b<<endl;
return 0;
}
扩展中国剩余定理（EXCRT）
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=1e5+5;
int n;
LL a[maxn],m[maxn],lcm,now,k,d,x,y;
inline LL exgcd(LL a,LL b,LL &x,LL &y){
if(b==0){x=1;y=0;return a;}
LL d=exgcd(b,a%b,x,y);
LL z=x;x=y;y=z-y*(a/b);
return d;
}
inline LL mult(LL a,LL b,LL p){//快速乘
LL ans=0;
for(;b;b>>=1){
if(b&1)ans=(ans+a)%p;
a=(a+a)%p;
}
return ans;
}
int main(){
n=read<int>();
for(register int i=1;i<=n;++i){
m[i]=read<LL>();
a[i]=read<LL>();
}
lcm=m[1];now=a[1];bool fail=0;
for(register int i=2;i<=n;++i){
a[i]=(a[i]-now%m[i]+m[i])%m[i];
d=exgcd(lcm,m[i],x,y);
if(a[i]%d==0)k=mult(x,a[i]/d,m[i]);
else {fail=1;break;}
now+=k*lcm;
lcm=lcm/d*m[i];
now=(now%lcm+lcm)%lcm;
}
if(fail)cout<<"-1"<<endl;
else cout<<now<<endl;
return 0;
}
矩阵快速幂
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=105,mod=1e9+7;
int n;
struct Matrix{
LL a[maxn][maxn];
Matrix(){mem(a,0);}
inline void init(void){
for(register int i=1;i<=n;++i)a[i][i]=1;
}
inline friend Matrix operator *(const Matrix &x,const Matrix &y){
Matrix z;
for(register int i=1;i<=n;++i){
for(register int j=1;j<=n;++j){
for(register int k=1;k<=n;++k){
(z.a[i][j]+=(x.a[i][k]*y.a[k][j])%mod)%=mod;
}
}
}
return z;
}
inline friend Matrix operator ^(Matrix x,LL b){
Matrix ans;ans.init();
for(;b;b>>=1){
if(b&1)ans=ans*x;
x=x*x;
}
return ans;
}
};
int main(){
n=read<int>();LL K=read<LL>();
Matrix cs;//初始矩阵
for(register int i=1;i<=n;++i){
for(register int j=1;j<=n;++j){
cs.a[i][j]=read<LL>()%mod;
}
}
cs=cs^K;
for(register int i=1;i<=n;++i){
for(register int j=1;j<=n;++j){
printf("%lld ",cs.a[i][j]);
}
puts("");
}
return 0;
}
矩阵优化/矩阵加速
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int mod=1000000007;
LL n;
struct Matrix{
LL a[3][3];
Matrix(){mem(a,0);}
inline void init(void){a[1][1]=a[2][2]=1;}
inline void init2(void){
a[1][1]=1;a[1][2]=1;
a[2][1]=1;a[2][2]=0;
}
inline friend Matrix operator*(Matrix x,Matrix y){
Matrix ans;
for(register int i=1;i<=2;++i){
for(register int j=1;j<=2;++j){
for(register int k=1;k<=2;++k){
(ans.a[i][j]+=(x.a[i][k]*y.a[k][j])%mod)%=mod;
}
}
}
return ans;
}
inline friend Matrix operator^(Matrix x,LL b){
Matrix ans;ans.init();
for(;b;b>>=1){
if(b&1)ans=ans*x;
x=x*x;
}
return ans;
}
};
inline void solve(void){
Matrix cs;cs.init2();
cs=cs^(n-2);
cout<<(cs.a[1][1]+cs.a[2][1])%mod<<endl;
}
int main(){
n=read<LL>();
if(n==1)cout<<1<<endl;
else if(n==2)cout<<1<<endl;
else solve();
return 0;
}
高斯消元法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=105;
int n;double a[maxn][maxn],x[maxn];
#define eps 1e-7
inline bool gause(void){
for(register int i=1;i<=n;++i){//枚举行
int k=i;
for(register int j=i+1;j<=n;++j){//枚举行
if(fabs(a[k][i])<fabs(a[j][i]))k=j;
}
if(fabs(a[k][i])<eps)return false;
for(register int j=i;j<=n+1;++j){//枚举列
swap(a[i][j],a[k][j]);
}
double Tmp=a[i][i];
for(register int j=i;j<=n+1;++j){//枚举列
a[i][j]/=Tmp;
}
for(register int j=1;j<=n;++j){//枚举行
if(j==i)continue;
double tmp=a[j][i];
for(register int k=i;k<=n+1;++k){//枚举列
a[j][k]-=a[i][k]*tmp;
}
}
}
for(register int i=1;i<=n;++i)x[i]=a[i][n+1];
return true;
}
int main(){
n=read<int>();
for(register int i=1;i<=n;++i){
for(register int j=1;j<=n+1;++j){
a[i][j]=read<int>();
}
}
if(!gause()){
puts("No Solution");return 0;
}
for(register int i=1;i<=n;++i)printf("%.2lf
",x[i]);
return 0;
}
树状数组 1（单点修改、区间查询）
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=500005;
#define lowbit(x) x&(-x)
int n,q,a[maxn];
int tree[maxn];
inline void add(int p,int val){
for(;p<=n;p+=lowbit(p)){
tree[p]+=val;
}
return;
}
inline int sum(int p){
int ret=0;
for(;p;p-=lowbit(p)){
ret+=tree[p];
}
return ret;
}
inline int query(int l,int r){
return sum(r)-sum(l-1);
}
int main(){
n=read<int>();q=read<int>();
for(register int i=1;i<=n;++i){
a[i]=read<int>();
add(i,a[i]);
}
while(q--){
int opt=read<int>();
if(opt==1){
int x=read<int>(),k=read<int>();
add(x,k);
}
else{
int l=read<int>(),r=read<int>();
cout<<query(l,r)<<endl;//李煜东：卡什么常啊，能不能有点追求！
}
}
return 0;
}
树状数组 2（区间修改，单点查询）
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=500005;
#define lowbit(x) x&(-x)
int n,q,a[maxn];
int tree[maxn];
inline void add(int p,int val){
for(;p<=n;p+=lowbit(p)){
tree[p]+=val;
}
return;
}
inline int sum(int p){
int ret=0;
for(;p;p-=lowbit(p)){
ret+=tree[p];
}
return ret;
}
int main(){
n=read<int>();q=read<int>();
for(register int i=1;i<=n;++i){
a[i]=read<int>();
}
for(register int i=1;i<=n;++i){
add(i,a[i]-a[i-1]);
}
while(q--){
int opt=read<int>();
if(opt==1){
int l=read<int>(),r=read<int>(),val=read<int>();
add(l,val);add(r+1,-val);
}
else{
int x=read<int>();
cout<<sum(x)<<endl;
}
}
return 0;
}
树状数组求逆序对
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=5e5+5;
int n,a[maxn],b[maxn];LL ans;
#define lowbit(x) x&(-x)
LL tree[maxn];
inline void add(int p,int val){
for(;p<=n;p+=lowbit(p)){
tree[p]+=val;
}
return;
}
inline LL sum(int p){
LL ret=0;
for(;p;p-=lowbit(p)){
ret+=tree[p];
}
return ret;
}
int main(){
n=read<int>();
for(register int i=1;i<=n;++i){
a[i]=read<int>();b[i]=a[i];
}
sort(b+1,b+n+1);
int len=unique(b+1,b+n+1)-b-1;
for(register int i=1;i<=n;++i){
a[i]=lower_bound(b+1,b+len+1,a[i])-b;
}
for(register int i=n;i>=1;--i){
ans+=sum(a[i]-1);
add(a[i],1);
}
cout<<ans<<endl;
return 0;
}
普通线段树
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=100005;
int n,q;
LL a[maxn];
#define lson (o<<1)
#define rson (o<<1|1)
LL sum[maxn<<2],add[maxn<<2],len[maxn<<2];
inline void pushup(int o){
sum[o]=sum[lson]+sum[rson];
}
inline void build(int o,int l,int r){
len[o]=r-l+1;
if(l==r){sum[o]=a[l];return;}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(o);
}
inline void Add(int o,int val){
add[o]+=val;
sum[o]+=len[o]*val;
}
inline void pushdown(int o){
if(!add[o])return;
Add(lson,add[o]);Add(rson,add[o]);
add[o]=0;
}
inline void Update(int o,int l,int r,int ql,int qr,LL v){
if(ql<=l&&r<=qr){Add(o,v);return;}
pushdown(o);
int mid=(l+r)>>1;
if(ql<=mid)Update(lson,l,mid,ql,qr,v);
if(qr>mid)Update(rson,mid+1,r,ql,qr,v);
pushup(o);
}
inline LL query(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return sum[o];
pushdown(o);
int mid=(l+r)>>1;LL ans=0;
if(ql<=mid)ans+=query(lson,l,mid,ql,qr);
if(qr>mid)ans+=query(rson,mid+1,r,ql,qr);
return ans;
}
int main(){
n=read<int>();q=read<int>();
for(register int i=1;i<=n;++i){
a[i]=read<LL>();
}
build(1,1,n);
while(q--){
int opt=read<int>();
if(opt==1){
int l=read<int>(),r=read<int>();LL val=read<LL>();
Update(1,1,n,l,r,val);
}
else{
int l=read<int>(),r=read<int>();
printf("%lld
",query(1,1,n,l,r));
}
}
return 0;
}
支持乘法和加法的线段树
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=100005;
int n,m;
LL p,a[maxn];
struct Segment_Tree{
#define lson (o<<1)
#define rson (o<<1|1)
LL addm[maxn<<2],addp[maxn<<2],sum[maxn<<2],len[maxn<<2];
inline void pushup(int o){
sum[o]=sum[lson]+sum[rson];
}
inline void build(int o,int l,int r){
len[o]=r-l+1;
sum[o]=addp[o]=0;
addm[o]=1;
if(l==r){sum[o]=a[l];return;}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
pushup(o);
}
inline void Plus(int o,LL val){
(addp[o]+=val)%=p;
(sum[o]+=len[o]*val)%=p;
}
inline void Mult(int o,LL val){
(sum[o]*=val)%=p;
(addm[o]*=val)%=p;
(addp[o]*=val)%=p;
return;
}
inline void pushdown(int o){
if(!addp[o]&&addm[o]==1)return;
Mult(lson,addm[o]);Mult(rson,addm[o]);
Plus(lson,addp[o]);Plus(rson,addp[o]);
addp[o]=0;addm[o]=1;
return;
}
inline void Update(int o,int l,int r,int ql,int qr,LL v,int k){
if(ql<=l&&r<=qr){
switch(k){
case 1:Mult(o,v);break;
case 2:Plus(o,v);break;
}
return;
}
pushdown(o);
int mid=(l+r)>>1;
if(ql<=mid)Update(lson,l,mid,ql,qr,v,k);
if(qr>mid)Update(rson,mid+1,r,ql,qr,v,k);
pushup(o);
}
inline LL query(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return sum[o];
pushdown(o);
int mid=(l+r)>>1;LL ans=0;
if(ql<=mid)(ans+=query(lson,l,mid,ql,qr))%=p;
if(qr>mid)(ans+=query(rson,mid+1,r,ql,qr))%=p;
return ans;
}
}T;
int main(){
n=read<int>();m=read<int>();p=read<LL>();
for(register int i=1;i<=n;++i)a[i]=read<LL>();
T.build(1,1,n);
while(m--){
int opt=read<int>(),l=read<int>(),r=read<int>();LL v=0;
switch(opt){
case 1:v=read<LL>();T.Update(1,1,n,l,r,v,1);break;
case 2:v=read<LL>();T.Update(1,1,n,l,r,v,2);break;
case 3:printf("%lld
",T.query(1,1,n,l,r));break;
}
}
return 0;
}
分块
//我发现一个可怕的事实：
//我的分块比线段树快！！！
//我现在正纠结于考场上写分块还是线段树……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=100005;
int n,m,t,R[maxn],L[maxn],bl[maxn];
LL a[maxn],sum[maxn],add[maxn];
inline void Update(int l,int r,LL val){
int p=bl[l],q=bl[r];
if(p==q){
for(register int i=l;i<=r;++i)a[i]+=val;
sum[p]+=val*(r-l+1);
}
else{
for(register int i=p+1;i<=q-1;++i)add[i]+=val;
for(register int i=l;i<=R[p];++i)a[i]+=val;
sum[p]+=val*(R[p]-l+1);
for(register int i=L[q];i<=r;++i)a[i]+=val;
sum[q]+=val*(r-L[q]+1);
}
}
inline LL query(int l,int r){
int p=bl[l],q=bl[r];LL ret=0;
if(p==q){
for(register int i=l;i<=r;++i)ret+=a[i];
ret+=add[p]*(r-l+1);
}
else{
for(register int i=p+1;i<=q-1;++i)
ret+=sum[i]+add[i]*(R[i]-L[i]+1);
for(register int i=l;i<=R[p];++i)ret+=a[i];
ret+=add[p]*(R[p]-l+1);
for(register int i=L[q];i<=r;++i)ret+=a[i];
ret+=add[q]*(r-L[q]+1);
}
return ret;
}
int main(){
n=read<int>();m=read<int>();
for(register int i=1;i<=n;++i)a[i]=read<LL>();
t=sqrt(n);
for(register int i=1;i<=t;++i){
L[i]=(i-1)*t+1;
R[i]=i*t;
}
if(R[t]<n)++t,L[t]=R[t-1]+1,R[t]=n;
for(register int i=1;i<=t;++i){
for(register int j=L[i];j<=R[i];++j){
bl[j]=i;
sum[i]+=a[j];
}
}
while(m--){
int opt=read<int>(),l=read<int>(),r=read<int>();
if(opt==1){
LL v=read<LL>();
Update(l,r,v);
}
else{
printf("%lld
",query(l,r));
}
}
return 0;
}
普通平衡树（01trie）
//我之所以选择这个不太著名的数据结构来当做普通平衡树的模板，是因为这玩意代码又短常数又小，我非常喜欢它！
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int base=1e7,maxn=100005;
int q;
int trie[35*maxn][2],tot=1,tag[32*maxn];
inline void insert(int val,int d){
int p=1;val+=base;
for(register int i=31;~i;--i){
int tmp=(val>>i)&1;
if(!trie[p][tmp])trie[p][tmp]=++tot;
p=trie[p][tmp];tag[p]+=d;
}
}
inline int rank(int val){
int p=1,ret=0;val+=base;
for(register int i=31;~i;--i){
int tmp=(val>>i)&1;
if(tmp)ret+=tag[trie[p][0]];
p=trie[p][tmp];
}
return ret+1;
}
inline int kth(int rank){
int ret=0,p=1;
for(register int i=31;~i;--i){
if(rank>tag[trie[p][0]])rank-=tag[trie[p][0]],ret|=(1<<i),p=trie[p][1];
else p=trie[p][0];
}
ret-=base;
return ret;
}
int main(){
q=read<int>();
while(q--){
int opt=read<int>(),x=read<int>();
switch(opt){
case 1:insert(x,1);break;
case 2:insert(x,-1);break;
case 3:printf("%d
",rank(x));break;
case 4:printf("%d
",kth(x));break;
case 5:printf("%d
",kth(rank(x)-1));break;
case 6:printf("%d
",kth(rank(x+1)));break;
}
}
return 0;
}
普通平衡树（Splay）
#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
#define mem(s, v) memset(s, v, sizeof s)
using namespace std;
inline LL read(void) {
LL x = 0, f = 1; char ch = getchar();
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;
}
const int maxn = 1100005, inf = 0x7fffffff;
int n, m;
struct Balance_Tree {
int son[maxn][2], cnt[maxn], siz[maxn], fa[maxn], key[maxn], root, sz;
inline void clear(int x) {
son[x][0] = son[x][1] = cnt[x] = siz[x] = fa[x] = key[x] = 0;
}
inline int get(int x) { return son[fa[x]][1] == x; }
inline void update(int x) {
if (!x) return;
siz[x] = cnt[x];
if (son[x][0]) siz[x] += siz[son[x][0]];
if (son[x][1]) siz[x] += siz[son[x][1]];
}
inline void rotate(int x) {
int y = fa[x], z = fa[y], k = get(x);
fa[y] = x; son[y][k] = son[x][k ^ 1]; fa[son[y][k]] = y;
son[x][k ^ 1] = y; fa[x] = z;
if (z) son[z][son[z][1] == y] = x;
update(y); update(x);
}
inline void splay(int x) {
for (int f; (f = fa[x]); rotate(x)) {
if (fa[f])
rotate((get(x) == get(f)) ? f : x);
}
root = x;
}
int find_closest(int x, int val) {
if (key[x] == val) return x;
if (val < key[x]) return (son[x][0] ? find_closest(son[x][0], val) : x);
if (val > key[x]) return (son[x][1] ? find_closest(son[x][1], val) : x);
}
inline void find(int val) {
splay(find_closest(root, val));
if (key[root] >= val) return;
int now = son[root][1];
while (son[now][0]) now = son[now][0];
splay(now);
}
inline int rank(int val) {
find(val);
return siz[son[root][0]] + 1;
}
inline int kth(int x, int k) {
if (siz[son[x][0]] >= k) return kth(son[x][0], k);
if (siz[son[x][0]] + cnt[x] >= k) return key[x];
return kth(son[x][1], k - siz[son[x][0]] - cnt[x]);
}
inline int pre(int val) {
int tmp = rank(val) - 1;
return kth(root, tmp);
}
inline int nxt(int val) {
int tmp = rank(val + 1);
return kth(root, tmp);
}
inline void insert(int val) {
if (!root) {
root = ++sz; son[root][0] = son[root][1] = fa[root] = 0;
siz[root] = cnt[root] = 1; key[root] = val; return;
}
find(val);
if (key[root] == val) { ++cnt[root]; ++siz[root]; return; }
key[++sz] = val; cnt[sz] = 1;
fa[son[root][0]] = sz;
son[sz][0] = son[root][0]; fa[sz] = root;
son[root][0] = sz;
update(sz); update(root);
}
inline void del(int val) {
find(val);
if (cnt[root] >= 2) { --cnt[root]; --siz[root]; return; }
int old = root;
if (!son[root][0]) { fa[son[root][1]] = 0; root = son[root][1]; clear(old); return; }
if (!son[root][1]) { fa[son[root][0]] = 0; root = son[root][0]; clear(old); return; }
find(pre(val));
old = son[root][1];
fa[son[old][1]] = root;
son[root][1] = son[old][1];
clear(old);
update(root);
}
}T;
int main() {
n = read(); m = read();
T.insert(inf);
for (register int i = 1; i <= n; ++i) {
T.insert(read());
}
int ans = 0, lst = 0, x, opt;
while (m--) {
opt = read(); x = read() ^ lst;
switch (opt) {
case 1: T.insert(x); break;
case 2: T.del(x); break;
case 3: lst = T.rank(x); ans ^= lst; break;
case 4: lst = T.kth(T.root, x); ans ^= lst; break;
case 5: lst = T.pre(x); ans ^= lst; break;
case 6: lst = T.nxt(x); ans ^= lst; break;
default: puts("Wish you a happy day!"); break;
}
}
printf("%d
", ans);
return 0;
}
单源最短路径
//不要用SPFA！
//不要用SPFA！
//不要用SPFA！
//重要的事情说三遍。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=100005,maxm=200005;
int n,m,st;
int head[maxn],tot,dis[maxn];
bool vis[maxn];
struct Edge{
int y,next,w;
Edge(){}
Edge(int _y,int _next,int _w):y(_y),next(_next),w(_w){}
}e[maxm];
inline void connect(int x,int y,int w){
e[++tot]=Edge(y,head[x],w);
head[x]=tot;
}
priority_queue<pair<int,int> >q;
inline void Dijkstra(void){
q.push(make_pair(0,st));
mem(dis,0x3f);dis[st]=0;
while(q.size()){
int x=q.top().second;q.pop();
if(vis[x])continue;
vis[x]=true;
for(register int i=head[x];i;i=e[i].next){
int y=e[i].y;
if(dis[y]>dis[x]+e[i].w){
dis[y]=dis[x]+e[i].w;
q.push(make_pair(-dis[y],y));
}
}
}
}
int main(){
n=read<int>();m=read<int>();st=read<int>();
for(register int i=1;i<=m;++i){
int x=read<int>(),y=read<int>(),w=read<int>();
connect(x,y,w);
}
Dijkstra();
for(register int i=1;i<=n;++i)printf("%d ",dis[i]);
return 0;
}
Kruskal
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxm=200005,maxn=5005;
int n,m;
int fa[maxn];
struct Group{
int x,y,w;
Group(){}
Group(int _x,int _y,int _w):x(_x),y(_y),w(_w){}
inline friend bool operator <(const Group &a,const Group &b){
return a.w<b.w;
}
}e[maxm];
inline int find(int x){
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
int main(){
n=read<int>();m=read<int>();
for(register int i=1;i<=n;++i)fa[i]=i;
for(register int i=1;i<=m;++i){
int x=read<int>(),y=read<int>(),w=read<int>();
e[i]=Group(x,y,w);
}
sort(e+1,e+m+1);
int ans=0,tot=0;
for(register int i=1;i<=m;++i){
int u=e[i].x,v=e[i].y;
u=find(u),v=find(v);
if(u==v)continue;
fa[u]=v;
++tot;
ans+=e[i].w;
if(tot==n-1)break;
}
printf("%d
",ans);
return 0;
}
Prim
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=5005;
int n,m,G[maxn][maxn],d[maxn],ans;
bool vis[maxn];
int main(){
n=read<int>();m=read<int>();
mem(G,0x3f);
for(register int i=1;i<=n;++i)G[i][i]=0;
for(register int i=1;i<=m;++i){
int x=read<int>(),y=read<int>(),w=read<int>();
G[y][x]=G[x][y]=min(G[x][y],w);
}
mem(d,0x3f);
d[1]=0;
for(register int i=1;i<n;++i){
int x=0;
for(register int j=1;j<=n;++j){
if(!vis[j]&&(x==0||d[j]<d[x]))x=j;
}
vis[x]=true;
for(register int y=1;y<=n;++y){
if(!vis[y])d[y]=min(d[y],G[x][y]);
}
}
for(register int i=2;i<=n;++i)ans+=d[i];
printf("%d
",ans);
return 0;
}
倍增LCA
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=500005;
int n,m,head[maxn],tot,fa[maxn][30],dep[maxn],st;
struct Edge{
int y,next;
Edge(){}
Edge(int _y,int _next):y(_y),next(_next){}
}e[maxn<<1];
inline void connect(int x,int y){
e[++tot]=Edge(y,head[x]);
head[x]=tot;
}
void dfs(int x,int father,int depth){
fa[x][0]=father;
for(register int j=1;j<=20;++j){
fa[x][j]=fa[fa[x][j-1]][j-1];
}
dep[x]=depth;
for(register int i=head[x];i;i=e[i].next){
int y=e[i].y;
if(y==father)continue;
dfs(y,x,depth+1);
}
}
inline int lca(int x,int y){
if(dep[x]<dep[y])x^=y^=x^=y;//swap(x,y)
for(register int i=20;i>=0;--i){
if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
}
if(x==y)return x;
for(register int i=20;i>=0;--i){
if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
int main(){
n=read<int>();m=read<int>();st=read<int>();
for(register int i=1;i<n;++i){
int x=read<int>(),y=read<int>();
connect(x,y);
connect(y,x);
}
dfs(st,0,1);
while(m--){
int x=read<int>(),y=read<int>();
printf("%d
",lca(x,y));
}
return 0;
}
SPFA判负环
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=2005,maxm=3005;
int T;
int head[maxn],tot,n,m,dis[maxn],cnt[maxn];
bool vis[maxn];
struct Edge{
int y,next,w;
Edge(){}
Edge(int _y,int _next,int _w):y(_y),next(_next),w(_w){}
}e[maxm<<1];
inline void connect(int x,int y,int w){
e[++tot]=Edge(y,head[x],w);
head[x]=tot;
}
inline void clear(void){
mem(head,0);mem(e,0);tot=0;
}
inline bool spfa(void){
queue<int>q;q.push(1);
mem(dis,0x3f);dis[1]=0;
mem(vis,0);vis[1]=true;
mem(cnt,0);cnt[1]=1;
while(q.size()){
int x=q.front();q.pop();vis[x]=false;
for(register int i=head[x];i;i=e[i].next){
int y=e[i].y;
if(dis[y]>dis[x]+e[i].w){
dis[y]=dis[x]+e[i].w;
cnt[y]=cnt[x]+1;
if(cnt[y]>n)return true;
if(!vis[y]){
q.push(y);vis[y]=true;
}
}
}
}
return false;
}
int main(){
T=read<int>();
while(T--){
clear();
n=read<int>();m=read<int>();
for(register int i=1;i<=m;++i){
int x=read<int>(),y=read<int>(),w=read<int>();
if(w<0)connect(x,y,w);
else connect(x,y,w),connect(y,x,w);
}
if(spfa())puts("YE5");
else puts("N0");
}
return 0;
}
缩点
//话说这能叫模板吗？QWQ
//一个常识：在有向无环图上的DP一般都要拓扑排序。
//包括期望DP。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=10005,maxm=100005;
int n,m,val[maxn];
int head[maxn],tot,head_new[maxn],tot_new;
int dfn[maxn],low[maxn],stack[maxn],top,bl[maxn],cnt,num,siz[maxn];
bool ins[maxn];
int in[maxn],dp[maxn],ans;
bool vis[maxn];
struct Edge{
int y,next;
Edge(){}
Edge(int _y,int _next):y(_y),next(_next){}
}e[maxm],e_new[maxm];
inline void connect(int x,int y){
e[++tot]=Edge(y,head[x]);
head[x]=tot;
}
inline void connect_new(int x,int y){
e_new[++tot_new]=Edge(y,head_new[x]);
head_new[x]=tot_new;
}
void Tarjan(int x){
low[x]=dfn[x]=++num;
stack[++top]=x;ins[x]=true;
for(register int i=head[x];i;i=e[i].next){
int y=e[i].y;
if(!dfn[y]){
Tarjan(y);
low[x]=min(low[x],low[y]);
}else if(ins[y]){
low[x]=min(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]){
int y;++cnt;
do{
y=stack[top--];ins[y]=false;
bl[y]=cnt;siz[cnt]+=val[y];
}while(x!=y);
}
}
inline void topsort(void){
queue<int>q;
for(register int i=1;i<=cnt;++i){
if(!in[i]){q.push(i);dp[i]=siz[i];ans=max(ans,dp[i]);}
}
while(q.size()){
int x=q.front();q.pop();
for(register int i=head_new[x];i;i=e_new[i].next){
int y=e_new[i].y;
--in[y];
if(!in[y]){
dp[y]=max(dp[y],dp[x]+siz[y]);
ans=max(ans,dp[y]);
q.push(y);
}
}
}
}
int main(){
n=read<int>();m=read<int>();
for(register int i=1;i<=n;++i)val[i]=read<int>();
for(register int i=1;i<=m;++i){
int x=read<int>(),y=read<int>();
connect(x,y);
}
for(register int i=1;i<=n;++i)if(!dfn[i])Tarjan(i);
for(register int x=1;x<=n;++x){
for(register int i=head[x];i;i=e[i].next){
int y=e[i].y;
if(bl[x]!=bl[y])connect_new(bl[x],bl[y]),++in[bl[y]];
}
}
topsort();
printf("%d
",ans);
return 0;
}
二分图匹配
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
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;
}
const int maxn=2005,maxm=1005*1005;
int n,m,E;
int head[maxn],tot,ans;
int match[maxn];
bool v[maxn];
struct Edge{
int y,next;
Edge(){}
Edge(int _y,int _next):y(_y),next(_next){}
}e[maxm<<1];
inline void connect(int x,int y){
e[++tot]=Edge(y,head[x]);
head[x]=tot;
}
bool dfs(int x){
for(register int i=head[x];i;i=e[i].next){
int y=e[i].y;
if(!v[y]){
v[y]=true;
if(!match[y]||dfs(match[y])){
match[y]=x;return true;
}
}
}
return false;
}
int main(){
n=read<int>();m=read<int>();E=read<int>();
for(register int i=1;i<=E;++i){
int x=read<int>(),y=read<int>()+n;
if(y-n>m)continue;//为了防毒瘤数据
connect(x,y);
}
for(register int i=1;i<=n;++i){
mem(v,0);
if(dfs(i))++ans;
}
cout<<ans<<endl;
return 0;
}