0% found this document useful (0 votes)

5 views74 pages

Advanced Algorithm Templates and Queries

Uploaded by

emergency.aba.kamaleldin

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as DOCX, PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

5 views74 pages

Advanced Algorithm Templates and Queries

Uploaded by

emergency.aba.kamaleldin

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as DOCX, PDF, TXT or read online on Scribd

Giant pizza (2-sat) Page #3

Mail delivery (euler-cycle) Page #5

Distinct Routes (Max-flow) Page #6
Segment tree template Page #8
Range interval Queries Page #9
Distinct Values Queries I (persistent segtree) Page #10
Distinct Values Queries II Page #12
Forest Queries II (2D segtree) Page #14
Polynomial Queries Page #16
Missing Coin Sum Queries Page #17
Path Queries II (HLD) Page #19
Fixed-Length Paths I (Centroid decomp) Page #21
Josephus Queries (k-th child) Page #23
Divisor Analysis Page #24
Sum of Divisors (1-n) Page #25
Bracket Sequences II Page #26
Counting Necklaces Page #28
Fibonacci Numbers (Matrix expo) Page #29
System of Linear Equations (Gauss) Page #30
All Palindromes (Manacher) Page #31
Palindrome Queries (Hashed template) Page #33
String Functions (kmp and Z algo) Page #37
Substring Order II (Includes Suffix Array and LCP) Page #38
Polygon Lattice Points (Geometry Template) Page #42
Lines and Queries II (Li-chao tree) Page #50
Reachability Queries (SCC) Page #51
Reversals and Sums (Treap) Page #53
Necessary Roads (Bridges) Page #55
Necessary Cities Page #56
1|Page
Monster Game II (Line Container) Page #58
Houses and Schools (Divide and Conquer) Page #59
Knuth Division (Knuth) Page #61
Apples and Bananas (FFT template) Page #62
Dynamic Connectivity Page #63
Parcel Delivery (Max-Flow with dijkestra) Page #66
All Subarray Xors (xor convolution) Page #67
SOS Bit Problem (SOS dp) Page #69
BM Page #70
Gphashtable Page #71
Ordered_set Page #72
Trie snippet (persistent) Page #72

2|Page
Giant pizza (2-sat):
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int n,m,ans[200010];
vector<int> v[200010],rv[200010];
int vis[200010],visscc[200010],visscc2[200010],root[1000010];
vector<int> vc[200010],comp,ord,roots;
set<int> ste[200010];
void dfsnorm(int idx){
if(visscc[idx])
return;
visscc[idx]=1;
for(int i=0;i<(int)v[idx].size();i++)
dfsnorm(v[idx][i]);
[Link](idx);
return;
}
void dfsrev(int idx){
if(visscc2[idx])
return;
visscc2[idx]=1;
for(int i=0;i<(int)rv[idx].size();i++)
dfsrev(rv[idx][i]);
[Link](idx);
return;
}
void scc(){
for(int i=1;i<=n;i++){
if(!visscc[i])
dfsnorm(i);
}
reverse([Link](),[Link]());
int curr=0;
for(int i=0;i<n;i++){
if(!visscc2[ord[i]]){
[Link]();
dfsrev(ord[i]);
int x=curr++;
[Link](x);
for(int j=0;j<(int)[Link]();j++)
root[comp[j]]=x;

3|Page
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<(int)v[i].size();j++){
int x=root[i];
int y=root[v[i][j]];
if(x==y)
continue;
ste[x].insert(y);
}
}
for(int i=1;i<=n;i++){
for(auto it:ste[i])
vc[i].pb(it);
}
return;
}
int inv(int x){
if(x>n)
return x-n;
return x+n;
}
void dfs(int idx){
if(vis[idx])
return;
vis[idx]=1;
for(auto it:vc[idx])
dfs(it);
[Link](idx);
return;
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>m>>n;
for(int i=0;i<m;i++){
char a,b;
int x,y;
cin>>a>>x>>b>>y;
if(a=='-')
x+=n;
if(b=='-')
y+=n;
v[inv(x)].pb(y);
rv[y].pb(inv(x));
v[inv(y)].pb(x);
rv[x].pb(inv(y));
}
n*=2;
scc();
n/=2;
for(int i=1;i<=n;i++){
if(root[i]==root[i+n]){
cout<<"IMPOSSIBLE\n";
return 0;
}
}
for(int i=1;i<=n;i++)

4|Page
cout<<(root[i]>root[i+n]?"+ ":"- ");
cout<<"\n";
}
return 0;
}

Mail delivery (Euler-cycle):

#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int n,m;
map<pair<int,int>,int> mp;
vector<int> v[100010];
vector<int> ans;
void dfs(int idx){
while(v[idx].size()){
if(mp[{idx,v[idx].back()}]){
v[idx].pop_back();
continue;
}
mp[{idx,v[idx].back()}]=mp[{v[idx].back(),idx}]=1;
dfs(v[idx].back());
}
[Link](idx);
return;
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
v[x].pb(y);
v[y].pb(x);
}

5|Page
bool x=1;
for(int i=1;i<=n;i++)
x&=v[i].size()%2==0;
dfs(1);
if(!x||[Link]()!=m+1||ans[0]!=[Link]()){
cout<<"IMPOSSIBLE\n";
continue;
}
for(auto it:ans)
cout<<it<<" ";
cout<<"\n";
}
return 0;
}

Distinct Routes (Max-flow):

int n,m,k,snk,rs[1010][1010],vis[1010],par[1010];
vector<int> v[1010],rl[1010];
vector<int> vec;
int bfs(){
queue<pair<int,int>> q;
[Link]({1,MAAX});
while([Link]()){
int idx=[Link]().f,cap=[Link]().s;
[Link]();
if(idx==snk)
return cap;
vis[idx]=1;
for(auto it:v[idx]){
if(rs[idx][it]&&!vis[it]){
vis[it]=1;
par[it]=idx;
[Link]({it,min(cap,rs[idx][it])});
}
}
}

6|Page
return 0;
}
vector<int> cur;
void dfs(int idx=1){
[Link](idx);
if(idx==snk)
return;
for(auto it:rl[idx]){
if(rs[idx][it]==0){
rs[idx][it]++;
dfs(it);
return;
}
}
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>m;
snk=n;
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
rs[x][y]++;
v[x].pb(y);
rl[x].pb(y);
v[y].pb(x);
}
int x,ans=0;
while(x=bfs()){
ans+=x;
int cur=snk;
while(cur){
int prv=par[cur];
rs[prv][cur]-=x;
rs[cur][prv]+=x;
cur=prv;
}
memset(vis,0,sizeof vis);
}
cout<<ans<<"\n";
while(ans--){
dfs(1);
cout<<[Link]()<<"\n";
for(auto it:cur)
cout<<it<<" ";
cout<<"\n";
[Link]();
}
}
return 0;
}

7|Page
Segment tree template:
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

template <typename T>

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>q;
for(int i=0;i<n;i++){
cin>>arr[i];
[Link](i,arr[i]);
}
while(q--){
int l,r;
cin>>l>>r;
l--,r--;

8|Page
cout<<[Link](l,r)<<"\n";
}
}
return 0;
}

Range interval Queries:

#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
// #define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

template <typename T>

9|Page
in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>q;
for(int i=0;i<n;i++){
cin>>arr[i];
[Link](arr[i]);
}
vector<pair<int,int>> qu;
for(int i=0;i<q;i++){
int l,r,a,b;
cin>>l>>r>>a>>b;
l--,r--;
[Link]({a,b});
[Link](a);
[Link](b);
if(l)
idl[l-1].pb(i);
idr[r].pb(i);
}
sort([Link](),[Link]());
unique([Link](),[Link]());
for(int i=0;i<n;i++){
arr[i]=get(arr[i]);
freq[arr[i]]++;
[Link](arr[i],freq[arr[i]]);
for(auto it:idl[i])
ans[it]-=[Link](get(qu[it].f),get(qu[it].s));
for(auto it:idr[i])
ans[it]+=[Link](get(qu[it].f),get(qu[it].s));
}
for(int i=0;i<q;i++)
cout<<ans[i]<<"\n";
}
return 0;
}

Distinct Values Queries I (persistent

segtree):
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
// #define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))

10 | P a g e
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

struct node{
int l,r,val;
};
vector<node> nds;
int update(int cur,int ns,int ne,int pos,int val){
if(ns>pos||ne<pos)
return cur;
[Link](nds[cur]);
cur=[Link]()-1;
if(ns==ne){
nds[cur].val=val;
return cur;
}
int mid=ns+(ne-ns)/2;
nds[cur].l=update(nds[cur].l,ns,mid,pos,val);
nds[cur].r=update(nds[cur].r,mid+1,ne,pos,val);
int l=nds[cur].l,r=nds[cur].r;
nds[cur].val=nds[l].val+nds[r].val;
return cur;
}
int query(int cur,int ns,int ne,int nl,int nr){
if(cur==0)
return 0;
if(ns>nr||ne<nl)
return 0;
if(ns>=nl&&ne<=nr)
return nds[cur].val;
int mid=ns+(ne-ns)/2;
return query(nds[cur].l,ns,mid,nl,nr)+query(nds[cur].r,mid+1,ne,nl,nr);
}
int n,q,arr[200010],roots[200010],freq[200010];
map<int,int> prv;

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>q;
[Link]({0,0,0});
roots[0]=0;
for(int i=1;i<=n;i++){
cin>>arr[i];
roots[i]=update(roots[i-1],0,n,prv[arr[i]],++freq[prv[arr[i]]]);
prv[arr[i]]=i;
}
while(q--){
int l,r;
cin>>l>>r;
cout<<query(roots[r],0,n,0,l-1)-query(roots[l-1],0,n,0,l-1)<<"\n";
}
}
return 0;

11 | P a g e
}

Distinct Values Queries II:

template <typename T>

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;

12 | P a g e
// cin>>tc;
while(tc--){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>arr[i];
[Link](arr[i]);
}
vector<pair<pair<int,int>,int>> qu;
for(int i=0;i<q;i++){
int a,b,c;
cin>>a>>b>>c;
[Link]({{a,b},c});
if(a==1)
[Link](c);
}
int xx=0;
for(auto it:st){
[Link](it);
pos[xx++].insert(0);
}
for(int i=1;i<=n;i++){
arr[i]=get(arr[i]);
pos[arr[i]].insert(i);
prv[i]=lst[arr[i]];
if(prv[i])
nxt[prv[i]]=i;
lst[arr[i]]=i;
[Link](i,prv[i]);
}
for(auto itq:qu){
int t=itq.f.f;
if(t==1){
int k=itq.f.s,x=get(itq.s);
if(nxt[k]){
prv[nxt[k]]=prv[k];
[Link](nxt[k],prv[k]);
}
if(prv[k])
nxt[prv[k]]=nxt[k];
pos[arr[k]].erase(pos[arr[k]].find(k));
arr[k]=x;
auto it=pos[x].lower_bound(k);
it--;
prv[k]=*it;
nxt[k]=0;
if(++it!=pos[x].end())
nxt[k]=*it;
if(prv[k])
nxt[prv[k]]=k;
if(nxt[k])
prv[nxt[k]]=k;
pos[arr[k]].insert(k);
[Link](k,prv[k]);
[Link](nxt[k],k);
}
else{
int l=itq.f.s,r=itq.s;
YN([Link](l,r)<l)
}
}
}

13 | P a g e
return 0;
}

Forest Queries II (2D segtree):

