各种板子[自用] 线段树 线性求逆元 ST表 Splay Miller_Rabin Manacher 最大流 线性筛莫比乌斯函数 高斯消元法 Lucas 树链剖分 桥 KMP 二分图匹配 矩阵快速幂 割点 (nlogn)求最长不下降子序列 欧拉回路 主席树 可持久化数组 对顶堆
手动开O(2)
#pragma G++ optimize(2)
#include<bits/stdc++.h>
#define in(i) (i=read())
using namespace std;
typedef long long lol;
lol read()
{
lol ans=0,f=1;
char i=getchar();
while(i<'0'||i>'9')
{
if(i=='-') f=-1;
i=getchar();
}
while(i>='0'&&i<='9')
{
ans=(ans<<3)+(ans<<1)+i-'0';
i=getchar();
}
return ans*f;
}
lol a[100010];
lol sum[400010],lazy[400010];
void build(lol node,lol l,lol r)
{
if(l==r)
{
sum[node]=a[l];
return;
}
lol mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
sum[node]=sum[node<<1]+sum[node<<1|1];
}
void pushdown(lol node,lol l,lol r)
{
lol mid=l+r>>1;
lazy[node<<1]+=lazy[node];
lazy[node<<1|1]+=lazy[node];
sum[node<<1]+=(mid-l+1)*lazy[node];
sum[node<<1|1]+=(r-mid)*lazy[node];
lazy[node]=0;
}
void update(lol node,lol l,lol r,lol left,lol right,lol k)
{
if(l>right||r<left) return;
if(left<=l&&r<=right)
{
lazy[node]+=k;
sum[node]+=(r-l+1)*k;
return;
}
lol mid=l+r>>1;
if(lazy[node]) pushdown(node,l,r);
if(left<=mid) update(node<<1,l,mid,left,right,k);
if(mid<right) update(node<<1|1,mid+1,r,left,right,k);
sum[node]=sum[node<<1]+sum[node<<1|1];
}
lol check(lol node,lol l,lol r,lol left,lol right)
{
if(l>right||r<left) return 0;
if(left<=l&&r<=right) return sum[node];
int mid=l+r>>1;
if(lazy[node]) pushdown(node,l,r);
lol a=check(node<<1,l,mid,left,right);
lol b=check(node<<1|1,mid+1,r,left,right);
return a+b;
}
int main()
{
//freopen("data.in","r",stdin);
// freopen("zuoti.out","w",stdout);
lol n,m;
lol flag,x,y,z;
in(n);in(m);
for(int i=1;i<=n;i++)
in(a[i]);
build(1,1,n);
for(int i=1;i<=m;i++)
{
in(flag);
if(flag==1)
{
in(x);in(y);in(z);
update(1,1,n,x,y,z);
}
else if(flag==2)
{
in(x);in(y);
printf("%lld
",check(1,1,n,x,y));
}
}
}
线性求逆元
#include<bits/stdc++.h>
#define lol long long
#define in(i) (i=read())
using namespace std;
lol read() {
lol ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
return ans*f;
}
const lol N=3e6+10;
lol n,p,inv[N]={1,1};
int main() {
in(n),in(p);puts("1");
for (lol i=2;i<=n;i++) {
inv[i]=(p-p/i)*inv[p%i]%p;
printf("%lld
",inv[i]);
}
}
ST表
#include<bits/stdc++.h>
#define in(i) (i=read())
#define inf 2147483647
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
int read() {
int ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=ans*10+i-'0',i=getchar();
return ans*f;
}
const int N=5e5+10;
int n,lm,rm,mid,num;
int a[N],v[N],lg[N]={-1},minn[N][20],gcd[N][20];
int GCD(int a,int b) {
return b==0?a:GCD(b,a%b);
}
void init() {
for (int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
for (int j=1;j<=lg[n];j++) {
for (int i=1;i<=n-(1<<j)+1;i++) {
minn[i][j]=Min(minn[i][j-1],minn[i+(1<<j-1)][j-1]);
gcd[i][j]=GCD(gcd[i][j-1],gcd[i+(1<<j-1)][j-1]);
}
}
}
int query(int l,int r) {
int k=lg[r-l+1];
return Min(minn[l][k],minn[r-(1<<k)+1][k]);
}
int ask(int l,int r) {
int k=lg[r-l+1];
return GCD(gcd[l][k],gcd[r-(1<<k)+1][k]);
}
bool check(int x) {
for (int l=1,r=l+x,mx=inf;r<=n;l++,r++) {
int a=query(l,r),b=ask(l,r);
if(a==b) return 1;
}return 0;
}
int main()
{
freopen("pair.in","r",stdin);
freopen("pair.out","w",stdout);
in(n); for (int i=1;i<=n;i++)
in(a[i]), minn[i][0]=a[i], gcd[i][0]=a[i];
init();
int lm=0,rm=n;
while(lm<rm) {
mid=lm+rm+1>>1;
if(check(mid)) lm=mid;
else rm=mid-1;
}
for (int l=1,r=1+lm,mx=inf;r<=n;l++,r++) {
int a=query(l,r),b=ask(l,r);
if(a==b) v[++num]=l;
}
cout<<num<<" "<<lm<<endl;
for (int i=1;i<=num;i++) printf("%d ",v[i]);cout<<endl;
}
Splay
#include<bits/stdc++.h>
#define il inline
#define rg register
#define lol long long
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
using namespace std;
const int N=1e5+10;
const int inf=2e9;
void in(int &ans)
{
ans=0; int f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0', i=getchar();
ans*=f;
}
int n,root,tot;
struct Splay {
int f,size,ch[2],val,cnt;
}t[N];
il bool get(int x) {
return t[t[x].f].ch[1]==x;
}
il void up(int x) {
t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt;
}
void rotate(int x) {
int f=t[x].f,gf=t[f].f;
int k1=get(x),k2=get(f);
t[f].ch[k1]=t[x].ch[k1^1], t[t[x].ch[k1^1]].f=f;
t[gf].ch[k2]=x, t[x].f=gf;
t[f].f=x, t[x].ch[k1^1]=f;
up(f); up(x);
}
void splay(int x,int goal) {
while(t[x].f!=goal) {
int f=t[x].f,gf=t[f].f;
if(gf!=goal)
(get(x)^get(f))?rotate(x):rotate(f);
rotate(x);
}
if(!goal) root=x;
}
void insert(int v) {
int u=root,f=0;
while(u && t[u].val!=v) {
f=u;
u=t[u].ch[v>t[u].val];
}
if(u) t[u].cnt++;
else {
u=++tot;
if(f) t[f].ch[v>t[f].val]=u;
t[u].cnt=t[u].size=1;
t[u].ch[0]=t[u].ch[1]=0;
t[u].val=v,t[u].f=f;
}
splay(u,0);
}
void find(int x) {
int u=root; if(!u) return;
while(t[u].ch[x>t[u].val] && x!=t[u].val)
u=t[u].ch[x>t[u].val];
splay(u,0);
}
int kth(int k) {
int u=root; if(t[u].size<k) return 0;
while(1) {
int y=t[u].ch[0];
if(k>t[y].size+t[u].cnt) {
k-=t[y].size+t[u].cnt;
u=t[u].ch[1];
}
else if(k<=t[y].size) u=y;
else return t[u].val;
}
}
int Rank(int x) {
find(x); int u=root;
return t[t[u].ch[0]].size;
}
int Get(int x,int f) {
find(x); int u=root;
if(t[u].val>x && f) return u;
if(t[u].val<x && !f) return u;
u=t[u].ch[f];
while(t[u].ch[f^1]) u=t[u].ch[f^1];
return u;
}
void Del(int x) {
int last=Get(x,0),nex=Get(x,1);
splay(last,0); splay(nex,last);
int u=t[nex].ch[0];
if(t[u].cnt>1) {
t[u].cnt--;
splay(u,0);
}
else t[nex].ch[0]=0;
}
int main()
{
in(n); insert(inf); insert(-inf);
for(rg int i=1;i<=n;i++) {
int op,x;
in(op),in(x);
if(op==1) insert(x);
if(op==2) Del(x);
if(op==3) printf("%d
",Rank(x));
if(op==4) printf("%d
",kth(x+1));
if(op==5) printf("%d
",t[Get(x,0)].val);
if(op==6) printf("%d
",t[Get(x,1)].val);
}
return 0;
}
Miller_Rabin
#include<bits/stdc++.h>
#define lol long long
#define il inline
#define rg register
#define Max(a,b) (a)>(b)?(a):(b)
#define Min(a,b) (a)<(b)?(a):(b)
using namespace std;
const lol table[]={2,3,7,61,24251};
lol x,n,m;
il void in(int &ans) {
ans=0; int f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0', i=getchar();
ans*=f;
}
il lol mul(lol x,lol y,lol mod) {//快速乘
x%=mod,y%=mod;
return ((x*y-(lol)(((long double)x*y+0.5)/mod)*mod)%mod+mod)%mod;
}
il lol qpow(lol a,lol x,lol p) {
lol ans=1;
while(x) {
if(x&1) ans=mul(ans,a,p);
x>>=1;
a=mul(a,a,p);
}
return ans;
}
il bool miller_rabin(lol x) {
if(x==2) return 1;
if(x%2==0||x==46856248255981) return 0;
lol t=x-1; int g=0;
while(t&1^1) t>>=1,++g;
for(int i=0;i<=4;i++) {
if(table[i]==x) return 1;
lol a,b; a=b=qpow(table[i],t,x);
for(int j=0;j<g;j++) {
b=mul(a,a,x);
if(b==1 && a!=1 && a!=x-1) return 0;
a=b;
}
if(b!=1) return 0;
}return 1;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
while(m--) {
cin>>x;
if(x!=1 && miller_rabin(x)) puts("Yes");
else puts("No");
}
return 0;
}
Manacher
#include<bits/stdc++.h>
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
#define in(i) (i=read())
using namespace std;
int read() {
int ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') {ans=(ans<<1)+(ans<<3)+i-'0'; i=getchar();}
return ans*f;
}
int n;
char s[12000010],s_new[24000010];
int p[24000010];
int init() {
int len=strlen(s),j=2;
s_new[0]='$'; s_new[1]='#';
for(int i=0;i<len;i++) {
s_new[j++]=s[i];
s_new[j++]='#';
}
s_new[j]=' ';
return j;
}
int Manacher() {
int len=init();int max_len=-1,id,mx=0;
for(int i=1;i<len;i++) {
if(i<mx) p[i]=Min(p[2*id-i],mx-i);
else p[i]=1;
while(s_new[i-p[i]]==s_new[i+p[i]]) p[i]++;
if(mx<i+p[i])
id=i,mx=i+p[i];
max_len=Max(max_len,p[i]-1);
}
return max_len;
}
int main()
{
scanf("%s",s);
printf("%d
",Manacher());
return 0;
}
最大流
#include<bits/stdc++.h>
#define il inline
#define rg register
#define lol long long
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
using namespace std;
const int N=1e5+10,M=1e6+10;
const int inf=2e9;
void in(int &ans) {
ans=0; int f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0', i=getchar();
ans*=f;
}
int n,m,s,t,ans,cur=1;
int to[M<<1],nex[M<<1],head[N],cap[M<<1],lev[N];
il void add(int a,int b,int c) {
to[++cur]=b,nex[cur]=head[a];
cap[cur]=c,head[a]=cur;
}
bool bfs(int s,int t) {
queue<int>q; memset(lev,-1,sizeof(lev));
q.push(s); lev[s]=0;
while(!q.empty()) {
int u=q.front(); q.pop();
for(int i=head[u];i;i=nex[i]) {
if(lev[to[i]]==-1 && cap[i]) {
lev[to[i]]=lev[u]+1;
q.push(to[i]);
}
}
}return lev[t]!=-1;
}
int dfs(int s,int f,int t,int rest=0)
{
if(s==t) return f;
for(int i=head[s];i;i=nex[i]) {
if(lev[to[i]]==lev[s]+1 && cap[i]>0) {
int r=dfs(to[i],Min(cap[i],f-rest),t);
if(r>0) cap[i]-=r,cap[i^1]+=r,rest+=r;
}
}
if(!rest) lev[s]=-1;
return rest;
}
int main()
{
int a,b,c;
in(n);in(m);in(s);in(t);
for(int i=1;i<=m;i++) {
in(a);in(b);in(c);
add(a,b,c),add(b,a,0);
}
while(bfs(s,t))
while(int c=dfs(s,inf,t)) ans+=c;
cout<<ans<<endl;
return 0;
}
线性筛莫比乌斯函数
void get_mu(int n)
{
mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i]){prim[++cnt]=i;mu[i]=-1;}
for(int j=1;j<=cnt&&prim[j]*i<=n;j++)
{
vis[prim[j]*i]=1;
if(i%prim[j]==0)break;
else mu[i*prim[j]]=-mu[i];
}
}
}
高斯消元法
#include<bits/stdc++.h>
#define il inline
#define rg register
using namespace std;
const int N=110;
const double eps=1e-9;
void in(int &ans) {
ans=0; int f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
ans*=f;
}
int n;
double tq[N],a[N][N];
void Gauss(int x) {
if(x==n+1) return;
if(fabs(a[x][x])<eps) {
for(int i=x+1;i<=n;i++)
if(fabs(a[i][x])>eps) {
for(int j=x;j<=n+1;j++)swap(a[x][j],a[i][j]);
break;
}
}
if(fabs(a[x][x])>eps) {
for(int i=x+1;i<=n;i++) {
double p=a[i][x]/a[x][x];
for(int j=x;j<=n+1;j++)
a[i][j]-=a[x][j]*p;
}
}Gauss(x+1);
double ans=a[x][n+1];
for(int i=x+1;i<=n;i++) ans-=1.0*a[x][i]*tq[i];
if(fabs(a[x][x])<eps && fabs(a[x][x+1]<eps)) puts("Infinite Answers"),exit(0);
else if(fabs(a[x][x])<eps && fabs(a[x][x+1]>eps)) puts("No Solution"),exit(0);
tq[x]=ans*1.0/a[x][x];
}
int main()
{
freopen("data.in","r",stdin);
in(n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n+1;j++)
scanf("%lf",&a[i][j]);
Gauss(1);
for(int i=1;i<=n;i++) printf("%.2lf
",tq[i]);
return 0;
}
Lucas
#include<bits/stdc++.h>
#define lol long long
using namespace std;
const lol N=1e5+10;
lol n,m,mod,T;
lol sum[N]={1},inv[N]={1};
void in(lol &ans) {
ans=0; lol f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<3)+(ans<<1)+(i^48),i=getchar();
ans*=f;
}
lol qpow(lol a,lol x,lol ans=1) {
while(x) {
if(x&1) ans=ans*a%mod;
x>>=1,a=a*a%mod;
}return ans;
}
void init() {
for(lol i=1;i<=mod;i++) sum[i]=sum[i-1]*i%mod;
for(lol i=1;i<=mod;i++) inv[i]=qpow(sum[i],mod-2);
}
lol C(lol m,lol n) {
if(m>n) return 0;
return sum[n]*inv[m]%mod*inv[n-m]%mod;
}
lol lucas(lol m,lol n) {
if(!m) return 1;
return C(m%mod,n%mod)%mod*lucas(m/mod,n/mod)%mod;
}
void print(lol x) {
if(x>9) print(x/10);
putchar(x%10+'0');
}
int main()
{
in(T);
while(T--) {
in(n),in(m),in(mod); init();
print(lucas(m,n+m)),putchar('
');
}
}
树链剖分
#include<bits/stdc++.h>
#define rg register
#define il inline
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
#define lol long long
#define mid (l+r>>1)
#define ll(x) (x<<1)
#define rr(x) (x<<1|1)
#define in(i) (i=read())
using namespace std;
const int N=1e5+10;
int read() {
int ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
return ans*=f;
}
int cur,n,m,dfscnt;
int head[N],nex[N<<1],to[N<<1];
int fa[N],dep[N],dfn[N],size[N],top[N],son[N];
int lazy[N<<2],sum[N<<2];
void add(int a,int b) {
to[++cur]=b,nex[cur]=head[a],head[a]=cur;
to[++cur]=a,nex[cur]=head[b],head[b]=cur;
}
void dfs(int u) {
int maxn=0; size[u]=1;
for(int i=head[u];i;i=nex[i]) {
if(to[i]==fa[u]) continue;
dep[to[i]]=dep[u]+1,fa[to[i]]=u;
dfs(to[i]); size[u]+=size[to[i]];
if(size[to[i]]>maxn) maxn=size[to[i]],son[u]=to[i];
}
}
void dfs2(int u,int AQ) {
dfn[u]=++dfscnt; top[u]=AQ;
if(son[u]) dfs2(son[u],AQ);
for(int i=head[u];i;i=nex[i]) {
if(to[i]==fa[u] || to[i]==son[u]) continue;
dfs2(to[i],to[i]);
}
}
void up(int x) {
sum[x]=sum[ll(x)]+sum[rr(x)];
}
void pushdown(int x,int l,int r) {
lazy[ll(x)]+=lazy[x];
lazy[rr(x)]+=lazy[x];
sum[ll(x)]+=lazy[x]*(mid-l+1);
sum[rr(x)]+=lazy[x]*(r-mid);
lazy[x]=0;
}
void change(int x,int l,int r,int left,int right) {
if(l>right || r<left) return;
if(l>=left && r<=right) {
lazy[x]+=1; sum[x]+=(r-l+1);
return;
}
if(lazy[x]) pushdown(x,l,r);
if(left<=mid) change(ll(x),l,mid,left,right);
if(mid<right) change(rr(x),mid+1,r,left,right);
up(x);
}
int check(int x,int l,int r,int left,int right,int ans=0) {
if(l>right || r<left) return 0;
if(l>=left && r<=right) return sum[x];
if(lazy[x]) pushdown(x,l,r);
if(left<=mid) ans+=check(ll(x),l,mid,left,right);
if(mid<right) ans+=check(rr(x),mid+1,r,left,right);
return ans;
}
int find(int x,int y,int op,int ans=0) {
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
if(op==1) change(1,1,n,dfn[fx],dfn[x]);
else ans+=check(1,1,n,dfn[fx],dfn[x]);
x=fa[fx],fx=top[x];
}
if(dfn[x]>dfn[y]) swap(x,y);
if(op==1) {change(1,1,n,dfn[x],dfn[y]); return 0;}
else return ans+check(1,1,n,dfn[x],dfn[y]);
}
int main()
{
freopen("inter.in","r",stdin);
freopen("inter.out","w",stdout);
in(n); int c=0;
for(int i=1,a,b;i<n;i++)
in(a),in(b),add(a,b);
dfs(1); dfs2(1,1); in(m);
while(m--) {
int a,b,c,d,ans;
in(a),in(b),in(c),in(d);
find(a,b,1); ans=find(c,d,2);
puts(ans>0?"YES":"NO");
memset(sum,0,sizeof(sum));
}
return 0;
}
桥
#include<bits/stdc++.h>
#define rg register
#define il inline
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
#define lol long long
#define in(i) (i=read())
using namespace std;
const lol N=1e4+10,M=1e5+10;
lol read() {
lol ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
return ans*=f;
}
int n,m,cur,dfscnt,num;
int head[N],nex[M<<1],to[M<<1];
int dfn[N],low[N];
void add(int a,int b) {
to[++cur]=b,nex[cur]=head[a],head[a]=cur;
to[++cur]=a,nex[cur]=head[b],head[b]=cur;
}
void tarjan(int u,int edge) {
dfn[u]=low[u]=++dfscnt;
for(int i=head[u];i;i=nex[i]) {
if(!dfn[to[i]]) {
tarjan(to[i],i),low[u]=Min(low[u],low[to[i]]);
if(dfn[u]<low[to[i]]) num++;
}
else if(i!=(edge^1)) low[u]=Min(low[u],dfn[to[i]]);
}
}
int main()
{
while(scanf("%d%d",&n,&m)==2) {
memset(head,0,sizeof(head)),cur=1,num=0;
memset(dfn,0,sizeof(dfn)),dfscnt=0;
for(int i=1,a,b;i<=m;i++)
in(a),in(b),add(a,b);
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i,0);
printf("%d
",num);
}
}
KMP
#include<bits/stdc++.h>
#define rg register
#define il inline
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
#define lol long long
#define in(i) (i=read())
using namespace std;
const int N=1e5+10;
lol read() {
lol ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
return ans*=f;
}
int m,nex[N];
char s1[N],s2[N];
void init(char *s,int p=0) {
m=strlen(s);
for(int i=1;i<m;i++) {
while(p && (s[i]!=s[p])) p=nex[p];
if(s[i]==s[p]) nex[i+1]=++p;
else nex[i+1]=0;
}
}
int kmp(char *s) {
int l=strlen(s),p=0;
for(int i=0;i<l;i++) {
while(p && s[i]!=s2[p]) p=nex[p];
p+=(s[i]==s2[p]);
if(p==m) return 1;
}return 0;
}
int main()
{
while(scanf("%s%s",s1,s2)==2) {
init(s2);
puts(kmp(s1)?"YES":"NO");
}
}
二分图匹配
#include<bits/stdc++.h>
#define rg register
#define il inline
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
#define lol long long
#define in(i) (i=read())
using namespace std;
const int N=1e3+10,M=1e4+10;
int read() {
int ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
return ans*=f;
}
int n,m,cur,cnt;
int head[N],to[M<<1],nex[M<<1],w[M<<1];
int line[N][N],girl[N];
bool vis[N];
void add(int a,int b) {
to[++cur]=b,nex[cur]=head[a],head[a]=cur;
}
int find(int x) {
for(int i=head[x];i;i=nex[i]) {
if(vis[i]) continue; vis[i]=1;
if((!girl[i]) || find(girl[i])) {
girl[i]=x; return 1;
}
}
return 0;
}
int main()
{
while(scanf("%d%d",&n,&m)==2) {
memset(head,0,sizeof(head)),cur=0;
int ans=0;
for(rg int i=1,a,b;i<=m;i++)
in(a),in(b),add(a,b);
for(rg int i=1;i<=n;i++) {
memset(vis,0,sizeof(vis));
if(find(i)) ans++;
}printf("%d
",ans);
}
}
矩阵快速幂
#include<bits/stdc++.h>
#define rg register
#define il inline
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
#define lol long long
#define in(i) (i=read())
using namespace std;
const lol N=1e3+10,M=1e4+10,mod=1e4;
lol read() {
lol ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
return ans*=f;
}
lol n,f[10],b[10];
lol a[10][10],c[10][10];
void matrix_ans() {
memcpy(b,f,sizeof(f));
memset(f,0,sizeof(f));
for(lol i=1;i<=2;i++) {
for(lol j=1;j<=2;j++)
f[i]=(f[i]+b[j]*a[j][i]%mod)%mod;
}
}
void matrix_n() {
memcpy(c,a,sizeof(c));
memset(a,0,sizeof(a));
for(lol i=1;i<=2;i++)
for(lol j=1;j<=2;j++)
for(lol k=1;k<=2;k++)
a[i][j]=(a[i][j]+c[i][k]*c[k][j]%mod)%mod;
}
int main()
{
while(scanf("%lld",&n)==1) {
memset(f,0,sizeof(f));
a[1][1]=0,a[1][2]=a[2][1]=a[2][2]=1;
if(n==-1) break;
if(n==0) {puts("0");continue;}
f[1]=f[2]=1;n--;
while(n) {
if(n&1) matrix_ans();
n>>=1,matrix_n();
}printf("%lld
",f[1]);
}
}
割点
#include<bits/stdc++.h>
#define rg register
#define il inline
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
#define lol long long
#define in(i) (i=read())
using namespace std;
const lol N=2e4+10,M=1e5+10;
lol read() {
lol ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
return ans*=f;
}
int n,m,cur,dfscnt,num,root;
int head[N],nex[M<<1],to[M<<1];
int dfn[N],low[N],cut[N];
void add(int a,int b) {
to[++cur]=b,nex[cur]=head[a],head[a]=cur;
to[++cur]=a,nex[cur]=head[b],head[b]=cur;
}
void tarjan(int u) {
dfn[u]=low[u]=++dfscnt; int cnt=0;
for(int i=head[u];i;i=nex[i]) {
if(!dfn[to[i]]) {
tarjan(to[i]),low[u]=Min(low[u],low[to[i]]);
if(dfn[u]<=low[to[i]]) {
cnt++;
if(u!=root || cnt>1) cut[u]=1;
}
}
else low[u]=Min(low[u],dfn[to[i]]);
}
}
int main()
{
in(n),in(m);
for(int i=1,a,b;i<=m;i++)
in(a),in(b),add(a,b);
for(int i=1;i<=n;i++)
if(!dfn[i]) root=i,tarjan(i);
for(int i=1;i<=n;i++)
if(cut[i]) num++;
printf("%d
",num);
for(int i=1;i<=n;i++)
if(cut[i]) printf("%d ",i);cout<<endl;
}
(nlogn)求最长不下降子序列
#include<bits/stdc++.h>
#define rg register
#define il inline
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define lol long long
#define in(i) (i=read())
using namespace std;
const int N=1e5+10;
int read() {
int ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
return ans*=f;
}
int n,len,a[N],b[N],dp[N],pos[N];
int main()
{
in(n); for(int i=1;i<=n;i++) in(a[i]),pos[a[i]]=i; for(int i=1;i<=n;i++) in(b[i]);
for(int i=1;i<=n;i++) {
if(pos[b[i]]>dp[len])
dp[++len]=pos[b[i]];
else {
int k=upper_bound(dp+1,dp+1+len,pos[b[i]])-dp;//最长上升就是lower_bound
dp[k]=pos[b[i]];
}
}printf("%d
",len);
}
欧拉回路
#include<bits/stdc++.h>
#define rg register
#define il inline
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
#define lol long long
#define in(i) (i=read())
#define it multiset<int>::iterator
using namespace std;
const int N=510;
int read() {
int ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
return ans*=f;
}
int n,m,s=1,t,cnt;
multiset<int>e[N];
stack<int>AQ;
int dg[N];
void dfs(int u) {
for(it i=e[u].begin();i!=e[u].end();i=e[u].begin()) {
int to=*i;
e[u].erase(i);
e[to].erase(e[to].find(u));
dfs(to);
}AQ.push(u);
}
int main()
{
in(n);
for(int i=1,a,b;i<=n;i++) {
in(a),in(b); dg[a]++,dg[b]++;
e[a].insert(b),e[b].insert(a);
}
for(int i=1;i<=500;i++)
if(dg[i]&1) {s=i; break;}
dfs(s);
while(!AQ.empty()) {
int u=AQ.top(); AQ.pop();
printf("%d
",u);
}
}
主席树
#include<bits/stdc++.h>
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define rg register
#define mid ((l+r)>>1)
#define in(i) (i=read())
using namespace std;
const int N=2e5+10,inf=2e9;
int read() {
int ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
return ans*=f;
}
int n,m,tot;
int a[N],b[N];
int rt[N<<5],lc[N<<5],rc[N<<5],sum[N<<5];
void update(int &u,int l,int r,int pre,int x) {
u=++tot;
sum[u]=sum[pre]+1,lc[u]=lc[pre],rc[u]=rc[pre];
if (l==r) return;
if(x<=mid) update(lc[u],l,mid,lc[pre],x);
else update(rc[u],mid+1,r,rc[pre],x);
}
int query(int u,int v,int l,int r,int k) {
if(l==r) return l;
int rest=sum[lc[v]]-sum[lc[u]];
if(k<=rest) return query(lc[u],lc[v],l,mid,k);
else return query(rc[u],rc[v],mid+1,r,k-rest);
}
int main()
{
in(n), in(m);
for (int i=1;i<=n;i++) in(a[i]), b[i]=a[i];
sort(b+1,b+1+n); int h=unique(b+1,b+1+n)-b-1;
for (int i=1;i<=n;i++) update(rt[i],1,h,rt[i-1],lower_bound(b+1,b+1+h,a[i])-b);
for (int i=1,l,r,k;i<=m;i++) {
in(l), in(r), in(k);
int ans=query(rt[l-1],rt[r],1,h,k);
printf("%d
",b[ans]);
}
}
可持久化数组
#include<bits/stdc++.h>
#define in(i) (i=read())
#define il extern inline
#define rg register
#define mid ((l+r)>>1)
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define lol long long
using namespace std;
const lol N=1e6+10;
lol read() {
lol ans=0, f=1; char i=getchar();
while (i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while (i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+(i^48), i=getchar();
return ans*f;
}
int n,m,tot;
int a[N],rt[N<<6];
struct President_Tree {
int l,r,v;
}t[N<<6];
void build(int &u,int l,int r) {
u=++tot;
if(l==r) {t[u].v=a[l]; return;}
build(t[u].l,l,mid);
build(t[u].r,mid+1,r);
}
void insert(int &u,int l,int r,int pre,int p,int v) {
t[u=++tot]=t[pre];
if(l==r) {t[u].v=v; return;}
if(p<=mid) insert(t[u].l,l,mid,t[pre].l,p,v);
else insert(t[u].r,mid+1,r,t[pre].r,p,v);
}
int query(int u,int l,int r,int x) {
if(l==r) return t[u].v;
if(x<=mid) return query(t[u].l,l,mid,x);
else return query(t[u].r,mid+1,r,x);
}
int main()
{
in(n), in(m);
for (int i=1;i<=n;i++) in(a[i]);
build(rt[0],1,n);
for (int i=1,v,op,loc,x;i<=m;i++) {
in(v), in(op), in(loc);
if(op==1) in(x),insert(rt[i],1,n,rt[v],loc,x);
else printf("%d
",query(rt[i]=rt[v],1,n,loc));
}
}
对顶堆
(!q.size()||x>q.top())?p.push(x):q.push(x);
while (q.size()>p.size()+1) p.push(q.top()),q.pop();
while (p.size()>q.size()+1) q.push(p.top()),p.pop();
printf("%d
",(q.size()>=p.size())?q.top():p.top());