# 競賽程式模板
by: 何煦(hush)
## 基本模板
### Default code
在code::blocks去Settings→Compiler→Other compiler options
加入編譯參數：-O2 -Wall -Wextra -DDEBUG
:::spoiler template
```C++=
#include<bits/stdc++.h>
#include<bits/extc++.h>
//#pragma GCC optimize("O2,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,ssse3,sse4,avx,avx2")
#ifdef DEBUG
#define ERR(v,e) cerr<<#v<<": "<<(v)<<(e);
#else
#define ERR(v,e) ((void)0)
#endif
#define int long long
#define itn int
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define EB emplace_back
#define MP make_pair
#define ALL(x) x.begin(),x.end()
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
//mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
constexpr int MOD=1e9+7,MAXN=2e5+5,INF=1e9;
signed main()
{
//colinorz;
}
```
:::
### Creat problems file
:::spoiler code
```dockerfile=
@echo off
setlocal
set n=10
for /l %%i in (1,1,%n%) do (
if not exist p%%i (
md p%%i
)
if not exist p%%i\p%%i.cpp (
type nul > p%%i\p%%i.cpp
)
for /l %%j in (1,1,3) do (
if not exist p%%i\%%j.txt (
type nul > p%%i\%%j.txt
)
)
)
endlocal
```
:::
### hash_template
:::spoiler code
```C++
#include <bits/stdc++.h>
using namespace std;
signed main()
{
string s,all;
ifstream in("zjq390.cpp");
while (getline(in,s))
{
stringstream ss(s);
string tmp;
while (ss >> tmp) all+=tmp;
cout<<s<<endl;
}
unsigned int h=7531357ULL;
for (unsigned char c:all)
h = (h^c)*775577ULL;
cout << h << '\n';
}
```
:::
### Common template
pending...
- Fast Power
:::spoiler code
```C++=
inline int fp(int a,int b,int m)
{
int re=1; a%=m;
while (b)
{
if (b&1) re=re*a%m;
b>>=1,a=a*a%m;
}
return re;
}
```
:::
- Discretization(離散化)
:::spoiler code
```C++=
void dct(const vi &raw,vi &re,int base=1)
{
re.resize(raw.size());
vi a=raw; sort(ALL(a));
a.erase(unique(ALL(a)),a.end());
for (int i=0;i<re.size();i++)
re[i]=lower_bound(ALL(a),raw[i])-a.begin()+base;
}
```
:::
- DSU(併查集)
:::spoiler code
```C++=
struct DSU
{
vi boss,sz;
DSU(int n=MAXN): boss(n+5),sz(n+5,1)
{ iota(ALL(boss),0); }
int fnd(int x) { return (x==boss[x]?x:boss[x]=fnd(boss[x])); }
bool sme(int a,int b) { return fnd(a)==fnd(b); }
void join(int a,int b)
{
a=fnd(a), b=fnd(b); if (a==b) return;
if (sz[a]>sz[b]) swap(a,b);
boss[a]=b,sz[b]+=sz[a];
}
};
```
:::
## 黑魔法 dark code
### I/O模板
:::spoiler template
```C++=
#define gtc getchar//_unlocked
#define ptc putchar//_unlocked
inline int rd()
{
int x=0,st=gtc();
if (st==EOF) return INF;
bool neg=0; char tmp=st;
while (tmp<'0' || tmp>'9')
{
if (tmp=='-') neg=1;
tmp=gtc();
}
while ('0'<=tmp && tmp<='9')
x=(x<<3)+(x<<1)+(tmp^'0'),tmp=gtc();
return neg?-x:x;
}
int buf[40];
inline void wt(int x,const char &ed)
{
if (!x) ptc('0');
else
{
if (x<0) x=-x,ptc('-');
int tp=0;
while (x) buf[tp++]=x%10^'0',x/=10;
while (tp--) ptc(buf[tp]);
}
ptc(ed);
}
#undef gtc
//#undef ptc
```
:::
### Random
- 快速亂數函式(xorshift)：
:::spoiler code
```C++=
static inline unsigned int xorshf() {
static unsigned int x=1000000009, y=433494437, z=43112609;
unsigned int t = x ^ (x << 16);
t ^= (t >> 5);
t ^= (t << 1);
x = y; y = z; z = t ^ x ^ y;
return z;
}
static inline int rnd() { return (int)(xorshf96() & 0x7fffffff); }
```
:::
### PBDS_tree
- 可在$O(\log n)$內查詢第k大的值或x第幾大
- 基本上就是set, map的爸爸
- 第二個type放`null_type`就是set，放其他是map
| 功能 | 查小於 x 數量 | 查第 k 小元素(0-based) |
| --- | ----- | ------------- |
| 函式 | `order_of_key(x)` | `find_by_order(k)` |
:::spoiler template
```C++
using namespace __gnu_pbds;
template<typename T>
using PBDS_tree=tree<T, null_type, less<T>, rb_tree_tag,
tree_order_statistics_node_update>;
// order_of_key, find_by_order
```
:::
### PBDS_trie
:::spoiler template
```C++
using PBDS_trie=trie<string, null_type, trie_string_access_traits<>, pat_trie_tag,trie_prefix_search_node_update>;
```
:::
遍歷一個前綴的所有字串
回傳是pair<Trie::iterator, Trie::iterator>
:::spoiler
```C++
auto range = tre.prefix_range(str);
for(auto it = range.first; it != range.second; it++)
cout << *it << '\n';
```
:::
### rope
- 可在$O(\log n)$內刪除、拼接的字串(陣列)
- 基本上就是string他爸爸(但常數超大)
- `using namespace __gnu_cxx;`
| 功能 | 在位置k插入字串s | 從位置k刪除c個元素 |
| --- | ----- | ------------- |
| 函式 | `insert(k,s);` | `erase(k,c);` |
## Data Type
### Matrix
:::spoiler code
```C++=
struct MAT: vector<vi>
{
int rw=0,cl=0;
MAT(int r,int c,int f=0):
vector<vi>(r,vi(c,f)),rw(r),cl(c) {}
MAT(const vector<vi>& v):
vector<vi>(v),rw(vvi.size()),cl(at(0).size()) {}
void rd()
{ for (int i=0;i<rw;i++) for (int j=0;j<cl;j++) cin >> at(i).at(j); }
void wt() const
{
for (int i=0;i<rw;i++) for (int j=0;j<cl;j++)
cout << at(i).at(j) << " \n"[j==cl-1];
}
MAT unit(const int& sz) const
{
MAT re(sz,sz,0);
for (int i=0;i<sz;i++) re[i][i]=1;
return re;
}
MAT operator + (const MAT &b) const
{
MAT re=*this;
for (int i=0;i<rw;i++) for (int j=0;j<cl;j++)
re[i][j]+=b[i][j];
return re;
}
MAT operator - (const MAT &b) const
{
MAT re=*this;
for (int i=0;i<rw;i++) for (int j=0;j<cl;j++)
re[i][j]-=b[i][j];
return re;
}
MAT operator * (const MAT &b) const
{
const int len=b.rw;
MAT re(rw,b.cl,0);
for (int i=0;i<rw;i++) for (int j=0;j<b.cl;j++)
for (int k=0;k<len;k++)
re[i][j]=(re[i][j]+at(i).at(k)*b[k][j])%MOD;
return re;
}
inline void operator *= (const MAT &b) { *this=(*this)*b; }
void fp(int b)
{
MAT re=unit(size()),a=*this;
while (b)
{
if (b&1) re*=a;
a*=a, b>>=1;
}
*this=re;
}
void T()
{
MAT re(cl,rw);
for (int i=0;i<rw;i++) for (int j=0;j<cl;j++)
re[j][i]=at(i).at(j);
*this=re;
}
};
```
:::
### Big Number
- 日月掛長orz(大部分是抄[他的模板](https://sunmoon-template.blogspot.com/2015/01/big-interger.html))
:::spoiler code
```C++=
//日月掛長orz
template<typename T>
inline string to_string(const T& x)
{
stringstream ss;
return ss<<x,ss.str();
}
struct BIG: vi
{
const static int base=1e9,wdt=log10(base);
bool neg;
BIG (const_iterator a,const_iterator b): vi(a,b) {}
BIG (string s)
{
if (s.empty()) return;
if (s[0]=='-') neg=1,s=s.substr(1);
else neg=0;
for (int i=(int)s.size()-1;i>=0;i-=wdt)
{
int tmp=0;
for (int j=max(0LL,i-wdt+1);j<=i;j++) tmp=tmp*10+(s[j]^'0');
EB(tmp);
}
trim();
}
template<typename T>
BIG (const T &a): BIG(to_string(a)) {}
BIG (): neg(0) {}
void rd()
{
string s; cin >> s;
*this=s;
}
void wt(const char& ed)
{
if (neg) cout << '-';
cout << (empty()?0:back());
for (int i=(int)size()-2;i>=0;i--) cout <<setw(wdt)<<setfill('0')<<at(i);
cout << ed;
}
void trim()
{
while (!empty() && !back()) pop_back();
if (empty()) neg=0;
}
void carry(int _base=base)
{
for (int i=0;i<size();i++)
{
if (at(i)>=0&&at(i)<_base) continue;
if (i+1==size()) EB(0);
int r=at(i)%_base;
if (r<0) r+=_base;
at(i+1)+=(at(i)-r)/_base,at(i)=r;
}
}
int abscmp(const BIG& b) const
{
if (size()>b.size()) return 1;
if (size()<b.size()) return -1;
for (int i=(int)size()-1;i>=0;i--)
{
if ((*this)[i]>b[i]) return 1;
if ((*this)[i]<b[i]) return -1;
}
return 0;
}
int cmp(const BIG& b) const
{
if (neg!=b.neg) return neg?-1:1;
return neg?-abscmp(b):abscmp(b);
}
bool operator < (const BIG& b) const { return cmp(b)<0; }
bool operator > (const BIG& b) const { return cmp(b)>0; }
bool operator <= (const BIG& b) const { return cmp(b)<=0; }
bool operator >= (const BIG& b) const { return cmp(b)>=0; }
bool operator == (const BIG& b) const { return !cmp(b); }
BIG abs() const
{
BIG re=(*this);
return re.neg=0, re;
}
BIG operator - () const
{
BIG re=*this;
return re.neg=!re.neg, re.trim(), re;
}
BIG operator * (int b) const
{
BIG re=*this;
if (b<0) re.neg=!re.neg,b=-b;
for (int i=0,_cry=0,sz=re.size();i<sz||_cry;i++)
{
if (i==sz) re.EB(0);
int sum=re[i]*b+_cry;
_cry=sum/base;
re[i]=sum%base;
}
return re.trim(), re;
}
BIG operator + (const BIG& b) const
{
if (neg) return -(-(*this)+(-b));
if (b.neg) return (*this)-(-b);
BIG re=*this;
if (size()<b.size()) re.resize(b.size());
for (int i=0;i<b.size();i++) re[i]+=b[i];
return re.carry(),re.trim(),re;
}
BIG operator - (const BIG& b) const
{
if (neg) return -(-(*this)-(-b));
if (b.neg) return (*this)+(-b);
if (abscmp(b)<0) return -(b-(*this));
BIG re=*this;
if (b.size()>size()) re.resize(b.size());
for (int i=0;i<b.size();i++) re[i]-=b[i];
return re.carry(),re.trim(),re;
}
BIG convert_base(int old_wdt,int new_wdt) const
{
vi p(max(old_wdt,new_wdt)+1,1);
for (int i=1;i<p.size();i++) p[i]=p[i-1]*10;
BIG re;
int tmp=0,id=0;
for (int i=0;i<size();i++)
{
tmp+=at(i)*p[id];
id+=old_wdt;
while (id>=new_wdt)
re.EB(tmp%p[new_wdt]), tmp/=p[new_wdt], id-=new_wdt;
}
return re.EB(tmp), re.trim(), re;
}
BIG kara(const BIG& b) const //karatsuba
{
BIG re; re.resize((int)size()<<1);
if (size()<33)
{
for (int i=0;i<size();i++) for (int j=0;j<size();j++)
re[i+j]+=at(i)*b[j];
return re;
}
int k=(int)size()>>1;
BIG a1(begin(),begin()+k),a2(begin()+k,end()),
b1(b.begin(),b.begin()+k),b2(b.begin()+k,b.end());
BIG a1b1=a1.kara(b1),a2b2=a2.kara(b2);
for (int i=0;i<k;i++) a2[i]+=a1[i],b2[i]+=b1[i];
BIG r=a2.kara(b2);
for (int i=0;i<a1b1.size();i++) r[i]-=a1b1[i];
for (int i=0;i<a2b2.size();i++) r[i]-=a2b2[i];
for (int i=0;i<r.size();i++) re[i+k]+=r[i];
for (int i=0;i<a1b1.size();i++) re[i]+=a1b1[i];
for (int i=0;i<a2b2.size();i++) re[i+(k<<1)]+=a2b2[i];
return re;
}
BIG operator * (const BIG& b) const
{
const static int mul_base=1e6,mul_wdt=log10(mul_base);
BIG aa=convert_base(wdt,mul_wdt),bb=b.convert_base(wdt,mul_wdt);
int sz=max(aa.size(),bb.size());
while (sz&(sz-1)) sz++;
aa.resize(sz); bb.resize(sz);
BIG re=aa.kara(bb);
re.neg=neg!=b.neg; re.carry(mul_base);
re=re.convert_base(mul_wdt,wdt);
return re.trim(), re;
}
BIG operator / (const BIG& b) const
{
int norm=base/(b.back()+1);
BIG x=abs()*norm,y=b.abs()*norm,q,r;
q.resize(x.size());
for (int i=(int)x.size()-1;i>=0;i--)
{
r=r*base+x[i];
int s1=r.size()<=y.size()?0:r[y.size()];
int s2=r.size()<y.size()?0:r[y.size()-1];
int d=(s1*base+s2)/y.back();
r=r-y*d;
while (r.neg) r=r+y,d--;
q[i]=d;
}
return q.neg=neg!=b.neg, q.trim(), q;
}
BIG operator % (const BIG& b) const { return *this-((*this)/b)*b; }
BIG fp (int b) const
{
BIG a=*this,re=1;
while (b)
{
if (b&1) re=re*a;
a=a*a,b>>=1;
}
return re;
}
};
//日月掛長orz
```
:::
### Fraction
:::spoiler code
```C++=
inline int gcd(int a,int b) { return (b?gcd(b,a%b):a); }
struct FRC: pii
{
FRC(): pii(0,1) {}
FRC(const int& a,int b=1): pii(a,b)
{
rdc();
if (se<0) fi=-fi,se=-se;
}
void rdc() //reduce
{
//if (!se) fi=1e16,se=1;
int gg=gcd(fi,se); fi/=gg,se/=gg;
}
FRC inv() const { return FRC(se,fi); }
FRC operator - () const { return FRC(-fi,se); }
FRC operator * (const int& b) const { return FRC(fi*b,se); }
FRC operator + (const FRC& b) const { return FRC(fi*b.se+se*b.fi,se*b.se); }
FRC operator - (const FRC& b) const { return *this+(-b); }
FRC operator * (const FRC& b) const { return FRC(fi*b.fi,se*b.se); }
FRC operator / (const FRC& b) const { return *this*b.inv(); }
void operator += (const FRC& b) { *this=*this+b; }
void operator -= (const FRC& b) { *this=*this-b; }
void operator *= (const FRC& b) { *this=*this*b; }
void operator /= (const FRC& b) { *this=*this/b; }
bool operator < (const FRC& b) const { return fi*b.se<b.fi*se; }
bool operator > (const FRC& b) const { return b<*this; }
bool operator <= (const FRC& b) const { return fi*b.se<=b.fi*se; }
bool operator >= (const FRC& b) const { return b<=*this; }
friend ostream & operator << (ostream& out,const FRC& b)
{
out<<b.fi;
if (b.se!=1) out<<'/'<<b.se;
return out;
}
friend istream& operator>>(istream& in, FRC& b) {
int f,s;
in >> f;
if (in.peek()=='/') in.ignore();
in >> s;
return b=FRC(f, s),in;
}
};
```
:::
## Data Structure
### IMP-Treap
- BST + Heap
- 這裡是implicit Treap，支持區間操作
:::spoiler code
```C++=
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
struct node //max-heap
{
int p=rnd(),sz=1,val,mn,sum,add=0;
bool rev=0;
node *lc=0,*rc=0;
node(int v): val(v), mn(v), sum(v) {}
inline void tagadd(int k) { sum+=k*sz, val+=k, add+=k; mn+=k; }
inline void tagrev() { rev^=1, swap(lc,rc); }
inline void pull()
{
sz=1, mn=sum=val;
for (auto i : {lc,rc}) if (i)
sz+=i->sz, mn=min(mn,i->mn),sum+=i->sum;
}
inline void push()
{
for (auto i : {lc,rc}) if (i)
{
if (add) i->tagadd(add);
if (rev) i->tagrev();
}
add=rev=0;
}
};
struct TRP
{
node *rt;
TRP(): rt(0) {}
int sz(node *cur) { return cur?cur->sz:0; }
void split(int k,node *&l,node *&r,node *cur)
{
if (!cur) return void(l=r=0);
cur->push();
int lsz=sz(cur->lc);
if (lsz+1<=k) l=cur, split(k-lsz-1,cur->rc,r,cur->rc);
else r=cur, split(k,l,cur->lc,cur->lc);
cur->pull();
}
node* mrg(node *l,node *r)
{
if (!l || !r) return l?l:r;
if (l->p < r->p) return r->push(), r->lc=mrg(l,r->lc), r->pull(), r;
return l->push(), l->rc=mrg(l->rc,r), l->pull(), l;
}
inline void insert(int k,int v,node *&cur)
{
node *l,*r; split(k,l,r,cur);
cur=mrg(mrg(l,new node(v)),r);
}
inline void insert(int k,int v) { insert(k,v,rt); }
inline void update(int id,int x,node *&cur)
{
node *l,*tar,*r;
split(id-1,l,tar,cur); split(1,tar,r,tar);
cur=mrg(mrg(l,new node(x)),r);
}
inline void update(int id,int x) { update(id,x,rt); }
inline void del(int k,node *&cur)
{
node *l,*tar,*r;
split(k-1,l,tar,cur); split(1,tar,r,tar);
cur=mrg(l,r);
}
inline void del(int k) { del(k,rt); }
inline void add(int k,int ql,int qr,node *&cur)
{
node *l,*tar,*r;
split(ql-1,l,tar,cur); split(qr-ql+1,tar,r,tar);
tar->tagadd(k); cur=mrg(mrg(l,tar),r);
}
inline void add(int k,int ql,int qr) { add(k,ql,qr,rt); }
inline int rmq(int ql,int qr,node *&cur)
{
node *tar,*l,*r;
split(ql-1,l,tar,cur); split(qr-ql+1,tar,r,tar);
int re=tar->mn;
return cur=mrg(mrg(l,tar),r), re;
}
inline int rmq(int ql,int qr) { return rmq(ql,qr,rt); }
inline void rev(int ql,int qr,node *&cur)
{
node *l,*tar,*r;
split(ql-1,l,tar,cur); split(qr-ql+1,tar,r,tar);
tar->tagrev(); cur=mrg(mrg(l,tar),r);
}
inline void rev(int ql,int qr) { rev(ql,qr,rt); }
inline void rot(int k, int ql, int qr, node *&cur)
{
int len = qr - ql + 1; k%=len;
if (!k) return;
node *l, *tl, *tr, *r;
split(ql - 1, l, tl, cur); split(len, tl, r, tl); split(len-k,tl,tr,tl);
cur = mrg(mrg(mrg(l, tr), tl), r);
}
inline void rot(int k,int ql,int qr) { rot(k,ql,qr,rt); }
};
```
:::
## 計算幾何 Computational Geometry
### 2D向量的基本操作
#### BASIC
:::spoiler template
```C++=
//#define pii pair<double,double>
#define X first
#define Y second
constexpr double eps=1e-9;
//向量的基本運算
pii operator+ (const pii& a,const pii& b){ return pii(a.X+b.X,a.Y+b.Y);}
pii operator- (const pii& a,const pii& b){ return pii(a.X-b.X,a.Y-b.Y);}
//內外積dot,cross
inline int dot(const pii& a,const pii& b){ return a.X*b.X+a.Y*b.Y;}
inline int cro(const pii& a,const pii& b){ return a.X*b.Y-a.Y*b.X;}
//判斷正負零
inline int sgn(int a){ if (a==0) return 0;return a>0 ? 1 : -1;}
//int sgn(double a){ if (abs(a)<eps) return 0;return a>0 ? 1 : -1;}
//1==逆,-1==順,0==平行
inline int ori(const pii& a,const pii& b,const pii& c){ return sgn(cro(b-a,c-a));}
//X座標由小到大排序
bool xcmp(const pii& a,const pii& b)
{
if (sgn(a.X-b.X)!=0) return sgn(a.X-b.X)<0;
return sgn(a.Y-b.Y)<0;
}
//極角排序
inline bool is_neg(pii a){ return sgn(a.Y)==0?sgn(a.X)<0 : sgn(a.Y)<0;}
bool ang_cmp(const pii& a,const pii& b)
{
int A=is_neg(a),B=is_neg(b);
if (A!=B) return A<B;
return sgn(cro(a,b))>0;
}
```
:::
#### 線段相交
:::spoiler code
```C++=
//is p between a and b
bool btw(const pii& p,const pii& a,const pii& b)
{
return ori(p,a,b)==0 && sgn(dot(a-p,b-p))<=0;
}
//is line intersect(banana)
bool ban(const pii& p1,const pii& p2,const pii& p3,const pii& p4)
{
if (btw(p1,p3,p4) || btw(p2,p3,p4) ||
btw(p3,p1,p2) || btw(p4,p1,p2)) return true;
//是否互相在異側
return ori(p1,p2,p3)*ori(p1,p2,p4) <0 &&
ori(p3,p4,p1)*ori(p3,p4,p2) <0;
}
//intersect point
pii ist(const pii& p1,const pii& p2,const pii& p3,const pii& p4)
{
int a123=cro(p2-p1,p3-p1),a124=cro(p2-p1,p4-p1);
//double a123=cro(p2-p1,p3-p1),a124=cro(p2-p1,p4-p1);
return (p4*a123-p3*a124)/(a123-a124);
}
```
:::
#### 凸包 Convex Hull
:::spoiler code
```C++=
vector<pii> hull;
void convex_hull(int n)
{
vector<pii> a(n);
for (auto &i : a) cin >> i.X >> i.Y;
sort(ALL(a),[](pii &a,pii& b){
return a.X==b.X?a.Y<b.Y:a.X<b.X;
});
int sz=0;
for (int _=0;_<2;_++)
{
for (auto &i : a)
{
while (hull.size()>=sz+2 &&
cro(hull.back()-*prev(hull.end(),2),i-*prev(hull.end(),2))<=0 ) hull.pop_back();
hull.EB(i);
}
hull.pop_back();
if (!_) reverse(ALL(a)),sz=hull.size();
}
}
```
:::
### 3D向量的基本操作
pending...
:::spoiler template
```C++=
```
:::
## 區間問題
### 線段樹 Segment Tree
1. 單點修改
[例題連結：CSES1649](https://cses.fi/problemset/task/1649/)
題意：RMQ，維護區間最小值(**單點修改，區間查詢**)
時間複雜度：修改：$O(\log n)$, 查詢：$O(\log n)$
:::spoiler code
```C++=
vector<int> seg(500000<<2,1e18);
#define lc cur<<1
#define rc cur<<1|1
#define mid (l+r)>>1
void update(int cur,int l,int r,int i,int x) //[l,r)
{
if (l==r-1)
{
seg[cur]=x;
return;
}
if (i<mid) update(lc,l,mid,i,x);
else update(rc,mid,r,i,x);
seg[cur]=min(seg[lc],seg[rc]);
}
int query(int cur,int l,int r,int ql,int qr) //[ql,qr)
{
if (l>=qr || r<=ql) return 1e18;
if (ql<=l && r<=qr) return seg[cur];
return min(query(lc,l,mid,ql,qr),query(rc,mid,r,ql,qr));
}
#undef lc
#undef rc
#undef mid
```
:::
2. 區間修改萬用模板
:::spoiler template
```C++=
#define lc cur<<1
#define rc cur<<1|1
#define mid (l+r)>>1
constexpr int MAXN=500005;
struct node
{
int val=0,tag=0; //0代表tag為空
} seg[MAXN<<2]={};
inline void addtag(int cur,int x)
{
//處理seg[cur].val
//處理seg[cur].tag
}
inline void push(int cur)
{
addtag(lc,seg[cur].tag), addtag(rc,seg[cur].tag);
seg[cur].tag=0; // 標記設定為空
}
void update(int cur,int l,int r,int ql,int qr,int x)
{
if (r<=ql || l>=qr) return;
if(ql<=l && r<=qr)
{
addtag(cur,x);
return;
}
push(cur);
update(lc,l,mid,ql,qr,x); update(rc,mid,r,ql,qr,x);
//pull
}
int query(int cur,int l,int r,int ql,int qr)
{
if (r<=ql || l>=qr) return 0; //回傳不可能的值
if (ql<=l && r<=qr) return seg[cur].val;
push(cur);
return //combine lc,rc;
}
#undef lc
#undef rc
#undef mid
```
:::
### BIT
"Binary index tree" or "Fenwick tree"
1. 單點加值
時間複雜度：修改、查詢$O(\log n)$
:::spoiler code
```C++=
constexpr int MAXN=500005;
int bit[MAXN+5]={};
inline int lsb(const int &x) { return x&-x; }
inline void add(int i,int x)
{ while (i<MAXN) bit[i]+=x,i+=lsb(i); }
inline int pre(int i)
{
int sum=0;
while (i) sum+=bit[i],i-=lsb(i);
return sum;
}
inline int sum(int l,int r) { return pre(r)-pre(l-1); }
```
:::
2. 區間加值
$\sum\limits_{j=1}^i{a[j]}=(i+1)(\sum\limits_{j=1}^i{d[j]})-\sum\limits_{j=1}^i{j\times d[j]}$
時間複雜度：修改、查詢$O(\log n)$
:::spoiler code
```C++
constexpr int MAXN=200005;
int bit[2][MAXN+5]={}; //bit[0]->d, bit[1]->d*i
inline int lsb(const int &x) { return x&-x; }
void add(int l,int r,int x) //[l,r]
{
for (int i=l,xi=x*l;i<MAXN;i+=lsb(i)) bit[0][i]+=x,bit[1][i]+=xi;
for (int i=r+1,xi=x*(r+1);i<MAXN;i+=lsb(i)) bit[0][i]-=x,bit[1][i]-=xi;
}
int pre(int i) //pre[i]=(i+1)*sum(d[j])-sum(d[j]*j), j:= 1->i
{
int x=0,mns=0;
for (int j=i;j;j-=lsb(j)) x+=bit[0][j],mns+=bit[1][j];
return x*(i+1)-mns;
}
inline int sum(int l,int r) { return pre(r)-pre(l-1); }
```
:::
### 莫隊
pending...
###
## 圖論 Graph theory
### 最小生成樹 MST
1. Kruskal's algorithm: 將邊以權重照順序拿取，若不成環則加入$MST$
$O(E\log E)$
:::spoiler code
```C++=
//include DSU
pair<int,pii> edge[MAXN];
vector<vector<vector<pii>>> mst;
bool MST(int n,int m,int tr=0)
{
if (mst.size()<=tr) mst.resize(tr+1);
mst[tr].assign(n+1,{});
DSU dsu(n);
int cnt=0;
sort(edge,edge+m);
for (int i=0;i<m;i++)
{
int w=edge[i].fi,u=edge[i].se.fi,v=edge[i].se.se;
if (!dsu.sme(u,v))
{
mst[tr][u].EB(MP(w,v)); mst[tr][v].EB(MP(w,u));
dsu.join(u,v);
cnt++;
}
}
return cnt==n-1;
}
```
:::
2. Prim's algorithm: 先隨便選一個點，將點周圍跟尚未使用的點連接的邊加入(優先)佇列，依序挑出(優先)佇列的邊，若不成環則加入$MST$，然後更新(優先)佇列
$O(E\log V)$
:::spoiler code
```C++=
vector<pii> edge[MAXN];
bitset<MAXN> used;
priority_queue<pii,vector<pii>,greater<pii>> pq;
bool MST(int n)
{
int cnt=0; used[1]=1;
for (const pii& i : edge[1]) pq.emplace(i);
while (!pq.empty())
{
int v=pq.top().se; pq.pop();
if (used[v]) continue;
used[v]=1; cnt++;
for (const pii& i : edge[v])
if (!used[i.se]) pq.emplace(i);
}
return cnt+1==n;
}
```
:::
### 最短路徑問題
- 全圖最短路徑
1. Floyd-Warshall : $O(V^3)$
對整張圖做$dp$，$dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])$
- 單點源最短路徑
1. Dijkstra : $O(E\log V)$
支援無負邊圖，概念是greedy+BFS
:::spoiler code
```C++
struct node
{
int v,w;
node(int _v,int _w): v(_v), w(_w) {}
bool operator < (const node& b) const { return w>b.w; }
};
vector<node> edge[MAXN];
vi d(MAXN,-1);
priority_queue<node> pq;
int dij(int st,int ed,const auto& edge)
{
fill(ALL(d),-1);
pq.emplace(node(st,0));
while (!pq.empty())
{
auto tmp=pq.top(); pq.pop();
if (d[tmp.v]!=-1) continue;
d[tmp.v]=tmp.w;
for (auto &i : edge[tmp.v]) if (d[i.v]==-1)
pq.emplace(node(i.v,i.w+d[tmp.v]));
}
return d[ed];
}
```
:::
2. Bellmen-Ford : $O(VE)$
支援有負邊圖，可以判斷負環，核心概念是relax，$dis(t)=min(dis(t),dis(s)+weight(s,t))$
:::spoiler code
```C++=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
vector<vector<pii>> edge(100005);
vector<int> d(100005,1e18);
signed main()
{
int n,m,s,t; cin >> n >> m >> s >> t;
for (int i=0;i<m;i++)
{
int u,v,w; cin >> u >> v >> w;
edge[u].emplace_back(w,v);
}
bool nc=0; d[s]=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (auto &k:edge[j])
if (d[k.se]>k.fi+d[j])
{
d[k.se]=k.fi+d[j];
if (i==n) nc=1;
}
if (nc) cout << "nc\n";
else cout << d[t] << endl;
}
```
:::
3. SPFA : $O(E)$~$O(VE)$
Bellman-Ford的優化，功能也一樣，期望複雜度很好，但是最差情況跟Bellmen-Ford一樣
:::spoiler code
```C++=
struct node
{
int v,w;
node (int _v,int _w): v(_v),w(_w) {}
};
vector<vector<node>> edge(MAXN);
vector<int> d(MAXN,INF),inq(MAXN,0),cnt(MAXN,0);
queue<int> q;
bool spfa(int st,int n,const auto& edge)
{
fill(ALL(d),INF); fill(ALL(inq),0); fill(ALL(cnt),0);
q.emplace(st);
d[st]=0; inq[st]=1;
while (!q.empty())
{
int u=q.front(); q.pop();
inq[u]=0;
for (auto &i : edge[u])
{
int w=i.w,v=i.v;
if (d[v]>w+d[u])
{
d[v]=w+d[u];
if (inq[v]) continue;
q.emplace(v); inq[v]=1;
if (++cnt[v]>n) return 0;
}
}
}
return 1;
}
```
:::
### LCA
1. Talgorithm ： $O(V+E+q)$
**<font color="red">constraint: offline query</font>**
:::spoiler code
```C++=
vector<vi> edge(200005),qst(200005);
bitset<200005> used;
int boss[200005],qa[200005],qb[200005],lca[200005];
inline void dsu(int n) { for (int i=1;i<=n;i++) boss[i]=i; } //called in main
int fnd(int a) { return a==boss[a]?a:boss[a]=fnd(boss[a]); }
void dfs(int cur,int p) //watch out cur==v
{
for (const int& i : edge[cur]) if (i!=p) dfs(i,cur);
used[cur]=1;
for (const int& i : qst[cur])
{
int v=cur^qa[i]^qb[i]; //the other vertex
if (used[v]) lca[i]=fnd(v);
}
boss[cur]=p;
}
signed main()
{
//colinorz;
int n,q; cin >> n >> q;
dsu(n);
for (int i=2;i<=n;i++)
{
int e; cin >> e;
edge[e].EB(i);
}
for (int i=0;i<q;i++)
{
int a,b; cin >> a >> b;
qst[a].EB(i); qst[b].EB(i); qa[i]=a; qb[i]=b;
}
dfs(1,-1);
for (int i=0;i<q;i++) cout << lca[i] << endl;
}
```
:::
2. binary lifting + alignment(or timestamp) ： $O(V\log V)$
:::spoiler code
```C++=
constexpr int lg=16;
vector<vi> edge(MAXN);
int dpt[MAXN]={},jmp[MAXN][lg+5];
void dfs(int cur,int p,int dd)
{
dpt[cur]=dd;
//build
jmp[cur][0]=p;
for (int stp=1;stp<=lg;stp++)
jmp[cur][stp]=jmp[ jmp[cur][stp-1] ][ stp-1 ];
for (const int i : edge[cur])
if (i!=p) dfs(i,cur,dd+1);
}
int lca(int a,int b)
{
if (dpt[a]<dpt[b]) swap(a,b);
//a jump to b's dpt
int dif=dpt[a]-dpt[b];
for (int stp=lg;stp>=0;stp--)
if (dif>=(1<<stp)) a=jmp[a][stp],dif-=1<<stp;
if (a==b) return a;
//fnd lca
for (int stp=lg;stp>=0;stp--)
if (jmp[a][stp]!=jmp[b][stp]) a=jmp[a][stp],b=jmp[b][stp];
return jmp[a][0];
}
```
:::
3. Euler tour + Segment tree ： $O(V\log V)$
:::spoiler code
```C++=
int n,tp=0,dpt[30005]={(int)1e16},seg[(60000<<2)+5]={}; //[l,r)
vi edge[30005],pos(30005,-1);
#define lc cur<<1
#define rc cur<<1|1
#define mid (l+r)>>1
void update(int cur,int l,int r,int i,int x) //x -> pos
{
if (l+1==r)
{
seg[cur]=x;
return;
}
if (i<mid) update(lc,l,mid,i,x);
else update(rc,mid,r,i,x);
seg[cur]=(dpt[seg[lc]]<dpt[seg[rc]]?seg[lc]:seg[rc]);
}
int query(int cur,int l,int r,int ql,int qr)
{
if (l>=qr || r<=ql) return 0;
if (ql<=l && r<=qr) return seg[cur];
int lp=query(lc,l,mid,ql,qr),rp=query(rc,mid,r,ql,qr);
return (dpt[lp]<dpt[rp]?lp:rp);
}
void dfs(int cur,int p,int dd)
{
dpt[cur]=dd;
if (pos[cur]==-1) pos[cur]=tp;
update(1,0,(n<<1)-1,tp++,cur);
for (const int i : edge[cur])
if (i!=p) dfs(i,cur,dd+1),update(1,0,(n<<1)-1,tp++,cur);
}
inline int lca(int a,int b)
{
int ql=pos[a],qr=pos[b];
if (ql>qr) swap(ql,qr);
return query(1,0,(n<<1)-1,ql,qr+1);
}
```
:::
### HLD
- Heavy Light Decomposition(重鍊分解)
- 例題：[CSES2134](https://cses.fi/problemset/task/2134)
- 時間複雜度：預處理$O(V+E)$，查詢$O(q\cdot \log ^2 V)$
:::spoiler code
```C++=
constexpr int MAXN=200005;
vi edge[MAXN];
int n,tt=1,v[MAXN],sz[MAXN],dpt[MAXN],prt[MAXN],hc[MAXN]={},up[MAXN],pos[MAXN],seg[MAXN<<2]={};
void update(int cur,int l,int r,int i,int x)
{
int lc=cur<<1,rc=cur<<1|1,mid=(l+r)>>1;
if (l+1==r)
{
seg[cur]=x; return;
}
if (i<mid) update(lc,l,mid,i,x);
else update(rc,mid,r,i,x);
seg[cur]=max(seg[lc],seg[rc]);
}
int query(int cur,int l,int r,int ql,int qr)
{
int lc=cur<<1,rc=cur<<1|1,mid=(l+r)>>1;
if (l>=qr || r<=ql) return -1e9;
if (ql<=l && r<=qr) return seg[cur];
return max(query(lc,l,mid,ql,qr),query(rc,mid,r,ql,qr));
}
void dfs(int cur=1,int p=-1,int dd=1)
{
prt[cur]=p,dpt[cur]=dd;
int sum=1,tmp=0,tmpsz=-1,csz;
for (const int &i : edge[cur]) if (i!=p)
{
dfs(i,cur,dd+1);
csz=sz[i],sum+=csz;
if (csz>tmpsz) tmp=i,tmpsz=csz;
}
hc[cur]=tmp,sz[cur]=sum;
}
void hld(int cur=1,int tp=1)
{
up[cur]=tp,pos[cur]=tt++;
update(1,1,n+1,pos[cur],v[cur]);
if (hc[cur])
{
hld(hc[cur],tp);
for (const int &i : edge[cur])
if (i!=prt[cur] && i!=hc[cur]) hld(i,i);
}
}
signed main()
{
//colinorz;
int q; cin >> n >> q;
for (int i=1;i<=n;i++) cin >> v[i];
for (int i=0;i+1<n;i++)
{
int a,b; cin >> a >> b;
edge[a].EB(b); edge[b].EB(a);
}
dfs(1,-1,1);
hld(1,1);
while (q--)
{
int op,a,b; cin >> op >> a >> b;
if (op==1) update(1,1,n+1,pos[a],b),v[a]=b;
else
{
int ans=0;
while (up[a]!=up[b])
{
if (dpt[up[b]]>dpt[up[a]]) swap(a,b); //jmp a
if (a==up[a]) ans=max(ans,v[a]);
else ans=max(ans,query(1,1,n+1,pos[up[a]],pos[a]+1));
a=prt[up[a]];
}
if (dpt[b]>dpt[a]) swap(a,b);
ans=max(ans,query(1,1,n+1,pos[b],pos[a]+1));
cout << ans << ' ';
}
}
}
```
:::
### 強連通分量 SCC
1. Tarjan : $O(V+E)$
:::spoiler code
```C++=
vi edge[MAXN];
int dfn[MAXN]={},up[MAXN],tp=0,scc_id[MAXN],scc_cnt=0;
bool ins[MAXN]={};
stack<int> stk;
void tar(int cur)
{
dfn[cur]=up[cur]=++tp;
stk.emplace(cur); ins[cur]=1;
for (int &i : edge[cur])
if (!dfn[i])
tar(i),up[cur]=min(up[cur],up[i]);
else if (ins[i])
up[cur]=min(up[cur],dfn[i]);
if (up[cur]==dfn[cur])
{
int tmp;
do
{
tmp=stk.top(); stk.pop();
scc_id[tmp]=scc_cnt; ins[tmp]=0;
} while (tmp!=cur);
scc_cnt++;
}
}
inline void fnd_scc(int num)
{
for (int i=1;i<=num;i++)
if (!dfn[i]) tar(i);
}
```
:::
- 縮點
:::spoiler code
```C++=
vi dag[MAXN];
int aa[MAXN]={};
void cnds(int n) //condense SCC
{
for (int i=1;i<=n;i++)
{
const int &cur=scc_id[i];
aa[cur]+=a[i];
for (int &j : edge[i]) if (cur!=scc_id[j])
dag[cur].EB(scc_id[j]);
}
}
```
:::
### 歐拉迴路(一筆畫)
1. Hierholzer : $O(V+E)$
:::spoiler code
```C++
vi ans;
void elc (int cur = 1) // euler circuit
{
while(!edge[cur].empty())
{
pii i=edge[cur].back(); edge[cur].pop_back();
if (kll[i.se]) continue;
kll [i.se]=1;
elc (i.fi);
}
ans.EB(cur);
}
```
:::
### 網路流問題
- 最大流 Maximum Flow
1. Dinic : $O(V^2E)$
通常會比理論上界快很多
:::spoiler code
```C++=
struct node
{
int frm,to,cap;
node(int f,int t,int c): frm(f),to(t),cap(c) {}
};
vector<node> edge[MAXN];
int lvl[MAXN],ptr[MAXN],st,ed;
queue<int> que;
inline void d_edge(int u,int v,int c) //directed graph
{
node uu(edge[v].size(),v,c),vv(edge[u].size(),u,0);
edge[u].EB(uu); edge[v].EB(vv);
}
inline void und_edge(int u,int v,int c) //undirected graph
{
node uu(edge[v].size(),v,c),vv(edge[u].size(),u,c);
edge[u].EB(uu); edge[v].EB(vv);
}
bool bfs()
{
memset(lvl,-1,sizeof(lvl));
que.emplace(st); lvl[st]=1;
while (!que.empty())
{
auto tmp=que.front(); que.pop();
for (auto &i : edge[tmp])
{
if (lvl[i.to]!=-1 || i.cap<=0) continue;
que.emplace(i.to); lvl[i.to]=lvl[tmp]+1;
}
}
return lvl[ed]!=-1;
}
int dfs(int cur=st,int fl=INF)
{
if (cur==ed) return fl;
for (int &id=ptr[cur];id<edge[cur].size();id++)
{
auto &e=edge[cur][id];
if (lvl[e.to]!=lvl[cur]+1 || e.cap<=0) continue;
int re=dfs(e.to,min(fl,e.cap));
if (!re) continue;
e.cap-=re;
edge[e.to][e.frm].cap+=re;
return re;
}
return 0;
}
int dnc(int _st,int _ed)
{
st=_st; ed=_ed;
int re=0;
while (bfs())
{
memset(ptr,0,sizeof(ptr));
while (int tmp=dfs())
re+=tmp;
}
return re;
}
```
:::
## 數論 Number theory
### 質數
- 質數判定
1. 試除法$O(\sqrt n)$
:::spoiler code
```C++=
bool is_p(int n)
{
if (n<2) return 0;
for (int i=2;i*i<=n;i++)
if (n%i==0) return 0;
return 1;
}
signed main()
{
//colinorz;
int n; cin >> n;
cout << is_p(n) << endl;
}
```
:::
2. Miller-Rabin $O(\log n)$
:::spoiler template
```C++=
inline int mul(int a,int b,int m) //防溢位乘法
{
unsigned int re=(unsigned int)a*b-
(unsigned int)((long double)a/m*b+0.5L)*m;
return re<m?re:re+m;
}
inline int fp(int a,int b,int m)
{
int re=1; a%=m;
while (b)
{
if (b&1) re=re*a%m;
b>>=1,a=a*a%m;
}
return re;
}
const int test[12]={2,3,5,7,11,13,17,19,23,29,31,37};
bool Miller_Rabin(int n)
{
if (n<3 || !(n&1)) return (n==2);
for (const int i : test) if (i==n) return 1;
int m=n-1,t=0;
while (!(m&1)) m>>=1,t++;
for (const int a : test)
{
int x=fp(a,m,n),isp=0;
if (x==1 || x==n-1) continue;
for (int i=0;!isp && i<t-1;i++)
{
x=mul(x,x,n);
if (x==1) return 0;
if (x==n-1) isp=1;
}
if (!isp) return 0;
}
return 1;
}
```
:::
- 建質數表(線性篩法)：$O(n)$
:::spoiler code
```C++=
vector<int> p;
int minp[1000005]={};
void build_p(int n)
{
for (int i=2;i<=n;i++)
{
if (!minp[i]) minp[i]=i,p.emplace_back(i);
for (int j : p)
{
if (j>minp[i] || j*i>n) break;
minp[j*i]=j;
}
}
}
signed main()
{
//colinorz;
build_p(1000000);
}
```
:::
### 質因數分解
- 建質數表+試除法： $O(\sqrt n+q\ \sqrt{\pi (n)})$
pending...
:::spoiler code
```C++=
```
:::
- Pollard's $\rho$： $O(\sqrt p)\approx O(n^{1/4})$
:::spoiler template
```C++=
//define Miller_Rabin
inline int gcd(int a,int b) { return (b?gcd(b,a%b):a); }
int Pollard_rho(int n)
{
int x=rand()%n+1,y=x,c=rand()%(n-1)+1;
int i=1,p=2;
while (1)
{
x=(mul(x,x,n)+c)%n;
int d=gcd(abs(x-y),n);
if (d>1) return d;
if (++i==p) y=x,p<<=1;
}
}
vector<int> factors;
void factorize(int n)
{
while (!(n&1)) n>>=1,factors.emplace_back(2);
if (n==1) return;
if (Miller_Rabin(n))
{
factors.emplace_back(n);
return;
}
int tmp;
do tmp=Pollard_rho(n); while (tmp==n);
factorize(tmp),factorize(n/tmp);
}
```
:::
### 擴展歐幾里得算法
- 求 $ax+by=c$ 的整數解：
$\text{let}\ d=\gcd(a,b)$
$\begin{cases}
\ x=x' \cdot \dfrac{c}{d},\; y=y' \cdot \dfrac{c}{d} & \text{, if } d \mid c \\
\text{no solution} & \text{, if } d \nmid c
\end{cases}$
:::spoiler code
```C++=
void exgcd(int a,int b,int &x,int &y,int &d) //solve ax+by=gcd(a,b)
{
if (b) exgcd(b,a%b,y,x,d),y-=a/b*x;
else d=a,x=1,y=0;
}
inline pii sol(int a,int b,int c) //solve ax+by=c
{
int x,y,d; exgcd(a,b,x,y,d);
if (c%d) return pii(1e18,1e18); //no solution
return pii(x/d*c,y/d*c);
}
```
:::
### 模逆元
1. 當 MOD **是**質數時可使用快速冪
$a^{-1}\equiv a^{p-2} \pmod p$
:::spoiler code
```C++=
inline int fp(int a,int b,int m)
{
int ans=1; a%=m;
while (b)
{
if (b&1) ans=ans*a%m;
b>>=1,a=a*a%m;
}
return ans;
}
inline int inv(int a) { return fp(a,MOD-2,MOD); }
```
:::
2. 當 MOD **不是**質數時使用exgcd
:::spoiler code
```C++=
void exgcd(int a,int b,int &x,int &y,int &d) //solve ax+by=gcd(a,b)
{
if (b) exgcd(b,a%b,y,x,d),y-=a/b*x;
else d=a,x=1,y=0;
}
inline int inv(int a,int m)
{
int x,y,d; exgcd(a,m,x,y,d);
if (d==1) return (x%m+m)%m;
return -1; //non-existent
}
```
:::
### CRT
:::spoiler code
```C++
int crt(const vi& a,const vi& r)
{
int re=0,sz=a.size(),m=1;
for (int i=0;i<sz;i++) m*=r[i];
for (int i=0;i<sz;i++)
{
int mi=m/r[i],k=inv(mi,r[i])%m;
int c=((__int128)mi*k)%m,tot=((__int128)a[i]*c)%m;
re=(re+tot)%m;
}
return (re%m+m)%m;
}
```
:::
## String
### String Match
1. rolling-hash
:::spoiler code
```C++
#include<bits/stdc++.h>
#define int long long
#define itn int
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
constexpr int MOD=1e9+7,P=203;
string s,t;
signed main()
{
//colinorz;
cin >> s >> t;
if (s.size()<t.size())
{
cout << "0\n";
return 0;
}
int tar=0;
for (int i=0,pp=1;i<t.size();i++,pp=(pp*P)%MOD) tar=(tar+t[i]*pp)%MOD;
int k=0,ans=0;
for (int i=s.size()-t.size(),pp=1;i<s.size();i++,pp=(pp*P)%MOD) k=(k+s[i]*pp)%MOD;
if (k==tar) ans++;
int mp=1;
for (int i=0;i<t.size();i++) mp=(mp*P)%MOD;
for (int j=(int)s.size()-t.size()-1;j>=0;j--)
{
k=((k*P+s[j]-(s[j+t.size()]*mp)%MOD)%MOD+MOD)%MOD;
if (k==tar) ans++;
}
cout << ans << endl;
}
```
:::
Sign in with Wallet
Connect another wallet