int n,q,tree[4010][4010];
string s[1010];
int build2(int ni,int ns,int ne,int ti,int nx,int ny){
if(ns==ne){
if(nx==ny)
return tree[ti][ni]=s[nx][ns]=='*';
return tree[ti][ni]=tree[ti*2+1][ni]+tree[ti*2+2][ni];
}
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
return tree[ti][ni]=build2(l,ns,mid,ti,nx,ny)+build2(r,mid+1,ne,ti,nx,ny);
}
void build(int ni,int ns,int ne){
if(ns==ne){
build2(0,0,n-1,ni,ns,ne);
return;
}
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
build(l,ns,mid);
build(r,mid+1,ne);
build2(0,0,n-1,ni,ns,ne);
return;
}
int update2(int ni,int ns,int ne,int idx,int val,int ti){
if(ns>idx||ne<idx)
return tree[ti][ni];
if(ns==ne)
return tree[ti][ni]+=val;
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
return tree[ti][ni]=update2(l,ns,mid,idx,val,ti)+update2(r,mid+1,ne,idx,val,ti);

14 | P a g e
}
void update(int ni,int ns,int ne,int idx,int idy,int val){
if(ns>idx||ne<idx)
return;
update2(0,0,n-1,idy,val,ni);
if(ns==ne)
return;
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
update(l,ns,mid,idx,idy,val);
update(r,mid+1,ne,idx,idy,val);
return;
}
int query2(int ni,int ns,int ne,int nl,int nr,int ti){
if(ns>nr||ne<nl)
return 0;
if(ns>=nl&&ne<=nr)
return tree[ti][ni];
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
return query2(l,ns,mid,nl,nr,ti)+query2(r,mid+1,ne,nl,nr,ti);
}
int query(int ni,int ns,int ne,int nl,int nl2,int nr,int nr2){
if(ns>nr||ne<nl)
return 0;
if(ns>=nl&&ne<=nr)
return query2(0,0,n-1,nl2,nr2,ni);
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
return query(l,ns,mid,nl,nl2,nr,nr2)+query(r,mid+1,ne,nl,nl2,nr,nr2);
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>q;
for(int i=0;i<n;i++)
cin>>s[i];
build(0,0,n-1);
while(q--){
int type;
cin>>type;
if(type==1){
int x,y;
cin>>x>>y;
x--,y--;
int v=s[x][y]=='.';
s[x][y]='.';
if(v)
s[x][y]='*';
if(!v)v--;
update(0,0,n-1,x,y,v);
}
else{
int l1,l2,r1,r2;
cin>>l1>>l2>>r1>>r2;
l1--,l2--,r1--,r2--;
cout<<query(0,0,n-1,l1,l2,r1,r2)<<"\n";
}

15 | P a g e
}
}
return 0;
}

Polynomial Queries:
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int n,q,arr[200010],tree[800010],lazy[800010],lsum[800010];
int build(int ni,int ns,int ne){
if(ns==ne)
return tree[ni]=arr[ns];
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
return tree[ni]=build(l,ns,mid)+build(r,mid+1,ne);
}
int calc(int ni,int ns,int ne,int cnt,int sum){
lazy[ni]+=cnt;
lsum[ni]+=sum;
return tree[ni]+=cnt*(ne*(ne+1)/2-ns*(ns-1)/2)-sum*(ne-ns+1);
}
int update(int ni,int ns,int ne,int nl,int nr){
if(ns>nr||ne<nl)
return tree[ni];
if(ns>=nl&&ne<=nr)
return calc(ni,ns,ne,1,nl-1);
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
if(lazy[ni]){
calc(l,ns,mid,lazy[ni],lsum[ni]);
calc(r,mid+1,ne,lazy[ni],lsum[ni]);
lazy[ni]=0;
lsum[ni]=0;
}
return tree[ni]=update(l,ns,mid,nl,nr)+update(r,mid+1,ne,nl,nr);
}
int query(int ni,int ns,int ne,int nl,int nr){
if(ns>nr||ne<nl)

16 | P a g e
return 0;
if(ns>=nl&&ne<=nr)
return tree[ni];
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
if(lazy[ni]){
calc(l,ns,mid,lazy[ni],lsum[ni]);
calc(r,mid+1,ne,lazy[ni],lsum[ni]);
lazy[ni]=0;
lsum[ni]=0;
}
return query(l,ns,mid,nl,nr)+query(r,mid+1,ne,nl,nr);
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>arr[i];
build(0,0,n);
while(q--){
int t;
cin>>t;
if(t==1){
int a,b;
cin>>a>>b;
update(0,0,n,a,b);
}
else{
int a,b;
cin>>a>>b;
cout<<query(0,0,n,a,b)<<"\n";
}
}
}
return 0;
}

Missing Coin Sum Queries:

17 | P a g e
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

struct node{
int l,r,val;
};
node nds[10000010];
int tot;
int update(int cur,int ns,int ne,int pos,int val){
nds[++tot]=nds[cur];
cur=tot;
if(ns==ne){
nds[cur].val+=val;
return cur;
}
int mid=(ns+ne)>>1;
if(pos<=mid)
nds[cur].l=update(nds[cur].l,ns,mid,pos,val);
else
nds[cur].r=update(nds[cur].r,mid+1,ne,pos,val);
int l=nds[cur].l,r=nds[cur].r;
nds[cur].val=nds[l].val+nds[r].val;
return cur;
}
int query(int cur,int ns,int ne,int nl,int nr){
if(cur==0)
return 0;
if(ns>nr||ne<nl)
return 0;
if(ns>=nl&&ne<=nr)
return nds[cur].val;
int mid=(ns+ne)>>1;
return query(nds[cur].l,ns,mid,nl,nr)+query(nds[cur].r,mid+1,ne,nl,nr);
}
int n,q,arr[200010],roots[200010];
vector<int> vec;
int get(int x){
return upper_bound([Link](),[Link](),x)-[Link]()-1;
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>q;
vector<int> vv;
for(int i=1;i<=n;i++){
cin>>arr[i];
[Link](arr[i]);
}
sort([Link](),[Link]());
for(auto it:vv){
if([Link]()||it!=[Link]())
[Link](it);
}
int xx=[Link]()+1;
nds[0]={0,0,0};

18 | P a g e
for(int i=1;i<=n;i++)
roots[i]=update(roots[i-1],0,xx,get(arr[i]),arr[i]);
while(q--){
int a,b;
cin>>a>>b;
int cur=1,prev=1;
while(1){
int l=get(prev-1)+1,r=get(cur);
int x=query(roots[b],0,xx,l,r)-query(roots[a-1],0,xx,l,r);
if(!x)
break;
prev=cur+1;
cur+=x;
}
cout<<cur<<"\n";
}
}
return 0;
}

Path Queries II (HLD):

template <typename T>

19 | P a g e
if (L & 1) l = F(l, S[L++]);
if (R & 1) r = F(S[--R], r);
}
return F(l, r);
}
};
segment_tree<int> tree(200010,0,[](int x,int y){return max(x,y);});
int n,q,arr[200010],comp[200010],id[200010],sz[200010],pr[200010]
[20],hv[200010],vis[200010],depth[200010],st[200010];
vector<int> v[200010];
void dfs(int idx=1,int par=0){
pr[idx][0]=par;
depth[idx]=depth[par]+1;
for(auto it:v[idx]){
if(par==it)
continue;
dfs(it,idx);
sz[idx]+=sz[it];
}
sz[idx]++;
return;
}
int curcmp,curid;
void dfs2(int idx=1,int par=0){
comp[idx]=curcmp;
id[idx]=curid++;
[Link](id[idx],arr[idx]);
int mx=0,mxi;
for(auto it:v[idx]){
if(it==par)
continue;
if(sz[it]>mx)
mx=sz[it],mxi=it;
}
if(mx)
dfs2(mxi,idx);
for(auto it:v[idx]){
if(it==par||it==mxi)
continue;
curcmp++;
st[curcmp]=it;
dfs2(it,idx);
}
return;
}
int up(int x,int k){
return k?up(pr[x][__lg(k)],k-(1ll<<__lg(k))):x?x:-1;
}
int lca(int a,int b){
if(depth[a]<depth[b])
swap(a,b);
a=up(a,depth[a]-depth[b]);
if(a==b)
return a;
for(int i=19;i>=0;i--){
if(pr[a][i]!=pr[b][i])
a=pr[a][i],b=pr[b][i];
}
return pr[a][0];
}
int fun(int cur,int tar){

20 | P a g e
if(comp[cur]==comp[tar])
return [Link](id[tar],id[cur]);
return max(fun(pr[st[comp[cur]]][0],tar),[Link](id[st[comp[cur]]],id[cur]));
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>arr[i];
for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
v[x].pb(y);
v[y].pb(x);
}
dfs();
st[0]=1;
dfs2();
for(int i=1;i<20;i++){
for(int j=1;j<=n;j++)
pr[j][i]=pr[pr[j][i-1]][i-1];
}
while(q--){
int t;
cin>>t;
if(t==1){
int s,x;
cin>>s>>x;
[Link](id[s],x);
}
else{
int a,b;
cin>>a>>b;
int l=lca(a,b);
cout<<max(fun(a,l),fun(b,l))<<" ";
}
}
}
return 0;
}

Fixed-Length Paths I (Centroid decomp):

21 | P a g e
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int n,k,dn[200010],sz[200010];
vector<int> v[200010];
int calcsz(int idx,int par=0){
sz[idx]=1;
for(auto it:v[idx]){
if(it==par||dn[it])
continue;
sz[idx]+=calcsz(it,idx);
}
return sz[idx];
}
int getcent(int idx,int tsz,int par=0){
for(auto it:v[idx]){
if(it==par||dn[it])
continue;
if(sz[it]*2>tsz)
return getcent(it,tsz,idx);
}
return idx;
}
int cfreq[200010],curf[200010],mx;
void dfs(int idx,int par,int d=1){
curf[d]++;
mx=max(mx,d);
for(auto it:v[idx]){
if(it==par||dn[it])
continue;
dfs(it,idx,d+1);
}
return;
}
int cendcmp(int idx=1){
idx=getcent(idx,calcsz(idx));
dn[idx]=1;
int ans=0;
int mxx=0;
cfreq[1]=1;
for(auto it:v[idx]){
if(dn[it])
continue;
mx=0;
dfs(it,idx);
for(int i=0;i<=mx;i++)
ans+=curf[i]*cfreq[k-i];
for(int i=0;i<=mx;i++){
cfreq[i+1]+=curf[i];
curf[i]=0;
}
mxx=max(mxx,mx);
}
memset(cfreq,0,(mxx+10)*sizeof(cfreq[0]));

22 | P a g e
for(auto it:v[idx]){
if(dn[it])
continue;
ans+=cendcmp(it);
}
return ans;
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>k;
k++;
for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
v[x].pb(y);
v[y].pb(x);
}
cout<<cendcmp()<<"\n";
}
return 0;
}

Josephus Queries (k-th child):

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
cin>>tc;
while(tc--){
int n,k;
cin>>n>>k;

23 | P a g e
int cur=0;
int z=0;
int cnt=0;
k++;
while(1){
int x=(n-cur)/(1<<(z+1))+1;
if(cnt+x>=k){
cout<<cur+(k-cnt-1)*(1<<(z+1))<<"\n";
goto a;
}
cnt+=x;
cur^=1<<z;
if((cur|(((~n)>>z)&1)<<(z+1))<=n)
cur|=(((~n)>>z)&1)<<(z+1);
z++;
}
a:;
}
return 0;
}

Divisor Analysis:
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int power(int x,int y){

if(y==0)
return 1;
int z=power(x,y/2);
z*=z;
z%=MOD;
if(y%2)
z*=x;
z%=MOD;
return z;
}
int mi(int x){
return power(x,MOD-2);
}

24 | P a g e
int ax[100010],ay[100010];

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
int n;
cin>>n;
int cnt=1,cnt2=1,sum=1,prod=1;
bool bol=0;
for(int i=0;i<n;i++){
int x,y;
cin>>x>>y;
ax[i]=x,ay[i]=y;
cnt*=y+1;
cnt%=MOD;
if(y%2&&!bol)
cnt2*=(y+1)/2,bol=1;
else
cnt2*=y+1;
cnt2%=MOD-1;
sum*=(power(x,y+1)+MOD-1)%MOD*mi(x-1)%MOD;
sum%=MOD;
}
for(int i=0;i<n;i++){
int x=ax[i],y=ay[i];
int a=cnt2,b=y;
if(bol==0)
b/=2;
prod*=power(x,a*b);
prod%=MOD;
}
cout<<cnt<<" "<<sum<<" "<<prod<<"\n";
}
return 0;
}

Sum of Divisors (1-n):

25 | P a g e
const int MOD=1e9+7;
const int MAX=1e9;

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
int n;
cin>>n;
int ans=0;
for(int i=1;i*i<=n;i++){
if(i!=n/i)
ans+=n/i * i;
ans%=MOD;
int l=n/(i+1),r=n/i;
ans+=i%MOD*((r%MOD*(r%MOD+1)%MOD*((MOD+1)/2)%MOD)-(l%MOD*(l%MOD+1)%MOD*((MOD+1)/2)%MOD))
%MOD;
ans%=MOD;
}
cout<<ans%MOD<<"\n";
}
return 0;
}

Bracket Sequences II:

