模板库
完善中……
优化
快读快输
inline int read(){
int t=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-') f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
t=t*10+ch-'0';
ch=getchar();
}
return t*f;
}
void write(int x){
if(x<0) {putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
飞读
namespace io {
class In {
public:
template<typename T>
inline In &operator>>(T &x) {
x=0; bool f=0; char c=getchar();
while(c<'0'||c>'9') f|=(c=='-'),c=getchar();
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
if(c=='.') {
c=getchar(); double dot=0.1;
while(c>='0'&&c<='9') x+=(c-'0')*dot,dot*=0.1,c=getchar();
} return (f?x=-x:x),*this;
}
inline In &operator>>(char &x) {while(isspace(x=getchar())); return *this;}
inline In &operator>>(char *x) {
char c=getchar(); while(isspace(c)) c=getchar(); while(!isspace(c)&&~c) *(x++)=c,c=getchar();
return *x=0,*this;
}
inline In &operator>>(string &x) {
char c=getchar(); x.clear();
while(isspace(c)) c=getchar(); while(!isspace(c)&&~c) x.push_back(c),c=getchar();
return *this;
}
inline In &operator>>(In &in) { return in;}
};
class Out {
private:
char buf[35]; short dot=6,top=0;
public:
template<typename T>
inline Out &operator<<(T x) {
if(x<0) putchar('-'),x=-x;
do { buf[++top]=x%10,x/=10;} while(x);
while(top) putchar(buf[top--]|'0'); return *this;
}
inline Out &operator<<(char c) {return putchar(c),*this;}
inline Out &operator<<(string x) {for(auto c:x) putchar(c); return *this;}
inline Out &operator<<(char *x) {while(*x) putchar(*(x++)); return *this;}
inline Out &operator<<(const char *x) {while(*x) putchar(*(x++)); return *this;}
inline Out &operator<<(double x) {snprintf(buf,sizeof(buf),"%.*lf",dot,x); return (*this)<<buf;}
inline Out &operator<<(Out &out) {return out;}
inline Out &setdot(const int n) {return dot=n,*this;}
};
In fin;
Out fout;
inline Out &setdot(const int n,Out& out=fout) {return fout.setdot(n),out;}
inline In &getline(char *x,In& in=fin) {
char c=getchar();
while(!(c==' '||!isspace(c))) c=getchar(); while(c==' '||!isspace(c)) (*x++)=c,c=getchar();
return *x=0,in;
}
inline In &getline(string &x,In& in=fin) {
char c=getchar(); x.clear();
while(!(c==' '||!isspace(c))) c=getchar(); while(c==' '||!isspace(c)) x.push_back(c),c=getchar();
return in;
}
}
using namespace io;
组合计数
逆元预处理
lx[0]=1;lx[1]=1;
for(int i=2;i<N;i++) lx[i]=lx[i-1]*i%mod;
inv[N-1]=ksm(lx[N-1],mod-2);
for(int i=N-2;i>=0;i--) inv[i]=(inv[i+1])*(i+1)%mod;
快速幂
int ksm(int x,int y) {int t=1;while(y){if(y&1)t=t*x%mod;x=x*x%mod;y>>=1;}return t;}
组合数
int C(int x,int y) {if(x<y) return 0;return lx[x]*inv[y]%mod*inv[x-y]%mod;}
lucas
int lucas(int x,int y) {
if(x<mod&&y<mod) return C[x][y];
return lucas(x%mod,y%mod)*lucas(x/mod,y/mod)%mod;
}
exgcd
void exgcd(int a,int b) {
if(b==0) {
y=0;x=1;return ;
}
exgcd(b,a%b);
tmp=x;
x=y;
y=tmp-y*(a/b);
}
数据结构
树状数组
#define int long long
#define lowbit(x) (x&(-x))
void add(int x,int y) {if(x==0) return ;while(x<N) {c[x]+=y;x+=lowbit(x);};}
int ask(int x) {int t=0;while(x) {t+=c[x];x-=lowbit(x);}return t;}
线段树
真是好标准一颗线段树，感觉自己已经很久没有写过build()了。
struct stu {
int maxx,minn,add;
friend stu operator +(stu a,stu b) {
a.minn=min(a.minn,b.minn);
a.maxx=max(a.maxx,b.maxx);
return a;
}
}t[N*4];
int read() {int x;cin>>x;return x;}
void spread(int p) {
if(t[p].add) {
t[p*2].add+=t[p].add;
t[p*2+1].add+=t[p].add;
t[p*2].minn+=t[p].add;
t[p*2+1].minn+=t[p].add;
t[p*2].maxx+=t[p].add;
t[p*2+1].maxx+=t[p].add;
t[p].add=0;
}
}
void change(int p,int l,int r,int tl,int tr,int k) {
if(tl<=l&&r<=tr) {
t[p].add+=k;
t[p].maxx+=k;
t[p].minn+=k;
return ;
}
spread(p);
int mid=(l+r)>>1;
if(tl<=mid) change(p*2,l,mid,tl,tr,k);
if(mid<tr) change(p*2+1,mid+1,r,tl,tr,k);
t[p].minn=min(t[p*2].minn,t[p*2+1].minn);
t[p].maxx=max(t[p*2].maxx,t[p*2+1].maxx);
}
stu ask(int p,int l,int r,int tl,int tr) {
if(tr<tl) {
return {-10000000,1000000000000,0};
}
if(tl<=l&&r<=tr) {
// cerr<<"Ask "<<p<<" "<<t[p].minn<<" "<<t[p].maxx<<" "<<l<<" "<<r<<endl;
return t[p];
}
spread(p);
int mid=(l+r)>>1;
stu ans; ans={0,0,0};
ans.minn=1e18;ans.maxx=-1e18;
if(tl<=mid) ans=ans+ask(p*2,l,mid,tl,tr);
if(mid<tr) ans=ans+ask(p*2+1,mid+1,r,tl,tr);
return ans;
}
void build(int p,int l,int r) {
t[p].add=0;t[p].minn=1e9;t[p].maxx=-1e9;
if(l==r) {
t[p].minn=t[p].maxx=min(l,n);
// cerr<<"Build "<<p<<" "<<t[p].minn<<" "<<t[p].maxx<<endl;
return ;
}
int mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
t[p].minn=min(t[p*2].minn,t[p*2+1].minn);
t[p].maxx=max(t[p*2].maxx,t[p*2+1].maxx);
}
字符串
KMP
nxt[1]=0;
for(int i=2,j=0;i<=m;i++) {
while(j&&s[j+1]!=s[i]) {j=nxt[j];}
if(s[j+1]==s[i]) {j++;}
nxt[i]=j;
if(nxt[i]==n) {cout<<i-n*2<<endl;}
}
Hash
manacher
void manacher() {
for(int r=0,mid=0,i=1;i<=tot;i++) {
man[i]=(i<=r?min(man[mid*2-i],r-i+1):1);
while(t[i+man[i]]==t[i-man[i]]) man[i]++;
if(i+man[i]>r) {
r=i+man[i]-1;
mid=i;
}
if(man[i]>ans) ans=man[i];
}
}
图论
差分约束
void spfa() {
memset(dis,0x3f,sizeof(dis));
queue<int>q;
q.push(n+1);
dis[n+1]=0;
vis[n+1]=1;
while(q.size()) {
int x=q.front();q.pop();
vis[x]=0;
cnt[x]++;
if(cnt[x]>=n) {
cout<<"NO"<<endl;
exit(0);
}
for(auto y:e[x]) {
if(dis[y.first]>dis[x]+y.second) {
dis[y.first]=dis[x]+y.second;
if(vis[y.first]==0) {
vis[y.first]=1;
q.push(y.first);
}
}
}
}
}
for(int i=1;i<=m;i++) {
int c1,c2,y;
c1=read();c2=read();y=read();
e[c2].push_back(make_pair(c1,y));
}
for(int i=1;i<=n;i++) {
e[n+1].push_back(make_pair(i,0));
}
Tarjan
边双
void tarjan(int x,int fa) {
dfn[x]=low[x]=++tot;
for(auto y:e[x]) {
if(y.second==fa) continue;
if(dfn[y.first]) {
low[x]=min(low[x],dfn[y.first]);
}
else {
tarjan(y.first,y.second);
low[x]=min(low[x],low[y.first]);
if(low[y.first]>dfn[x]) {
bridge[y.second]=1;
}
}
}
}
void dfs(int x,int fa) {
vis[x]=1;
o[cnt].push_back(x);
for(auto y:e[x]) {
if(bridge[y.second]) continue;
if(vis[y.first]) continue;
dfs(y.first,x);
}
}
浙公网安备 33010602011771号