模板库
Math_rad_round · · 个人记录
目录
点击即可跳转到对应部分
最大流 费用流 快读快写 多项式/二次剩余
平衡树（替罪羊结构体版）
最短路dij 最短路spfa（带负环）
RMQ 2-SAT LCT+并查集
数论 对拍库 矩阵（乘法/方程/行列式）
网络最大流
#include<iostream>
#include<cstdio>
using namespace std;
#define For(u,i,v) for(int i=head[u],v=tu[i].v;i;i=tu[i].ne,v=tu[i].v)
typedef long long liu;
struct bian{
liu f;int ne,v;
};
const int N=100000,M=1000000;
bian tu[M];int we=1;
int head[N];
int des[N],gap[N];
int qi,zo;liu ans;
void out(){
for(int o=1;o<=9;o++){cout<<o<<" : ";
For(o,i,v){cout<<v<<","<<tu[i].f<<" ";}cout<<endl;}}
void clear(int le){ans=0;
for(int i=1;i<=le;i++){des[i]=gap[i]=0;}
}
void cclear(int le){
for(int i=1;i<=we;i++){tu[i].v=tu[i].f=tu[i].ne=0;}
we=1;for(int i=1;i<=le;i++)head[i]=0;
}
int bfs(){static int l[N];
int h=0,w=0;l[w++]=zo;
while(w>h){
int u=l[h];h++;
For(u,i,v){
if(tu[i^1].f==0)continue;
if(des[v]||v==zo)continue;
gap[des[v]=des[u]+1]++;l[w++]=v;
}
}return des[qi]!=0;
}
liu dfs(int w,liu f){
if(w==zo){ans+=f;return f;}int uo=f;
For(w,i,v){
if(tu[i].f==0)continue;
if(des[v]!=des[w]-1)continue;
int o=dfs(v,min(f,tu[i].f));
if(o==0)continue;
f-=o;tu[i].f-=o;tu[i^1].f+=o;
if(f==0)return uo;
}
--gap[des[w]]?++gap[++des[w]]:des[qi]=-9999;
return uo-f;
}
liu ISAP(int qii,int zoo){
clear(zoo+2);
qi=qii;zo=zoo;
if(!bfs())return 0;
while(des[qi]>=0){
dfs(qi,1e9);
}return ans;
}
void add(int u,int v,int f){
tu[++we].ne=head[u];head[u]=we;tu[we].v=v;tu[we].f=f;
tu[++we].ne=head[v];head[v]=we;tu[we].v=u;tu[we].f=0;
}
int in[N],ou[N];
void more(int u,int v,int f1,int f2){
add(u,v,f2-f1);in[v]+=f1;ou[u]+=f1;
}
int getans(int n,int qi,int zo){
int op=0;
for(int i=1;i<=n;i++){
int k=in[i]-ou[i];
if(k==0)continue;
else if(k>0){
op+=k;add(n+1,i,k);
}else add(i,n+2,-k);
in[i]=ou[i]=0;
}add(zo,qi,1e9);if(ISAP(n+1,n+2)!=op){cclear(n+2);return -1;}
head[qi]=tu[head[qi]].ne;head[zo]=tu[head[zo]].ne;
int po=ISAP(qi,zo);cclear(n+2);return op+po;
}
dinic
#include<iostream>
#define For(u,v,i) for(int i=he[u],v=t[i].v;i;i=t[i].ne,v=t[i].v)
using namespace std;
struct bian{
int ne,v,f;
}t[1000000];
int qi,zo;
const int N=100000;
int d[N],ga[N],l[N],he[N],mk[N],we=1,tib=0;
void add(int u,int v,int f){
t[++we].ne=he[u];he[u]=we;t[we].v=v;t[we].f=f;
t[++we].ne=he[v];he[v]=we;t[we].v=u;t[we].f=0;
}
void out(int n){
for(int j=1;j<=n;j++){cout<<j<<" :: ";
For(j,v,i)cout<<v<<","<<t[i].f<<" ";cout<<endl;
}
}
bool bfs(){tib++;
int w=0,h=0;l[w++]=zo;mk[zo]=tib;
while(w>h){
int u=l[h];h++;
For(u,v,i){
if(mk[v]==tib)continue;
if(t[i^1].f){
mk[v]=tib;
ga[d[v]=d[u]+1]++;l[w++]=v;
}
}
}return mk[qi]==tib;
}
int ans=0;
int dfs(int w,int f){
if(w==zo){ans+=f;return f;}
int uf=f;
For(w,v,i){
if(d[v]!=d[w]-1||t[i].f==0)continue;
int o=dfs(v,min(f,t[i].f));
if(o){f-=o;t[i].f-=o;t[i^1].f+=o;if(f==0)return uf;}
}
return uf-f;
}
int Dinic(){
while(bfs())dfs(qi,1e9);return ans;
}
int main(){
int n,m;cin>>n>>m>>qi>>zo;
for(int i=1;i<=m;i++){
int a1,a2,a3;cin>>a1>>a2>>a3;add(a1,a2,a3);
}
cout<<Dinic();return 0;
}最小费用最大流
#include<iostream>
#include<vector>
#define For(u,v,i) for(int i=he[u],v=t[i].v;i;v=t[i=t[i].ne].v)
using namespace std;
typedef long long ll;
struct bian{
int u,v,ne;ll f,l;
};
const int N=100000,M=1000000;
bian t[M];
int he[N],l[N],p[N],we=1,qi,zo,in[N];
ll d[N],o[N];
ll inf=1e18;
void more(int u,int v,ll l,ll f){
t[++we].ne=he[u];he[u]=we;t[we].u=u;t[we].v=v;t[we].l=l;t[we].f=f;
}
void add(int u,int v,ll l,ll f){more(u,v,l,f);more(v,u,0,-f);}
void out(int n){
for(int p=1;p<=n;p++){cout<<p<<"::";
For(p,v,i){
cout<<v<<","<<t[i].l<<","<<t[i].v<<" ";
}cout<<endl;
}
}
bool spfa(int n){
int w=0,h=0;l[w++]=qi;in[qi]=1;
for(int i=1;i<=n;i++){d[i]=inf*2;p[i]=o[i]=0;}o[qi]=inf;d[qi]=0;
while(w>h){
int u=l[h];h++;in[u]=0;
For(u,v,i){
if(t[i].l==0)continue;
if(d[v]>d[u]+t[i].f){
d[v]=d[u]+t[i].f;o[v]=min(o[u],t[i].l);p[v]=i;
if(in[v]==0){in[v]=1;l[w++]=v;}
}
}
}return o[zo];
}
ll ans,ansf;
void run(int n){
ans=ansf=0;
while(spfa(n)){
ans+=o[zo];ansf+=o[zo]*1LL*d[zo];
for(int i=p[zo];i;i=p[t[i].u]){
t[i].l-=o[zo];t[i^1].l+=o[zo];
}
}
}
inline int read(){
int x=0,f=1;char a1=getchar();while(a1<'0'||a1>'9'){if(a1=='-')f=-f;a1=getchar();}
while(a1>='0'&&a1<='9'){x=x*10+(a1^48);a1=getchar();}return x*f;
}
int main(){
}spfa+dij
#include<iostream>
#include<queue>
#define For(u,v,i) for(int i=he[u],v=t[i].v;i;v=t[i=t[i].ne].v)
using namespace std;
const int N=60000,M=1000000;
struct bian{
int u,v,f,l,ne;
};bian t[M];
int d[N],p[N],he[N],o[N],hw[N],we=1,l[M],qi,zo,in[N];
void add(int u,int v,int l,int f){
t[++we].ne=he[u];he[u]=we;t[we].u=u;t[we].v=v;t[we].l=l;t[we].f=f;
t[++we].ne=he[v];he[v]=we;t[we].u=v;t[we].v=u;t[we].l=0;t[we].f=-f;
}
int spfa(int n){
int h=0,w=0;l[w++]=qi;
for(int i=1;i<=n;i++){d[i]=2e9;o[i]=0;}d[qi]=0;in[qi]=1;o[qi]=2e9;
while(w>h){
int u=l[h];h++;in[u]=0;
For(u,v,i){
if(t[i].l==0)continue;
if(d[u]+t[i].f<d[v]){
o[v]=min(o[u],t[i].l);d[v]=d[u]+t[i].f;p[v]=i;
if(in[v]==0){in[v]=1;l[w++]=v;}
}
}
}
return o[zo];
}struct rot{int h,d;};
bool operator < (rot a,rot b){return a.d>b.d;}
priority_queue<rot> e;
int dij(int n){e.push(rot{qi,0});
for(int i=1;i<=n;i++){d[i]=2e9;o[i]=0;in[i]=0;}d[qi]=0;o[qi]=2e9;
for(int te=1;te<=n;te++){
while(!e.empty()&&in[e.top().h])e.pop();
if(e.empty())break;
int u=e.top().h;e.pop();in[u]=1;
For(u,v,i){
if(in[v]||t[i].l==0)continue;
int le=t[i].f+hw[u]-hw[v];
if(d[u]+le<d[v]){
o[v]=min(o[u],t[i].l);d[v]=d[u]+le;p[v]=i;
e.push(rot{v,d[v]});
}
}
}while(!e.empty())e.pop();
return o[zo];
}
int ans,ansf;
void ask(int n){ans=ansf=0;
if(!spfa(n))return;do{
ans+=o[zo];ansf+=o[zo]*1LL*(d[zo]+hw[zo]-hw[qi]);
for(int i=1;i<=n;i++)hw[i]+=d[i];
for(int u=zo,i=p[u];u!=qi;i=p[u=t[i].u]){
t[i].l-=o[zo];t[i^1].l+=o[zo];
}
}while(dij(n));
}
void clear(int n){
we=1;for(int i=1;i<=n;i++){he[i]=in[i]=p[i]=hw[i]=0;}
}FASTIO
inline char gc() {
static char buf[1048576], *p1, *p2;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1048576, stdin), p1 == p2) ? EOF : *p1++;}
inline int read() {
char c = gc(); int r = 0;
for (; c < '0' || '9' < c; c = gc());for (; '0' <= c && c <= '9'; c = gc()) r = r * 10 + (c - '0');return r;}
inline int read(){
int x=0,f=1;char a1=getchar();while(a1<'0'||a1>'9'){if(a1=='-')f=-f;a1=getchar();}
while(a1>='0'&&a1<='9'){x=x*10+(a1^48);a1=getchar();}return x*f;}
inline void write(int a){
if(a<0){putchar('-');a=-a;}if(a==0){putchar('0');return;}
int z=0,k=0;while(a){z=(z*10)+a%10;a/=10;k++;}while(k--){putchar('0'+(z%10));z/=10;}}
typedef long long ll;
inline long long read(){
long long x=0,f=1;char a1=getchar();while(a1<'0'||a1>'9'){if(a1=='-')f=-f;a1=getchar();}
while(a1>='0'&&a1<='9'){x=x*10+(a1^48);a1=getchar();}return x*f;}
inline void write(ll a,int ok=1){
if(a<0){putchar('-');a=-a;}if(a==0)putchar('0');else
{unsigned long long z=0,k=0;while(a){z=(z*10)+a%10;a/=10;k++;}while(k--){putchar('0'+(z%10));z/=10;}}if(ok==1)putchar('\n');else if(ok==2)putchar(' ');}
write自带换行，附加参数0取消，2改为空格多项式全家桶
压行了，但在后面有说明（也就不到100行）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#define clr(i,k) memset(i,0,sizeof(int)*(k))
#define cpy(i,j,k) memcpy(i,j,sizeof(int)*(k))
#define mu 998244353
#define getln int ln=1;while(ln<n)ln<<=1;
#define getmi int mi=(l+r)/2;
#define add1(e,f) e+=f;if(e>=mu)e-=mu;
#define add2(e,f) e-=f;if(e<0)e+=mu;
using namespace std;typedef long long ll;
int kpow(ll a,int b=mu-2){ll ans=1;while(b){if(b&1)ans=ans*a%mu;a=a*a%mu;b>>=1;}return ans;}
////////////////////////////////
ll ci;struct comp{
ll a,i;comp operator *(comp b){return (comp){(a*b.a+i*b.i%mu*ci)%mu,(a*b.i+i*b.a)%mu};}
comp operator %(int b){return (comp){a%b,i%b};}};
comp kpow(comp a,ll b){comp ans=(comp){1,0};while(b){if(b&1)ans=ans*a%mu;a=a*a%mu;b>>=1;}return ans;}
bool fang(int n){return kpow(n,(mu-1)/2)==1;}
int msqrt(int n){if(n<=0)return n;if(!fang(n))return -1;ll a;do{a=rand()*1LL*rand()+1;a%=mu;ci=(a*1LL*a-n+mu)%mu;
}while(fang(ci));comp w=(comp){a,1};w=kpow(w,(mu+1)/2);int a1=w.a,a2=mu-a1;if(a1>a2)swap(a1,a2);return a1;}
////////////////////////////////
const int G=3,iG=kpow(G),N=1001000;
inline long long read(){
long long x=0,f=1;char a1=getchar();while(a1<'0'||a1>'9'){if(a1=='-')f=-f;a1=getchar();}
while(a1>='0'&&a1<='9'){x=x*10+(a1^48);a1=getchar();}return x*f;}
inline void write(ll a,int ok=1){
if(a<0){putchar('-');a=-a;}if(a==0)putchar('0');else
{ll z=0,k=0;while(a){z=(z*10)+a%10;a/=10;k++;}while(k--){putchar('0'+(z%10));z/=10;}}
if(ok==1)putchar('\n');else if(ok==2)putchar(' ');}
void print(int a[],int n){for(int i=0;i<n;i++)write(a[i],2);putchar('\n');}
int mod_read(int m=mu){int x=0;char a1=getchar();while(a1<'0'||a1>'9')a1=getchar();
while(a1>='0'&&a1<='9'){x=(x*10LL+(a1^48))%m;a1=getchar();}return x;}
int readp(int a[],int o=0){int n=(o?o:read());for(int i=0;i<n;i++)a[i]=read();return n; }
void NTT(int s[],int op,int n){
static int las,r[N];getln;if(las!=ln){for(int i=1;i<ln;i++)r[i]=((r[i>>1]>>1)|(i&1?ln>>1:0));las=ln;}
for(int i=0;i<ln;i++)if(i<r[i])swap(s[i],s[r[i]]);for(int i=1,i2=2;i<ln;i<<=1,i2<<=1){
int u=kpow(op?G:iG,(mu-1)/i2);for(int j=0;j<ln;j+=i2){ll d=1;for(int l=j;l<j+i;++l){
int tt=d*s[l+i]%mu;s[l+i]=s[l];add2(s[l+i],tt);add1(s[l],tt);d=d*u%mu;}}}
if(op==0){int yu=kpow(ln);for(int i=0;i<n;i++)s[i]=s[i]*1LL*yu%mu;}}
void dot(int a[],int b[],int n){for(int i=0;i<n;i++)a[i]=a[i]*1LL*b[i]%mu;}
void times(int a[],int b[],int n,int m){n+=m;getln;NTT(a,1,n);NTT(b,1,n);dot(a,b,ln);NTT(a,0,ln);clr(a+n-1,ln);}
void invp(int s[],int n){
getln;static int r[N],w[N],sa[N],sav[N];w[0]=kpow(s[0]);
for(int i=1,i2=2;i<ln;i<<=1,i2<<=1){cpy(r,w,i);cpy(sa,s,i2);NTT(r,1,i2);cpy(sav,r,i2);NTT(sa,1,i2);dot(r,sa,i2);
NTT(r,0,i2);clr(r,i);NTT(r,1,i2);dot(r,sav,i2);NTT(r,0,i2);for(int j=i;j<i2;j++){w[j]=2LL*w[j]-r[j]+mu;if(w[j]>=mu)w[j]-=mu;}
}cpy(s,w,n);clr(r,ln<<1);clr(w,ln<<1);clr(sa,ln<<1);}
void fan(int a[],int n){for(int i=0;i<n/2;i++)swap(a[i],a[n-i-1]);}
void div(int a[],int b[],int n,int m){
static int w[N],r[N];getln;clr(w,ln<<1);clr(r,ln<<1);int yu=n-m+1;cpy(w,a,n);cpy(r,b,m);fan(a,n);fan(b,m);
invp(b,yu);times(a,b,n,n);clr(b,ln<<1);cpy(b,r,m);clr(a+yu,ln<<1);fan(a,yu);clr(r,ln);cpy(r,a,yu);times(b,a,n,yu);
for(int i=0;i<m-1;i++)b[i]=(w[i]-b[i]+mu)%mu;cpy(a,r,yu);clr(b+m-1,ln);}
int iv[N],ic[N],inid;
void init(int n,int ko=0){iv[0]=iv[1]=ic[0]=1;
for(ll i=1;i<=n;i++)ic[i]=ic[i-1]*i%mu;for(int i=2;i<=n;i++)iv[i]=iv[mu%i]*1LL*(mu-mu/i)%mu;
if(ko)for(int i=2;i<=n;i++)iv[i]=iv[i]*1LL*iv[i-1]%mu;inid=ko?0:n;}
void dao(int s[],int n){for(int i=1;i<n;i++)s[i-1]=s[i]*1LL*i%mu;s[n-1]=0;}
void jifen(int s[],int n){if(inid<n)init(n);for(int i=n-1;i;i--)s[i]=s[i-1]*1LL*iv[i]%mu;s[0]=0;}
void lnp(int s[],int n){static int o[N];cpy(o,s,n);dao(s,n);invp(o,n);times(s,o,n,n);jifen(s,n);clr(s+n,n<<1);getln;clr(o,ln<<1);}
void sqrtp(int s[],int n){
getln;static int r[N],w[N],sa[N];w[0]=1;
for(int i=1,i2=2;i<ln;i<<=1,i2<<=1){for(int j=0;j<i;j++){r[j]=w[j]*2;if(r[j]>=mu)r[j]-=mu;}invp(r,i2);
cpy(sa,w,i2);NTT(sa,1,i2);dot(sa,sa,i2);NTT(sa,0,i2);for(int j=0;j<i2;j++){add1(sa[j],s[j]);}
times(sa,r,i2,i2);clr(r,i2<<1);for(int j=i;j<i2;j++)w[j]=sa[j];clr(sa,i2<<1);
}cpy(s,w,n);clr(r,ln<<1);clr(w,ln<<1);clr(sa,ln<<1);}
void expp(int s[],int n){
getln;static int r[N],w[N];w[0]=1;for(int i=1,i2=2;i<ln;i<<=1,i2<<=1){cpy(r,w,i);clr(r+i,i2);lnp(r,i2);
for(int j=0;j<i2;j++){r[j]=s[j]-r[j];add1(r[j],mu);}add1(r[0],1);times(w,r,i2,i2);clr(w+i2,i2);}cpy(s,w,n);clr(r,ln<<1);clr(w,ln<<1);}
void kpowp(int s[],int n,int k){lnp(s,n);for(int i=0;i<n;i++)s[i]=s[i]*1LL*k%mu;expp(s,n);}
void FDT(int s[],int n,int op){static int r[N];getln;if(op)for(int i=0;i<n;i++)r[i]=iv[i];
else for(int i=0;i<n;i++)r[i]=(i&1)?(mu-iv[i]):iv[i];times(s,r,n,n);clr(r,ln<<1);clr(s+n,ln<<1);}
void FDTtimes(int a[],int b[],int n,int m){
n+=m;init(n,1);FDT(a,n,1);FDT(b,n,1);for(int i=0;i<n;i++){a[i]=a[i]*1LL*b[i]%mu*ic[i]%mu;}FDT(a,n,0);}
const int UM=2;/*推荐2e7*/ int g[N],*f[N],*d[N],tmp[N],t[UM],*to=t,t2[UM],*to2=t;
void Cdtop(int w,int l,int r){
if(l==r){f[w]=to;d[w]=to2;if(l==0){f[w][0]=d[w][0]=g[0];}
else{f[w][1]=d[w][1]=g[l]*1LL*kpow(g[l-1])%mu;f[w][0]=d[w][0]=(mu-f[w][1])*1LL*(l-1)%mu;}
to+=5;to2+=5;return;};getmi;Cdtop(w*2,l,mi);Cdtop(w*2+1,mi+1,r);
f[w]=to,d[w]=to2;int n=r-l+2;getln;cpy(tmp,f[w*2],mi-l+2);NTT(tmp,1,n);
cpy(f[w],f[w*2+1],r-mi+1);NTT(f[w],1,n);dot(f[w],tmp,ln);NTT(f[w],0,ln);clr(f[w]+n,ln);
cpy(d[w],d[w*2+1],r-mi+1);NTT(d[w],1,n);dot(d[w],tmp,ln);NTT(d[w],0,ln);
for(int i=0;i<mi-l+2;i++){add1(d[w][i],d[w*2][i]);}to+=2*n;to2+=2*n;clr(tmp,ln<<1);}
void DtoP(int s[],int n){to=t;to2=t2;cpy(g,s,n);Cdtop(1,0,n-1);cpy(s,d[1],n);clr(t,to-t+10);clr(t2,to2-t2+10);}
void dcdq(int w,int l,int r){if(l==r){d[w]=to;d[w][0]=(mu-l)%mu;d[w][1]=1;to+=3;return;}getmi;
dcdq(w*2,l,mi);dcdq(w*2+1,mi+1,r);d[w]=to;cpy(d[w],d[w*2],mi-l+2);cpy(tmp,d[w*2+1],r-mi+1);
times(d[w],tmp,mi-l+2,r-mi+1);clr(tmp,4*(r-mi+1));to+=r-l+4;}
void Cptod(int w,int l,int r){if(l==r){tmp[l]=f[w][0];return;}getmi;
f[w*2+1]=to2;to2+=4*(r-l+1);f[w*2]=to2;to2+=4*(r-l+1);
cpy(f[w*2+1],f[w],r-l+1);cpy(f[w*2],d[w*2],r-l+1);
div(f[w*2+1],f[w*2],r-l+1,mi-l+2);Cptod(w*2,l,mi);Cptod(w*2+1,mi+1,r);}
void PtoD(int s[],int n){to=t;f[1]=to2=t2;to2+=n+5;cpy(f[1],s,n);
dcdq(1,0,n-1);Cptod(1,0,n-1);cpy(s,tmp,n);clr(t,to-t+10);clr(t2,to2-t2+10);}
/* kpow(a,b) a^b%mu（省略b为逆元) msqrt(x) x的较小二次剩余
read()::读ll mod_read(m=mu)读一个数，边读边mod write(a,ok=1)写一个ll，ok=1换行，2空格 print(a*,n)输出数组a前n个数
readp(a*,n)读一个n项式，省略n时也读入n并返回n NTT(a*,op,n)op=1为正0逆，a长n位 dot(a*,b*,n) 点乘a,b
times(a*,b*,n,m)a=a*b,NTT掉b invp(a*)a=a^-1 fan(a*,n) 反转n项式a
div(a*,b*,n,m)a=a/b b=a%b init(n)预处理1-n的ic[x]=x!,ic[x]=x^1附带参数1使ic[x]=(x!)^-1
dao(a*,n) jifen(a*n) 对a求导/积分 lnp(a*,n) expp(a*,n) 求ln a/e^a sqrtp(a*,n) 求a^0.5
kpowp(a*,n,k) a=a^k 要求a[0]=1 FDT(a*,n)求下降式a的EGF FDTtimes(a*,b*,n,m) 同times,但为下降式
UM 转化下降式和多项式用，最好取2e7 DtoP(a*,n)下降式转多项式 PtoD(a*,n)多项式转下降式 */ 替罪羊平衡树
#include<iostream>
#include<vector>
using namespace std;
const int N=1000000;
double A=0.75,B=0.3;
int zz[N],hea;
struct sheep{
vector<int> s,f,g,b,si,c[2];
int head,we=0;
void out(int w){cout<<head<<"::\n";
for(int i=1;i<=w;i++){
cout<<i<<" : "<<s[i]<<" = "<<f[i]<<" "<<c[0][i]<<","<<c[1][i]<<" "<<si[i]<<" "<<g[i]<<" "<<b[i]<<endl;
}
}
void dfs(int w){if(w==0)return;
dfs(c[0][w]);if(si[w])zz[++hea]=w;dfs(c[1][w]);
}
int build(int fa,int l,int r){
if(r<l)return 0;int mi=(l+r)/2,w=zz[mi];f[w]=fa;
c[0][w]=build(w,l,mi-1);c[1][w]=build(w,mi+1,r);
g[w]=si[w]+g[c[0][w]]+g[c[1][w]];b[w]=0;
return w;
}
void recon(int x){
hea=0;dfs(x);
// for(int i=1;i<=hea;i++)cout<<zz[i]<<" ";cout<<endl<<endl<<endl;
if(f[x]==0)head=build(f[x],1,hea);
else c[s[f[x]]<s[x]][f[x]]=build(f[x],1,hea);
}
void check(int x,int op){
int w=x;hea=0;
while(w){if(!op)b[w]++;w=f[w];zz[++hea]=w;}
for(int i=hea-1;i;i--){
w=zz[i];
if(g[w]*B<b[w]||max(g[c[0][w]],g[c[1][w]])>g[w]*A){
recon(w);return;
}
}
}
void insert(int x){
if(s.size()<we+2){
int u=s.size()*2+3;
s.resize(u);c[0].resize(u);c[1].resize(u);f.resize(u);g.resize(u);b.resize(u);si.resize(u);
}
int w=head;int fa=-1;
while(w){g[fa=w]++;
if(s[w]==x){si[w]++;return;}
w=c[x>s[w]][w];
};w=++we;f[w]=fa;s[w]=x;g[w]=si[w]=1;
if(fa==-1){head=w;f[w]=0;}else c[x>s[fa]][fa]=w;
check(w,1);
}
void del(int x){
int w=head;
while(w){
g[w]--;
if(s[w]==x){check(w,--si[w]);break;}
w=c[x>s[w]][w];
};if(g[head]==0)head=0;
}
int getrank(int x){
int w=head,ans=1;
while(w){
if(s[w]==x)return ans+g[c[0][w]];
if(x>s[w]){ans+=g[c[0][w]]+si[w];w=c[1][w];}
else w=c[0][w];
}return ans;
}
int rankget(int x){
int w=head;
while(w){
if(g[c[0][w]]>=x)w=c[0][w];
else if(g[c[0][w]]+si[w]>=x)return s[w];
else{x-=(g[c[0][w]]+si[w]);w=c[1][w];}
}
return 0;
}
int qian(int x){return rankget(getrank(x)-1);}
int hou(int x){return rankget(getrank(x+1));}
};
inline int read(){
int x=0,f=1;char a1=getchar();while(a1<'0'||a1>'9'){if(a1=='-')f=-f;a1=getchar();}
while(a1>='0'&&a1<='9'){x=x*10+(a1^48);a1=getchar();}return x*f;
}
sheep a;
int main(){
}标准dij最短路
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N=1000000;
vector<int> t[N],c[N];
int d[N],in[N];
struct rout{
int h,d;
};bool operator < (rout a,rout b){return a.d>b.d;}
priority_queue<rout> tu;
void add(int u,int v,int w){t[u].push_back(v);t[v].push_back(u);
c[u].push_back(w);c[v].push_back(w);
}void more(int u,int v,int w){t[u].push_back(v);c[u].push_back(w);}
int inf=((1LL<<31)-1);
int dij(int n,int u,int v){
for(int i=1;i<=n;i++)d[i]=inf;d[u]=0;tu.push(rout{u,0});
while(!tu.empty()){int u=tu.top().h;tu.pop();if(in[u])continue;
in[u]=1;int pl=t[u].size();
for(int i=0,v;i<pl;i++){v=t[u][i];
if(!in[v]&&d[v]>d[u]+c[u][i])tu.push(rout{v,d[v]=d[u]+c[u][i]});
}
}return d[v];
}
int main(){
}判负环spfa
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N=1000000;
vector<int> t[N],c[N];
int d[N],l[N*15],in[N],al[N];
void add(int u,int v,int w){t[u].push_back(v);t[v].push_back(u);
c[u].push_back(w);c[v].push_back(w);
}void more(int u,int v,int w){t[u].push_back(v);c[u].push_back(w);}
int inf=((1LL<<31)-1);
bool spfa(int n,int u){
int h=0,w=0;
for(int i=1;i<=n;i++){d[i]=inf;al[i]=in[i]=0;}d[u]=0;l[w++]=u;
while(w>h){int u=l[h];in[u]=0;h++;int pl=t[u].size();
for(int i=0,v;i<pl;i++){v=t[u][i];
if(d[v]>d[u]+c[u][i]){
d[v]=d[u]+c[u][i];if(in[v])continue;in[v]=1;
if(++al[v]>=n)return 1;l[w++]=v;
}
}
}return 0;
}
void clear(int n){for(int i=1;i<=n;i++){t[i].clear();c[i].clear();}}
int main(){
}O(n--1)RMQ
结构体版：
#define rint register int
int lg[1000000],last;
struct RMQ{
vector<int> b,ho,qi,ku;vector<vector<int> >st;
void make(int n){if(n<=last)return;last=n;for(rint i=1,lo=0,ln=2;i<=n;i++){lg[i]=lo;if(i>=ln){lo++;ln<<=1;}}}
void init(int a[],int n,int B){
b.resize(n+2);ho.resize(n+2);qi.resize(n+2);ku.resize(n+2);make(n/B+10);st.resize(n/B+10);
for(rint i=1,jo=1;jo<=n;i++){int ma=0;
for(rint o=1;o<=B&&jo<=n;jo++,o++){b[jo]=a[jo];ku[jo]=i;ma=max(ma,a[jo]);}
st[i].push_back(ma);
}int zo=ku[n];
for(rint i=1;(1<<i)<=zo;i++){
int le=(1<<i)-1,h=1<<(i-1);
for(rint j=1;j+le<=zo;j++)st[j].push_back(max(st[j][i-1],st[j+h][i-1]));
}for(rint i=1;i<=n;i++)qi[i]=max((ku[i-1]!=ku[i]?0:qi[i-1]),a[i]);
for(rint i=n;i;i--)ho[i]=max((ku[i+1]!=ku[i]?0:ho[i+1]),a[i]);}
inline int ask(rint l,rint r){rint an=0,z=ku[l],y=ku[r];
if(z==y){for(rint j=l;j<=r;j++)an=max(an,b[j]);return an;
}else{z++;y--;if(z>y)return max(ho[l],qi[r]);
rint o=lg[y-z+1];return max(max(ho[l],qi[r]),max(st[z][o],st[y-(1<<o)+1][o]));}}
};
非结构体
const int N=20000010,NB=10010;
int b[N],ho[N],qi[N];
int ku[N],st[NB][15];
int lg[NB];
#define rint register int
void init(int a[],int n,int B){
for(rint i=1,jo=1;jo<=n;i++){
int ma=0;
for(rint o=1;o<=B&&jo<=n;jo++,o++){
ku[jo]=i;ma=max(ma,a[jo]);
}st[i][0]=ma;
}int zo=ku[n];
for(rint i=1;(1<<i)<=zo;i++){
int le=(1<<i)-1,h=1<<(i-1);
for(rint j=1;j+le<=zo;j++){
st[j][i]=max(st[j][i-1],st[j+h][i-1]);
}
}
for(rint i=1;i<=n;i++)qi[i]=max((ku[i-1]!=ku[i]?0:qi[i-1]),a[i]);
for(rint i=n;i;i--)ho[i]=max((ku[i+1]!=ku[i]?0:ho[i+1]),a[i]);
for(rint i=1,lo=0,ln=2;i<=zo;i++){lg[i]=lo;if(i>=ln){lo++;ln<<=1;}}
}
int ask(int a[],int l,int r){
int an=0,z=ku[l],y=ku[r];
if(z==y){
for(rint j=l;j<=r;j++)an=max(an,a[j]);return an;
}else{z++;y--;
if(z>y)return max(ho[l],qi[r]);
int o=lg[y-z+1];
return max(max(ho[l],qi[r]),max(st[z][o],st[y-(1<<o)+1][o]));
}
}2-SAT模板
#include<iostream>
#include<vector>
using namespace std;
const int N=2100000;
vector<int> t[N];
void add(int a,int b){
t[a].push_back(b);
}
#define Z(i,j) (((i)*2)-1+(j))
void add(int a,int b,int c,int d){
if(a==c){
if(b==d)add(Z(a,b^1),Z(a,b));
}else {
add(Z(a,b^1),Z(c,d));add(Z(c,d^1),Z(a,b));
}
}
int lo[N],d[N],dfn,scc,sc[N],zz[N],hea,in[N];
void tarjan(int w){
zz[++hea]=w;d[w]=lo[w]=++dfn;in[w]=1;
int pl=t[w].size();
for(int i=0,v;i<pl;i++){
v=t[w][i];
if(!d[v]){
tarjan(v);lo[w]=min(lo[w],lo[v]);
}else if(in[v])lo[w]=min(lo[w],d[v]);
}
if(d[w]==lo[w]){int v;scc++;
do{sc[v=zz[hea--]]=scc;in[v]=0;}while(v!=w);
}
}
int ans[N];
bool run(int n){
for(int i=1;i<=2*n;i++){
if(d[i]==0)tarjan(i);
}
for(int i=1;i<=2*n;i+=2){
if(sc[i]==sc[i+1])return 0;
}
for(int i=2;i<=2*n;i+=2){
ans[i/2]=(sc[i]<sc[i-1]);
}return 1;
}
void clear(int n){
for(int i=1;i<=2*n;i++){
d[i]=lo[i]=sc[i]=in[i]=0;
}hea=dfn=scc=0;
}LCT加并查集
#include<iostream>
#include<algorithm>
#define rt(i) (s[f[i]][0]!=i&&s[f[i]][1]!=i)
using namespace std;
const int N=500002;
int f[N],s[N][2],v[N],q[N],x[N],fo[N];
void fan(int w){
if(w==0)return;
x[w]^=1;swap(s[w][0],s[w][1]);
}
void down(int w){
if(x[w]){
fan(s[w][0]);fan(s[w][1]);x[w]=0;
}
}
void up(int w){
v[w]=q[w];fo[w]=w;
if(s[w][0]&&v[w]>v[s[w][0]])v[w]=v[s[w][0]],fo[w]=fo[s[w][0]];
if(s[w][1]&&v[w]>v[s[w][1]])v[w]=v[s[w][1]],fo[w]=fo[s[w][1]];
}
void out(int n){
for(int i=1;i<=n;i++){
cout<<i<<" :: "<<f[i]<<" <"<<s[i][0]<<","<<s[i][1]<<"> "<<v[i]<<" "<<fo[i]<<" "<<q[i]<<endl;
}
}
int opt=0;
void read(int &x){
x=0;char a1=getchar();
while(a1<'0'||a1>'9')a1=getchar();
while(a1>='0'&&a1<='9'){
x=x*10+(a1^48);a1=getchar();
}
}
void zhuan(int w){
if(f[w]==0)return;
int fa=f[w],gr=f[fa],k=s[fa][1]==w,s2=s[w][!k];
if(!rt(fa))s[gr][s[gr][1]==fa]=w;
f[w]=gr;f[fa]=w;s[fa][k]=s2;s[w][!k]=fa;
if(s2)f[s2]=fa;up(fa);
}
int z[N],he=0;
void splay(int w){
int fa,gr=w;
z[++he]=w;
while(!rt(gr))z[++he]=gr=f[gr];
while(he)down(z[he--]);
while(!rt(w)){
fa=f[w];gr=f[fa];
if(!rt(fa))zhuan(((s[gr][1]==fa)^(s[fa][1]==w))?w:fa);
zhuan(w);
}
up(w);
}
void acc(int w){
for(int so=0;w;w=f[so=w]){
splay(w);s[w][1]=so;up(w);
}
}
void make(int w){
acc(w);splay(w);fan(w);
}
int find(int w){
acc(w);splay(w);
while(s[w][0]){down(w);w=s[w][0];}
splay(w);
return w;
}
int split(int x,int y){
make(x);acc(y);splay(y);return f[x]==y;
}
void link(int x,int y){
make(x);
if(find(y)!=x)f[x]=y;up(y);
}
void cut(int x,int y){
make(x);
if(find(y)==x&&f[y]==x&&!s[y][0]){
f[y]=s[x][1]=0;up(x);
}//out();
}
void change(int w,int k){
splay(w);q[w]=k;//up(w);
}
struct bian{
int u,v,l;
};
bool cmp(bian a,bian b){
return a.l<b.l;
}
int fa[N];
int fin(int a){
return fa[a]==a?a:fa[a]=fin(fa[a]);
}
bian t[N];
int annex(int a,int b){
a=fin(a);b=fin(b);if(a==b)return 1;
fa[a]=b;return 0;
}数论全家桶
高度压行
#include<cmath>
#include<map>
#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
typedef long long ll;
inline ll read(){
ll x=0,f=1;char a1=getchar();while(a1<'0'||a1>'9'){if(a1=='-')f=-f;a1=getchar();}
while(a1>='0'&&a1<='9'){x=x*10+(a1^48);a1=getchar();}return x*f;}
inline void write(int a){
if(a<0){putchar('-');a=-a;}if(a==0){putchar('0');return;}
int z=0,k=0;while(a){z=(z*10)+a%10;a/=10;k++;}while(k--){putchar('0'+(z%10));z/=10;}}
ll gcd(ll a,ll b){if(a==0)return b;if(a<0)a=-a;ll t;while(b){t=a%b;a=b;b=t;}return a;}
ll exgcd(ll a,ll b,ll &x,ll &y){//ax+by=gcd(a,b); return gcd(a,b)
if(b==0){x=1;y=0;return a;}ll z=exgcd(b,a%b,y,x);y-=x*(a/b);return z;}
ll inv(ll a,ll p){if(p==1)return 1;ll a1,a2;exgcd(a,p,a1,a2);return (a1%p+p)%p;}
ll mul(ll a,ll b,ll m){//return a*b%m
ll d=((long double)a/m*b+0.5);long long r=a*b-d*m;return r<0?r+m:r;}
ll kpow(ll a,ll b,ll p){//return a^b%m
ll ans=1;if(p>1000000010)while(b){if(b&1)ans=mul(ans,a,p);a=mul(a,a,p);b>>=1;}
else while(b){if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;}return ans;}
bool merge(ll &x1,ll &p1,ll x2,ll p2){//s=x1(mod p1),s=x2(mod p2)-->s=x1(mod p1),no answer->1
ll e=(x2-x1%p2+p2)%p2,k,o,z=exgcd(p1,p2,k,o),np=p1/z*p2;
if(e%z)return 1;k=mul(k,e/z,np);x1=(x1+mul(p1,k,np))%np;p1=np;return 0;}
ll indef(ll a,ll b,ll c,ll &x,ll &y){//ax+by=c; return gcd(a,b)(No solution->return 0)
ll z=exgcd(a,b,x,y);if(c%z!=0)return 0;ll t=a/z;a=b/z;b=t;
x*=c/z;y*=c/z;ll s=ceil((-x+1)/(double)a);x+=a*s;y-=b*s;return z;}
ll modef(ll a,ll c,ll p){//ax=c(mod p)return x; (No solution->return -1)
ll x=0,y=0;int e=indef(a,p,c,x,y);return e?x:-1;}
ll bsgs(ll a,ll c,ll p){//a^x=c(mod p) (gcd(a,p)==1))return x;
map<ll,ll> t;t.clear();ll u=sqrt(p-1)+1;ll k=1,e=1;
for(ll i=0;i<u;i++,k=mul(k,a,p))t[mul(k,c,p)]=i+1;e=k;
for(ll i=u;i<=p+u;i+=u,e=mul(e,k,p))if(t.count(e))return i-t[e]+1;return -999999;}
ll exbsgs(ll a,ll c,ll p){//a^x=c(mod p) return x; (No solution->return a nagetive number)
if(p==1)return a==c?0:-1000;if(c==1)return 0;if(!a)return (!c)?1:-1000;
if(a==c)return 1;ll z=gcd(a,p);if(z==1)return bsgs(a,c,p);if(c%z)return -999999;
c/=z;p/=z;c=mul(c,inv(a/z,p),p);return exbsgs(a%p,c,p)+1;}
//不保证接下来的函数正确性
bool hack(ll n,ll p){ll t=n-1;while(!(t&1))t>>=1;ll bu=kpow(p,t,n);
if(bu==1||bu==n-1)return 0;while((t<<=1)<n-1){bu=mul(bu,bu,n);if(bu==n-1)return 0;}return 1;}
bool ptest(ll n){//return [n is an prime]
if(n<2)return 0;for(int i=2;i*i<=min(n,2000ll);i++)if(n%i==0)return 0;if(n<=2000)return 1;
int pic[8]={2,3,5,7,13,19,61,233};for(int i=0;i<8;i++)if(hack(n,pic[i]))return 0;return 1;}
ll prho(ll n,int _th){//return one of n's factor
const int lim=128;ll sa[lim+10]={};ll x1=(_th+1)%n,x2=mul(x1,x1,n)+_th;ll bu;int to=0;
while(1){bu=mul(x1-x2,bu,n);sa[++to]=x1-x2;
if(to==lim){if(gcd(n,bu)>1)break;to=0;}
x1=mul(x1,x1,n)+_th;x2=mul(x2,x2,n)+_th;x2=mul(x2,x2,n)+_th;
}for(int i=1;i<=to;i++){bu=gcd(n,sa[i]);if(bu>1)return bu;}return n;}
int sovfz(ll n,ll fz[]){
if(n==1||ptest(n)){fz[1]=n;return 1;}ll z;
int ce[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43};
for(int i=0;i<14;i++)if(n%ce[i]==0){z=ce[i];goto jum;}
z=prho(n,rand()%(n-1)+1);while(z==n)z=prho(n,rand()%(n-1)+1);
jum:;int e=sovfz(z,fz);e+=sovfz(n/z,fz+e);return e;
}
int getfz(ll n,ll fz[]){int e=sovfz(n,fz);sort(fz+1,fz+e+1);e=unique(fz+1,fz+e+1)-fz;return e-1;}
ll getg(ll n,ll mu,int cnt,ll fz[]){
for(int i=1;i<=n;i++){if(kpow(i,mu,n)!=1)continue;
for(int j=1;j<=cnt;j++){if(kpow(i,mu/fz[j],n)==1)goto out; }return i;out:;}return 0;}
ll mu(ll n,ll fz[],int cnt){if(n==1)return 0;ll ans=1;//return miu(n)
for(int i=1;i<=cnt;i++){ans*=fz[i]-1;n/=fz[i];while(n%fz[i]==0){n/=fz[i];ans*=fz[i];}}return ans;}
ll getord(ll n,ll p,ll mu,ll fz[],ll cnt){
ll ans=1;for(int i=1;i<=cnt;i++){ll sav=mu;int c=0;while(sav%fz[i]==0){sav/=fz[i];c++;}
for(ll x=1;c;x*=fz[i],c--){if(kpow(n,sav*x,p)>1)ans*=fz[i];}
}return ans;
}
自动对拍机
使用方式是将你的程序my.cpp，标程std.cpp，自动生成器gen.cpp，测试器（名字无关紧要）放入一个文件夹，编译前三个，运行测试器即可
自动测试器
#include<iostream>
#include<windows.h>
#include<ctime>
using namespace std;
int main(){int k=0;
while(1){cerr<<"generating-->";
system("gen.exe");cerr<<"running yours-->";//生成器
system("my.exe < ask.in > ask.out");cerr<<"running std-->";//程序
system("std.exe < ask.in > ask.ans");cerr<<"OK!"<<endl;//std
int p=system("fc ask.out ask.ans");
if(p==1){
return 0;
}else cout<<++k<<" "<<clock()<<endl;
}
}生成询问
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<cstdio>
#include<fstream>
using namespace std;
long long e9=1e9,la;
unsigned int rran(){return la^=((rand()^rand())*rand())^rand()%e9;}
int ran(int a){return rran()%a+1;}//return 1-a
int main(){
srand(time(NULL)+clock());
ifstream sdin("seed.txt");sdin>>la;
ofstream sdout("seed.txt");sdout<<rran();
ofstream cout("ask.in");
//在这行之后写生成数据的代码
int n;cout<<n<<endl;
for(int i=1;i<=n;i++)
//......
return 0;
}
矩阵全家桶
#include<iostream>
#include<vector>
#include<cstdio>
#define num long long
#define abs(a) (((a)<0)?(-(a)):(a))
using namespace std;
num mu;
const int nu=1001;
struct matrix{
vector<vector<num> > t;
num x,y;
void resi(int a,int b){
t.clear();
x=a;y=b;
t.resize(a+1);
for(int i=1;i<=a;i++){
t[i].resize(b+1);
}
}
void read(int a,int b){
// resi(a,b);
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++){
cin>>t[i][j];
}
}
}
void out(){
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
cout<<t[i][j]<<" ";
}cout<<endl;
}
}
void swp(int a,int b){
for(int i=1;i<=y;i++){
swap(t[a][i],t[b][i]);
}
}
long long det(){
int p[nu];for(int i=1;i<=x;i++)p[i]=0;int ww=1;
for(int i=1;i<=x;i++){
for(int j=i+1;j<=x;j++){
if(j==i)continue;
while(t[i][i]){
int di=t[j][i]/t[i][i];
for(int l=i;l<=x;l++){
t[j][l]=(t[j][l]-1LL*di*t[i][l]%mu+mu)%mu;
}
swp(i,j);ww=-ww;
}
swp(i,j);ww=-ww;
t[j][i]=0;
}
}
num ans=ww;
for(int i=1;i<=x;i++){
ans=ans*t[i][i]%mu;
}
return (ans+mu)%mu;
}
};xxs
int r[N],g;
int p[N];
void xxs(int n){
for(int i=2;i<=n;i++){
if(p[i]==0){
r[++g]=i;zh[i]=i;
}for(int j=1;j<=g;j++){
int v=i*r[j];if(v>n)break;
p[v]=1;zh[v]=r[j];if(i%r[j]==0)break;
}
}
}缺省源
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<map>
#include<queue>
#define getmi int mi=(l+r)/2;
#define addm(a,b); {a+=b;if(a>=mu)a-=mu;}
#define decm(a,b); {a-=b;if(a<0)a+=mu;}
#define mtim(a,b) a=a*1LL*(b)%mu
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
inline long long read(){
long long x=0,f=1;char a1=getchar();while(a1<'0'||a1>'9'){if(a1=='-')f=-f;a1=getchar();}
while(a1>='0'&&a1<='9'){x=x*10+(a1^48);a1=getchar();}return x*f;}
inline void write(ll a,int ok=1){
if(a<0){putchar('-');a=-a;}if(a==0)putchar('0');else
{unsigned long long z=0,k=0;while(a){z=(z*10)+a%10;a/=10;k++;}while(k--){putchar('0'+(z%10));z/=10;}}if(ok==1)putchar('\n');else if(ok==2)putchar(' ');}
const int N=1000000;
int main(){
return 0;
}