int power(int x,int y){

if(y==0)
return 1;
int z=power(x,y/2);
z*=z;
z%=MOD;
if(y%2)
z*=x;

26 | P a g e
z%=MOD;
return z;
}
int mi(int x){
return power(x%MOD,MOD-2);
}
int fact[1000010],inv[1000010];
int ncr(int n,int k){
return fact[n]*inv[k]%MOD*inv[n-k]%MOD;
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
fact[0]=inv[0]=1;
for(int i=1;i<=1000000;i++){
fact[i]=fact[i-1]*i%MOD;
inv[i]=mi(fact[i]);
}
while(tc--){
int n;
string s;
cin>>n>>s;
if(n%2){
cout<<"0\n";
continue;
}
int k=0;
for(int i=0;i<[Link]();i++){
if(s[i]==')')
k--;
else
k++;
if(k<0){
cout<<"0\n";
return 0;
}
}
n-=[Link]();
n-=k;
n/=2;
if(n<0){
cout<<"0\n";
return 0;
}
if(n==0){
cout<<"1\n";
return 0;
}
int ans=0;
for(int i=0;i<n+k;i++)
ans+=ncr(n+i-1,i);
for(int i=0;i<n-1;i++)
ans-=ncr(n+k+i,i);
ans%=MOD;
ans+=MOD;
ans%=MOD;
cout<<ans<<"\n";
}
return 0;

27 | P a g e
}

Counting Necklaces:
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int power(int x,int y){

if(y==0)
return 1;
int z=power(x,y/2);
z*=z;
z%=MOD;
if(y%2)
z*=x;
z%=MOD;
return z;
}
int mi(int x){
return power(x,MOD-2);
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
int n,m;
cin>>n>>m;
int ans=0;
for(int i=1;i<=n;i++){
ans+=power(m,__gcd(i,n));
ans%=MOD;
}
ans*=mi(n);
ans%=MOD;
cout<<ans<<"\n";
}
return 0;
}

28 | P a g e
Fibonacci Numbers (Matrix expo):
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

struct matrix{
vector<vector<int>> v;
void init(vector<vector<int>> vec){
this->v=vec;
return;
}
matrix operator*(const matrix x) const{
matrix ans;
int n=this->[Link]();
int m=x.v[0].size();
int m2=this->v[0].size();
[Link](n);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
ans.v[i].pb(0);
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
for(int k=0;k<m2;k++){
ans.v[i][j]+=(this->v[i][k])*(x.v[k][j]);
ans.v[i][j]%=MOD;
}
}
}
return ans;
}
};
matrix mpower(matrix x,int y,matrix init){
if(y==0){
return init;
}
matrix z=mpower(x,y/2,init);
z=z*z;
if(y%2)

29 | P a g e
z=z*x;
return z;
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
int n;
cin>>n;
matrix x;
[Link]({{0,1},{1,1}});
matrix y;
[Link]({{1,0},{0,1}});
cout<<mpower(x,n,y).v[0][1]<<"\n";
}
return 0;
}

System of Linear Equations (Gauss):

int power(int x,int y){

if(y==0)
return 1;
int z=power(x,y/2);
z*=z;
z%=MOD;
if(y%2)
z*=x;
z%=MOD;
return z;
}
int mi(int x){
return power(x,MOD-2);
}
int n,m,vis[510],ans[510];

30 | P a g e
int arr[510][510],org[510][510];

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<=m;j++){
cin>>arr[i][j];
org[i][j]=arr[i][j];
}
}
for(int i=0;i<m;i++){
int idx=-1;
for(int j=n-1;j>=0;j--){
if(arr[j][i]&&!vis[j])
idx=j;
}
if(idx==-1)
continue;
vis[idx]=1;
int x=mi(arr[idx][i]);
for(int j=0;j<=m;j++)
arr[idx][j]=arr[idx][j]*x%MOD;
for(int j=0;j<n;j++){
if(j==idx)
continue;
int z=MOD-arr[j][i];
for(int k=0;k<=m;k++)
arr[j][k]=(arr[j][k]+z*arr[idx][k])%MOD;
}
}
for(int i=0;i<n;i++){
bool bol=0;
for(int j=0;j<m;j++){
if(arr[i][j]==1&&!bol)
ans[j]=arr[i][m];
bol|=!!arr[i][j];
}
if(!bol&&arr[i][m]){
cout<<"-1\n";
return 0;
}
}
for(int i=0;i<m;i++)
cout<<ans[i]<<" ";
cout<<"\n";
}
return 0;
}

All Palindromes (Manacher):

#pragma GCC optimize("O3,unroll-loops,Ofast")

31 | P a g e
#include <bits/stdc++.h>
using namespace std;
typedef int in;
// #define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int tree[800010],lazy[800010];
int update(int ni,int ns,int ne,int nl,int nr,int val){
if(ns>nr||ne<nl)
return tree[ni];
if(ns>=nl&&ne<=nr){
lazy[ni]=min(lazy[ni],val);
tree[ni]=min(tree[ni],val);
return tree[ni];
}
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
tree[l]=min(tree[l],lazy[ni]);
tree[r]=min(tree[r],lazy[ni]);
lazy[l]=min(lazy[l],lazy[ni]);
lazy[r]=min(lazy[r],lazy[ni]);
lazy[ni]=MAAX;
return tree[ni]=min(update(l,ns,mid,nl,nr,val),update(r,mid+1,ne,nl,nr,val));
}
int query(int ni,int ns,int ne,int idx){
if(ns>idx||ne<idx)
return MAAX;
if(ns==ne)
return tree[ni];
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
tree[l]=min(tree[l],lazy[ni]);
tree[r]=min(tree[r],lazy[ni]);
lazy[l]=min(lazy[l],lazy[ni]);
lazy[r]=min(lazy[r],lazy[ni]);
lazy[ni]=MAAX;
return min(query(l,ns,mid,idx),query(r,mid+1,ne,idx));
}
int devn[200010],dodd[200010];
int d[400010];
void runman(string s){
int l=0,r=1;
d[0]=1;
for(int i=1;i+1<[Link]();i++){
if(i<r)
d[i]=min(r-i,d[l+(r-i)]);
while(s[i-d[i]]==s[i+d[i]]){
d[i]++;
}

32 | P a g e
if(i+d[i]>r)
r=i+d[i],l=i-d[i];
}
d[[Link]()-1]=1;
}
void manacher(string s){
string t="$#";
for(int i=0;i<[Link]();i++){
t+=s[i];
t+="#";
}
t+="%";
runman(t);
for(int i=2;i+2<[Link]();i++){
if(i%2)
devn[i/2-1]=d[i]/2;
else
dodd[i/2-1]=d[i]/2;
}
return;
}
string s;

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>s;
manacher(s);
int n=[Link]();
for(int i=0;i<=n*4;i++)
tree[i]=MAAX,lazy[i]=MAAX;
for(int i=0;i<n;i++){
update(0,0,n-1,i,i+dodd[i]-1,i*2-1);
if(devn[i])
update(0,0,n-1,i+1,i+devn[i],i*2);
}
for(int i=0;i<n;i++){
int x=query(0,0,n-1,i);
cout<<(i-x/2)*2-x%2<<" ";
}
}
return 0;
}

Palindrome Queries (Hashed template):

#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second

33 | P a g e
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

template <typename T>

struct segment_tree {
int N;
T E;
vector <T> S;
function <T(T, T)> F;
segment_tree(int n, T e, function <T(T, T)> f) : N(n), E(e), S(n << 1, e), F(f) {}
void update(int j, T x) {
for (S[j += N] = x; j >>= 1; ) S[j] = F(S[j << 1], S[j << 1 | 1]);
}
T get(int L, int R) {
if(L < 0 || R < 0 || L > R) return E;
R++;
T l = E, r = E;
for (L += N, R += N; L < R; L >>= 1, R >>= 1) {
if (L & 1) l = F(l, S[L++]);
if (R & 1) r = F(S[--R], r);
}
return F(l, r);
}
};
segment_tree<pair<int,int>> preftree(200000,{0,0},[](pair<int,int> x,pair<int,int> y){in
mod1=1000001011,mod2=1000010101;return make_pair((x.f+y.f)%mod1,(x.s+y.s)%mod2);});
segment_tree<pair<int,int>> suftree(200000,{0,0},[](pair<int,int> x,pair<int,int> y){in
mod1=1000001011,mod2=1000010101;return make_pair((x.f+y.f)%mod1,(x.s+y.s)%mod2);});
int premi1[1000010],premi2[1000010],prepow1[1000010],prepow2[1000010];
in powerm(int x,in y,in mod){
int res = 1;
while (y > 0) {
if (y & 1){
res = res * x;
res%=mod;
}
y = y >> 1;
x = x * x;
x%=mod;
}
return res;
}
in mim(in y,in mod){
return powerm(y,mod-2,mod);;
}
struct hashed{
string s;
in mod1=1000001011,mod2=1000010101;
vector<in> pref,suf,pref2,suf2;
void precomp(){
int cur1=1,cur2=1;
int x=mim(83,this->mod1);
int y=mim(83,this->mod2);

34 | P a g e
int xpow=1,ypow=1;
for(int i=0;i<=this->[Link]();i++){
premi1[i]=cur1;
premi2[i]=cur2;
prepow1[i]=xpow;
prepow2[i]=ypow;
cur1*=x;
cur2*=y;
cur1%=this->mod1;
cur2%=this->mod2;
xpow*=83;
ypow*=83;
xpow%=this->mod1;
ypow%=this->mod2;
}
}
void calchash(string t){
this->[Link]([Link]());
this->[Link]([Link]());
this->[Link]([Link]()+1);
this->[Link]([Link]()+1);
this->s=t;
int cur1=1,cur2=1;
for(in i=0;i<(in)[Link]();i++){
this->pref[i]=0,this->pref2[i]=0;
if(i){
this->pref[i]=this->pref[i-1];
this->pref2[i]=this->pref2[i-1];
}
this->pref[i]+=(t[i]-'A'+1)*cur1%mod1;
this->pref2[i]+=(t[i]-'A'+1)*cur2%mod2;
if(pref[i]>=this->mod1)
pref[i]-=this->mod1;
if(pref2[i]>=this->mod2)
pref2[i]-=this->mod2;
cur1*=83;
cur2*=83;
cur1%=this->mod1;
cur2%=this->mod2;
}
this->suf[[Link]()]=0;
this->suf2[[Link]()]=0;
cur1=1,cur2=1;
for(in i=[Link]()-1;i>=0;i--){
this->suf[i]=this->suf[i+1];
this->suf2[i]=this->suf2[i+1];
this->suf[i]+=(t[i]-'A'+1)*cur1%mod1;
this->suf2[i]+=(t[i]-'A'+1)*cur2%mod2;
if(suf[i]>=this->mod1)
suf[i]-=this->mod1;
if(suf2[i]>=this->mod2)
suf2[i]-=this->mod2;
cur1*=83;
cur2*=83;
cur1%=this->mod1;
cur2%=this->mod2;
}
return;
}
pair<in,in> gethash(in l,in r,bool seg=0){
if(l<=r){

35 | P a g e
int x,y;
if(!seg)
x=this->pref[r]-(l?this->pref[l-1]:0)+this->mod1,y=this->pref2[r]-(l?this->pref2[l-
1]:0)+this->mod2;
else
x=[Link](l,r).f,y=[Link](l,r).s;
if(x>=this->mod1)
x-=this->mod1;
if(y>=this->mod2)
y-=this->mod2;
return {(1ll*x*(premi1[l]?premi1[l]:mim(powerm(83,l,this->mod1),this->mod1)))%this->mod1,
(1ll*y*(premi2[l]?premi2[l]:mim(powerm(83,l,this->mod2),this->mod2)))%this->mod2};
}
int x,y;
if(!seg)
x=this->suf[r]-this->suf[l+1]+mod1,y=this->suf2[r]-this->suf2[l+1]+mod2;
else
x=[Link](r,l).f,y=[Link](r,l).s;
if(x>=this->mod1)
x-=this->mod1;
if(y>=this->mod2)
y-=this->mod2;
return {1ll*x*(premi1[this->[Link]()-l-1]?premi1[this->[Link]()-l-1]:mim(powerm(83,this-
>[Link]()-l-1,this->mod1),this->mod1))%this->mod1,1ll*y*(premi2[this->[Link]()-l-1]?premi2[this-
>[Link]()-l-1]:mim(powerm(83,this->[Link]()-l-1,this->mod2),this->mod2))%this->mod2};
}
bool compsub(in l1,in r1,in l2,in r2,bool seg=0){
return gethash(l1,r1,seg)==gethash(l2,r2,seg);
}
void build(){
int n=this->[Link]();
for(int i=0;i<n;i++){
[Link](i,gethash(0,i));
if(i)
[Link](i,{(gethash(0,i).f-gethash(0,i-1).f+this->mod1)%this->mod1,
(gethash(0,i).s-gethash(0,i-1).s+this->mod2)%this->mod2});
[Link](i,gethash(n-1,i));
if(i<n-1)
[Link](i,{(gethash(n-1,i).f-gethash(n-1,i+1).f+this->mod1)%this->mod1,
(gethash(n-1,i).s-gethash(n-1,i+1).s+this->mod2)%this->mod2});
}
return;
}
void update(int idx,char c){
int n=this->[Link]();
[Link](idx,{(prepow1[idx]?prepow1[idx]:powerm(83,idx,this->mod1))*(c-'A'+1)%this-
>mod1,(prepow2[idx]?prepow2[idx]:powerm(83,idx,this->mod2))*(c-'A'+1)%this->mod2});
[Link](idx,{(prepow1[n-idx-1]?prepow1[n-idx-1]:powerm(83,n-idx-1,this-
>mod1))*(c-'A'+1)%this->mod1,(prepow2[n-idx-1]?prepow2[n-idx-1]:powerm(83,n-idx-1,this-
>mod2))*(c-'A'+1)%this->mod2});
return;
}
};

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
int n,q;
string s;

