我要復(fù)習(xí)所有的模板
二分 gcd
int gcd(int a,int b) {
int az=__builtin_ctz(a), bz=__builtin_ctz(b), z=min(az,bz), dif;
b>>=bz;
while(a) {
a>>=az, dif=b-a;
az=__builtin_ctz(dif);
if(a<b) b=a;
a=dif<0?-dif:dif;
}
return b<<z;
}
異或多重集樹哈希
const ull mask=std::chrono::steady_clock::now().time_since_epoch().count();
int ull shift(ull x) {
x^=mask, x^=x<<13, x^=x>>7, x^=x<<17, x^=mask;
return x;
}
void dp(int x,int fa) {
int ms=0; siz[x]=1;
for(int y:to[x]) if(y^fa) dp(y,x), siz[x]+=siz[y], ms=max(ms,siz[y]);
ms=max(ms,n-siz[x]);
if(ms<=n/2) heart.pb(x);
}
void Hash(int x,int fa) {
hsh[x]=1;
for(int y:to[x]) if(y^fa) Hash(y,x), hsh[x]+=shift(hsh[y]);
trees.insert(hsh[x]);
}
heart.clear(), dp(1,0);
for(int rt:heart) {
trees.clear(), Hash(rt,0);
qwq=max(trees,qwq);
質(zhì)數(shù)樹哈希
int vis[M], p[M], top;
void init() {
int d=1299709;
up(i,2,d) if(!vis[i]) {
vis[i]=1, p[++top]=i;
up(j,2,d/i) vis[i*j]=1;
}
}
struct Tree {
int n, siz[N]; ull hsh[N]; vector<int> to[N];
void build(int x) { n=x; }
void eadd(int u,int v) { to[u].pb(v), to[v].pb(u); }
void Hash(int x,int fa) {
hsh[x]=1, siz[x]=1;
for(int y:to[x]) if(y^fa) Hash(y,x), siz[x]+=siz[y], hsh[x]+=hsh[y]*p[siz[y]];
}
void change(int x,int fa,int I) {
if(fa) hsh[x]=hsh[x]+p[n-siz[x]]*(hsh[fa]-hsh[x]*p[siz[x]]);
for(int y:to[x]) if(y^fa) change(y,x,I);
}
};
拓展歐幾里得
我們要求一組 \(ax+by=c\) 的解 \((x,y)\)，首先充要條件是 \(\gcd(x,y)|c\)，于是我們先在做歐幾里得的時(shí)候求解一組 \(ax+by=\gcd(a,b)\) 再簡(jiǎn)單乘即可。
\[ax_1+by_1=\gcd(a,b)=bx_2+(a\mod b)y_2
\]
\[=bx_2+(a-b\lfloor\frac{a}{b}\rfloor)y_2=ay_2+(x_2-\lfloor\frac{a}{b}\rfloor y_2)b
\]
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 t=x; x=y, y=t-a/b*y;
return d;
}
lnk，括歐還可以在模意義下部分還原分?jǐn)?shù)，具體見 P10383。
設(shè) \(g=\text{lcm}(a,b)\)，求出一組特解 \(ax_0+by_0=c\)，那么一元二次的通解形式是 \(a(x_0+\frac{g}{b}k)+b(y_0-\frac{g}{a}k)=c\)
線性篩素?cái)?shù)
埃氏篩一個(gè)合數(shù)被標(biāo)記次數(shù)沒有嚴(yán)格保證，我們考慮讓一個(gè)合數(shù)只被標(biāo)記一次，貢獻(xiàn)方式為「\(最小質(zhì)因子\times 常數(shù)\)」，那么一個(gè)常數(shù)要去成所有不超過其最小質(zhì)因子的素?cái)?shù)去貢獻(xiàn)。
int n, q, p[M], top; bool vis[N];
up(i,2,n) {
if(!vis[i]) p[++top]=i;
for(int j=1; j<=top&&i*p[j]<=n; ++j) {
int x=i*p[j]; vis[x]=1;
if(i%p[j]==0) break;
}
}
在素?cái)?shù)的位置帶 \(\log\) 總的復(fù)雜度仍然是 \(O(n)\)，因?yàn)橘|(zhì)數(shù)的冪總共只有 \(\frac{n}{\log n}\) 那么多。
歐拉篩線性遞推 歐拉/莫比烏斯 函數(shù)
分別照著定義式遞推即可，代碼包含在杜教篩那里 qwq
\[\phi(n)=n\prod_{p 是 n 的質(zhì)因子}\frac{p-1}{p}
\]
\[\mu(n)=\begin{cases}(-1)^{n 的質(zhì)因子數(shù)量}&n沒有平方因子\\0&otherwise\end{cases}
\]
杜教篩
具體過程如 lnk，因?yàn)槟甏⒉痪眠h(yuǎn)不再贅述。
數(shù)論函數(shù)求前綴和可以套杜教篩公式，計(jì)算 \(S(n)=\sum_{i=1}^n f(i)\)，不妨構(gòu)造 \(h(i)=\sum_{d|i}f(d)g(\frac{n}w0obha2h00)\)，然后套用公式 \(g(1)S(n)=\sum_{i=1}^n h(i)-\sum_{i=2}^n g(i)S(\lfloor\frac{n}{i}\rfloor)\)，整除分塊+記憶化復(fù)雜度 \(O(n^{\frac{3}{4}})\)，加上到 \(n^{\frac{2}{3}}\) 的預(yù)處理可以做到 \(O(n^{\frac{2}{3}})\)。
思想大概是什么考慮構(gòu)造卷積，然后考慮 \(f\) 對(duì) \(g\) 的貢獻(xiàn)發(fā)現(xiàn)是前綴和的形式，歐拉函數(shù)和莫比烏斯函數(shù)用 \(n=\sum_{d|n}\phi(d),[n=1]=\sum_{d|n}\mu(d)\) 來做（
int t, n, k=5e6;
int vis[N], p[N], top, phi[N], mu[N];
map<int,int> sphi, smu;
void init() {
vis[0]=vis[1]=phi[1]=mu[1]=1;
up(i,2,k) {
if(!vis[i]) p[++top]=i, phi[i]=i-1, mu[i]=-1;
for(int j=1; j<=top&&i*p[j]<=k; ++j) {
int x=i*p[j]; vis[x]=1;
if(i%p[j]) mu[x]=-mu[i], phi[x]=phi[i]*(p[j]-1);
else { mu[x]=0, phi[x]=phi[i]*p[j]; break; }
}
}
up(i,1,k) phi[i]+=phi[i-1], mu[i]+=mu[i-1];
}
int getphi(int x) {
if(x<=k) return phi[x];
if(sphi.find(x)!=sphi.end()) return sphi[x];
int res=(1+x)*x/2;
for(int l=2, r; l<=x; l=r+1) {
r=min(x,x/(x/l));
res-=(r-l+1)*getphi(x/l);
}
return sphi[x]=res;
}
int getmu(int x) {
if(x<=k) return mu[x];
if(smu.find(x)!=smu.end()) return smu[x];
int res=1;
for(int l=2, r; l<=x; l=r+1) {
r=min(x,x/(x/l));
res-=(r-l+1)*getmu(x/l);
}
return smu[x]=res;
}
康托展開
\[A_i=\sum_{j=i}^n[a_j<a_i],Ans=1+\sum_{i=1}^n A_i\times (n-i)!
\]
考慮比 \(a\) 小的排列數(shù)，枚舉 \(1,\dots,i-1\) 位相同，那么 \(a'_i<a_i\)，從后面拉一個(gè)上來，然后剩下的可以隨便排列。
差分約束
考慮一堆方程組形如 \(x_i+d\geq x_j\)，不妨寫成 \(i\to j:d\) 去跑最短路，無解就是存在負(fù)環(huán)（有點(diǎn) \(入隊(duì)次數(shù)>n\)）。
注意最短路去跑具有極大性，就是說每一個(gè) \(x\) 其實(shí)都盡量往極值去取了，天生極端化了字典序。
dfs spfa 判負(fù)環(huán)
負(fù)環(huán)從某個(gè)位置開始走可以一直都是負(fù)的，我們可以用這個(gè)來優(yōu)化常數(shù)，有些題目（比如 P3199）下這樣判斷跑的飛快。
int spfa(int x) {
vis[x]=1;
for(pii p:to[x]) {
int y=p.first; db val=p.second;
if(dis[x]+val<dis[y]) {
dis[y]=dis[x]+val;
if(vis[y]||spfa(y)) return 1;
}
}
vis[x]=0;
return 0;
}
bool check() {
up(i,1,n) dis[i]=vis[i]=0;
up(i,1,n) if(spfa(i)) return 1;
return 0;
}
無向圖 割邊/割點(diǎn) 判定法則
考慮隨便搜出一個(gè) dfs 樹，一個(gè) 邊/點(diǎn) 是不是割就看有沒有跨越的東西就行了，為了方便，不妨令 \(dfn/low\) 表示 時(shí)間戳/能回溯的最小時(shí)間戳，這樣只用比大小就能判斷了，注意割邊要判重。
一條邊 \((x,y)\) 在 \(low[y]>dfn[x]\) 是為割邊，一個(gè)點(diǎn)在有兒子 \(y\) 使得 \(low[y]\geq dfn[x]\) 時(shí)是割點(diǎn)，但是注意特判根，根的判定是具有多個(gè)兒子。
邊雙聯(lián)通分量
去掉割邊然后算聯(lián)通即可，然后重新建圖是簡(jiǎn)單東西。
#define num(x) ((x+1)>>1)
int n, m, tot, dfn[N], low[N], stamp, cut[M], gp[N], cnt;
vector<pair<int,int> > to[N];
void tarjan(int x,int lnk) {
dfn[x]=low[x]=++stamp;
for(pii p:to[x]) {
int y=p.first, i=p.second;
if(num(i)==num(lnk)) continue;
if(dfn[y]) low[x]=min(low[x],dfn[y]);
else {
tarjan(y,i), low[x]=min(low[x],low[y]);
if(low[y]>dfn[x]) cut[num(i)]=1;
}
}
}
void dfs(int x) {
for(pii p:to[x]) {
int y=p.first, i=p.second;
if(cut[num(i)]||gp[y]) continue;
gp[y]=cnt, dfs(y);
}
}
cin >> n >> m;
up(i,1,m) {
int u, v;
cin >> u >> v;
to[u].pb(mp(v,++tot));
to[v].pb(mp(u,++tot));
}
up(i,1,n) if(!dfn[i]) tarjan(i,0);
up(i,1,n) if(!gp[i]) gp[i]=++cnt, dfs(i);
點(diǎn)雙聯(lián)通分量、廣義圓方樹
首先點(diǎn)雙在搜索棧里面考慮就行了，建圖可以使用廣義圓方樹，就是對(duì)于每一個(gè)點(diǎn)雙建立一個(gè)方點(diǎn)，然后向所在的分量的圓點(diǎn)連邊，這樣子可以保證性質(zhì)不變，注意方點(diǎn)要開兩倍空間，重邊要特判。
int n, m, dfn[N], low[N], tot, stamp, stk[N], top;
vector<int> F[N], G[N<<1];
void tarjan(int x) {
dfn[x]=low[x]=++stamp, stk[++top]=x;
for(int y:F[x]) {
if(dfn[y]) low[x]=min(low[x],dfn[y]);
else {
tarjan(y), low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]) {
++tot; int p;
while(stk[top+1]!=y) {
p=stk[top--];
G[p].pb(tot), G[tot].pb(p);
}
G[tot].pb(x), G[x].pb(tot);
}
}
}
}
cin >> n >> m, tot=n;
up(i,1,m) {
int u, v; cin >> u >> v;
if(u!=v) F[u].pb(v), F[v].pb(u);
}
up(i,1,n) if(!dfn[i]) tarjan(i);
強(qiáng)聯(lián)通分量
其實(shí)可以不寫 tarjan，正圖做一次 dfs 記錄回溯時(shí)間壓入棧，按照回溯時(shí)間大到小在反圖上搜出強(qiáng)聯(lián)通分量，應(yīng)該很好理解。
int n, m, stk[N], top, gp[N], cnt, vis[N], p;
vector<int> F[N], G[N];
void dfs(int x) {
vis[x]=1;
for(int y:F[x]) if(!vis[y]) dfs(y);
stk[++top]=x;
}
void stain(int x) {
for(int y:G[x]) if(!gp[y]) gp[y]=cnt, stain(y);
}
cin >> n >> m;
up(i,1,m) {
int u, v; cin >> u >> v;
F[u].pb(v), G[v].pb(u);
}
up(i,1,n) if(!vis[i]) dfs(i);
dn(i,n,1) if(!gp[p=stk[i]]) gp[p]=++cnt, stain(p);
網(wǎng)絡(luò)最大流
建出反邊，每次找出增廣路流，是一個(gè)分層圖最短路。
注意有些題目需要 \(\infty\) 的連邊，但是不能給初始流量的 \(\infty\uparrow\) 不然會(huì)不夠流。
int n, m, s, t, dis[N], maxflow, cur[N];
int hd[N], nxt[M], eg[M], to[M], tot=1, fl;
queue<int> q;
void eadd(int u,int v,int w) {
to[++tot]=v, eg[tot]=w;
nxt[tot]=hd[u], hd[u]=tot;
}
bool bfs() {
up(i,1,n) dis[i]=0;
while(q.size()) q.pop();
dis[s]=1, q.push(s);
while(q.size()) {
int x=q.front(); q.pop();
for(int i=hd[x]; i; i=nxt[i]) {
int y=to[i], w=eg[i];
if(w&&!dis[y]) dis[y]=dis[x]+1, q.push(y);
}
}
return dis[t];
}
int dfs(int x,int sum) {
if(x==t) return sum;
int res=0;
for(int i=cur[x]; i&∑ i=nxt[i]) {
cur[x]=i;
int y=to[i], w=eg[i];
if(w&&dis[x]+1==dis[y]) {
int k=dfs(y,min(sum,w));
if(!k) dis[y]=0;
eg[i]-=k, eg[i^1]+=k, res+=k, sum-=k;
}
}
return res;
}
int getflow() {
while(bfs()) {
up(i,1,n) cur[i]=hd[i];
maxflow+=dfs(s,inf);
}
return maxflow;
}
費(fèi)用流
int n, m, s, t, dis[N], in[N], maxflow, mincost;
int hd[N], nxt[M], eg[M], to[M], lv[M], tot=1, cur[N];
queue<int> q;
inline void fadd(int u,int v,int w,int l) { to[++tot]=v, eg[tot]=w, lv[tot]=l, nxt[tot]=hd[u], hd[u]=tot; }
void eadd(int u,int v,int w,int l) { fadd(u,v,w,l), fadd(v,u,0,-l); }
int spfa() {
int flag=0;
up(i,1,n) dis[i]=inf;
dis[s]=0, q.push(s), in[s]=1;
while(q.size()) {
int x=q.front(); q.pop();
flag|=(x==t), in[x]=0;
for(int i=hd[x]; i; i=nxt[i]) {
int y=to[i], w=eg[i], v=lv[i];
if(w&&dis[x]+v<dis[y]) {
dis[y]=dis[x]+v;
if(!in[y]) in[y]=1, q.push(y);
}
}
}
return flag;
}
int dfs(int x,int sum) {
if(x==t) return sum;
in[x]=1; int res=0;
for(int i=cur[x]; i&∑ i=nxt[i]) {
cur[x]=i;
int y=to[i], w=eg[i], v=lv[i];
if(!in[y]&&w&&dis[x]+v==dis[y]) {
int k=dfs(y,min(sum,w));
if(k) eg[i]-=k, eg[i^1]+=k, res+=k, sum-=k, mincost+=k*v;
}
}
in[x]=0;
return res;
}
int getflow() {
while(spfa()) {
up(i,1,n) cur[i]=hd[i];
maxflow+=dfs(s,inf);
}
}
FFT
#include<bits/stdc++.h>
#define db double
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
using namespace std;
const db pi=acos(-1);
const int N=2145141;
int n, m, tr[N];
struct cp { db x, y; } f[N], g[N], sav[N];
typedef const cp ccp;
cp operator+(ccp &a,ccp &b) { return (cp){a.x+b.x,a.y+b.y}; }
cp operator-(ccp &a,ccp &b) { return (cp){a.x-b.x,a.y-b.y}; }
cp operator*(ccp &a,ccp &b) { return (cp){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x}; }
void fft(cp *f,bool op) {
up(i,0,n-1) if(i<tr[i]) swap(f[i],f[tr[i]]);
for(int p=2; p<=n; p<<=1) {
int len=p>>1;
cp tG=(cp){cos(2*pi/p),sin(2*pi/p)};
if(!op) tG.y*=-1;
for(int k=0; k<n; k+=p) {
cp buf=(cp){1,0};
up(l,k,k+len-1) {
cp tt=buf*f[len+l];
f[len+l]=f[l]-tt, f[l]=f[l]+tt;
buf=buf*tG;
}
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
up(i,0,n) cin >> f[i].x;
up(i,0,m) cin >> g[i].x;
for(m+=n, n=1; n<=m; n<<=1);
up(i,0,n-1) tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
fft(f,1), fft(g,1);
up(i,0,n-1) f[i]=f[i]*g[i];
fft(f,0);
up(i,0,m) cout << (int)(f[i].x/n+0.49) << ' ';
return 0;
}
FFT（三次變兩次）
#include<bits/stdc++.h>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define db double
using namespace std;
const db pi=acos(-1);
struct cp { db x, y; };
typedef const cp ccp;
cp operator+(ccp &a,ccp &b) { return (cp){a.x+b.x,a.y+b.y}; }
cp operator-(ccp &a,ccp &b) { return (cp){a.x-b.x,a.y-b.y}; }
cp operator*(ccp &a,ccp &b) { return (cp){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x}; }
vector<cp> w[20];
void init(int m) {
for(int i=1; (1<<i)<=m; ++i) {
int n=(1<<i); w[i].resize(n>>1);
up(j,0,(n>>1)-1) w[i][j]=(cp){cos(2*j*pi/n),sin(2*j*pi/n)};
}
}
void dft(vector<cp> &f) {
int n=f.size();
if(n==1) return;
vector<cp> f0(n>>1), f1(n>>1);
up(i,0,n-1) if(i&1) f1[i>>1]=f[i]; else f0[i>>1]=f[i];
dft(f0), dft(f1);
int id=0; while((1<<id)<n) ++id;
up(i,0,(n>>1)-1) {
cp tmp=w[id][i]*f1[i];
f[i]=f0[i]+tmp, f[i+(n>>1)]=f0[i]-tmp;
}
}
void idft(vector<cp> &f) {
int n=f.size();
dft(f), reverse(&f[1],&f[n]);
up(i,0,n-1) f[i].x/=n, f[i].y/=n;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, N=1;
cin >> n >> m;
while(N<=n+m) N<<=1;
init(N); vector<cp> f(N);
up(i,0,n) cin >> f[i].x;
up(i,0,m) cin >> f[i].y;
dft(f);
up(i,0,N-1) f[i]=f[i]*f[i];
idft(f);
up(i,0,n+m) {
int res=f[i].y*0.5+0.1;
cout << res << ' ';
}
return 0;
}
NTT
lnk，常見素?cái)?shù)及其原根。
#include<bits/stdc++.h>
#define int long long
#define db long double
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
using namespace std;
const int P=998244353, G=3, N=1350000;
int ksm(int a,int b=P-2) {
int res=1;
for( ; b; b>>=1) {
if(b&1) res=res*a%P;
a=a*a%P;
}
return res;
}
int n, m, tr[N<<1], f[N<<1], g[N<<1], invn, invG=ksm(G);
void NTT(int *f,bool op) {
up(i,0,n-1) if(i<tr[i]) swap(f[i],f[tr[i]]);
for(int p=2; p<=n; p<<=1) {
int len=p>>1, tG=ksm(op?G:invG,(P-1)/p);
for(int k=0; k<n; k+=p) {
int buf=1;
up(l,k,k+len-1) {
int tt=buf*f[len+l]%P;
f[len+l]=f[l]-tt;
if(f[len+l]<0) f[len+l]+=P;
f[l]=f[l]+tt;
if(f[l]>P) f[l]-=P;
buf=buf*tG%P;
}
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m, ++n, ++m;
up(i,0,n-1) cin >> f[i];
up(i,0,m-1) cin >> g[i];
for(m+=n, n=1; n<m; n<<=1);
up(i,0,n-1) tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(f,1), NTT(g,1);
up(i,0,n-1) f[i]=f[i]*g[i]%P;
NTT(f,0), invn=ksm(n);
up(i,0,m-2) cout << f[i]*invn%P << ' ';
return 0;
}
Splay 平衡樹
#include<bits/stdc++.h>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
using namespace std;
inline int read() {
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
const int N=8000005, inf=1<<30;
int tot, root, fa[N], son[N][2], val[N], cnt[N], siz[N];
void build() {
tot=2, val[1]=inf, val[2]=-inf;
son[1][0]=2, root=fa[2]=1;
}
void upt(int x) { siz[x]=cnt[x]+siz[son[x][0]]+siz[son[x][1]]; }
void rotato(int x) {
int y=fa[x], z=fa[y];
if(z) son[z][son[z][1]==y]=x; fa[x]=z;
bool k=(son[y][1]==x);
son[y][k]=son[x][k^1], fa[son[x][k^1]]=y;
son[x][k^1]=y, fa[y]=x;
upt(y), upt(x), upt(z);
}
void splay(int x,int goal) {
while(fa[x]!=goal) {
int y=fa[x], z=fa[y];
if(z!=goal) (x==son[y][0])^(y==son[z][0])?rotato(x):rotato(y);
rotato(x);
}
if(!goal) root=x;
}
void find(int v) {
int x=root;
while(val[x]!=v&&son[x][v>val[x]]) x=son[x][v>val[x]];
splay(x,0);
}
void Insert(int v) {
int x=root, fad=0;
while(x&&val[x]!=v) fad=x, x=son[x][v>val[x]];
if(x) ++cnt[x];
else {
x=++tot;
if(fad) son[fad][v>val[fad]]=x, fa[x]=fad;
val[x]=v, cnt[x]=1;
}
splay(x,0);
}
int Next(int v,int f) {
find(v);
int x=root;
if((val[x]<v&&!f)||(val[x]>v&&f)) return x;
x=son[x][f];
while(son[x][f^1]) x=son[x][f^1];
splay(x,0);
return x;
}
void Delete(int v) {
int pre=Next(v,0), nxt=Next(v,1);
splay(pre,0), splay(nxt,pre);
int del=son[nxt][0];
if(val[del]!=v) return;
if(cnt[del]>1) --cnt[del], splay(del,0);
else son[nxt][0]=0, splay(nxt,0);
}
int kth(int v) {
int x=root;
if(siz[x]<v) return 0;
while(1) {
int y=son[x][0];
if(v>siz[y]+cnt[x]) v-=siz[y]+cnt[x], x=son[x][1];
else {
if(siz[y]>=v) x=y;
else {
splay(x,0);
return val[x];
}
}
}
}
int Rank(int v) {
int pre=Next(v,0);
splay(pre,0);
return siz[son[pre][0]]+cnt[pre]+1;
}
signed main() {
build();
int n, m, opt, x, lst=0, Ans=0;
n=read(), m=read();
while(n--) Insert(read());
while(m--) {
opt=read(), x=read()^lst;
if(opt==1) Insert(x);
if(opt==2) Delete(x);
if(opt==3) lst=Rank(x), Ans^=lst;
if(opt==4) lst=kth(x), Ans^=lst;
if(opt==5) lst=val[Next(x,0)], Ans^=lst;
if(opt==6) lst=val[Next(x,1)], Ans^=lst;
}
cout << Ans;
return 0;
}
Splay 區(qū)間反轉(zhuǎn)
#include<bits/stdc++.h>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
using namespace std;
inline int read() {
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
const int N=8000005, inf=1<<30;
int n, m;
int son[N][2], siz[N], root, tag[N], fa[N];
void build(int n) {
root=1;
up(i,2,n) fa[i]=i-1, son[i-1][1]=i;
up(i,1,n) siz[i]=n-i+1;
}
inline void tup(int x) {
siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
}
inline void tagrev(int x) {
tag[x]^=1, swap(son[x][0],son[x][1]);
}
void tdn(int x) {
if(tag[x]) tagrev(son[x][0]), tagrev(son[x][1]), tag[x]=0;
}
void rotato(int x) {
int y=fa[x], z=fa[y];
if(z) son[z][son[z][1]==y]=x; fa[x]=z;
bool k=(son[y][1]==x);
son[y][k]=son[x][k^1], fa[son[x][k^1]]=y;
son[x][k^1]=y, fa[y]=x;
tup(y), tup(x); if(z) tup(z);
}
void splay(int x,int goal) {
while(fa[x]!=goal) {
int y=fa[x], z=fa[y];
if(z!=goal) (x==son[y][0])^(y==son[z][0])?rotato(x):rotato(y);
rotato(x);
}
if(!goal) root=x;
}
int kth(int v) {
int x=root;
while(1) {
tdn(x);
int y=son[x][0];
if(v>siz[y]+1) v-=siz[y]+1, x=son[x][1];
else {
if(siz[y]>=v) x=y;
else {
splay(x,0);
return x;
}
}
}
}
void flip(int l,int r) {
int L=kth(l-1), R=kth(r+1);
splay(L,0), splay(R,L), tagrev(son[son[L][1]][0]);
}
void dfs(int x) {
tdn(x);
if(son[x][0]) dfs(son[x][0]);
if(1<x&&x<n) cout << x-1 << ' ';
if(son[x][1]) dfs(son[x][1]);
}
signed main() {
build(n=read()+2), m=read();
while(m--) {
int l, r;
l=read()+1, r=read()+1;
flip(l,r);
}
dfs(root);
return 0;
}
后綴數(shù)組
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
using namespace std;
const int N=1000100;
int n, m, x[N], y[N], c[N], sa[N];
char s[N];
void SA() {
m=122;
up(i,1,m) c[i]=0;
up(i,1,n) x[i]=s[i], c[x[i]]++;
up(i,2,m) c[i]+=c[i-1];
up(i,1,n) sa[c[x[i]]--]=i;
for(int k=1; k<=n; k<<=1) {
int num=0;
up(i,n-k+1,n) y[++num]=i;
up(i,1,n) if(sa[i]>k) y[++num]=sa[i]-k;
up(i,1,m) c[i]=0;
up(i,1,n) c[x[i]]++;
up(i,2,m) c[i]+=c[i-1];
dn(i,n,1) sa[c[x[y[i]]]--]=y[i];
up(i,1,n) y[i]=x[i], x[i]=0;
num=1, x[sa[1]]=1;
up(i,2,n) {
if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=num;
else x[sa[i]]=++num;
}
if(num==n) break; m=num;
}
}
signed main() {
scanf("%s", s+1), n=strlen(s+1);
SA();
up(i,1,n) cout << sa[i] << ' ';
return 0;
}
KMP
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
using namespace std;
const int N=1000100;
int n, m, f[N], g[N], j;
char a[N], b[N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> (b+1), cin >> (a+1);
m=strlen(b+1), n=strlen(a+1);
up(i,2,n) {
while(j&&a[j+1]!=a[i]) j=g[j];
j+=(a[j+1]==a[i]), g[i]=j;
}
j=0;
up(i,1,m) {
while(j&&(a[j+1]!=b[i]||j==n)) j=g[j];
j+=(a[j+1]==b[i]), f[i]=j;
if(f[i]==n) cout << i-n+1 << '\n';
}
up(i,1,n) cout << g[i] << ' ';
return 0;
}
2-SAT
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_back
using namespace std;
const int N=2000010, M=2000010;
int n, m, vis[N], dfn[N], low[N], tc, cnt, bel[N];
int hd[N], nxt[M], to[M], tot=1, stk[N], top;
void eadd(int u,int v) { nxt[++tot]=hd[u], hd[u]=tot, to[tot]=v; }
void tarjan(int x) {
low[x]=dfn[x]=++tc;
vis[x]=1, stk[++top]=x;
for(int i=hd[x]; i; i=nxt[i]) {
int y=to[i];
if(vis[y]==2) continue;
if(!vis[y]) tarjan(y);
low[x]=min(low[x],low[y]);
}
if(dfn[x]==low[x]) {
int p; ++cnt;
while(stk[top+1]!=x) {
p=stk[top--];
vis[p]=2, bel[p]=cnt;
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
up(k,1,m) {
int i, a, j, b, l, r;
cin >> i >> a >> j >> b;
l=(2*i)^(!a), r=(2*j)^(!b);
eadd(l^1,r), eadd(r^1,l);
}
up(i,2,2*n+1) if(!dfn[i]) tarjan(i);
up(i,1,n) if(bel[2*i]==bel[(2*i)^1]) { cout << "IMPOSSIBLE"; return 0; }
cout << "POSSIBLE\n";
up(i,1,n) if(bel[2*i]<bel[(2*i)^1]) cout << 1 << ' '; else cout << 0 << '\n';
return 0;
}
線性基
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_back
using namespace std;
const int N=111;
int n, a, mg[N];
void add(int x) {
dn(i,60,0) if(x>>i&1) {
if(mg[i]) x=x^mg[i];
else { mg[i]=x; break; }
}
}
int ask() {
int res=0;
dn(i,60,0) if((res^mg[i])>>i&1)
res=res^mg[i];
return res;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
up(i,1,n) cin >> a, add(a);
cout << ask();
return 0;
}
歐拉回路
#include<bits/stdc++.h>
#define int long long
#define ldb long double
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_back
using namespace std;
const int N=500005;
int n, m, in[N], out[N], cur[N], s, t;
vector<int> F[N], Ans;
void dfs(int x) {
for(int i=cur[x]; i<F[x].size(); i=cur[x])
++cur[x], dfs(F[x][i]);
Ans.pb(x);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
up(i,1,m) {
int u, v;
cin >> u >> v;
++out[u], ++in[v];
F[u].pb(v);
}
up(i,1,n) {
if(in[i]+1==out[i]&&!s) s=i;
else if(out[i]+1==in[i]&&!t) t=i;
else if(in[i]!=out[i]) { cout << "No"; return 0; }
}
up(i,1,n) sort(F[i].begin(),F[i].end());
dfs(max(1ll,s));
dn(i,Ans.size()-1,0) cout << Ans[i] << ' ';
return 0;
}
高斯消元
#include<bits/stdc++.h>
#define db double
#define up(i,l,r) for(register int i=l; i<=r; ++i)
#define dn(i,r,l) for(register int i=r; i>=l; --i)
using namespace std;
const int N=105;
int n; db g[N][N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
up(i,1,n) up(j,1,n+1) cin >> g[i][j];
up(i,1,n) {
int now=i;
up(j,i+1,n) if(fabs(g[now][i])<fabs(g[j][i])) now=j;
up(j,i,n+1) swap(g[now][j],g[i][j]);
if(g[i][i]==0) { cout << "No Solution"; return 0; }
up(j,i+1,n+1) g[i][j]/=g[i][i];
g[i][i]=1;
up(j,i+1,n) {
up(k,i+1,n+1) g[j][k]-=g[j][i]*g[i][k];
g[j][i]=0;
}
}
dn(i,n,1) {
up(j,i+1,n) {
g[i][n+1]-=g[i][j]*g[j][n+1];
g[i][j]=0;
}
g[i][n+1]/=g[i][i], g[i][i]=1;
}
up(i,1,n) cout << fixed << setprecision(2) << g[i][n+1] << '\n';
return 0;
}
浙公網(wǎng)安備 33010602011771號(hào)