# 競賽模板
ac自动机fail树上dfs序建可持久化线段树
后缀自动机的next指针DAG图上求SG函数
## 一些數
### 質數
999961
999979
999983
998244353
1000000009
1000000007
### 黃金比例常數
0x9e3779b97f4a7c15ULL
## DP
### 0/1Knapsack
#### 重量限制小
```cpp
for(int i=1;i<=n;++i) cin>>w[i]>>v[i];
for(int i=1;i<=n;++i){
for(int j=m;j>=w[i];--j){
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[m]<<endl;
```
#### 重量限制大、物品價值小
```cpp
for(int i=1;i<=n;++i) cin>>w[i]>>v[i];
for(int i=1;i<maxn;++i) dp[i] = inf;
for(int i=1;i<=n;++i){
for(int j=maxn-1;j>=v[i];--j){
dp[j] = min(dp[j],dp[j-v[i]]+w[i]);
}
}
for(int i=maxn-2;i>=1;--i){
if(dp[i] <= m) {cout<<i<<endl; break; }
}
```
### 有限背包 O(NM) 單調對列優化
```cpp
for(int i=1;i<=n;++i){
for(int mod = 0;mod<p[i].w;++mod){
Q.clear();
for(int j=mod;j <= T;j += p[i].w){
val[j] = dp[j] - (j/p[i].w)*p[i].v;
while(!Q.empty() && val[Q.back()] <= val[j])
Q.pop_back();
Q.push_back(j);
dp[j] = val[Q.front()] + (j/p[i].w)*p[i].v;
if(Q.front() == j-p[i].w*p[i].c)
Q.pop_front();
}
}
}
```
### LCS (回朔解)
```cpp
ls = s.size(), lt = t.size();
s = ' '+s, t = ' '+t;
for(int i=1;i<=ls;++i){
for(int j=1;j<=lt;++j){
if(s[i] == t[j]) dp[i][j] = dp[i-1][j-1] + 1, d[i][j] = 1;
else dp[i][j] = max(dp[i-1][j],dp[i][j-1]), d[i][j] = (dp[i-1][j] > dp[i][j-1])?2:3;
}
}
int x = ls,y = lt;
while(x >= 1 && y >= 1){
if(d[x][y] == 1) as += s[x], x--, y--;
else if(d[x][y] == 2) x--;
else y--;
}
reverse(as.begin(),as.end());
cout<<as<<endl;
```
### LIS (嚴格遞增)
```cpp
for(int i=1;i<=n;++i){
if(dp.empty() || arr[i] > dp.back()){
dp.push_back(arr[i]);
}else{
auto it = lower_bound(dp.begin(),dp.end(),arr[i]);
*it = arr[i];
}
}
lis = dp.size();
```
### 回朔 LIS (非嚴格遞增)
```cpp
for(int i=1;i<=n;++i){
if(dp.empty() || dp.back() <= p[i]){
dp.push_back(p[i]);
int tmp = dp.size();
id[tmp] = i;
if(tmp > 1) pre[i] = id[tmp-1];
}else{
int it = upper_bound(dp.begin(),dp.end(),p[i])-dp.begin();
dp[it] = p[i];
it++;
id[it] = i;
if(it > 1) pre[i] = id[it-1];
}
}
int len = dp.size();
int pos = id[len];
vector<int> tmp;
tmp.push_back(id[len]);
for(int i=1;i<len;++i){
pos = pre[pos];
tmp.push_back(pos);
}
reverse(tmp.begin(),tmp.end());
```
### 樹背包
```cpp
const LL mod = 998244353;
LL n,dp[maxn][maxn][.];
int sz[maxn];
vector<int> E[maxn];
void dfs(int x,int p){
sz[x] = 1;
// init
for(int i:E[x]){
if(i==p) continue;
dfs(i,x);
int oS = sz[x];
int C = sz[i];
sz[x] += sz[i];
int S = sz[x];
vector<LL> s0(S+1),s1(S+1); // 算極值要初始化
for(int a=0;a<=oS;++a){
for(int b=0;b<=C;++b){
// update
}
}
for(int k=0;k<=S;++k){
dp[x][k][.] = s0[k];
dp[x][k][.] = s1[k];
}
}
}
```
### 迴圈式數位DP
ex : ABC235F
```cpp
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'
const LL inf = 1e18, maxn = 200005, mod = 998244353;
int n,m,reqmask;
LL pres,premask;
string s;
inline void add(LL &x,const LL&a){
x = (x+a)%mod;
}
main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>s>>m;
for(int i=1;i<=m;++i){
int a; cin>>a;
reqmask |= (1<<a);
}
n = s.size();
vector<LL> dps(1<<10),dpc(1<<10);
for(int d=0;d<n;++d){
vector<LL> nds(1<<10),ndc(1<<10);
for(int S=1;S<(1<<10);++S){
for(int i=0;i<=9;++i){
int nm = S|(1<<i);
add(ndc[nm],dpc[S]);
add(nds[nm],(dps[S]*10%mod+i*dpc[S]%mod)%mod);
}
}
if(d!=0){
for(int i=1;i<=9;++i){
int nm = (1<<i);
add(ndc[nm],1);
add(nds[nm],i);
}
}
int c = s[d]-'0';
for(int i=(d==0?1:0);i<c;++i){
int nm = premask|(1<<i);
add(ndc[nm],1);
add(nds[nm],(pres*10%mod+i)%mod);
}
dps.swap(nds);
dpc.swap(ndc);
premask |= (1<<c);
pres = (pres*10%mod+c)%mod;
}
LL as = 0;
for(int i=1;i<(1<<10);++i){
if((i&reqmask) == reqmask) add(as,dps[i]);
}
if((premask&reqmask) == reqmask) add(as,pres);
cout<<as<<endl;
}
```
### 無分支版 SOS
```cpp
for(int i=0;i<D;++i){
int tmp = (1<<i);
for(int j=0;j<(1<<D);j+=(tmp<<1)){
for(int k=0;k<tmp;++k){
dp[k+j+tmp] += dp[k+j];
}
}
}
```
## 圖論
### MST (prim) O(ElogV)
```cpp
int primMST(int s){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> Q;
bitset<maxn> vi;
Q.push({0,s});
int sum = 0;
while(!Q.empty()){
auto x = Q.top(); Q.pop();
if(vi[x.second]) continue;
sum += x.first;
vi[x.second] = 1;
for(auto i:E[x.second]){
if(!vi[i.first]) Q.push({i.second,i.first});
}
}
return sum;
}
```
### MST (prim) O(n^2) 用於完全圖
dis[i] : i到MST的最小距離
```cpp
for(int i=1;i<=n;++i) dis[i] = inf;
int as = 0, id = 1;
dis[1] = 0;
for(int i=1;i<=n;++i){
vi[id] = 1;
for(int j=1;j<=n;++j){
if(vi[j]) continue;
dis[j] = min(dis[j],cal(id,j));
}
int mn = inf;
as += dis[id];
for(int j=1;j<=n;++j){
if(vi[j]) continue;
if(dis[j] < mn){
mn = dis[j];
id = j;
}
}
}
```
### 拓譜排序
```cpp
void dfs(int x){
vi[x] = 1;
for(int i:E[x]) nif(!vi[i]) dfs(i);
tp.push_back(x);
}
main(){
cin>>n>>m;
for(int i=0;i<m;++i){
int a,b; cin>>a>>b;
E[a].push_back(b);
}
for(int i=1;i<=n;++i) if(!vi[i]) dfs(i);
reverse(tp.begin(),tp.end());
}
```
### 二分圖最大匹配
```cpp
int n,k,ma[maxn],mb[maxn];
vector<int> E[maxn];
bitset<maxn> vi;
bool dfs(int x){
vi[x] = 1;
for(int i:E[x]){
if(!~mb[i] || (!vi[mb[i]] && dfs(mb[i]))){
ma[x] = i;
mb[i] = x;
return 1;
}
}
return 0;
}
main(){
for(int i=1;i<=n;++i) ma[i] = mb[i] = -1;
int as = 0;
for(int i=1;i<=n;++i){
vi.reset();
if(dfs(i)) as++;
}
}
```
### SPFA
if(!Q.empty() && cost[i.v] < cost[Q.front()]) Q.push_front(i.v);
else Q.push_back(i.v);
優化
```cpp
void SPFA(int s){
for(int i=1;i<=n;++i) cnt[i] = in[i] = 0, dis[i] = inf;
queue<int> Q;
Q.push(s); in[s] = 1;
dis[s] = 0;
while(!Q.empty()){
int x = Q.front(); Q.pop();
in[x] = 0;
if(++cnt[x] >= n){
cout<<"find nag"<<endl;
}
for(auto i:E[x]) if(dis[x]+i.second < dis[i.first]){
dis[i.first] = dis[x] + i.second;
if(!in[i.first]) Q.push(i.first), in[i.first] = 1;
}
}
}
```
### dij
```cpp!
struct comp{
bool operator()(const pair<int,int>&a,const pair<int,int>&b){
return a.second > b.second;
}
};
priority_queue<pair<int,int>,vector<pair<int,int>>,comp> Q;
vector<pair<int,int>> E[maxn];
bitset<maxn> vi;
void dij(int s,int dis[]){
for(int i=1;i<=n;++i) dis[i] = inf;
dis[s] = 0;
Q.push({s,0});
vi.reset();
while(!Q.empty()){
auto x = Q.top(); Q.pop();
if(vi[x.first]) continue;
vi[x.first] = 1;
for(auto i:E[x.first]){
if(vi[i.first]) continue;
if(dis[i.first] > dis[x.first]+i.second){
dis[i.first] = dis[x.first] + i.second;
Q.push({i.first,dis[i.first]});
}
}
}
}
```
### 歐拉迴路 / 路徑
```cpp
void dfs(int x){
vi[x] = 1;
while(!E[x].empty()){
int i = *E[x].begin();
E[x].erase(i);
E[i].erase(x);
cnt++;
dfs(i);
}
as.push_back(x);
}
```
### SCC (Kosaraju's Algorithm)
```cpp
int n,m,sn,scc[maxn];
vector<int> E[maxn],pE[maxn],tp;
bitset<maxn> vi;
void dfs1(int x){
vi[x] = 1;
for(int i:E[x]){
if(!vi[i]) dfs1(i);
}
tp.push_back(x);
}
void dfs2(int x){
scc[x] = sn;
for(int i:pE[x]){
if(!scc[i]) dfs2(i);
}
}
main(){
cin>>n>>m;
for(int i=1;i<=m;++i){
int a,b; cin>>a>>b;
E[a].push_back(b);
pE[b].push_back(a);
}
for(int i=1;i<=n;++i) if(!vi[i]) dfs1(i);
reverse(tp.begin(),tp.end());
for(int i=0;i<n;++i){
if(!scc[tp[i]]){
sn++;
dfs2(tp[i]);
}
}
}
```
### 關節點
```cpp
int n,m,dfn[maxn],low[maxn],timer,isap[maxn];
vector<int> E[maxn];
void dfs(int x,int p){
dfn[x] = low[x] = ++timer;
int cnt = 0;
for(int i:E[x]){
if(i == p) continue;
if(!dfn[i]){
cnt++;
dfs(i,x);
low[x] = min(low[x],low[i]);
if(low[i] >= dfn[x] && p!=0){
isap[x] = 1;
}
}else if(dfn[i] < dfn[x]){
low[x] = min(low[x],dfn[i]);
}
}
if(p==0 && cnt >= 2){
as.push_back(1);
}
}
```
### 橋
```cpp
int n,m,dfn[maxn],low[maxn],timer;
vector<int> E[maxn];
vector<pair<int,int>> br;
void dfs(int x,int p){
low[x] = dfn[x] = ++timer;
for(int i:E[x]){
if(i == p) continue;
if(!dfn[i]){
dfs(i,x);
low[x] = min(low[x],low[i]);
if(low[i] > dfn[x]){
br.push_back({i,x});
}
}else if(dfn[i] < dfn[x]){
low[x] = min(low[x],dfn[i]);
}
}
}
```
### 邊雙連通分量
E[x].first : 點編號
E[x].second : 邊編號
```cpp
int n,m,dfn[maxn],low[maxn],timer,bcnt,bcc[maxn]; // 這個點屬於哪個bcc
vector<pair<int,int>> E[maxn];
vector<int> inbcc[maxn]; // 這個bcc有哪些點
stack<int> st;
void dfs(int x,int p){
low[x] = dfn[x] = ++timer;
st.push(x);
for(auto i:E[x]){
if(i.second == p) continue;
if(!dfn[i.first]){
dfs(i.first,i.second);
low[x] = min(low[x],low[i.first]);
if(low[i.first] > dfn[x]){
bcnt++;
while(st.top() != i.first)
bcc[st.top()] = bcnt, inbcc[bcnt].push_back(st.top()), st.pop();
bcc[st.top()] = bcnt, inbcc[bcnt].push_back(st.top()), st.pop();
}
}else if(dfn[i.first] < dfn[x]){
low[x] = min(low[x],dfn[i.first]);
}
}
if(p == 0){
bcnt++;
while(st.top() != x)
bcc[st.top()] = bcnt, inbcc[bcnt].push_back(st.top()), st.pop();
bcc[st.top()] = bcnt, inbcc[bcnt].push_back(st.top()), st.pop();
}
}
```
### 點雙連通分量
```cpp
void dfs(int x,int p){
low[x] = dfn[x] = ++timer;
st.push(x);
for(int i:E[x]){
if(i == p) continue;
if(!dfn[i]){
dfs(i,x);
low[x] = min(low[x],low[i]);
if(low[i] >= dfn[x]){
bcnt++;
ap[x] = 1;
while(st.top() != i){
in_bcc[st.top()].push_back(bcnt); bcc[bcnt].push_back(st.top());
st.pop();
}
in_bcc[st.top()].push_back(bcnt); bcc[bcnt].push_back(st.top());
st.pop();
in_bcc[x].push_back(bcnt);
bcc[bcnt].push_back(x);
}
}else if(dfn[i] < dfn[x]){
low[x] = min(low[x],dfn[i]);
}
}
}
```
### Block-Cut Tree (點雙縮點)
```cpp
vector<int> E[maxn],bE[maxn*2];
int n,m,q,low[maxn],dfn[maxn],timer,ap[maxn],bcnt;
vector<int> bcc[maxn],in_bcc[maxn];
stack<int> st;
void dfs(int x,int p){
low[x] = dfn[x] = ++timer;
st.push(x);
for(int i:E[x]){
if(i == p) continue;
if(!dfn[i]){
dfs(i,x);
low[x] = min(low[x],low[i]);
if(low[i] >= dfn[x]){
bcnt++;
ap[x] = 1;
while(st.top() != i){
in_bcc[st.top()].push_back(bcnt); bcc[bcnt].push_back(st.top());
st.pop();
}
in_bcc[st.top()].push_back(bcnt); bcc[bcnt].push_back(st.top());
st.pop();
in_bcc[x].push_back(bcnt);
bcc[bcnt].push_back(x);
}
}else if(dfn[i] < dfn[x]){
low[x] = min(low[x],dfn[i]);
}
}
}
main(){
cin>>n>>m>>q;
for(int i=1;i<=m;++i){
int a,b; cin>>a>>b;
E[a].push_back(b);
E[b].push_back(a);
}
dfs(1,0);
for(int i=1;i<=n;++i){
if(in_bcc[i].size()>1){
for(int j:in_bcc[i]){
bE[i+bcnt].push_back(j);
bE[j].push_back(i+bcnt);
}
}
}
}
```
### 線段樹優化建圖
```cpp!
#define maxn 100005
const int D = maxn*4;
int n,m,to[maxn];
vector<pair<int,int>> E[maxn*8];
void build(int l,int r,int x){
if(l==r){
to[l] = x;
E[x].push_back({x+D,0});
E[x+D].push_back({x,0});
return;
}
int ls = x*2 ,rs = ls+1,mid = (l+r)/2;
E[x].push_back({ls,0}); E[x].push_back({rs,0});
E[ls+D].push_back({x+D,0}); E[rs+D].push_back({x+D,0});
build(l,mid,ls);
build(mid+1,r,rs);
}
void modify(int a,int b,int l,int r,int x,int v,int w,int op){
if(l>=a&&r<=b){
if(!op) E[x+D].push_back({to[v],w});
else E[to[v]].push_back({x,w});
return;
}
int ls = x*2, rs = ls+1, mid = (l+r)/2;
if(mid >= a) modify(a,b,l,mid,ls,v,w,op);
if(mid < b) modify(a,b,mid+1,r,rs,v,w,op);
}
```
### Dinic’s Algorithm
```cpp
struct EDG{
int v,f,re;
};
int n,m,st,ed,it,d[maxn];
vector<int> E2[maxn];
inline void con(int a,int b,int c){
E[a].push_back({b,c,(int)E[b].size()});
E[b].push_back({a,0,(int) E[a].size()-1});
}
bool bfs(){
for(int i=1;i<=it;++i) d[i] = -1;
queue<int> Q;
Q.push(st);
d[st] = 0;
while(!Q.empty()){
int x = Q.front(); Q.pop();
for(auto i:E[x]){
if(i.f > 0 && d[i.v] == -1){
d[i.v] = d[x] + 1;
Q.push(i.v);
}
}
}
if(d[ed] == -1) return 0;
return 1;
}
int dfs(int x,int nf){
if(x == ed) return nf;
int res = 0;
for(auto &i:E[x]){
if(i.f > 0 && d[i.v] == d[x]+1){
int tf = dfs(i.v,min(nf,i.f));
nf -= tf;
i.f -= tf;
res += tf;
E[i.v][i.re].f += tf;
if(nf == 0) return res;
}
}
if(res == 0) d[x] = -1;
return res;
}
```
### MCF
```cpp
struct EDG{
int v,f,w,re;
};
int n,m,vi[maxn],inq[maxn],cost[maxn],pre[maxn],preid[maxn],st,ed,K;
vector<EDG> E[maxn];
inline void con(int a,int b,int c,int w){
E[a].push_back({b,c,w,(int)E[b].size()});
E[b].push_back({a,0,-w,(int)E[a].size()-1});
}
inline void init(){
for(int i=1;i<=n;++i){
cost[i] = inf;
vi[i] = inq[i] = pre[i] = preid[i] = 0;
}
}
pair<int,int> mcmf(){
init();
queue<int> Q;
Q.push(st);
cost[st] = 0;
while(!Q.empty()){
int x = Q.front(); Q.pop();
inq[x] = 0; vi[x] = 1;
for(int id=0;id<E[x].size();++id){
auto i = E[x][id];
if(i.f > 0 && cost[i.v] > cost[x]+i.w){
cost[i.v] = cost[x]+i.w;
pre[i.v] = x;
preid[i.v] = id;
if(!inq[i.v]){
inq[i.v] = 1;
Q.push(i.v);
}
}
}
}
if(vi[ed] == 0) return {0,0};
int res = inf;
for(int x = ed; x != st; x = pre[x]){
res = min(res,E[pre[x]][preid[x]].f);
}
for(int x = ed; x != st; x = pre[x]){
E[pre[x]][preid[x]].f -= res;
E[x][E[pre[x]][preid[x]].re].f += res;
}
return {res,cost[ed]};
}
main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>m>>K;
st = 1;
ed = n;
for(int i=1;i<=m;++i){
int a,b,c,d; cin>>a>>b>>c>>d;
con(a,b,c,d);
}
int as = 0;
while(K){
pair<int,int> res = mcmf();
if(res.first == 0){
as = -1;
break;
}
as += min(K,res.first)*res.second;
K -= min(K,res.first);
}
cout<<as<<endl;
}
```
## 樹論
### 樹練剖分
```cpp
vector<int> E[maxn];
int n,hs[maxn],f[maxn],sz[maxn],d[maxn],val[maxn],tp[maxn],dfn[maxn],timer,arr[maxn],tree[maxn*4],q;
void dfs(int x,int p){
sz[x] = 1;
hs[x] = -1;
for(int i:E[x]){
if(i==p) continue;
f[i] = x;
d[i] = d[x]+1;
dfs(i,x);
sz[x] += sz[i];
if(hs[x]==-1||sz[hs[x]] < sz[i]) hs[x] = i;
}
}
void link(int x,int top){
tp[x] = top;
dfn[x] = ++timer;
arr[timer] = val[x];
if(hs[x]!=-1) link(hs[x],top);
for(int i:E[x]){
if(i==f[x] || i==hs[x]) continue;
link(i,i);
}
}
int jump(int a,int b){
int mx = 0;
while(tp[a]!=tp[b]){
if(d[tp[b]]>d[tp[a]]) swap(a,b);
mx = max(mx,query(dfn[tp[a]],dfn[a],1,n,1));
a = f[tp[a]];
}
if(dfn[a]>dfn[b]) swap(a,b);
mx = max(mx,query(dfn[a],dfn[b],1,n,1));
return mx;
}
```
### 虛樹
lca.first : lca
lca.second : dis
```cpp
bool comp(int a,int b){
return dfn[b] > dfn[a];
}
void dfs(int x,int p){
dfn[x] = ++timer;
for(int i:E[x]){
if(i==p) continue;
d[i] = d[x]+1;
anc[i][0] = x;
dfs(i,x);
}
}
int lca(int a,int b){
if(d[b] > d[a]) swap(a,b);
int dh = d[a]-d[b];
for(int i=0;i<=25;++i) if(dh&(1<<i)) a = anc[a][i];
if(a==b) return a;
for(int i=25;i>=0;--i){
if(anc[a][i] != anc[b][i]){
a = anc[a][i];
b = anc[b][i];
}
}
return anc[a][0];
}
inline void init(){
for(int i:rec) E2[i].clear();
rec.clear();
}
inline void con(int a,int b){
E2[a].push_back(b);
E2[b].push_back(a);
rec.push_back(a);
rec.push_back(b);
}
inline void build(vector<int> &h){
sort(h.begin(),h.end(),comp);
vector<int> tmp;
int len = h.size();
for(int i=0;i<len-1;++i){
tmp.push_back(h[i]);
tmp.push_back(lca(h[i],h[i+1]));
}
tmp.push_back(h.back());
sort(tmp.begin(),tmp.end(),comp);
tmp.resize(unique(tmp.begin(),tmp.end())-tmp.begin());
for(int i=0;i<(int)tmp.size()-1;++i){
int lc = lca(tmp[i],tmp[i+1]);
con(tmp[i+1],lc);
}
}
```
### 重心剖分(蓋重心樹)
```cpp
void dfs_sz(int x,int p){
sz[x] = 1;
for(int i:E[x]){
if(i==p || vi[i]) continue;
dfs_sz(i,x);
sz[x] += sz[i];
}
}
int find_c(int x,int p,int tot){
for(int i:E[x]){
if(i==p || vi[i]) continue;
if(sz[i]*2 > tot) return find_c(i,x,tot);
}
return x;
}
void build_cd(int x,int p){
dfs_sz(x,0);
int c = find_c(x,0,sz[x]);
vi[c] = 1;
pa[c] = p;
for(int i:E[c]){
if(i==p || vi[i]) continue;
build_cd(i,c);
}
}
```
## 資節
### unordered pair hash
```cpp
struct phash{
size_t operator()(const pair<int,int>& a) const{
size_t h = 0;
h ^= hash<int>{}(a.first) + 0x9e3779b97f4a7c15ULL + (h<<6) + (h>>2);
h ^= hash<int>{}(a.second) + 0x9e3779b97f4a7c15ULL + (h<<6) + (h>>2);
return h;
}
};
```
### pbds
less_equal : multiset，lower_bound -> upper_bound
```cpp
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> s2;
tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> s1;
main(){
s1.insert(3);
s1.insert(5);
s1.insert(7);
s1.insert(9);
int k = 3;
cout<<*s1.find_by_order(k)<<endl; // an iterator of the (k+1)th smallest element
cout<<s1.order_of_key(k)<<endl; // the number of elements are less than k
s1.erase(s1.find(k)); //erase 要指標
}
```
### ST表
```cpp
int n,m,arr[maxn],ST[20][maxn];
void build(){
for(int i=1;i<=n;++i) ST[0][i] = arr[i];
for(int k=1;(1<<k) <= n;++k){
for(int i=1;i+(1<<k)-1 <= n;++i){
ST[k][i] = min(ST[k-1][i],ST[k-1][i+(1<<(k-1))]);
}
}
}
int query(int l,int r){
int k = __lg(r-l+1);
return min(ST[k][l],ST[k][r-(1<<k)+1]);
}
```
### 帶權並查集
題目 : ABC 328 F - Good Set Query
```cpp
int findroot(int x){
if(ds[x] == x) return x;
int r = findroot(ds[x]);
w[x] = w[x]+w[ds[x]];
return ds[x] = r;
}
bool add(int a,int b,int v){
int ra = findroot(a), rb = findroot(b);
if(ra == rb) return w[b]-w[a] == v;
ds[rb] = ra;
w[rb] = v-(w[b]-w[a]);
return true;
}
```
### two-stack trick
無法快速維護erase操作的雙指標問題
https://codeforces.com/edu/course/2/lesson/9/2/practice/contest/307093/problem/G
```cpp
struct STK{
stack<int> st,val;
STK(){
val.push(0);
}
bool empty(){
return st.empty();
}
void push(int x){
st.push(x);
val.push(__gcd(val.top(),x));
}
void pop(){
st.pop();
val.pop();
}
int get(){
return val.top();
}
int top(){
return st.top();
}
} s1,s2;
void ers(){
if(s1.empty()){
while(!s2.empty()){
s1.push(s2.top());
s2.pop();
}
s1.pop();
}else{
s1.pop();
}
}
void add(int id){
s2.push(arr[id]);
}
int query(){
return __gcd(s1.get(),s2.get());
}
```
### 區間加值改值求和線段樹
```cpp
struct node{
int tag1,tag2,sum;
node(){
tag1 = 0;
tag2 = inf;
sum = 0;
}
};
node tree[maxn*4];
void mark1(int l,int r,int x,int v){
tree[x].tag1 += v;
tree[x].sum += v*(r-l+1);
}
void mark2(int l,int r,int x,int v){
tree[x].tag2 = v;
tree[x].sum = v*(r-l+1);
tree[x].tag1 = 0;
}
void pushdown(int l,int r,int x){
if(l==r) return;
int ls = x*2, rs = ls+1, m =(l+r)/2;
if(tree[x].tag2 != inf){
mark2(l,m,ls,tree[x].tag2);
mark2(m+1,r,rs,tree[x].tag2);
tree[x].tag2 = inf;
}
if(tree[x].tag1){
mark1(l,m,ls,tree[x].tag1);
mark1(m+1,r,rs,tree[x].tag1);
tree[x].tag1 = 0;
}
}
void modify(int a,int b,int l,int r,int x,int v,int op){
if(l>=a && r<=b){
if(!op) mark1(l,r,x,v);
else mark2(l,r,x,v);
return;
}
int ls = x*2, rs = ls+1, m = (l+r)/2;
pushdown(l,r,x);
if(m >= a) modify(a,b,l,m,ls,v,op);
if(m < b) modify(a,b,m+1,r,rs,v,op);
tree[x].sum = tree[ls].sum + tree[rs].sum;
}
int query(int a,int b,int l,int r,int x){
if(l>=a && r<=b) return tree[x].sum;
int ls = x*2, rs = ls+1,m = (l+r)/2;
pushdown(l,r,x);
int res = 0;
if(m >= a) res += query(a,b,l,m,ls);
if(m < b) res += query(a,b,m+1,r,rs);
return res;
}
```
### Merge Sort Tree
Count the numbers smaller than or equal to k in range [l,r]
```cpp
void build(int l,int r,int x){
if(l == r){
tree[x].push_back(arr[l]);
return;
}
int ls = x*2,rs = ls+1, m = (l+r)/2;
build(l,m,ls);
build(m+1,r,rs);
int sz1 = m-l+1, sz2 = r-m;
int i = 0, j = 0;
while(i<sz1 && j<sz2)
tree[x].push_back((tree[ls][i] <= tree[rs][j])?tree[ls][i++]:tree[rs][j++]);
while(i<sz1) tree[x].push_back(tree[ls][i++]);
while(j<sz2) tree[x].push_back(tree[rs][j++]);
}
int query(int a,int b,int l,int r,int x,int k){
if(l>=a && r<=b){
auto it = upper_bound(tree[x].begin(),tree[x].end(),k);
return it-tree[x].begin();
}
int ls = x*2, rs = ls+1, m = (l+r)/2;
int sum = 0;
if(m >= a) sum += query(a,b,l,m,ls,k);
if(m < b) sum += query(a,b,m+1,r,rs,k);
return sum;
}
```
### time segment tree Ｘ undoDSU
```cpp
struct EVENT{
int st,et,a,b;
};
vector<EVENT> E;
vector<pair<int,int>> oper[maxn*4];
int n,m,k,as[maxn],ds[maxn],sz[maxn],cc;
stack<pair<int,int>> his;
map<pair<int,int>,int> mp;
void init(){
cc = n;
for(int i=1;i<=n;++i){
sz[i] = 1;
ds[i] = i;
}
while(!his.empty()) his.pop();
}
int findroot(int x){
if(ds[x] == x) return x;
return findroot(ds[x]);
}
void add(int a,int b){
a = findroot(a), b = findroot(b);
if(sz[b] > sz[a]) swap(a,b);
his.push({a,b});
sz[a] += sz[b];
ds[b] = a;
cc--;
}
void undo(){
auto x = his.top(); his.pop();
ds[x.second] = x.second;
sz[x.first] -= sz[x.second];
cc++;
}
void modify(int a,int b,int l,int r,int x,pair<int,int> edg){
if(l>=a && r<=b){
oper[x].push_back(edg);
return;
}
int ls = x*2, rs = ls+1, m = (l+r)/2;
if(m >= a) modify(a,b,l,m,ls,edg);
if(m < b) modify(a,b,m+1,r,rs,edg);
}
void query(int l,int r,int x){
int cnt = 0;
for(auto i:oper[x]){
if(findroot(i.first) != findroot(i.second)){
cnt++;
add(i.first,i.second);
}
}
if(l==r) as[l] = cc;
else{
int ls = x*2, rs = ls+1, m = (l+r)/2;
query(l,m,ls);
query(m+1,r,rs);
}
while(cnt--){
undo();
}
}
```
### 持久化線段樹
```cpp
struct node{
node *ls,*rs;
int cnt;
node():ls(nullptr),rs(nullptr),cnt(0){};
void pull();
};
int n,q,arr[maxn],to[maxn];
node *root[maxn];
void node::pull(){
cnt = ls->cnt+rs->cnt;
}
void build(int l,int r,node*x){
if(l==r) return;
int mid = (l+r)/2;
x->ls = new node;
x->rs = new node;
build(l,mid,x->ls);
build(mid+1,r,x->rs);
}
void modify(int a,int l,int r,node*x,node*pre,int v){
if(l==r){
x->cnt = v;
return;
}
int mid = (l+r)/2;
x->ls = pre->ls;
x->rs = pre->rs;
if(mid >= a){
x->ls = new node{};
modify(a,l,mid,x->ls,pre->ls,v);
}else{
x->rs = new node{};
modify(a,mid+1,r,x->rs,pre->rs,v);
}
x->pull();
}
```
### 李超
```cpp
struct line{
int a,b;
line():a(0),b(inf){}
line(int c,int d){
a = c;
b = d;
}
int operator()(const int x){
return a*x+b;
}
};
line tree[1000006*4];
void insert(int l,int r,int x,line L){
int ls = x*2, rs = ls+1, mid = (l+r)/2;
if(L(mid) < tree[x](mid)) swap(L,tree[x]);
if(L.a == tree[x].a || l==r) return;
if(L.a > tree[x].a) insert(l,mid,ls,L);
else insert(mid+1,r,rs,L);
}
int query(int a,int l,int r,int x){
int ls = x*2, rs = ls+1, mid = (l+r)/2;
int res = tree[x](a);
if(l==r) return res;
if(mid >= a) res = min(res,query(a,l,mid,ls));
else res = min(res,query(a,mid+1,r,rs));
return res;
}
```
### 動態開點李超線段樹
```cpp
struct line{
LL a,b;
line(){
a = 0;
b = -inf;
}
line(LL c,LL d){
a = c;
b = d;
}
LL operator()(LL x){
return x*a+b;
}
};
struct node{
node *ls,*rs;
line L;
node(){
ls = rs = nullptr;
}
};
void insert(int l,int r,node *x,line L){
int mid = (l+r)/2;
if(L(mid) > x->L(mid)) swap(x->L,L);
if(l==r || L.a == x->L.a) return;
if(L.a < x->L.a){
if(x->ls == nullptr) x->ls = new node;
insert(l,mid,x->ls,L);
}
else{
if(x->rs == nullptr) x->rs = new node;
insert(mid+1,r,x->rs,L);
}
}
LL query(int a,int l,int r,node *x){
if(x == nullptr) return -inf;
LL res = x->L(a);
int mid = (l+r)/2;
if(l==r) return res;
if(mid >= a) return max(res,query(a,l,mid,x->ls));
else return max(res,query(a,mid+1,r,x->rs));
}
```
### treap (區間反轉區間min，可 logn 找元素位置)
```cpp
mt19937 rng(21342);
struct node{
node *ls,*rs,*pa;
int sz,pri,val,mn,tag;
node(int v):ls(nullptr),rs(nullptr),pa(nullptr),sz(1),pri(rng()),val(v),mn(v),tag(0){}
};
node *node_of[maxn];
inline int size(node *a){
if(a == nullptr) return 0;
return a->sz;
}
inline int getmn(node *a){
if(a == nullptr) return inf;
return a->mn;
}
inline void pull(node *a){
a->mn = min({getmn(a->ls),getmn(a->rs),a->val});
a->sz = size(a->ls) + size(a->rs)+1;
if(a->ls != nullptr) a->ls->pa = a;
if(a->rs != nullptr) a->rs->pa = a;
}
inline void mark(node *a){
if(a == nullptr) return;
a->tag = !a->tag;
swap(a->ls,a->rs);
}
inline void push(node *a){
if(a == nullptr) return;
if(a->tag){
mark(a->ls);
mark(a->rs);
a->tag = 0;
}
}
node *merg(node *a,node *b){
if(a == nullptr){
if(b != nullptr) b->pa = nullptr;
return b;
}
if(b == nullptr){
if(a != nullptr) a->pa = nullptr;
return a;
}
if(a->pri < b->pri){
push(a);
a->rs = merg(a->rs,b);
pull(a);
a->pa = nullptr;
return a;
}else{
push(b);
b->ls = merg(a,b->ls);
pull(b);
b->pa = nullptr;
return b;
}
}
void split(node *p,node *&a,node *&b,int k){
if(p == nullptr){
a = nullptr;
b = nullptr;
return ;
}
push(p);
if(size(p->ls) < k){
a = p;
split(a->rs,a->rs,b,k-size(p->ls)-1);
pull(a);
}else{
b = p;
split(b->ls,a,b->ls,k);
pull(b);
}
if(a != nullptr) a->pa = nullptr;
if(b != nullptr) b->pa = nullptr;
}
inline void rev(node *&root,int l,int r){
node *a,*b,*c;
split(root,a,b,r);
split(a,a,c,l-1);
mark(c);
root = merg(merg(a,c),b);
}
void push_path(node *x){
vector<node*> tmp;
for(node* i=x;i!=nullptr;i = i->pa) tmp.push_back(i);
for(int i=(int)tmp.size()-1;i>=0;--i) push(tmp[i]);
}
int find_id(node *x){
push_path(x);
int res = size(x->ls)+1;
while(x->pa != nullptr){
node *nw = x->pa;
if(nw->rs == x) res += size(nw->ls)+1;
x = nw;
}
return res;
}
```
## 數學
### 模m下的高斯消去法
```cpp
LL n,m,v[105][105];
LL power(LL x,LL y,LL md){
LL res = 1;
while(y){
if(y&1) res = res*x%md;
x = x*x%md;
y >>= 1;
}
return res;
}
inline void oper(int a,int b,LL c){
for(int i=1;i<=n+1;++i) v[b][i] = ((v[b][i]+v[a][i]*c)%m+m)%m;
}
void GE(){
for(int i=1;i<n;++i){
if(v[i][i] == 0){
int id = -1;
for(int j=i+1;j<=n;++j){
if(v[j][i] != 0){
id = j;
break;
}
}
if(id != -1) oper(id,i,1);
else continue;
}
for(int j=i+1;j<=n;++j){
if(v[j][i] == 0) continue;
LL tmp = -power(v[i][i],m-2,m);
tmp *= v[j][i];
oper(i,j,tmp);
}
}
for(int i=n;i>1;--i){
if(v[i][i] == 0){
int id = -1;
for(int j=i-1;j>=1;--j){
if(v[j][i] != 0){
id = j;
break;
}
}
if(id != -1) oper(id,i,1);
else continue;
}
for(int j=i-1;j>=1;--j){
if(v[j][i] == 0) continue;
LL tmp = -power(v[i][i],m-2,m);
tmp *= v[j][i];
oper(i,j,tmp);
}
}
}
```
### 擴展歐基里德
```cpp
pair<int,int> exgcd(int a,int b){
if(b==0) return {1,0};
pair<int,int> res = exgcd(b,a%b);
int x = res.first%mod, y = res.second%mod;
return {y,x-(a/b)*y%mod};
}
int findmi(int a, int mod) {
pair<int, int> res = exgcd(a, mod);
return (result.first%mod+mod)%mod;
}
```
### 中國剩餘定理
$p[i].first$ $:$ $a_i$
$p[i].second$ $:$ $n_i$
res : x
```cpp
vector<pair<int,int>> p;
int N = 1, res = 0;
for(auto i:p) N *= i.second;
for(auto i:p){
int tmp = N/i.second;
int mi = findmi(tmp,i.second);
res = (res + i.first*tmp%N*mi%N)%N;
}
```
### 約瑟夫問題 O(n)求存活人
```cpp
int js(int a,int b){ // a人一圈 數b人淘汰
if(a==1) return 0;
return (js(a-1,b)+b)%a;
}
```
### Miller Rabin 質數判定法
```cpp
vector<LL> p = {2,3,5,7,11,13,17};
inline LL lb(LL a){
return a&(-a);
}
LL power(__int128 x,LL y,LL mod){
__int128 res = 1;
x = x%mod;
while(y){
if(y&1) res = res*x%mod;
x = x*x%mod;
y >>= 1;
}
return res;
}
inline bool Miller_Rabin(LL n){
if(n <= 17){
if(*lower_bound(p.begin(),p.end(),n) == n) return 1;
return 0;
}
LL s = __lg(lb(n-1));
LL d = (n-1)/lb(n-1);
for(LL a:p){
auto check = [&]() -> bool{
LL x = power(a,d,n);
if(x == 1 || x == n-1) return 1;
for(int i=1;i<s;++i){
x = (__int128)x*x%n;
if(x == n-1) return 1;
}
return 0;
};
if(!check()) return 0;
}
return 1;
}
```
### floor_sum
$calculate \;\;\; \mathrm{floor\_sum}(n,m,a,b) = \sum_{i=1}^{n} \lfloor \frac{ai+b}{m} \rfloor \;\; in \;\; O(logV)$
```cpp
LL floor(LL a,LL b){
if(a>=0 && b>=0 || (a<=0 && b<=0) || (a%b==0)) return a/b;
return a/b-1;
}
LL floor_sum(LL n,LL m,LL a,LL b){
LL qa = (floor(a,m)%mod+mod)%mod, qb = (floor(b,m)%mod+mod)%mod;
LL res = (((n*(n+1)/2LL)%mod*qa%mod + n*qb%mod)%mod+mod)%mod;
a -= floor(a,m)*m;
b -= floor(b,m)*m;
if(n==0 || a==0) return res;
return ((res + ((a*n+b)/m)*n%mod - floor_sum((a*n+b)/m,a,m,-b-1))%mod+mod)%mod;
}
```
### phi
```cpp
LL phi(LL d){
LL res = d;
for(LL p=2;p*p<=d;++p){
if(d%p == 0){
while(d%p == 0) d /= p;
res = res-res/p;
}
}
if(d > 1) res = res-res/d;
return res;
}
```
### 卡特蘭數
### 生成函數
## 字串
### Manacher's Algorithm
```cpp
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
#define inf 1e18
#define maxn 2000006
#define endl '\n'
string s,t;
int n,R[maxn],m,T[maxn];
inline int cal(int l,int r){
int tmp = 0;
while(l-tmp >= 0 && r+tmp<m && t[l-tmp] == t[r+tmp]) tmp++;
return tmp;
}
main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>s;
n = s.size();
m = n*2+1;
t.resize(m);
for(int i=0;i<m;++i){
if(i&1) t[i] = s[i/2];
else t[i] = '.';
}
int mx = -1,center=-1;
for(int i=0;i<m;++i){
if(i > mx){
R[i] = cal(i,i);
mx = i+R[i]-1;
center = i;
}else{
int len = mx-i+1;
int j = center-(i-center);
if(R[j] == len){
R[i] = R[j]+cal(i-len,i+len);
if(i+R[i]-1 > mx){
mx = i+R[i]-1;
center = i;
}
}else if(R[j] < len) R[i] = R[j];
else R[i] = len;
}
}
int as = 0;
for(int i=0;i<m;++i){
as = max(as,R[i]);
}
for(int i=0;i<m;++i){
if(R[i] == as){
for(int j=i-R[i]+1;j<=i+R[i]-1;++j) if(t[j] != '.') cout<<t[j];
cout<<endl;
return 0;
}
}
}
```
### Z-algorithm
```cpp
void build_z(string p){
int len = p.size();
int L = 0, R = 0;
z[0] = len;
for(int i=1;i<len;++i){
if(i > R || z[i-L] >= R-i+1){
if(i>R) z[i] = 0;
else z[i] = R-i+1;
while(z[i]+i<=len && p[i+z[i]] == p[z[i]]) z[i]++;
if(z[i]){
L = i;
R = i+z[i]-1;
}
}else z[i] = z[i-L];
}
}
```
### KMP
```cpp
int nxt[maxn];
void build(string p){
int len = p.size(); p = ' '+p;
int k = 0;
nxt[1] = 0;
for(int i=2;i<=len;++i){
while(k>0 && p[k+1] != p[i]) k = nxt[k];
if(p[k+1] == p[i]) k++;
nxt[i] = k;
}
}
int query(string s,string p){
int sz = s.size(), pz = p.size(), it = 0, cnt = 0;
s = ' '+s; p = ' '+p;
for(int i=1;i<=sz;++i){
while(it > 0 && p[it+1] != s[i]) it = nxt[it];
if(p[it+1] == s[i]) it++;
if(it == pz){
cnt++;
it = nxt[it];
}
}
return cnt;
}
```
### Suffix Array 、 LCP Array
```cpp
void c_sort(vector<int> &sa,vector<int> &ra,int k){
int n = sa.size();
vector<int> cnt(max((int)260,n)), tmpsa(n);
for(int i=0;i<n;++i){
cnt[(i+k<n? ra[i+k]+1:0)]++;
}
for(int i=1;i<cnt.size();++i) cnt[i] += cnt[i-1];
for(int i=n-1;i>=0;--i){
int tmp = sa[i]+k<n ? ra[sa[i]+k]+1 : 0;
tmpsa[--cnt[tmp]] = sa[i];
}
sa = tmpsa;
}
pair<vector<int>,vector<int>> build_sfx(string &s){
int n = s.size();
vector<int> ra(n),sa(n),tmpra(n);
for(int i=0;i<n;++i){
sa[i] = i;
ra[i] = s[i];
}
sort(sa.begin(),sa.end(),[&](int a,int b){return s[b] > s[a];});
for(int k=1;k<n;k<<=1){
auto comp = [&](int a,int b){
if(ra[a] != ra[b]) return ra[b] > ra[a];
int aa = a+k<n ? ra[a+k] : -1;
int bb = b+k<n ? ra[b+k] : -1;
return bb > aa;
};
c_sort(sa,ra,k);
c_sort(sa,ra,0);
tmpra[sa[0]] = 0;
for(int i=1;i<n;++i){
tmpra[sa[i]] = tmpra[sa[i-1]];
if(comp(sa[i-1],sa[i])){
tmpra[sa[i]]++;
}
}
ra = tmpra;
if(ra[sa[n-1]] == n-1) break;
}
return {sa,ra};
int k = 0;
}
vector<int> build_lcp(vector<int> &sa,vector<int> &ra,string &s){
int n = s.size(),k = 0;
vector<int> lcp(n);
for(int i=0;i<n;++i){
int tmp = ra[i];
if(tmp == 0) continue;
int j = sa[ra[i]-1];
while(i+k<n && j+k<n && s[i+k] == s[j+k]) k++;
lcp[tmp] = k;
if(k > 0) k--;
}
return lcp;
}
```
## 計算幾何
### 基礎模板
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 1e18
#define maxn 200005
#define endl '\n'
#define X first
#define Y second
typedef pair<int,int> pl;
pl operator+(const pl&a,const pl&b){
return pl(a.X+b.X,a.Y+b.Y);
}
pl operator-(const pl&a,const pl&b){
return pl(a.X-b.X,a.Y-b.Y);
}
int operator*(const pl&a,const pl&b){
return a.X*b.X+a.Y*b.Y;
}
int operator^(const pl&a,const pl&b){
return a.X*b.Y-a.Y*b.X;
}
int sing(int a){
return a==0 ? 0 : a>0 ? 1:-1;
}
int ori(pl a,pl b,pl c){
return sing((b-a)^(c-a));
}
```
### 線段香蕉
```cpp
int btw(pl a,pl b,pl c){
return ori(a,b,c)==0 && (b-a)*(c-a) <= 0;
}
bool cross(pl a1,pl a2,pl b1,pl b2){
if(btw(a1,b1,b2) || btw(a2,b1,b2) || btw(b1,a1,a2) || btw(b2,a1,a2)) return true;
return ori(a1,a2,b1)!=ori(a1,a2,b2) && ori(b1,b2,a1)!=ori(b1,b2,a2);
}
```
### 凸包
```cpp
int n;
pl p[maxn];
vector<pl> convex_hull(){
sort(p+1,p+1+n);
vector<pl> Q;
for(int t=0;t<2;++t){
int sz = Q.size();
for(int i=1;i<=n;++i){
while((int)Q.size()-sz >= 2 && ori(Q.end()[-2],Q.end()[-1],p[i]) == -1)
Q.pop_back();
Q.push_back(p[i]);
}
Q.pop_back();
reverse(p+1,p+1+n);
}
return Q;
}
```
### 計算 $\angle{bac}$ 度數
```cpp
inline double cal_angle(pl a,pl b,pl c){
pl v1 = (b-a), v2 = (c-a), v3 = (b-c);
return acos((v1*v1+v2*v2-v3*v3)/(2.*sqrt(v1*v1)*sqrt(v2*v2)))*(180./M_PI);
}
```
### 最小包覆圓 (隨機)
```cpp!
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
#define inf 1e18
#define maxn 200005
#define endl '\n'
#define X first
#define Y second
#define double long double
mt19937 rng(243243);
typedef pair<double,double> pl;
struct Line{
pl o,v;
};
struct circle{
pl o;
double r;
};
int n;
pl p[maxn];
pl operator+(const pl&a,const pl&b){
return pl(a.X+b.X,a.Y+b.Y);
}
pl operator-(const pl&a,const pl&b){
return pl(a.X-b.X,a.Y-b.Y);
}
double operator*(const pl&a,const pl&b){
return a.X*b.X+a.Y*b.Y;
}
pl operator*(double a,const pl&b){
return pl(b.X*a,b.Y*a);
}
double operator^(const pl&a,const pl&b){
return a.X*b.Y-a.Y*b.X;
}
double dis(const pl&a,const pl&b){
return sqrt((a-b)*(a-b));
}
Line mid_line(const pl&a,const pl&b){
return {{(a.X+b.X)/2.,(a.Y+b.Y)/2.},{(b-a).Y,-(b-a).X}};
}
pl inter(const Line &a,const Line&b){
double tmp = ((b.o-a.o)^b.v)/(a.v^b.v);
return {a.o+tmp*a.v};
}
circle circum(pl a,pl b,pl c){
pl o = inter(mid_line(a,b),mid_line(a,c));
return {o,dis(o,a)};
}
main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n;
cout<<fixed<<setprecision(17);
for(int i=1;i<=n;++i) cin>>p[i].X>>p[i].Y;
shuffle(p+1,p+1+n,rng);
circle C = {{0,0},0};
auto check = [&](const pl a) -> bool{
if(dis(C.o,a) > C.r) return 0;
return 1;
};
for(int i=1;i<=n;++i){
if(check(p[i])) continue;
C = {p[i],0};
for(int j=1;j<i;++j){
if(check(p[j])) continue;
C = {0.5*(p[i]+p[j]),dis(p[i],p[j])/2.};
for(int k=1;k<j;++k){
if(check(p[k])) continue;
C = circum(p[i],p[j],p[k]);
}
}
}
cout<<C.r<<endl;
cout<<C.o.X<<' '<<C.o.Y<<endl;
}
```
## 其他
### 莫隊
```cpp
bool comp(const qus &a,const qus &b){
if(a.x/D != b.x/D) return b.x/D > a.x/D;
return (a.x/D)&1 ? a.y < b.y : b.y < a.y;
}
void add(int id){
// add arr[id]
}
void ers(int id){
// erase arr[id]
}
main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>q;
D = n/sqrt(q)+1;
for(int i=1;i<=n;++i) cin>>arr[i];
for(int i=1;i<=q;++i){
cin>>p[i].l>>p[i].r;
p[i].id = i;
}
sort(p+1,p+1+q,comp);
int l = 1,r = 0;
for(int i=1;i<=q;++i){
while(r < p[i].r) add(++r);
while(l > p[i].l) add(--l);
while(r > p[i].r) ers(r--);
while(l < p[i].l) ers(l++);
as[p[i].id] = res;
}
for(int i=1;i<=q;++i) cout<<as[i]<<endl;
}
```
### 字典序二分搜
```cpp
int lb(vector<int> &x,vector<vector<int>> &t){
int l = -1, r = t.size(),mid;
while(l+1<r){
mid = (l+r)/2;
if(t[mid] >= x) r = mid;
else l = mid;
}
return r;
}
int ub(vector<int> &x,vector<vector<int>> &t){
int l = -1, r = t.size(),mid;
while(l+1<r){
mid = (l+r)/2;
if(t[mid] > x) r = mid;
else l = mid;
}
return r;
}
```
### 枚舉子集S中的子集T
```cpp
for(int S = 0;S < (1<<n);++S)
for(int T = S;T; T = (T-1) & S)
```
### 編譯優化
```cpp
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma comment(linker, "/stack:200000000")
```
### Gray Code
```cpp
int n,p[maxn];
main(){
cin>>n;
for(int i=0;i<(1<<n);++i){
p[__builtin_ctz(i)] ^= 1;
for(int j=0;j<n;++j) cout<<p[j];
cout<<endl;
}
}
```
### 動態第t小
```cpp
multiset<int> Q1,Q2;
inline void add(int x){
if(Q1.size() >= t) Q2.insert(x);
else Q1.insert(x);
if(!Q1.empty() && !Q2.empty() && *Q2.begin() < *Q1.rbegin()){
int tmpa = *Q1.rbegin(), tmpb = *Q2.begin();
Q1.erase(Q1.find(tmpa));
Q2.erase(Q2.find(tmpb));
Q2.insert(tmpa);
Q1.insert(tmpb);
}
}
inline void ers(int x){
if(Q2.count(x)){
Q2.erase(Q2.find(x));
}else{
Q1.erase(Q1.find(x));
Q1.insert(*Q2.begin());
Q2.erase(Q2.begin());
}
}
```
### encoding&decoding permutation
```cpp
const int dignum = 45;
string permutation_encode(vector<int> p){
int n = 16;
vector<int> cnt(n);
vector<LL> fac(n+2);
fac[0] = 1;
for(int i=1;i<=n;++i) fac[i] = fac[i-1]*(i);
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j) if(p[j] < p[i]) cnt[i]++;
}
LL res = 0;
for(int i=0;i<n;++i){
res += cnt[i]*fac[(n-(i+1))];
}
bitset<dignum> bt = res;
string s;
for(int i=0;i<dignum;++i){
if(bt[i]) s.push_back('1');
else s.push_back('0');
}
return s;
}
vector<int> permutation_decode(string s){
LL x = 0,tmp = 1;
int m = dignum, n = 16;
vector<LL> fac(n+2),p(n);
fac[0] = 1;
for(int i=1;i<=n;++i) fac[i] = fac[i-1]*i;
for(int i=0;i<m;++i){
if(s[i] == '1') x += tmp;
tmp <<= 1;
}
for(int i=0;i<n;++i){
LL tmp = fac[n-(i+1)];
while(x-tmp >= 0){
p[i]++;
x -= tmp;
}
}
vector<int> num,res;
for(int i=0;i<n;++i) num.push_back(i);
int it = 0;
while(!num.empty()){
int idx = p[it++];
res.push_back(num[idx]);
num.erase(num.begin()+idx);
}
return res;
}
```
# 競賽筆記
## 套路
### 問題轉換
區間修改 -> 差分 ->圖論 (條件傳換)
ex: https://atcoder.jp/contests/typical90/tasks/typical90_aw
其怪的圖論問題(特殊條件，特殊距離定義) -> 建新圖、虛點
ex:
https://atcoder.jp/contests/arc061/tasks/arc061_c
https://atcoder.jp/contests/typical90/tasks/typical90_bj (逆向思考)
位元有關問題 -> 獨立考慮
https://atcoder.jp/contests/typical90/tasks/typi
最短路
https://atcoder.jp/contests/abc216/tasks/abc216_g
https://atcoder.jp/contests/abc404/tasks/abc404_g (差分約束)
## 數學
錢幣問題：
對於面額 $a,b$ ,符合 $gcd(a,b)=1$
令 $f=ab-a-b$
則對於 $w>f$ 皆可以用兩種面額組出，$w=f$不可組出，$w < f$ 用dp
組合問題不用模又要算C時，可以建帕斯卡三角形
令 f(i,j) 為從 (0,0)走到 (i,j) 的方法數(只能往下或右走)
it holds that f(r + 1, c) = f(r, 0) + f(r, 1) + ... + f(r, c)
令 $p_n$ 為第n個質數 :
$p_n \sim n\log n$ (皆為自然對數)
## 圖論
### 最大反鍊 = 最小路徑覆蓋 (路徑可重疊)
### 最小路徑覆蓋 (路徑可交疊)求法:
對於每一個(x,y) 符合 x 有一條路徑可已走到 y ，在二分圖中建邊 L[x]->R[y]
求最大匹配
### 最小路徑覆蓋 (路徑不可交疊)求法:
對於每一個(x,y) 符合 x 有一邊直接連到 y ，在二分圖中建邊 L[x]->R[y]
求最大匹配
### 數數
簡單圖單點開始的簡單路徑數量:bit mask dp + 限制初始條件
### 其他
網格圖都是二分圖
## 小技巧
有相同數字時，可以加上第二維資訊 (A[i],i)
Sign in with Wallet
Connect another wallet