36 | P a g e
cin>>n>>q>>s;
hashed sh;
[Link](s);
[Link]();
[Link]();
while(q--){
int type;
cin>>type;
if(type==1){
int idx;
char c;
cin>>idx>>c;
[Link](idx-1,c);
}
else{
int l,r;
cin>>l>>r;
l--,r--;
YN([Link](l,r,r,l,1));
}
}
}
return 0;
}

String Functions (kmp and Z algo):

string s;
int pi[1000010],z[1000010];

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>s;
int n=[Link]();

37 | P a g e
for(int i=1;i<n;i++){
int j=pi[i-1];
while(j&&s[j]!=s[i])
j=pi[j-1];
if(s[j]==s[i])
j++;
pi[i]=j;
}
int l=1,r=0;
z[0]=0;
for(int i=1;i<n;i++){
if(i<=r)
z[i]=min(r-i,z[i-l]);
while(i+z[i]<[Link]()&&s[i+z[i]]==s[z[i]])z[i]++;
if(r<i+z[i])
l=i,r=i+z[i];
}
for(int i=0;i<n;i++)
cout<<z[i]<<" ";
cout<<"\n";
for(int i=0;i<n;i++)
cout<<pi[i]<<" ";
cout<<"\n";
}
return 0;
}

Substring Order II (Includes Suffix Array

and LCP):
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

vector<int> sort_cyclic_shifts(string const& s) {

int n = [Link]();
const int alphabet = 256;

38 | P a g e
vector<int> p(n), c(n), cnt(max(alphabet, n), 0);
for (int i = 0; i < n; i++)
cnt[s[i]]++;
for (int i = 1; i < alphabet; i++)
cnt[i] += cnt[i-1];
for (int i = 0; i < n; i++)
p[--cnt[s[i]]] = i;
c[p[0]] = 0;
int classes = 1;
for (int i = 1; i < n; i++) {
if (s[p[i]] != s[p[i-1]])
classes++;
c[p[i]] = classes - 1;
}
vector<int> pn(n), cn(n);
for (int h = 0; (1 << h) < n; ++h) {
for (int i = 0; i < n; i++) {
pn[i] = p[i] - (1 << h);
if (pn[i] < 0)
pn[i] += n;
}
fill([Link](), [Link]() + classes, 0);
for (int i = 0; i < n; i++)
cnt[c[pn[i]]]++;
for (int i = 1; i < classes; i++)
cnt[i] += cnt[i-1];
for (int i = n-1; i >= 0; i--)
p[--cnt[c[pn[i]]]] = pn[i];
cn[p[0]] = 0;
classes = 1;
for (int i = 1; i < n; i++) {
pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
if (cur != prev)
++classes;
cn[p[i]] = classes - 1;
}
[Link](cn);
}
return p;
}
vector<int> suffix_array_construction(string s) {
s += "$";
vector<int> sorted_shifts = sort_cyclic_shifts(s);
sorted_shifts.erase(sorted_shifts.begin());
return sorted_shifts;
}
vector<int> kasai(string &s,vector<int> &sa){
int n=[Link](),k=0;
vector<int> lcp(n,0);
vector<int> rank(n,0);
for(int i=0;i<n;i++)
rank[sa[i]]=i;
for(int i=0;i<n;i++,k?k--:0){
if(rank[i]==n-1){
k=0;
continue;
}
int j=sa[rank[i]+1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
lcp[rank[i]]=k;

39 | P a g e
}
return lcp;
}
template <typename T>
struct segment_tree {
int N;
T E;
vector <T> S;
function <T(T, T)> F;
segment_tree(int n, T e, function <T(T, T)> f) : N(n), E(e), S(n << 1, e), F(f) {}
void update(int j, T x) {
for (S[j += N] = x; j >>= 1; ) S[j] = F(S[j << 1], S[j << 1 | 1]);
}
T get(int L, int R) {
if(L < 0 || R < 0 || L > R) return E;
R++;
T l = E, r = E;
for (L += N, R += N; L < R; L >>= 1, R >>= 1) {
if (L & 1) l = F(l, S[L++]);
if (R & 1) r = F(S[--R], r);
}
return F(l, r);
}
};
segment_tree<int> tree(100010,MAAX,[](int x,int y){return min(x,y);});
string s;
int n,k,pref[100010],arr[100010],p[100010][20],ans[100010][20];
void pre(){
for(int i=1;i<=n;i++)
pref[i]=pref[i-1]+arr[i];
stack<int> st;
arr[n+1]=MAAX;
[Link](n+1);
for(int i=n;i>=1;i--){
while(arr[i]>=arr[[Link]()])
[Link]();
int x=[Link]();
p[i][0]=x;
ans[i][0]=arr[i]*(x-i)-pref[x-1]+pref[i-1];
[Link](i);
}
p[n+1][0]=n+1;
for(int i=1;i<20;i++){
for(int j=1;j<=n+1;j++){
p[j][i]=p[p[j][i-1]][i-1];
ans[j][i]=ans[j][i-1]+ans[p[j][i-1]][i-1];
}
}
return;
}
int query(int l,int r){
if(l==0)
l++;
int x=0;
int cur=l;
for(int i=19;i>=0;i--){
if(p[cur][i]<=r)
x+=ans[cur][i],cur=p[cur][i];
}
x+=arr[cur]*(r-cur)-pref[r]+pref[cur];
return x;

40 | P a g e
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>s>>k;
n=[Link]();
vector<int> sa=suffix_array_construction(s);
vector<int> lcp=kasai(s,sa);
for(int i=0;i<n;i++)
arr[i+1]=-lcp[i];
pre();
vector<int> v(n,0);
for(int i=0;i<n;i++)
[Link](i,lcp[i]);
for(int i=0;i<n;i++){
int prv=0;
if(i)
prv=lcp[i-1];
int st=i-1,e=n-1;
while(st<e){
int mid=st+(e-st+1)/2;
if([Link](i,mid)>prv)
st=mid;
else
e=mid-1;
}
int sm=n-sa[i]+(-pref[st+1]+pref[i])-query(i+1,st+1);
sm=sm-prv*(st-i+2);
if(sm<k)
k-=sm;
else{
int cur=n-sa[i],idx=i,sum=0;
while(cur>prv){
sum+=cur-prv;
v[cur-prv]++;
cur=min(cur,lcp[idx++]);
}
for(int j=n-sa[i];j>=0;j--)
v[j]+=v[j+1];
for(int j=sa[i];k>0;j++){
cout<<s[j];
if(j-sa[i]+1-prv>0)
k-=v[j-sa[i]+1-prv];
}
return 0;
}
}
}
return 0;
}

41 | P a g e
Polygon Lattice Points (Geometry
Template):
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define X real()
#define Y imag()

namespace geometry{
using Real = long long;
using Point = complex<Real>;
const Real EPS = 1e-12;
const Real PI = acos(-1);
inline bool equal(const Real& a, const Real& b){
return fabs(a - b) < EPS;
}
inline int sign(const Real &r) { return r <= -EPS ? -1 : r >= EPS ? 1 : 0; }
bool compare_x(const Point &a, const Point &b) {
return equal(real(a), real(b)) ? imag(a) < imag(b) : real(a) < real(b);
}
bool compare_y(const Point &a, const Point &b) {
return equal(imag(a), imag(b)) ? real(a) < real(b) : imag(a) < imag(b);
}
Point unitvector(const Point& a){
return a / abs(a);
}
Point normalvector(const Point& a){
return a * Point(0, 1);
}
Real dot(const Point &a, const Point &b){
return ([Link]() * [Link]() + [Link]() * [Link]());
}
Real cross(const Point &a, const Point &b){
return ([Link]() * [Link]() - [Link]() * [Link]());
}
Point rotate(const Point &p, const Real &rad){
return Point([Link]() * cos(rad) - [Link]() * sin(rad), [Link]() * sin(rad) + [Link]() *
cos(rad));
}
Real radtodeg(const Real &rad){
return rad * 180 / PI;
}
Real degtorad(const Real &deg){
return deg * PI / 180;
}
struct Line{
Point a, b;
Line() = default;
Line(const Point &a, const Point &b): a(a), b(b){}
Line(Real A, Real B, Real C){
if(equal(A, 0)){
a = Point(0, C / B);
b = Point(1, C / B);
}else if(equal(B, 0)){
a = Point(C / A, 0);

42 | P a g e
b = Point(C / A, 1);
}else{
a = Point(0, C / B);
b = Point(C / A, 0);
}
}
};
struct Segment: Line{
Segment() = default;
Segment(Point a, Point b): Line(a, b){}
};
struct Circle{
Point p;
Real r;
Circle() = default;
Circle(const Point &p, const Real &r): p(p), r(r){}
};
Point projection(const Line &l, const Point &p){
Real t = dot(p - l.a, l.a - l.b);
t /= norm(l.a - l.b);
return l.a + (l.a - l.b) * t;
}
Point reflection(const Line &l, const Point &p){
return p + (projection(l, p) - p) * (Real)2;
}
int ccw(const Point &a, const Point &b, const Point &c){
Point d = b - a;
Point e = c - a;
if(cross(d, e) > EPS) return 1; // counter clockwise
if(cross(d, e) < -EPS) return -1; // clockwise
if(dot(d, e) < 0) return 2; // c-b-a
if(norm(d) < norm(e)) return -2; // a-b-c
return 0; // a-c-b
}
bool is_orthogonal(const Line &l1, const Line &l2){
return equal(dot(l1.b - l1.a, l2.b - l2.a), 0);
}
bool is_parallel(const Line &l1, const Line &l2){
return equal(cross(l1.b - l1.a, l2.b - l2.a), 0);
}
bool is_intersect(const Segment &s1, const Segment &s2){
return (ccw(s1.a, s1.b, s2.a) * ccw(s1.a, s1.b, s2.b) <= 0 && ccw(s2.a, s2.b, s1.a) * ccw(s2.a,
s2.b, s1.b) <= 0);
}
Point crosspoint(const Line &l1, const Line &l2){
Real A = cross(l1.b - l1.a, l2.b - l2.a);
Real B = cross(l1.b - l1.a, l1.b - l2.a);
if(equal(abs(A), 0) && equal(abs(B), 0)){
return l1.a;
}
return (l2.b - l2.a) * (B / A) + l2.a;
}
Point crosspoint(const Segment &s1, const Segment &s2){
return crosspoint(Line(s1), Line(s2));
}
Real distanceLineAndPoint(const Line &l, const Point &p){
return abs(cross(l.b - l.a, p - l.a)) / abs(l.b - l.a);
}
Real distanceSegmentAndPoint(const Segment &l, const Point &p){
if(dot(l.b - l.a, p - l.a) < EPS){
return abs(p - l.a);

43 | P a g e
}
if(dot(l.a - l.b, p - l.b) < EPS){
return abs(p - l.b);
}
return abs(cross(l.b - l.a, p - l.a)) / abs(l.b - l.a);
}
Real distanceSegmentAndSegment(const Segment &s1, const Segment &s2){
if(is_intersect(s1, s2)){
return (Real)(0);
}
return min({distanceSegmentAndPoint(s1, s2.a), distanceSegmentAndPoint(s1, s2.b),
distanceSegmentAndPoint(s2, s1.a), distanceSegmentAndPoint(s2, s1.b)});
}
Real PolygonArea(const vector<Point> &p){
Real res = 0;
int n = [Link]();
for(int i = 0; i < n - 1; ++i){
res += cross(p[i], p[i + 1]);
}
res += cross(p[n - 1], p[0]);
return abs(res);
}
bool isConvex(const vector<Point> &p){
int n = [Link]();
int now, pre, nxt;
for(int i = 0; i < n; ++i){
pre = (i - 1 + n) % n;
nxt = (i + 1) % n;
now = i;
if(ccw(p[pre], p[now], p[nxt]) == -1){
return false;
}
}
return true;
}
int isContained(const vector<Point> &g, const Point &p){
bool in = false;
int n = (int)[Link]();
for(int i = 0; i < n; ++i){
Point a = g[i] - p;
Point b = g[(i + 1) % n] - p;
if(imag(a) > imag(b)) swap(a, b);
if(imag(a) <= EPS && EPS < imag(b) && cross(a, b) < -EPS) in = !in;
if(cross(a, b) == 0 && dot(a, b) <= 0) return 1;
}
return (in ? 2 : 0);
}
vector<Point> ConvexHull(vector<Point> &p, bool strict = true){
long double si = -1;
if(strict) si = 1;
int n = (int)[Link](), k = 0;
sort(begin(p), end(p), [](const Point &a, const Point &b){
return (real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b));
});
vector<Point> ch(2 * n);

for(int i = 0; i < n; ch[k++] = p[i++]){

while(k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS * si) --k;
}
for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]){
while(k >= t && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS * si) --k;

44 | P a g e
}
[Link](k - 1);
return ch;
}
pair<int, int> ConvexDiameter(const vector<Point> &p){
int n = (int)[Link]();
int is = 0, js = 0;
for(int i = 1; i < n; ++i){
if(imag(p[i]) > imag(p[is])) is = i;
if(imag(p[i]) < imag(p[js])) js = i;
}
Real maxdis = norm(p[is] - p[js]);
int maxi, maxj, i, j;
i = maxi = is;
j = maxj = js;
do{
if(cross(p[(i + 1) % n] - p[i], p[(j + 1) % n] - p[j]) >= 0){
j = (j + 1) % n;
}else{
i = (i + 1) % n;
}
if(norm(p[i] - p[j]) > maxdis){
maxdis = norm(p[i] - p[j]);
maxi = i;
maxj = j;
}
}while(i != is || j != js);
return make_pair(maxi, maxj);
}
vector<Point> ConvexCut(const vector<Point> &p, const Line &l){
vector<Point> ret;
for(int i = 0; i < [Link](); ++i){
const Point &now = p[i];
const Point &nxt = p[(i + 1) % [Link]()];
auto cf = cross(l.a - now, l.b - now);
auto cs = cross(l.a - nxt, l.b - nxt);
if(sign(cf) >= 0){
ret.push_back(now);
}
if(sign(cf) * sign(cs) < 0){
ret.push_back(crosspoint(Line(now, nxt), l));
}
}
return ret;
}
Real ClosestPair(vector<Point> p){
sort(begin(p), end(p), [](const Point &a, const Point &b){
return real(a) < real(b);
});
int n = [Link]();
if(n <= 1){
return 1e18;
}
int m = n / 2;
Real x = real(p[m]);
Real res = min(ClosestPair(vector<Point>(begin(p), begin(p) + m)),
ClosestPair(vector<Point>(begin(p) + m, end(p))));
sort(begin(p), end(p), [](const Point &a, const Point &b){
return imag(a) < imag(b);
});
deque<int> deq;

45 | P a g e
for(int i = 0; i < n; ++i){
if(res - abs(real(p[i]) - x) < EPS) continue;
while(![Link]() && imag(p[[Link]()]) - imag(p[i]) + res < EPS) deq.pop_front();
for(auto e: deq){
if(res > sqrt(norm(p[i] - p[e]))){
res = sqrt(norm(p[i] - p[e]));
}
}
deq.push_back(i);
}
return res;
}
Circle MinimumEnclosingCircle(vector<Point> p, int seed = random_device()()){
int n = [Link]();
assert(n >= 1);
if(n == 1){
return Circle(p[0], 0.0);
}
std::mt19937 mt(seed);
std::shuffle(begin(p), end(p), mt);
auto ps = begin(p);
auto make_circle_3 = [](const Point &a, const Point &b, const Point &c) -> Circle {
Real A = norm(b - c), B = norm(c - a), C = norm(a - b);
Real S = cross(b - a, c - a);
Point p = (A * (B + C - A) * a + B * (C + A - B) * b + C * (A + B - C) * c) / (4 * S * S);
Real r2 = norm(p - a);
return Circle(p, r2);
};
auto make_circle_2 = [](const Point &a, const Point &b) -> Circle {
Point c = (a + b) / (Real)2;
Real r2 = norm(a - c);
return Circle(c, r2);
};
auto in_circle = [](const Point &a, const Circle &c) -> bool {
return norm(a - c.p) <= c.r + EPS;
};
Circle c = make_circle_2(ps[0], ps[1]);
for(int i = 2; i < n; ++i){
if(!in_circle(ps[i], c)){
c = make_circle_2(ps[0], ps[i]);
for(int j = 1; j < i; ++j){
if(!in_circle(ps[j], c)){
c = make_circle_2(ps[i], ps[j]);
for(int k = 0; k < j; ++k){
if(!in_circle(ps[k], c)){
c = make_circle_3(ps[i], ps[j], ps[k]);
}
}
}
}
}
}
c.r = sqrt(c.r);
return c;
}
int CircleIntersect(const Circle &c1, const Circle &c2){
Real dist = (real(c1.p) - real(c2.p)) * (real(c1.p) - real(c2.p)) + (imag(c1.p) - imag(c2.p)) *
(imag(c1.p) - imag(c2.p));
if(equal(dist, (c1.r - c2.r) * (c1.r - c2.r))) return 1;
if(equal(dist, (c1.r + c2.r) * (c1.r + c2.r))) return 3;
if(dist > (c1.r + c2.r) * (c1.r + c2.r)) return 4;

46 | P a g e
if(dist < (c1.r - c2.r) * (c1.r - c2.r)) return 0;
return 2;
}
Circle InCircle(const Point &a, const Point &b, const Point &c){
Real A = abs(b - c), B = abs(c - a), C = abs(a - b);
Point p(A * real(a) + B * real(b) + C * real(c), A * imag(a) + B * imag(b) + C * imag(c));
p /= (A + B + C);
Real r = distanceLineAndPoint(Line(a, b), p);
return Circle(p, r);
}
Circle CircumCircle(const Point &a, const Point &b, const Point &c){
Real A = norm(b - c), B = norm(c - a), C = norm(a - b);
Real S = cross(b - a, c - a);
Point p = (A * (B + C - A) * a + B * (C + A - B) * b + C * (A + B - C) * c) / (4 * S * S);
Real r = abs(p - a);
return Circle(p, r);
}
vector<Point> CrossPointLineAndCircle(const Circle &c, const Line &l){
vector<Point> res;
Real d = distanceLineAndPoint(l, c.p);
if(d > c.r + EPS) return res;
Point h = projection(l, c.p);
if(equal(d, c.r)){
res.push_back(h);
return res;
}
Point e = unitvector(l.b - l.a);
Real ph = sqrt(c.r * c.r - d * d);
res.push_back(h - e * ph);
res.push_back(h + e * ph);
return res;
}
vector<Point> CrossPointSegmentAndCircle(const Circle &c, const Segment &l){
auto res1 = CrossPointLineAndCircle(c, (Line)l);
vector<Point> res;
for(auto p: res1){
if(abs(ccw(l.a, p, l.b)) == 2) res.push_back(p);
}
return res;
}
vector<Point> CrossPointCircleAndCircle(const Circle &c1, const Circle &c2){
vector<Point> res;
int mode = CircleIntersect(c1, c2);
Real d = abs(c1.p - c2.p);
if(mode == 4){
return res;
}
if(mode == 0){
return res;
}
if(mode == 3){
Real t = c1.r / (c1.r + c2.r);
res.push_back(c1.p + (c2.p - c1.p) * t);
return res;
}
if(mode == 1){
if(c2.r < c1.r - EPS){
res.push_back(c1.p + (c2.p - c1.p) * (c1.r / d));
}else{
res.push_back(c2.p + (c1.p - c2.p) * (c2.r / d));
}

47 | P a g e
return res;
}
Real rc1 = (c1.r * c1.r + d * d - c2.r * c2.r) / (2 * d);
Real rs1 = sqrt(c1.r * c1.r - rc1 * rc1);
if(c1.r - abs(rc1) < EPS)
rs1 = 0;
Point e12 = (c2.p - c1.p) / abs(c2.p - c1.p);
res.push_back(c1.p + rc1 * e12 + rs1 * e12 * Point(0, 1));
res.push_back(c1.p + rc1 * e12 + rs1 * e12 * Point(0, -1));
return res;
}
vector<Point> tangentToCircle(const Point &p, const Circle &c){
return CrossPointCircleAndCircle(c, Circle(p, sqrt(norm(c.p - p) - c.r * c.r)));
}

Real CommonAreaCircleAndPolygon(const Circle &c, const vector<Point> &ps){

const int n = [Link]();
vector<Point> nps;
for(int i = 0; i < n; ++i){
Point p1 = ps[i], p2 = ps[(i + 1) % n];
nps.push_back(p1 - c.p);
auto res1 = CrossPointLineAndCircle(c, Line(p1, p2));
if([Link]() == 2){
Point dp1 = res1[0], dp2 = res1[1];
Real ratio1 = dot(dp1 - p1, p2 - p1) / norm(p2 - p1);
Real ratio2 = dot(dp2 - p1, p2 - p1) / norm(p2 - p1);
if(0 < ratio1 && ratio1 < 1){
if(0 < ratio2 && ratio2 < 1){
if(ratio1 > ratio2) swap(dp1, dp2);
nps.push_back(dp1 - c.p);
nps.push_back(dp2 - c.p);
}else{
nps.push_back(dp1 - c.p);
}
}else if(0 < ratio2 && ratio2 < 1){
nps.push_back(dp2 - c.p);
}
}
}
int m = [Link]();
Real res = 0;
for(int i = 0; i < m; ++i){
Point p1 = nps[i], p2 = nps[(i + 1) % m];
Point mid = (p1 + p2) / (Real)2.0;
if(norm(mid) > c.r * c.r - EPS){
Real th = atan2(cross(p1, p2), dot(p1, p2));
res += c.r * c.r * th / 2.0;
}else{
res += cross(p1, p2) / 2.0;
}
}
return res;
}
Real CommonAreaCircleAndCircle(const Circle &c1, const Circle &c2){
Real d = norm(c1.p - c2.p);
Real res = 0.0;
if(d <= (c1.r - c2.r) * (c1.r - c2.r)) res = min(c1.r, c2.r) * min(c1.r, c2.r) * acos(-1);
else if(d < (c1.r + c2.r) * (c1.r + c2.r)){
Real t1 = acosl((Real)(c1.r * c1.r - c2.r * c2.r + d) / 2.0 / c1.r / sqrtl(d));
Real t2 = acosl((Real)(c2.r * c2.r - c1.r * c1.r + d) / 2.0 / c2.r / sqrtl(d));

48 | P a g e
res = c1.r * c1.r * t1 + c2.r * c2.r * t2 - c1.r * c1.r * sinl(2 * t1) / 2.0 - c2.r * c2.r
* sinl(2 * t2) / 2.0;
}
return res;
}
Point readPoint(){
Real x,y;
int a,b;
cin>>a>>b;
x=a,y=b;
return Point(x,y);
}
}

using namespace geometry;

typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int get(Point x,Point y){

return __gcd((int)(abs(real(x)-real(y))+EPS),(int)(abs(imag(y)-imag(x))+EPS));
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
int n;
cin>>n;
vector<Point> v;
while(n--)
[Link](readPoint());
int a2=PolygonArea(v);
int b=get([Link](),v[0]);
for(int i=1;i<[Link]();i++)
b+=get(v[i],v[i-1]);
int i=(a2-b)/2+1;
cout<<i<<" "<<b<<"\n";
}
return 0;
}

49 | P a g e
Lines and Queries II (Li-chao tree):
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

typedef complex<int> point;

#define x real
#define y imag
int dot(point a,point b){
return (conj(a)*b).x();
}
int f(point a,int x){
return dot(a,{x,1});
}
point tree[400010];
void add(int ni,int ns,int ne,point nw){
int mid=ns+(ne-ns)/2;
bool lf=f(nw,ns)>f(tree[ni],ns);
bool md=f(nw,mid)>f(tree[ni],mid);
if(md)
swap(tree[ni],nw);
if(ns==ne)
return;
int l=ni*2+1,r=ni*2+2;
if(lf!=md)
add(l,ns,mid,nw);
else
add(r,mid+1,ne,nw);
return;
}
void update(int ni,int ns,int ne,int nl,int nr,point nw){
if(ns>nr||ne<nl)
return;
if(ns>=nl&&ne<=nr){
add(ni,ns,ne,nw);
return;
}
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
update(l,ns,mid,nl,nr,nw);
update(r,mid+1,ne,nl,nr,nw);
return;
}

50 | P a g e
int get(int ni,int ns,int ne,int x){
if(ns>x||ne<x)
return -MAAX;
if(ns==ne)
return f(tree[ni],x);
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
return max({f(tree[ni],x),get(r,mid+1,ne,x),get(l,ns,mid,x)});
}
int n;

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
for(int i=0;i<=4e5;i++)
tree[i]={0,-MAAX};
cin>>n;
while(n--){
int type;
cin>>type;
if(type==1){
int a,b,l,r;
cin>>a>>b>>l>>r;
update(0,0,1e5,l,r,{a,b});
}
else{
int x;
cin>>x;
int ans=get(0,0,1e5,x);
if(ans==-MAAX)
YN(0)
else
cout<<ans<<"\n";
}
}
}
return 0;
}

Reachability Queries (SCC):

51 | P a g e
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int n,m,q;
vector<int> v[50010],rv[50010];
int visscc[200010],visscc2[200010],root[1000010];
vector<int> vc[200010],comp,ord,roots;
set<int> ste[200010];
void dfsnorm(int idx){
if(visscc[idx])
return;
visscc[idx]=1;
for(int i=0;i<(int)v[idx].size();i++)
dfsnorm(v[idx][i]);
[Link](idx);
return;
}
void dfsrev(int idx){
if(visscc2[idx])
return;
visscc2[idx]=1;
for(int i=0;i<(int)rv[idx].size();i++)
dfsrev(rv[idx][i]);
[Link](idx);
return;
}
void scc(){
for(int i=1;i<=n;i++){
if(!visscc[i])
dfsnorm(i);
}
reverse([Link](),[Link]());
for(int i=0;i<n;i++){
if(!visscc2[ord[i]]){
[Link]();
dfsrev(ord[i]);
int x=[Link]();
[Link](x);
for(int j=0;j<(int)[Link]();j++)
root[comp[j]]=x;
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<(int)v[i].size();j++){
int x=root[i];
int y=root[v[i][j]];
if(x==y)
continue;
ste[x].insert(y);
}
}
for(int i=1;i<=n;i++){
for(auto it:ste[i])
vc[i].pb(it);
}
return;
}

52 | P a g e
bitset<50010> ans[50010];
void dfs(int idx){
if(ans[idx][idx])
return;
ans[idx][idx]=1;
for(auto it:vc[idx]){
dfs(it);
ans[idx]|=ans[it];
}
return;
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>m>>q;
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
v[x].pb(y);
rv[y].pb(x);
}
scc();
for(auto it:roots)
dfs(it);
while(q--){
int x,y;
cin>>x>>y;
YN(ans[root[x]][root[y]])
}
}
return 0;
}

Reversals and Sums (Treap):

#pragma GCC optimize("unroll-loops,Ofast")
// #pragma GCC target("lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;

53 | P a g e
const int MAX=1e9;

mt19937 rng;
struct node{
int key,prior,cnt;
node *l,*r;
node(){}
node(int key):key(key),prior(rng()),cnt(1),l(NULL),r(NULL){}
node(int key,int prior):key(key),prior(prior),cnt(1),l(NULL),r(NULL){}
};
typedef node* pnode;
int cnt(pnode t){
return t?t->cnt:0;
}
void updcnt(pnode t){
if(t)
t->cnt=1+cnt(t->l)+cnt(t->r);
}
void split(pnode t,pnode &l,pnode &r,int key,int add=0){
if(!t)
return void(l=r=0);
int cur_key=add+cnt(t->l);
if(key<=cur_key)
split(t->l,l,t->l,key,add),r=t;
else
split(t->r,t->r,r,key,add+1+cnt(t->l)),l=t;
updcnt(t);
return;
}
void merge(pnode &t,pnode l,pnode r){
if(!l||!r)
t=l?l:r;
else if(l->prior>r->prior)
merge(l->r,l->r,r),t=l;
else
merge(r->l,l,r->l),t=r;
updcnt(t);
return;
}
void erase(pnode &t,int key){
if(t->key==key){
pnode th=t;
merge(t,t->l,t->r);
delete th;
}
else
erase(key<t->key?t->l:t->r,key);
updcnt(t);
return;
}
int n,m;
string s;
void print(pnode t){
if(!t)
return;
print(t->l);
cout<<s[t->key];
print(t->r);
return;
}
pnode root;

54 | P a g e
void print(){
print(root);
cout<<"\n";
return;
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
[Link](72^time(0));
while(tc--){
cin>>n>>m>>s;
for(int i=0;i<n;i++)
merge(root,root,new node(i));
while(m--){
int x,y;
cin>>x>>y;
x--;
pnode a=nullptr,b=nullptr,c=nullptr;
split(root,a,b,x);
split(b,b,c,y-x);
merge(a,a,c);
merge(root,a,b);
}
print();
}
return 0;
}

Necessary Roads (Bridges):

int n,m,vis[100010],tin[100010],low[100010],timer;
vector<int> v[100010];
vector<pair<int,int>> ans;
void bridge(int x,int y){

55 | P a g e
[Link]({x,y});
return;
}
void dfs(int idx,int p=0){
vis[idx]=1;
tin[idx]=low[idx]=timer++;
bool par=0;
for(auto it:v[idx]){
if(it==p&&!par){
par=1;
continue;
}
if(vis[it])
low[idx]=min(low[idx],tin[it]);
else{
dfs(it,idx);
low[idx]=min(low[idx],low[it]);
if(low[it]>tin[idx])
bridge(idx,it);
}
}
return;
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
v[x].pb(y);
v[y].pb(x);
}
for(int i=1;i<=n;i++){
if(!vis[i])
dfs(i);
}
cout<<[Link]()<<"\n";
for(auto [x,y]:ans)
cout<<x<<" "<<y<<"\n";
}
return 0;
}

Necessary Cities:
#pragma GCC optimize("unroll-loops,Ofast")
// #pragma GCC target("lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double

56 | P a g e
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int n,m,vis[100010],tin[100010],low[100010],timer;
int cnt[100010];
vector<int> v[100010];
set<int> ans;
void dfs(int idx,int p=0){
vis[idx]=1;
tin[idx]=low[idx]=timer++;
bool par=0;
int cnt=0;
int mn=MAAX;
bool bol=0;
for(auto it:v[idx]){
if(it==p&&!par){
par=1;
cnt++;
continue;
}
if(vis[it])
low[idx]=min(low[idx],tin[it]);
else{
cnt++;
dfs(it,idx);
mn=min(mn,low[it]);
bol|=low[it]>=tin[idx];
low[idx]=min(low[idx],low[it]);
}
}
if(cnt>1&&bol)
[Link](idx);
return;
}

57 | P a g e
cout<<[Link]()<<"\n";
for(auto it:ans)
cout<<it<<" ";
cout<<"\n";
}
return 0;
}

Monster Game II (Line Container):

#define ll long long

struct Line {
mutable ll m, b, p;
bool operator<(const Line& o) const { return m < o.m; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b);
}
bool isect(iterator x, iterator y) {
if (y == end()) { x->p = inf; return false; }
if (x->m == y->m) x->p = x->b > y->b ? inf : -inf;
else x->p = div(y->b - x->b, x->m - y->m);
return x->p >= y->p;
}
void add(ll m, ll b) {
auto z = insert({m, b, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
}
ll query(ll x) {
assert(!empty());

58 | P a g e
auto l = *lower_bound(x);
return l.m * x + l.b;
}
}cht;
int n,x,dp[200010],s[200010],f[200010];

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>x;
for(int i=1;i<=n;i++)
cin>>s[i];
for(int i=1;i<=n;i++)
cin>>f[i];
f[0]=x;
dp[0]=0;
[Link](-f[0],0);
for(int idx=1;idx<=n;idx++){
dp[idx]=-[Link](s[idx]);
[Link](-f[idx],-dp[idx]);
}
cout<<dp[n]<<"\n";
}
return 0;
}

Houses and Schools (Divide and Conquer):

//Divide and conquer optimization is possible when dp[j][i]=min{p<i}dp[j-1][p]+cost(p,i)
//where cost(a,c)+cost(b,d)<=cost(a,d)+cost(b,c)
#pragma GCC optimize("unroll-loops,Ofast")
// #pragma GCC target("lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int n,k,arr[3010],dp[3010][3010],pref[3010],suf[3010],cnt[3010],rnd[3010];
int cost(int prv,int i){
int md=(i+prv)/2;
return pref[i]-cnt[i]*(n-i)+rnd[md]-cnt[md]*(prv+i)+suf[prv]+(prv?cnt[prv-1]:0)*prv;

59 | P a g e
}
void fun(int lft,int l,int r,int mnl,int mxr){
if(l>r)
return;
int mid=l+(r-l)/2;
int prv=mid;
int bst=mnl,bst2=mnl,ans=MAAX;
for(int i=max(mnl,prv+1);i<=mxr;i++){
int cur=dp[lft-1][i]+cost(prv,i);
if(cur<ans)
bst=i,ans=cur;
if(cur==ans)
bst2=i;
}
dp[lft][prv]=ans;
if(l!=r){
fun(lft,l,mid-1,mnl,bst2);
fun(lft,mid+1,r,bst,mxr);
}
return;
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>arr[i];
pref[i]=arr[i]*(n-i);
cnt[i]=arr[i];
if(i)
cnt[i]+=cnt[i-1],pref[i]+=pref[i-1];
}
for(int i=n-1;i>=0;i--)
suf[i]=arr[i]*i+suf[i+1];
for(int i=0;i<=n;i++)
rnd[i]=-suf[i+1]-pref[i]+cnt[i]*n;
int ans=MAAX;
for(int prv=0;prv<n;prv++)
dp[0][prv]=suf[prv]-suf[n]-(cnt[n-1]-(prv?cnt[prv-1]:0))*(prv);
for(int lft=1;lft<k;lft++)
fun(lft,0,n-1,0,n-1);
for(int lft=0;lft<k;lft++){
for(int prv=0;prv<n;prv++)
ans=min(ans,dp[lft][prv]+(prv?pref[prv-1]:0)-(prv?cnt[prv-1]:0)*(n-prv));
}
cout<<ans<<"\n";
}
return 0;
}

60 | P a g e
Knuth Division (Knuth):
//Knuth optimization is possible when dp[i][j]=min{i<=k<j}dp[i][k]+cost[k+1][j]+cost(i,j)
//where cost(a,c)+cost(b,d)<=cost(a,d)+cost(b,c)
//and cost(b,c)<=cost(a,d)
#pragma GCC optimize("unroll-loops,Ofast")
// #pragma GCC target("lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int n,arr[5010],pref[5010],dp[5010][5010],pos[5010][5010];

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
pref[i+1]=arr[i]+pref[i];
pos[i][i]=i;
}
for(int l=n-1;l>=0;l--){
for(int r=l+1;r<n;r++){
dp[l][r]=MAAX;
for(int x=pos[l][r-1];x<=pos[l+1][r];x++){
int cur=dp[l][x]+dp[x+1][r]+pref[r+1]-pref[l];
if(cur<dp[l][r])
pos[l][r]=x,dp[l][r]=cur;
}
}
}
cout<<dp[0][n-1]<<"\n";
}
return 0;
}

61 | P a g e
Apples and Bananas (FFT template):
#pragma GCC optimize("unroll-loops,Ofast")
// #pragma GCC target("lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

using cd = complex<double>;
const double PI = acos(-1);

void fft(vector<cd> & a, bool invert) {

int n = [Link]();

for (int i = 1, j = 0; i < n; i++) {

int bit = n >> 1;
for (; j & bit; bit >>= 1)
j ^= bit;
j ^= bit;

if (i < j)
swap(a[i], a[j]);
}

for (int len = 2; len <= n; len <<= 1) {

double ang = 2 * PI / len * (invert ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1);
for (int j = 0; j < len / 2; j++) {
cd u = a[i+j], v = a[i+j+len/2] * w;
a[i+j] = u + v;
a[i+j+len/2] = u - v;
w *= wlen;
}
}
}

if (invert) {
for (cd & x : a)
x /= n;
}
}
vector<int> multiply(vector<int> const& a, vector<int> const& b) {
vector<cd> fa([Link](), [Link]()), fb([Link](), [Link]());

62 | P a g e
int n = 1;
while (n < [Link]() + [Link]())
n <<= 1;
[Link](n);
[Link](n);

fft(fa, false);
fft(fb, false);
for (int i = 0; i < n; i++)
fa[i] *= fb[i];
fft(fa, true);

vector<int> result(n);
for (int i = 0; i < n; i++)
result[i] = round(fa[i].real());
return result;
}
int k,n,m;

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>k>>n>>m;
vector<int> v1(k+1,0),v2(k+1,0);
for(int i=0;i<n;i++){
int x;
cin>>x;
v1[x]++;
}
for(int i=0;i<m;i++){
int x;
cin>>x;
v2[x]++;
}
vector<int> ans=multiply(v1,v2);
for(int i=2;i<=2*k;i++)
cout<<ans[i]<<" ";
cout<<"\n";
}
return 0;
}

Dynamic Connectivity:
#pragma GCC optimize("unroll-loops,Ofast")
// #pragma GCC target("lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back

63 | P a g e
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

struct dsuStruct{
vector<int> par,sz;
stack<int> compst;
stack<pair<int,int>> parst;
stack<pair<int,int>> szst;
void init(int n){
[Link](n+1);
[Link](n+1);
for(int i=0;i<=n;i++)
par[i]=i,sz[i]=1;
[Link](n);
}
int get(int x){
return par[x]==x?x:get(par[x]);
}
void unite(int u,int v){
u=get(u),v=get(v);
if(u!=v){
if(sz[u]<sz[v])
swap(u,v);
[Link]({v,par[v]});
par[v]=u;
[Link]({u,sz[u]});
sz[u]+=sz[v];
[Link]([Link]()-1);
}
else{
[Link]({0,0});
[Link]({0,0});
[Link]([Link]());
}
return;
}
void rollback(){
[Link]();
pair<int,int> x=[Link]();
[Link]();
par[x.f]=x.s;
x=[Link]();
[Link]();
sz[x.f]=x.s;
return;
}
int comp(){
return [Link]();
}
}dsu;
int n,m,k,mx;
int t=0;
vector<pair<int,int>> vec[400010];
map<pair<int,int>,int> mp;

64 | P a g e
void update(int ni,int ns,int ne,int nl,int nr,int x,int y){
if(ns>nr||ne<nl)
return;
if(ns>=nl&&ne<=nr){
vec[ni].pb({x,y});
return;
}
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
update(l,ns,mid,nl,nr,x,y);
update(r,mid+1,ne,nl,nr,x,y);
return;
}
void walk(int ni,int ns,int ne){
for(auto [x,y]:vec[ni])
[Link](x,y);
if(ns==ne)
cout<<[Link]()<<" ";
else{
int mid=ns+(ne-ns)/2;
int l=ni*2+1,r=ni*2+2;
walk(l,ns,mid);
walk(r,mid+1,ne);
}
for(auto [x,y]:vec[ni])
[Link]();
return;
}

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>m>>k;
[Link](n);
mx=k+1;
while(m--){
int x,y;
cin>>x>>y;
if(x>y)
swap(x,y);
mp[{x,y}]=t;
}
t++;
while(k--){
int type;
cin>>type;
if(type==1){
int x,y;
cin>>x>>y;
if(x>y)
swap(x,y);
mp[{x,y}]=t;
}
else{
int x,y;
cin>>x>>y;
if(x>y)
swap(x,y);
update(0,0,mx-1,mp[{x,y}],t-1,x,y);

65 | P a g e
[Link]({x,y});
}
t++;
}
for(auto it=[Link]();it!=[Link]();it++){
pair<int,int> x=(*it).f;
int ky=(*it).s;
update(0,0,mx-1,ky,t-1,x.f,x.s);
}
walk(0,0,mx-1);
cout<<"\n";
}
return 0;
}

Parcel Delivery (Max-Flow with dijkestra):

priority_queue<pair<int,int>> cap[510][510];
int cost[510],cnt[510],par[510];
int n,m,k;

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n>>m>>k;
for(int i=0;i<m;i++){
int a,b,r,c;
cin>>a>>b>>r>>c;
cap[a][b].pp({-c,r});
}
int ans=0;
while(k){
for(int i=1;i<=n;i++)
cost[i]=MAAX,cnt[i]=0;

66 | P a g e
cost[1]=0;
cnt[1]=MAAX;
priority_queue<pair<int,pair<int,int>>> pq;
[Link]({0,{MAAX,1}});
while([Link]()){
int cst=-[Link]().f,mx=[Link]().s.f,idx=[Link]().s.s;
[Link]();
if(cost[idx]<cst)
continue;
for(int i=1;i<=n;i++){
if(cap[idx][i].empty())
continue;
int ncst=cst-cap[idx][i].top().f;
int nidx=i;
int nmx=min(mx,cap[idx][i].top().s);
if(cost[i]>ncst){
cost[i]=ncst;
par[i]=idx;
cnt[i]=nmx;
[Link]({-ncst,{nmx,nidx}});
}
}
}
if(cnt[n]){
int mn=min(k,cnt[n]);
k-=mn;
ans+=mn*cost[n];
int cur=n;
while(cur!=1){
int prv=par[cur];
pair<int,int> x=cap[prv][cur].top();
cap[prv][cur].pop();
cap[cur][prv].pp({-x.f,mn});
x.s-=mn;
if(x.s)
cap[prv][cur].pp(x);
cur=prv;
}
}
else{
ans=-1;
k=0;
}
}
cout<<ans<<"\n";
}
return 0;
}

All Subarray Xors (xor convolution):

#pragma GCC optimize("unroll-loops,Ofast")
// #pragma GCC target("lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
typedef int in;

67 | P a g e
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;
const int inv2=(MOD+1)/2;

void xormul(vector<int> &a, vector<int> &b, vector<int> &c) {

int m = (int) [Link]();
[Link](m);
if (m == 1) {
c[0] = a[0] * b[0] % MOD;
return;
}
vector<int> ap, bp, an, bn;
for (int i = 0; i < m / 2; i++) {
ap.push_back((a[i] + a[i + m / 2]) % MOD);
bp.push_back((b[i] + b[i + m / 2]) % MOD);
an.push_back((a[i] - a[i + m / 2] + MOD) % MOD);
bn.push_back((b[i] - b[i + m / 2] + MOD) % MOD);
}
vector<int> d0, d1;
xormul(ap, bp, d0);
xormul(an, bn, d1);
for (int i = 0; i < m / 2; i++) {
c[i] = (d0[i] + d1[i]) * inv2 % MOD;
c[i + m / 2] = (d0[i] - d1[i] + MOD) * inv2 % MOD;
}
}
int n,arr[200010],can[2000010];
vector<int> v,ans;

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n;
for(int i=0;i<1<<20;i++)
[Link](0),[Link](0);
vector<int> basis;
v[0]=1;
for(int i=1;i<=n;i++){
cin>>arr[i];
arr[i]^=arr[i-1];
v[arr[i]]++;
}
xormul(v,v,ans);
if(ans[0]<=n+1)
ans[0]=0;
int cnt=0;
for(int i=0;i<1<<20;i++)

68 | P a g e
cnt+=!!ans[i];
cout<<cnt<<"\n";
for(int i=0;i<1<<20;i++){
if(ans[i])
cout<<i<<" ";
}
cout<<"\n";
}
return 0;
}

SOS Bit Problem (SOS dp):

int n,sos[2000010],sos2[2000010],arr[200010];

in main(){
ios_base::sync_with_stdio(0);[Link](0);[Link](0);
int tc=1;
// cin>>tc;
while(tc--){
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
sos[arr[i]]++;
sos2[arr[i]]++;
}
for(int i=0;i<20;i++){
for(int x=0;x<(1<<20);x++){
if(x&(1<<i)){
sos[x]+=sos[x^(1<<i)];
sos2[x^(1<<i)]+=sos2[x];
}
}
}
for(int i=0;i<n;i++)
cout<<sos[arr[i]]<<" "<<sos2[arr[i]]<<" "<<n-sos[(~arr[i])&((1<<20)-1)]<<"\n";

69 | P a g e
}
return 0;
}

BM:
#define SZ 233333
int qp(int a,int b)
{
int x=1; a%=MOD;
while(b)
{
if(b&1) x=x*a%MOD;
a=a*a%MOD; b>>=1;
}
return x;
}
namespace linear_seq {
inline vector<int> BM(vector<int> x)
{
//ls: (shortest) relation sequence (after filling zeroes) so far
//cur: current relation sequence
vector<int> ls,cur;
//lf: the position of ls (t')
//ld: delta of ls (v')
int lf,ld;
for(int i=0;i<(int)([Link]());++i)
{
int t=0;
//evaluate at position i
for(int j=0;j<(int)([Link]());++j)
t=(t+x[i-j-1]*(int)cur[j])%MOD;
if((t-x[i])%MOD==0) continue; //good so far
//first non-zero position
if(![Link]())
{
[Link](i+1);
lf=i; ld=(t-x[i])%MOD;
continue;
}
//cur=cur-c/ld*(x[i]-t)
int k=-(x[i]-t)*qp(ld,MOD-2)%MOD/*1/ld*/;
vector<int> c(i-lf-1); //add zeroes in front
[Link](k);
for(int j=0;j<(int)([Link]());++j)
[Link](-ls[j]*k%MOD);
if([Link]()<[Link]()) [Link]([Link]());
for(int j=0;j<(int)([Link]());++j)
c[j]=(c[j]+cur[j])%MOD;
//if cur is better than ls, change ls to cur
if(i-lf+(int)[Link]()>=(int)[Link]())
ls=cur,lf=i,ld=(t-x[i])%MOD;
cur=c;
}
for(int i=0;i<(int)([Link]());++i)
cur[i]=(cur[i]%MOD+MOD)%MOD;

70 | P a g e
return cur;
}
int m; //length of recurrence
//a: first terms
//h: relation
int a[SZ],h[SZ],t_[SZ],s[SZ],t[SZ];
//calculate p*q mod f
inline void mull(int*p,int*q)
{
for(int i=0;i<m+m;++i) t_[i]=0;
for(int i=0;i<m;++i) if(p[i])
for(int j=0;j<m;++j)
t_[i+j]=(t_[i+j]+p[i]*q[j])%MOD;
for(int i=m+m-1;i>=m;--i) if(t_[i])
//miuns t_[i]x^{i-m}(x^m-\sum_{j=0}^{m-1} x^{m-j-1}h_j)
for(int j=m-1;~j;--j)
t_[i-j-1]=(t_[i-j-1]+t_[i]*h[j])%MOD;
for(int i=0;i<m;++i) p[i]=t_[i];
}
inline int calc(int K)
{
for(int i=m;~i;--i)
s[i]=t[i]=0;
//init
s[0]=1; if(m!=1) t[1]=1; else t[0]=h[0];
//binary-exponentiation
while(K)
{
if(K&1) mull(s,t);
mull(t,t); K>>=1;
}
int su=0;
for(int i=0;i<m;++i) su=(su+s[i]*a[i])%MOD;
return (su%MOD+MOD)%MOD;
}
inline int work(vector<int> x,int n)
{
if(n<(int)([Link]())) return x[n];
vector<int> v=BM(x); m=[Link](); if(!m) return 0;
for(int i=0;i<m;++i) h[i]=v[i],a[i]=x[i];
return calc(n);
}
}
using linear_seq::work;

Gphashtable:
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<int, int> table;
struct chash {
const int RANDOM = (long long)(make_unique<char>().get()) ^
chrono::high_resolution_clock::now().time_since_epoch().count();
static unsigned long long hash_f(unsigned long long x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;

71 | P a g e
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
static unsigned hash_combine(unsigned a, unsigned b) { return a * 31 + b; }
int operator()(int x) const { return hash_f(x)^RANDOM; }
};

Ordered_set:
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

Trie (persistent):
class Trie {

public:

//N is number of possible characters in a string

const static int N = 26;

//baseChar defines the base character for possible characters

//like '0' for '0','1','2'... as possible characters in string
const static char baseChar = 'a';

struct TrieNode
{
int next[N];
//if isEnd is set to true , a string ended here
bool isEnd;
//freq is how many times this prefix occurs
int freq;

TrieNode()
{
for(int i=0;i<N;i++)
next[i] = -1;
isEnd = false;
freq = 0;
}
};

//the implementation is via vector and each position in this vector

//is similar as new pointer in pointer type implementation
vector <TrieNode> tree;

//Base Constructor
Trie ()
{
tree.push_back(TrieNode());
}

//inserting a string in trie

72 | P a g e
void insert(const string &s)
{
int p = 0;
tree[p].freq++;
for(int i=0;i<[Link]();i++)
{
// tree[]
if(tree[p].next[s[i]-baseChar] == -1)
{
tree.push_back(TrieNode());
tree[p].next[s[i]-baseChar] = [Link]()-1;
}

p = tree[p].next[s[i]-baseChar];
tree[p].freq++;
}
tree[p].isEnd = true;
}

//check if a string exists as prefix

bool checkPrefix(const string &s)
{
int p = 0;
for(int i=0;i<[Link]();i++)
{
if(tree[p].next[s[i]-baseChar] == -1)
return false;

p = tree[p].next[s[i]-baseChar];
}
return true;
}

//check is string exists

bool checkString(const string &s)
{
int p = 0;
for(int i=0;i<[Link]();i++)
{
if(tree[p].next[s[i]-baseChar] == -1)
return false;

p = tree[p].next[s[i]-baseChar];
}

return tree[p].isEnd;
}

//persistent insert
//returns location of new head
int persistentInsert(int head , const string &s)
{
int old = head;

tree.push_back(TrieNode());
int now = [Link]()-1;
int newHead = now;

int i,j;

for(i=0;i<[Link]();i++)

73 | P a g e
{
if(old == -1)
{
tree.push_back(TrieNode());
tree[now].next[s[i]-baseChar] = [Link]() - 1;
tree[now].freq++;
now = tree[now].next[s[i]-baseChar];
continue;
}
for(j=0;j<N;j++)
tree[now].next[j] = tree[old].next[j];
tree[now].freq = tree[old].freq;
tree[now].isEnd = tree[old].isEnd;

tree[now].freq++;

tree.push_back(TrieNode());
tree[now].next[s[i]-baseChar] = [Link]()-1;

old = tree[old].next[s[i]-baseChar];
now = tree[now].next[s[i]-baseChar];
}

tree[now].freq++;
tree[now].isEnd = true;

return newHead;
}

//persistent check prefix

bool persistentCheckPrefix(int head, const string &s)
{
int p = head;
for(int i=0;i<[Link]();i++)
{
if(tree[p].next[s[i]-baseChar] == -1)
return false;

p = tree[p].next[s[i]-baseChar];
}
return true;
}

//persistent check string

bool persistentCheckString(int head, const string &s)
{
int p = head;
for(int i=0;i<[Link]();i++)
{
if(tree[p].next[s[i]-baseChar] == -1)
return false;

p = tree[p].next[s[i]-baseChar];
}
return tree[p].isEnd;
}
};

74 | P a g e

Snippets
No ratings yet
Snippets
11 pages
Zonedout Template
No ratings yet
Zonedout Template
3 pages
Final Snippet
No ratings yet
Final Snippet
4 pages
Code Snippets for Algorithms and Data Structures
No ratings yet
Code Snippets for Algorithms and Data Structures
11 pages
Buet Template (AutoRecovered)
No ratings yet
Buet Template (AutoRecovered)
28 pages
Editorial
No ratings yet
Editorial
7 pages
PROGRAMMING (AutoRecovered) (AutoRecovered)
No ratings yet
PROGRAMMING (AutoRecovered) (AutoRecovered)
74 pages
Tarjan's Algorithm and Data Structures
No ratings yet
Tarjan's Algorithm and Data Structures
35 pages
C++ Code for Optimized Graph Solver
No ratings yet
C++ Code for Optimized Graph Solver
7 pages
Flatten Binary Tree To Linked List: Assignment-5 P. Tarak VU21CSEN0300105
No ratings yet
Flatten Binary Tree To Linked List: Assignment-5 P. Tarak VU21CSEN0300105
12 pages
ICPC C++ Cheat Sheet for Algorithms
No ratings yet
ICPC C++ Cheat Sheet for Algorithms
17 pages
Tree Sure
No ratings yet
Tree Sure
5 pages
Code Solutions for Algorithms and Data Structures
No ratings yet
Code Solutions for Algorithms and Data Structures
33 pages
Advanced C++ Competitive Programming Techniques
No ratings yet
Advanced C++ Competitive Programming Techniques
25 pages
Template ICPC - HackMD
No ratings yet
Template ICPC - HackMD
24 pages
C++ Data Structures and Algorithms
No ratings yet
C++ Data Structures and Algorithms
8 pages
UST Da Nang Algorithm Techniques Guide
No ratings yet
UST Da Nang Algorithm Techniques Guide
19 pages
Icpc Template IICPC
No ratings yet
Icpc Template IICPC
19 pages
C++ Algorithms for Data Structures
No ratings yet
C++ Algorithms for Data Structures
4 pages
DP Op
No ratings yet
DP Op
65 pages
Meesho Coding Questions and Solutions
No ratings yet
Meesho Coding Questions and Solutions
24 pages
Vectores Colineares y Algoritmos
No ratings yet
Vectores Colineares y Algoritmos
14 pages
DP Mic
No ratings yet
DP Mic
59 pages
C++ Algorithms: Modular Exponentiation & Graphs
No ratings yet
C++ Algorithms: Modular Exponentiation & Graphs
25 pages
Flow Algorithms and Large Number Operations
No ratings yet
Flow Algorithms and Large Number Operations
45 pages
Đệ Quy và Cấu Trúc Dữ Liệu
No ratings yet
Đệ Quy và Cấu Trúc Dữ Liệu
25 pages
Editorial
No ratings yet
Editorial
12 pages
Algorithms for Modular Arithmetic and Graphs
No ratings yet
Algorithms for Modular Arithmetic and Graphs
9 pages
Algolab Solutions for CSE Lab Report
No ratings yet
Algolab Solutions for CSE Lab Report
5 pages
C++ Recursive Algorithms and Sorting Techniques
No ratings yet
C++ Recursive Algorithms and Sorting Techniques
4 pages
C++ Solutions for HackWithInf Challenges
No ratings yet
C++ Solutions for HackWithInf Challenges
8 pages
Efficient Range Query with Segment Trees
No ratings yet
Efficient Range Query with Segment Trees
3 pages
Dijkstra Algorithm Implementation in C++
No ratings yet
Dijkstra Algorithm Implementation in C++
24 pages
Codes
No ratings yet
Codes
10 pages
Segment Tree Implementation in C++
No ratings yet
Segment Tree Implementation in C++
8 pages
Advanced Data Structures in C++
No ratings yet
Advanced Data Structures in C++
19 pages
Graph Algorithms Implementation
No ratings yet
Graph Algorithms Implementation
3 pages
Max-Min Difference of Array Sums
No ratings yet
Max-Min Difference of Array Sums
9 pages
Counting Nested Segments in Arrays
No ratings yet
Counting Nested Segments in Arrays
3 pages
Strongly Connected Components in Graphs
No ratings yet
Strongly Connected Components in Graphs
3 pages
Teamplate Final
No ratings yet
Teamplate Final
7 pages
Gennady Korotkevich's Coding Challenges
No ratings yet
Gennady Korotkevich's Coding Challenges
3 pages
Dsa Lab Assignment 4
No ratings yet
Dsa Lab Assignment 4
28 pages
Graph Algorithms: Bellman-Ford & More
No ratings yet
Graph Algorithms: Bellman-Ford & More
20 pages
Finding Articulation Points in Graphs
No ratings yet
Finding Articulation Points in Graphs
17 pages
C++ Graph Matching Algorithm Code
No ratings yet
C++ Graph Matching Algorithm Code
3 pages
Euler Tour Techinuqe
No ratings yet
Euler Tour Techinuqe
1 page
Turing Machine Reference - IIIT Hyderabad
No ratings yet
Turing Machine Reference - IIIT Hyderabad
25 pages
数据结构实践
No ratings yet
数据结构实践
46 pages
Codeforces 36D Chess Piece Solution
No ratings yet
Codeforces 36D Chess Piece Solution
104 pages
Algorithmia Final Round Editorials
No ratings yet
Algorithmia Final Round Editorials
20 pages
Largest Sum Cycle in Graph
No ratings yet
Largest Sum Cycle in Graph
2 pages
Zscaler Interview Coding Questions
No ratings yet
Zscaler Interview Coding Questions
3 pages
Centroid Decomposition in Trees
No ratings yet
Centroid Decomposition in Trees
3 pages
Mushroom and Flight Problem Solutions
No ratings yet
Mushroom and Flight Problem Solutions
25 pages
C++ Algorithms: Exponentiation, Graphs
No ratings yet
C++ Algorithms: Exponentiation, Graphs
10 pages
Data Structures and Algorithms Guide
No ratings yet
Data Structures and Algorithms Guide
23 pages
C++ OOP Concepts Explained
No ratings yet
C++ OOP Concepts Explained
26 pages
C++ Simple Billing System Project
No ratings yet
C++ Simple Billing System Project
31 pages
Polymorphism in Publication Classes
No ratings yet
Polymorphism in Publication Classes
5 pages
Overview of Data Module Types
No ratings yet
Overview of Data Module Types
97 pages
B.Tech Academic Regulations 2009-10
No ratings yet
B.Tech Academic Regulations 2009-10
114 pages
24P 0726 Lab12
No ratings yet
24P 0726 Lab12
21 pages
C++ Game Development with Blender
No ratings yet
C++ Game Development with Blender
5 pages
Python Loops: While, For, and Control Statements
No ratings yet
Python Loops: While, For, and Control Statements
7 pages
C++ Conditional Statements Examples
No ratings yet
C++ Conditional Statements Examples
2 pages
Understanding Mobile Cloning Techniques
No ratings yet
Understanding Mobile Cloning Techniques
23 pages
C++ OOP Concepts: Bank Account Example
No ratings yet
C++ OOP Concepts: Bank Account Example
62 pages
C++ Programming Overview Presentation
No ratings yet
C++ Programming Overview Presentation
20 pages
C++ Aim Smoothing Settings Manager
No ratings yet
C++ Aim Smoothing Settings Manager
2 pages
C/C++ Programming Fundamentals Course
No ratings yet
C/C++ Programming Fundamentals Course
2 pages
Introduction to Java Programming
No ratings yet
Introduction to Java Programming
33 pages
Student Management System in C++
No ratings yet
Student Management System in C++
8 pages
Understanding Polymorphism in OOP
No ratings yet
Understanding Polymorphism in OOP
41 pages
Introduction to Object-Oriented Programming
No ratings yet
Introduction to Object-Oriented Programming
4 pages
C++ Functions Overview and Examples
No ratings yet
C++ Functions Overview and Examples
52 pages
C++ Full Reviewer Complete
No ratings yet
C++ Full Reviewer Complete
3 pages
C++ Programming Lab Exercises
No ratings yet
C++ Programming Lab Exercises
4 pages
Understanding C++ Namespaces
No ratings yet
Understanding C++ Namespaces
14 pages
Introduction to Java Programming History
No ratings yet
Introduction to Java Programming History
34 pages
Understanding Functions in Programming
No ratings yet
Understanding Functions in Programming
23 pages
Java Christmas Tree Animation Code
No ratings yet
Java Christmas Tree Animation Code
2 pages
Structured Programming Quiz IT223
No ratings yet
Structured Programming Quiz IT223
2 pages
C Program for Doubly Linked List Operations
No ratings yet
C Program for Doubly Linked List Operations
7 pages
Scott Meyers C++ Modern Effective2
No ratings yet
Scott Meyers C++ Modern Effective2
75 pages
C++ Programming Worksheet
No ratings yet
C++ Programming Worksheet
2 pages
C++/CLI Tutorial and Examples
No ratings yet
C++/CLI Tutorial and Examples
30 pages

Advanced Algorithm Templates and Queries

Uploaded by

Advanced Algorithm Templates and Queries

Uploaded by

Giant pizza (2-sat) Page #3

Mail delivery (euler-cycle) Page #5

Mail delivery (Euler-cycle):

Distinct Routes (Max-flow):

template <typename T>

Range interval Queries:

template <typename T>

Distinct Values Queries I (persistent

Distinct Values Queries II:

template <typename T>

Forest Queries II (2D segtree):

Missing Coin Sum Queries:

Path Queries II (HLD):

template <typename T>

Fixed-Length Paths I (Centroid decomp):

Josephus Queries (k-th child):

int power(int x,int y){

Sum of Divisors (1-n):

Bracket Sequences II:

int power(int x,int y){

int power(int x,int y){

System of Linear Equations (Gauss):

int power(int x,int y){

All Palindromes (Manacher):

Palindrome Queries (Hashed template):

template <typename T>

String Functions (kmp and Z algo):

Substring Order II (Includes Suffix Array

vector<int> sort_cyclic_shifts(string const& s) {

for(int i = 0; i < n; ch[k++] = p[i++]){

Real CommonAreaCircleAndPolygon(const Circle &c, const vector<Point> &ps){

using namespace geometry;

int get(Point x,Point y){

typedef complex<int> point;

Reachability Queries (SCC):

Reversals and Sums (Treap):

Necessary Roads (Bridges):

Monster Game II (Line Container):

#define ll long long

Houses and Schools (Divide and Conquer):

void fft(vector<cd> & a, bool invert) {

for (int i = 1, j = 0; i < n; i++) {

for (int len = 2; len <= n; len <<= 1) {

Parcel Delivery (Max-Flow with dijkestra):

All Subarray Xors (xor convolution):

void xormul(vector<int> &a, vector<int> &b, vector<int> &c) {

SOS Bit Problem (SOS dp):

//N is number of possible characters in a string

//baseChar defines the base character for possible characters

//the implementation is via vector and each position in this vector

//inserting a string in trie

//check if a string exists as prefix

//check is string exists

//persistent check prefix

//persistent check string

You might also like