NOI Reference
Last edited: 15th
March 2018
Graph Theory
Depth First Search O(V+E)
vector<pi> adjlist[N];
bool visited[N];
int dist[N];
void dfs(int x){
if(visited[x]) return;
visited[x] = true;
for(auto i : adjlist[x]){
if(visited[i]) continue;
dist[i] = dist[x]+i.second; // dist only valid for
trees!
dfs(i);
}
}
Toposort (DFS) O(V+E)
vector<int> adjList[N],
topo;
bool visited[N];
void dfs (int x) {
if (visited[x]) return;
visited[x] = 1;
for (auto i : adjList[x]) {
if (visited[i]) continue;
dfs(i);
}
topo.push_back(x); // post ordering
}
/* Usage */
topo.clear();
memset(visited, 0,
sizeof(visited));
for (int i = 0; i < N;
++i) {
if (visited[i]) continue;
dfs(i);
}
reverse(topo.begin(),
topo.end()); //to get the correct topological order
Breadth First Search O(V+E)
int dx[8] = {-1, 0, 1, -1, 1,
-1, 0, 1};
int dy[8] = {-1, -1, -1, 0,
0, 1, 1, 1};
int dist[H][W];
dist[sx][sy] = 0;
q.push(pi(sx, sy)); // x,y
while(!q.empty()){
int x = q.front().first.first;
int y = q.front().first.second;
q.pop();
for(int i = 0; i<8; i++){
int newx = x+dx[i]; int newy = y+dy[i];
if(!valid(newx, newy)) continue;
if(!visited[newx][newy]){
dist[newx][newy] = dist[x][y]+1; // only for
unweighted graphs
q.push(pi(newx, newy));
}
}
}
UFDS Amortized O(1)
int p[N];
int findSet(int x){
if(p[x] == x) return x;
else return p[x] = findSet(p[x]);
}
bool same(int x, int y){
return findSet(x) == findSet(y);
}
void merge(int x, int y){
p[findSet(x)] = findSet(y);
}
Floyd (APSP) O(V3)
int adjmat[N][N];
// remember adjmat[i][i] == 0
for(int k = 0; k<N; k++){
// intermediate node outside
for(int i = 0; i<N; i++){
for(int j = 0; j<N; j++){
if(adjmat[i][k] == -1 or adjmat[k][j] == -1)
continue;
if(adjmat[i][j] == -1 or
adjmat[i][j]>adjmat[i][k]+adjmat[k][j])
adjmat[i][j] =
adjmat[i][j]+adjmat[k][j];
}
}
}
Bellman-Ford (SSSP) O(NE)
dist[s]=0; //dist all others
= INF
for (int i=0; i<N-1; i++){
for (int j=0; j<E; j++){
dist[v]=min(dist[v],dist[u]+c); // dir edge from u to
v with c cost
}
}
Dijkstra(SSSP) O(ElogN)
priority_queue<pi,
vector<pi>, greater<pi>> pq; // greater is important!
memset(dist, -1, sizeof
dist);
dist[source] = 0;
pq.push(pi(0, source));
while(!pq.empty()){
int node = pq.top().second; int d =
pq.top().first; pq.pop();
if(dist[node] != d) continue; // important!
for(auto i : adjlist[node]){
int childnode = i.first, childdist =
i.second;
if(dist[childnode] == -1 or dist[childnode] > dist[node] +
childdist){
//note: strictly greater than is important!
dist[childnode] = dist[node] + childdist;
pq.push(pi(dist[childnode], childnode));
}
}
}
Dijkstra Variant (Longest
Path, Positive Cycle Detection) (problem: girlfriend)
#include
<bits/stdc++.h>
#define INF -2
using namespace std;
typedef pair<int, int>
pi;
vector<pi>
adjlist[100050];
bool infinite[100050];
int visited[100050];
priority_queue<pi> pq;
int dist[100050];
int n,e,source,dest;
void dfs(int x){
if(visited[x]) return;
visited[x] = 1;
for(auto i : adjlist[x]){
if(visited[i.first] == 0) dfs(i.first);
else if(visited[i.first] == 1) infinite[i.first] =
true;
}
visited[x] = 2;
}
int main(){
cin >> n >> e >> source >> dest;
for(int i = 0; i<e; i++){
int a,b,c;
cin >> a >> b >> c;
adjlist[a].push_back(pi(b,c));
}
memset(dist, -1, sizeof dist);
for(int i = 0; i<n; i++) if(visited[i] == 0) dfs(i);
if(infinite[source])
dist[source] = -2; else dist[source] = 0;
pq.push(pi(dist[source], source));
while(!pq.empty()){
int node = pq.top().second; int d = pq.top().first;
pq.pop();
if(d != dist[node]) continue;
for(auto i : adjlist[node]){
int childnode = i.first; int childdist =
i.second;
if(dist[node] == INF){
if(dist[childnode] == INF) continue;
dist[childnode] = INF;
pq.push(pi(dist[childnode], childnode));
}else if(dist[childnode] == INF) continue;
else if(dist[childnode] == -1 or
(dist[childnode] < dist[node] + childdist)){
if(infinite[childnode]) dist[childnode]
= INF;
else dist[childnode] = dist[node] +
childdist;
pq.push(pi(dist[childnode], childnode));
}
}
}
}
Dijkstra with Ways Counting
memset(dist, -1, sizeof
dist);
dist[source] = 0;
ways[source] = 1;
pq.push(pi(0,source));
while(!pq.empty()){
int node = pq.top().second; int d =
pq.top().first; pq.pop();
if(dist[node] != d) continue;
for(auto i : adjlist[node]){
int childnode = i.first;
int childdist = i.second;
if(dist[childnode] == -1 or dist[childnode]
> dist[node] + childdist){
dist[childnode] = dist[node]+childdist;
ways[childnode] = ways[node];
pq.push(pi(dist[childnode], childnode));
}else if(dist[childnode] ==
dist[node]+childdist) {
ways[childnode] += ways[node];
}
}
}
Dijkstra with Shortest Path
DAG
memset(from, -1, sizeof
from);
memset(dist, -1, sizeof
dist);
dist[source] = 0;
from[source] = -1;
pq.push(pi(0,source));
while(!pq.empty()){
ll node = pq.top().second; ll d = pq.top().first; pq.pop();
if(dist[node] != d) continue;
for(auto i : adjlist[node]){
ll childnode = i.first;
ll childdist = i.second;
if(dist[childnode] == -1 or dist[childnode] >
dist[node] + childdist){
dist[childnode] = dist[node]+childdist;
from[childnode] = node;
pq.push(pi(dist[childnode], childnode));
}
}
}
0-1 BFS (SSSP on 0-1 edges)
O(E+V)
memset(dist, -1, sizeof
dist);
dist[source] = 0;
pq.push_front(pi(0, source));
while(!pq.empty()){
int node = pq.front().second; int d =
pq.front().first;
if(dist[node] != d) continue;
for(auto i : adjlist[node]){
int childnode = i.first, childdist =
i.second; // childdist == 0 or 1
if(dist[childnode] == -1 or dist[childnode]
> dist[node] + childdist){
dist[childnode] = dist[node] + childdist;
if(childdist == 1){
pq.push_back(pi(dist[childnode],
childnode));
}else{
pq.push_front(pi(dist[childnode],
childnode));
}
}
}
}
SPFA(SSSP) (untested)
typedef pair<int,int>
pi;
vector<pi>
adjList[10000]; // node, weight
queue<int> q; // node
bitset<10000> in_q; //1
if node is in queue, bitset is same as bool array
int dist[10000];
memset(dist, -1,
sizeof(dist)); // initialise to -1, representing infinity
q.push(source); dist[source]
= 0; in_q[source] = 1;
while(!q.empty()){
int c = q.front();
q.pop();
in_q[c] = 0;
for(auto i : adjList[c]){
if(dist[i.first] == -1 || dist[i.first] > dist[c] +
i.second){
dist[i.first] = dist[c] + i.second;
if (!in_q[i.first]) q.push(i.first);
in_q[i.first] = 1;
}
}
}
Bipartite Matching
bool dfs(int x){
if(visited[x]) return false;
visited[x] = true;
for(auto i : adjlist[x]){
if(color[i] == color[x]){ /*clash*/ }
color[i] = 3-color[x];
if(!visited[i]) {
if(dfs(i)) { /*clash*/ }
}
}
return false; // no clash
}
Kruskal (MST) O(ElogV)
//UFDS
int p[N];
int findSet(int x){
if(p[x] == x) return x;
else return p[x] = findSet(p[x]);
}
bool same(int x, int y){
return findSet(x) == findSet(y);
}
void merge(int x, int y){
p[findSet(x)] = findSet(y);
}
sort(edgelist+1,
edgelist+e+1);
int totalcost = 0;
for(int i = 1; i <= e;
i++){
int cost = edgelist[i].first;
int firstguy = edgelist[i].second.first;
int secondguy = edgelist[i].second.second;
if (same(firstguy, secondguy)) continue;
totalcost += cost;
merge(firstguy, secondguy);
}
Prim (MST) O(ElogV)
typedef pair<int,int>
pi;
vector<pi>
adjList[10000]; // node, weight
priority_queue<pi,
vector<pi>, greater<pi> > pq;
bool visited[10000];
pq.push(pi(0, 0));
while(!pq.empty()){
pi c = pq.top();
pq.pop();
if(visited[c.second]) continue;
visited[c.second] = true;
for(auto i : adjList[c.second]){
if(!visited[i.second]){
pq.push(pi(i.second, i.first));
}
}
}
Tree Diameter
int treediam(){
memset(visited, false, sizeof visited);
memset(dist, -1, sizeof dist);
dist[V[0]] = 0;
dfs(V[0]);
int furthestdist = -1, furthestindex = 0;
for(int i = 0; i<n; i++){
if(dist[i] > furthestdist){
furthestdist = dist[i];
furthestindex = i;
}
}
memset(visited, false, sizeof visited);
memset(dist, -1, sizeof dist);
dist[furthestindex] = 0;
furthestdist = -1;
for(int i = 0; i<n; i++){
if(dist[i] > furthestdist){
furthestdist = dist[i];
furthestindex = i;
}
}
return furthestdist;
}
TSP on Tree
int ans = 0;
int V[N]; // nodes to visit
bool goals[N]; // whether
node is a place to visit
// find the subtree
bool dfs(ll x){
if(visited[x]) return false;
visited[x] = true;
bool need=false;
if(goals[x]) need=true;
for(auto i : adjlist[x]){
if(dfs(i.first)) ans+=i.second, need=true;
}
return need;
}
dfs(V[0]);
ans*=2; // subtree weights *
2
ans -= treediam(); // minus the tree diameter
2k Decomposition
<O(NlogN), O(logN)>
int p[100050][20];
vector<int>
adjlist[100050];
int q,n;
void roottree(int x, int
par){
p[x][0] = par;
for(auto i : adjlist[x]){
if(i.first == par) continue;
dist[i.first] = dist[x] + i.second;
depth[i.first] = depth[x]+1;
roottree(i.first, x);
}
}
void tkd(){
for(int k = 1; k<20; k++){
for(int i = 0; i<n; i++){
if(p[i][k-1] != -1){
p[i][k] = p[p[i][k-1]][k-1];
}else p[i][k] = -1;
}
}
}
int query(int x, int k){
for(int i = 20; i>=0; i--){
if(k>=(1<<i)){
if(x!=-1) x = p[x][i];
k-=(1<<i);
}
}
return x;
}
LCA
// 2KD
int lca(int a, int b){
if(depth[a] < depth[b]) swap(a,b);
for(int k = 19; k>=0; k--){
if(p[a][k] != -1 and depth[p[a][k]] >=
depth[b]){
a = p[a][k];
}
}
if(a==b) return a;
for(int k = 19; k>=0; k--){
if(p[a][k] != p[b][k]) a=p[a][k],
b=p[b][k];
}
return p[a][0];
}
APSP
//LCA
int apsp(int a, int b){
return dist[a]+dist[b]-2*dist[lca(a,b)];
}
MCBM (Augmenting Path) (slow)
vector<int>
adjlist[255];
int p[255];
bool visited[255];
int aug(int x){
if(visited[x]) return 0;
visited[x] = true;
for(auto i : adjlist[x]){
if(p[i] == -1 or aug(p[i])){
p[i] = x;
p[x] = i;
return 1;
}
}
return 0;
}
memset(p, -1, sizeof p);
int ans = 0;
for(auto i : left){
memset(visited, false, sizeof visited); //
very important***
if(p[i] == -1) ans += aug(i);
}
Note: On Bipartite Graph,
|MVC| == |MCBM| (Knigճ Theorem)
Note: On Bipartite Graph,
|MIS| == |V|-|MCBM|
MCBM (Hopcroft Karp) (fast)
O(sqrt(V)E)
#define MAX 100001 // edit
accordingly
#define nil 0
#define inf INT_MAX
using namespace std;
struct MCBM{
vector<int> adjlist[MAX];
int n, m, match[MAX], dist[MAX];
// n: number of nodes on left side, nodes are numbered 1 to n
// m: number of nodes on right side, nodes are numbered n+1 to
n+m
// G = nil[0] _ G1[G[1---n]] _ G2[G[n+1---n+m]] // important!!
MCBM(int nn, int mm){
n = nn;
m = mm;
}
bool bfs() {
int i, u, v, len;
queue< int > Q;
for(i=1; i<=n; i++) {
if(match[i]==nil) {
dist[i] =
0;
Q.push(i);
}
else dist[i]
= inf;
}
dist[nil] = inf;
while(!Q.empty()) {
u = Q.front();
Q.pop();
if(u!=nil) {
for(auto
v : adjlist[u]){
if(dist[match[v]]==inf) {
dist[match[v]] = dist[u] + 1;
Q.push(match[v]);
}
}
}
}
return (dist[nil]!=inf);
}
bool dfs(int u) {
int i, v, len;
if(u!=nil) {
len =
adjlist[u].size();
for(i=0;
i<len; i++) {
v =
adjlist[u][i];
if(dist[match[v]]==dist[u]+1) {
if(dfs(match[v])) {
match[v] = u;
match[u] = v;
return true;
}
}
}
dist[u] =
inf;
return false;
}
return true;
}
int hopcroft_karp() {
int matching = 0, i;
// match[] is assumed nil for all vertex in adjlist
while(bfs())
for(i=1;
i<=n; i++)
if(match[i]==nil && dfs(i))
matching++;
return matching;
}
void addEdge(int u, int v){ // left to right
assert(v>n);
adjlist[u].push_back(v);
}
}; //usage MCBM g(n,m);
g.addEdge(a,b);
Tarjanճ SCC
#include
<bits/stdc++.h>
using namespace std;
typedef pair<int, int>
pi;
int n,e;
vector<int>
adjlist[100050]; // normal adjlist
int disc[100050],
low[100050]; // required for tarjan
bool onstack[100050];
//required for tarjan
int inSCC[100050]; // which
scc a node is in
set<int>
sccAdjlist[100050]; // scc adjlist
vector<int> s, newscc;
vector<vector<int>
> SCCs; // list of sccs
vector<pi> edgelist; //
normal edgelist
int counter = 0;
void scc(int x){
disc[x] = low[x] = counter++;
s.push_back(x);
onstack[x] = true;
for(auto i : adjlist[x]){
if(disc[i] == -1){
scc(i);
low[x] = min(low[x], low[i]);
}
else if(onstack[i]){
low[x] = min(low[x], disc[i]);
}
}
if(disc[x] == low[x]){
newscc.clear();
do{
newscc.push_back(s.back());
onstack[s.back()] = false;
inSCC[s.back()] = SCCs.size();
s.pop_back();
}while(newscc[newscc.size()-1] != x);
SCCs.push_back(newscc);
}
}
int main(){
memset(disc, -1, sizeof disc);
cin >> n >> e;
for(int i = 0; i<e; i++){
int a,b;
cin >> a >> b;
adjlist[a].push_back(b);
edgelist.push_back(pi(a,b));
}
for(int i = 0; i<n; i++) if(disc[i] == -1) scc(i);
for(auto i : edgelist){
sccAdjlist[inSCC[i.second]].insert(inSCC[i.first]);
}
for(int i = 0; i<SCCs.size(); i++){
if(sccAdjlist[i].find(i) != sccAdjlist[i].end())
sccAdjlist[i].erase(sccAdjlist[i].find(i));
}
}
Transitive Closure O(V^2)
bool trans[2050][2050];
void dfs(int x, int y){
trans[x][y] = true;
for(auto i : adjlist[y]){
if(!trans[x][i]) dfs(x,i);
}
}
int main(){
for(int i = 0; i<n; i++){
dfs(i,i);
}
}
Random ҴeleportӠsolution
int visited[500050];
int pre[500050];
int ctr = 0;
int stopat = -1;
int n, A[500050];
int dfs(int x){
if(visited[x] > 0) return visited[x];
if(visited[x] == -1){
visited[x] = ctr-pre[x];
stopat = x;
return -visited[x];
}
pre[x] = ctr++;
visited[x] = -1;
int ret = dfs(A[x]);
if(ret < 0){
visited[x] = -ret;
if(stopat == x){
stopat = -1;
return -ret;
}
return ret;
}
visited[x] = ret + 1;
return visited[x];
}
Articulation points
(bombing2)
#include
<bits/stdc++.h>
using namespace std;
typedef pair<int, int>
pi;
bool visited[200050];
int depth[200050];
int low[200050];
int parent[200050];
set<int>
adjlist[200050];
int childcount = 0;
int components[200050];
int n,e;
vector<int>
articulationpoints;
int d = 0;
int atp(int x){
visited[x] = true;
depth[x] = d;
low[x] = d;
d++;
childcount = 0;
for(auto i : adjlist[x]){
if(!visited[i]){
parent[i] = x;
atp(i);
if(low[i] >= depth[x]){
components[x]++;
}
low[x] = min(low[x], low[i]);
}else if(i != parent[x]) low[x] = min(low[x],
depth[i]);
}
}
int main(){
parent[0] = -1;
cin >> n >> e;
for(int i = 0; i<e; i++){
int a,b; cin >> a >> b;
adjlist[a].insert(b);
adjlist[b].insert(a);
}
atp(0);
int ans = components[0];
for(int i = 1; i<n; i++){
ans = max(ans, components[i]+1);
// printf("%d: %d\n", i, components[i]);
}
cout << ans;
}
Pseudocode:
GetArticulationPoints(i, d)
visited[i] = true
depth[i] = d
low[i] = d
childCount = 0
isArticulation = false
for each ni in adj[i]
if not visited[ni]
parent[ni] = i
GetArticulationPoints(ni, d + 1)
childCount = childCount + 1
if low[ni] >= depth[i]
isArticulation = true
low[i] = Min(low[i], low[ni])
else if ni <> parent[i]
low[i] = Min(low[i], depth[ni])
if (parent[i] <> null and isArticulation) or
(parent[i] == null and childCount > 1)
Output i as articulation point
Articulation Bridges
Pseudocode:
GetBridges(i, d)
visited[i] = true
depth[i] = d
low[i] = d
for each ni in adj[i]
if not visited[ni]
parent[ni] = i
GetBridges(ni, d + 1)
if low[ni] > depth[i]
Output i,ni as bridge
low[i] = Min(low[i], low[ni])
else if ni <> parent[i]
low[i] = Min(low[i], depth[ni])
Centroid Decomposition
int nn = 0; // num nodes
int subsize[100050];
int cpar[100050];
void dfs1(int x, int p){ //
compute subtree sizes
subsize[x] = 1;
nn++;
for(auto i : adjlist[x]){
if(i == p) continue;
dfs1(i, x);
subsize[x] += subsize[i];
}
}
int dfs2(int x, int p){ //
finds the centroid in subtree rooted at x
for(auto i : adjlist[x]){
if(i == p) continue;
if(subsize[i] > nn/2) return dfs2(i, x);
}
return x;
}
void decomp(int x, int p){
nn = 0;
dfs1(x, x);
int centroid = dfs2(x,x);
if(p == -1) p=centroid;
cpar[centroid] = p;
for(auto i : adjlist[centroid]){
adjlist[i].erase(centroid);
decomp(i, centroid);
}
adjlist[centroid].clear();
}
// called with decomp(0, -1);
Centroid Decomp (primedst)
#include
<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dist[20][50050]; // depth
of tree, dist to centroid
ll subsize[50005];
ll nn = 0;
ll n;
vector<ll> primes;
set<ll> adjlist[50050];
bitset<50050> isPrime;
void calcsize(ll x, ll p){
subsize[x] = 1;
nn++;
for(auto i : adjlist[x]){
if(i == p) continue;
calcsize(i, x);
subsize[x] += subsize[i];
}
}
ll centroid(ll x, ll p){
for(auto i : adjlist[x]){
if(i == p) continue;
if(subsize[i] > nn/2) return centroid(i, x);
}
return x;
}
void edit(ll x, ll p, ll
depth, ll d, ll change){
// update the subtree at depth, x, all by change
dist[depth][d] += change;
for(auto i : adjlist[x]){
if(i == p) continue;
edit(i, x, depth, d+1, change); // recurse on children
}
}
ll getadd(ll x, ll p, ll
depth, ll d){ // this node is currently at distance d away
ll ret = 0;
for(auto i : primes){
if(i-d < 0) continue;
ll add = dist[depth][i-d]; // number of nodes, i-d away
from centroid
if(add == 0) break;
if(i == d) add*=2;
ret += add;
}
for(auto i : adjlist[x]){
if(i != p) ret+=getadd(i,x,depth,d+1);
}
return ret;
}
ll ans = 0;
void decomp(ll x, ll depth){
nn = 0;
calcsize(x, x);
ll cen = centroid(x,x);
edit(cen, cen, depth, 0, 1); // make all one
ll add=0;
for(auto i : adjlist[cen]){
edit(i,cen,depth,1,-1); // remove this subtree
contribution
add+=getadd(i,cen,depth,1); // get the contributions
edit(i,cen,depth,1,1); // change back
}
ans += add;
for(auto i : adjlist[cen]){
adjlist[i].erase(cen);
decomp(i, depth+1);
}
for(ll i = 0; i<=n; i++) dist[depth][i] = 0;
}
void genprimes(){
isPrime.reset(); isPrime.flip();
isPrime[2] = true;
primes.push_back(2);
for(ll i = 2; i*2 <= n+10; i++) isPrime[i*2] = false;
for(ll i = 3; i<=n+10; i+=2){
if(!isPrime[i]) continue;
primes.push_back(i);
for(ll j = 2; i*j<=n+10; j++) isPrime[i*j] = false;
}
}
int main(){
freopen("input.txt", "r", stdin);
cin >> n;
genprimes();
for(ll i = 0; i<n; i++){
ll a,b;
cin >> a >> b;
adjlist[a].insert(b);
adjlist[b].insert(a);
}
decomp(1,1);
double a = (double) ans / 2.0; // divide by two because double
counting
double b = ((double) n * (double) (n-1)) / 2.0;
cout << a/b;
}
LCA to RMQ & Euler Tour
Decomp (ants) Version #1
#include
<bits/stdc++.h>
#include "ants.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll>
pi;
vector<pi>
adjlist[100050];
ll fw[200050];
ll S[100050], E[100050];
ll ctr=1;
ll n, edges;
// lca setup
int st[200050][19]; //
s[x][0] is self
int pre[100050];
int pre_r[100050];
int prectr = 1;
void dfs(int x, int p){
pre[x] = prectr;
pre_r[prectr] = x;
prectr++;
for(auto i : adjlist[x]){
if(i.first == p) continue;
dfs(i.first, x);
}
}
void update(ll p, ll v){
for(;p<=2*edges+9;p+=p&(-p)) fw[p] += v;
}
ll query(ll x, ll y){
ll ans = 0;
for(;y;y-=y&(-y)) ans+=fw[y];
x--;
for(;x;x-=x&(-x)) ans-=fw[x];
return ans;
}
void printfw(){
for(int i=1; i<=2*edges+9; i++) printf("%d ",
query(i, i)); printf("\n");
}
void roottree(ll x, ll p, ll
d){
st[ctr][0] = pre[x];
S[x] = ctr++;
for(auto i : adjlist[x]){
if(i.first == p) continue;
update(ctr, i.second);
roottree(i.first, x, d+i.second);
update(ctr, -i.second);
st[ctr][0] = pre[x];
ctr++;
}
E[x] = ctr;
}
void sparse_init(){
for(int k = 1; k<=16; k++){
for(int i = 0; i<2*edges+9; i++){
st[i][k] = min( st[i][k-1],
st[i+(1<<(k-1))][k-1] );
}
}
}
int minq(int x, int y){ //
[x, y]
// if(x>y) swap(x,y);
assert(x<=y);
int len = y-x+1;
int k = 32-1-__builtin_clz(len);
return min(st[x][k], st[y-(1<<k)+1][k]);
}
int lca(int x, int y){
if(S[x]
> S[y]) swap(x,y);
int ans = pre_r[minq(S[x], S[y])];
return ans;
}
typedef pair<pi, ll>
iii;
vector<iii> edgelist;
void tree(int _N, int _E, int
A[], int B[], int D[]) {
n = _N, edges = _E;
for(ll i = 0; i<_E; i++){
adjlist[A[i]].push_back({B[i], D[i]});
adjlist[B[i]].push_back({A[i], D[i]});
edgelist.emplace_back(iii(pi(A[i], B[i]), D[i]));
}
dfs(0, -1);
roottree(0, -1, 0);
sparse_init();
// for(ll i = 0; i<n; i++) printf("%d-%d\n", S[i],
E[i]); printf("\n");
// for(ll i = 1; i<2*edges+9; i++) printf("%d: %d\n",
i, query(i, i)); printf("\n");
// for(ll i = 1; i<2*edges+9; i++) printf("%d: %d\n",
i, st[i][0]); printf("\n");
return;
}
void adjust(int e, int v){
ll a = edgelist[e].first.first, b = edgelist[e].first.second;
ll d = edgelist[e].second;
if(S[a] > S[b]) swap(a,b);
// a is the earlier one
update(S[b], -d);
update(E[b], d);
update(S[b],
v);
update(E[b],
-v);
edgelist[e].second = v;
return;
}
ll inf = INT_MAX;
void safe(int e) { // bug
occurs when 2 0 and 2 1, and 0 1 3 (perhaps use lca stuff)
ll a = edgelist[e].first.first, b = edgelist[e].first.second;
if(S[a] > S[b]) swap(a,b);
// a is the earlier one
update(S[b], -inf);
update(E[b], inf);
return;
}
void dangerous(int e) {
ll a = edgelist[e].first.first, b = edgelist[e].first.second;
if(S[a] > S[b]) swap(a,b);
// a is the earlier one
update(S[b], inf);
update(E[b], -inf);
return;
}
int energy(int x, int y) {
// printf("q(%d,%d)=\n", x, y);
// printf("S(%d) to S(%d)=\n", E[x], S[y]);
int p = lca(x, y);
ll ans = query(E[x], S[p]);
ll ans2 = query(E[p], S[y]);
// ll ans2 = 0;
if(ans < -inf/2 or ans > inf/2) return 0;
if(ans2 < -inf/2 or ans2 > inf/2) return 0;
return ans+ans2;
}
PushRelabel (maxflow, mincut)
(noiref, tested) O(N^3)
typedef long long ll;
struct Edge {
int to;
ll cap, flow;
Edge(int tar, ll capacity): to(tar),
cap(capacity), flow(0) {}
ll amt() { return cap-flow; }
};
struct PushRelabel {
int N;
vector<Edge> E;
vector<vector<int> >G;
vector<int> height, cnt;
vector<bool> inq;
vector<ll> excess;
queue<int> q;
PushRelabel(int _N): N(_N), height(_N),
cnt(2*_N), inq(_N), excess(_N), G(_N) {}
void AddEdge(int a, int b, ll c) { //directed edge a -> b with capacity c
if (a == b) return;
G[a].push_back(E.size());
E.push_back({b, c});
G[b].push_back(E.size());
E.push_back({a, 0});
}
void Enqueue(int x) {
if (inq[x] || excess[x] == 0) return;
inq[x] = 1;
q.push(x);
}
void Push(int x, int ed) {
int it = E[ed].to;
if (height[x] <= height[it]) return;
ll flow = min(excess[x], E[ed].amt());
if (flow == 0) return;
E[ed].flow += flow;
E[ed^1].flow -= flow;
excess[x] -= flow;
excess[it] += flow;
Enqueue(it);
}
void Relabel(int x) {
if (excess[x] == 0) return;
--cnt[height[x]];
height[x] = 2*N;
for (auto it:G[x]) {
if (E[it].amt() == 0) continue;
height[x] = min(height[x],
height[E[it].to]+1);
}
++cnt[height[x]];
Enqueue(x);
}
void GapHeuristic(int g) {
for (int i = 0; i < N; ++i) {
if (height[i] >= g) {
--cnt[height[i]];
height[i] = max(height[i], N+1);
++cnt[height[i]];
Enqueue(i);
}
}
}
void Discharge(int x) {
for (auto it:G[x]) {
Push(x, it);
if (excess[x] == 0) return;
}
if (cnt[height[x]] == 1)
GapHeuristic(height[x]);
else Relabel(x);
}
ll MaxFlow(int S, int T) {
height[S] = N;
cnt[0] = N-1, cnt[N] = 1;
inq[S] = inq[T] = 1;
for (auto it:G[S]) {
excess[S] += E[it].cap;
Push(S, it);
}
while (!q.empty()) {
int x = q.front();
q.pop(), inq[x] = 0;
Discharge(x);
}
return excess[T];
}
vector<int> MinCut(int S, int T) {
MaxFlow(S, T);
int split = N;
vector<int> ans;
for (int i = 1; i <= N; ++i) {
if (cnt[i] == 0) {
split = i;
break;
}
}
for (int i = 0; i < N; ++i) {
if (height[i] > split)
ans.push_back(i);
}
return ans;
}
};
LCA to RMQ Version #2
(taqtree)
#include
<bits/stdc++.h>
using namespace std;
typedef pair<int, int>
pi;
int n,q;
vector<pi>
adjlist[100050];
int pre[100050],
pre_r[100050]; // pre maps node to pre-ordering, pre_r maps pre-ordering to
node
int fw[200050];
int S[100050], E[100050];
int st[500050][19];
void add(int p, int v){
for(;p<=2*n+10;p+=p&(-p)) fw[p] += v;
}
int query(int a, int b){
int ans = 0;
int p = a-1;
assert(p != -1);
for(;p;p-=p&(-p)) ans-=fw[p];
p = b;
for(;p;p-=p&(-p)) ans+=fw[p];
return ans;
}
struct edge{
int a,b,c;
edge();
edge(int aa, int bb, int cc){ a = aa, b = bb, c = cc; }
};
vector<edge> edgelist;
int prectr = 1;
void preorder(int x, int
par){ // this is for lca (rmq)
pre_r[prectr] = x;
pre[x] = prectr++;
for(auto i : adjlist[x]){
if(i.first == par) continue;
preorder(i.first, x);
}
}
int ctr=0;
void dfs(int x, int par){ //
this is for euler (fenwick)
ctr++;
S[x] = ctr;
st[ctr][0] = pre[x];
for(auto i :
adjlist[x]){
if(i.first == par) continue;
add(ctr+1, i.second);
st[ctr][0] = pre[x];
dfs(i.first, x);
add(ctr+1, -i.second);
ctr++;
}
E[x] = ctr+1;
st[ctr][0] = pre[x];
}
// settle lca (rmq, st),
euler (fenwick)
int lca(int a, int b){
if(S[a] > S[b]) swap(a,b);
int len = S[b]-S[a]+1;
int k = 32-__builtin_clz(len)-1;
return pre_r[min(st[S[a]][k], st[S[b]-(1<<k)+1][k])];
}
void pre_st(){
for(int k = 1; k<=18; k++){
for(int i = 1; i<=2*n+9; i++){
assert(i+(1<<(k-1)) <= 500000);
st[i][k] = min(st[i][k-1],
st[i+(1<<(k-1))][k-1]);
}
}
}
int main(){
freopen("taqtree.txt", "r", stdin);
cin >> n;
for(int i = 0; i<n-1; i++){
int a,b,c;
cin >> a >> b >> c;
adjlist[a].push_back(pi(b,c));
adjlist[b].push_back(pi(a,c));
edgelist.push_back(edge(a,b,c));
}
preorder(1, -1);
dfs(1, -1);
pre_st();
cin >> q;
while(q--){
int a,b,c;
cin >> a >> b >> c;
if(a == 1){
// edit
b--;
int olda = edgelist[b].a, oldc = edgelist[b].c,
oldb = edgelist[b].b;
if(S[olda] > S[oldb]) swap(olda, oldb); //
olda is now the parent of oldb
add(S[oldb], -oldc);
add(E[oldb], oldc);
add(S[oldb], c);
add(E[oldb], -c);
edgelist[b].c
= c;
}else{
// change
if(S[b] > S[c]) swap(b,c);
int d = lca(b,c);
int ans = 0;
int td = d; if(S[td] > S[b]) swap(td, b);
ans += query(S[td]+1, S[b]);
td = d; if(S[td] > S[c]) swap(td, c); ans +=
query(S[td]+1, S[c]);
cout << ans << "\n";
}
}
}
Common Paths between Two
Paths (sherlockgraphs)
#include
<bits/stdc++.h>
using namespace std;
int n,m,q;
vector<int>
adjlist[100050];
bool visited[100050];
int p[100050][20];
int low[100050];
int depth[100050];
int pre[100050];
bool atp[100050];
int atppre[100050];
int ctr=0;
void dfs(int x){ // just for
ATB
visited[x] = true;
low[x] = ctr;
pre[x] = ctr;
ctr++;
for(auto i : adjlist[x]){
if(!visited[i]){
p[i][0]=x;
depth[i] = depth[x]+1;
dfs(i);
if(low[i]>pre[x]){
atp[i] = true;
}
low[x] = min(low[i], low[x]);
}else if(i != p[x][0]) low[x] = min(low[x], pre[i]);
}
}
void atpprecom(int x){
visited[x] = true;
for(auto i : adjlist[x]){
if(visited[i]) continue;
if(p[x][0] != i){
atppre[i] = atppre[x]+atp[i];
atpprecom(i);
}
}
}
void tkd(){
for(int k = 1; k<20; k++){
for(int i = 1; i<=n; i++){
if(p[i][k-1] != -1){
p[i][k] = p[p[i][k-1]][k-1];
}else p[i][k] = -1;
}
}
}
int lca(int a, int b){
if(depth[a]<depth[b]) swap(a,b);
for(int k = 19; k>=0; k--){
if(p[a][k] != -1 and depth[p[a][k]] >= depth[b])
a=p[a][k];
}
if(a==b) return a;
for(int k = 19; k>=0; k--){
if(p[a][k] != p[b][k]) a=p[a][k],b=p[b][k];
}
return p[a][0];
}
int dist(int a, int b){
return atppre[a] + atppre[b] - 2*atppre[lca(a,b)];
}
int inter(int a, int b, int
c, int d){
// a and c are the lcas
int ans = 0;
int ac = lca(a,c);
int bd = lca(b,d);
if(ac != a and ac != c) return 0; // disjoint paths
else if(ac == a){
// a is acestor of c (c stems)
if(lca(bd, c) == bd) return 0;
else ans = dist(bd, c);
}else{
// c is acestor of a
if(lca(bd, a) == bd) return 0;
else ans = dist(bd, a);
}
return ans;
}
int main(){
cin >> n >> m >> q;
for(int i = 0; i<m; i++){
int a,b;
cin >> a >> b;
adjlist[a].push_back(b);
adjlist[b].push_back(a);
}
depth[1] = 1;
dfs(1);
tkd();
memset(visited, false, sizeof visited);
atpprecom(1);
while(q--){
int a,b,c,d;
cin >> a >> b >> c >> d;
// join node a and b
// output path from c to d
int ans = 0;
int u = lca(a,b), v = lca(c,d);
ans = inter(u, a, v, c) + inter(u, b, v, c) + inter(u,
a, v, d) + inter(u, b, v, d);
cout << dist(c, d) - ans << "\n";
}
}
Heavy Light Decomposition
(grassplant)
#include
<bits/stdc++.h>
using namespace std;
typedef int ll;
// now a fenwick -.-
struct node{
vector<int> fw, fw2; // note this is 1 indexed, queries
are built to be 0 indexed
int s;
node(){}
node(int sz){ s = sz; fw.resize(sz+2); fw2.resize(sz+2); }
int query1(int x){
x++;
int ans = 0;
for(;x;x-=x&(-x)) ans+=fw[x];
return ans;
}
int query2(int x){
x++;
int ans = 0;
for(;x;x-=x&(-x)) ans+=fw2[x];
return ans;
}
void update1(int x, int v){
x++;
for(;x<=s;x+=x&(-x)) fw[x]+=v;
}
void update2(int x, int v){
x++;
for(;x<=s;x+=x&(-x)) fw2[x]+=v;
}
int point_query(int x){
return query1(x) * x + query2(x);
}
int range_query(int x, int y){
return point_query(y) - point_query(x-1);
}
void range_add(int x, int y, int v){
update1(x, v);
update1(y+1, -v);
update2(x, -(x-1)*v);
update2(y+1, y*v);
}
};
vector< node* > seg;
ll n, q;
struct treenode{
ll par, chain, depth, size, pos, weight;
// pos is position in chain it is in
// chain is the chain it is in
treenode(){ par = chain = depth = size = pos = weight = 0; }
} nodes[100050]; // struct to
contain a node
vector<ll>
adjlist[100050]; // adjacency list
ll segroot[100050],
segsize[100050]; // segroot[chain] = root of that segment, segsize[chain] =
size of that segment
void dfs_size(ll x, ll p){ //
for hld, calculate sizes , and a bunch of other stuff
nodes[x].size = 1;
for(auto i : adjlist[x]){
if(i == p) continue;
nodes[i].weight = 0;
nodes[i].par = x;
nodes[i].depth = nodes[x].depth + 1;
dfs_size(i, x);
nodes[x].size += nodes[i].size;
}
}
ll curchain = 0;
void hld(ll x, ll p){ // HLD
nodes[x].chain = curchain;
segsize[nodes[x].chain] = max(segsize[nodes[x].chain],
nodes[x].pos+1);
ll largest = 0, largest_size = 0;
for(auto i : adjlist[x]){
if(i == p) continue;
if(nodes[i].size >= largest_size) largest = i,
largest_size = nodes[i].size;
}
if(largest == 0) return;
// curchain remains at curchain
nodes[largest].pos = nodes[x].pos+1;
hld(largest, x);
for(auto i : adjlist[x]){
if(i == p or i == largest) continue;
curchain++; // curchain should only be the number of
light edges... but it reaches up to 100K
segroot[curchain] = i; // root of new chain
nodes[i].pos = 0; // root of new chain
hld(i, x);
}
}
ll lca(ll a, ll b){
if(a == b) return a;
ll ac = nodes[a].chain;
ll bc = nodes[b].chain;
if(ac == bc){
return nodes[a].depth < nodes[b].depth ? a : b;
}
ll ra = segroot[ac];
ll rb = segroot[bc];
if(nodes[ra].depth > nodes[rb].depth) return
lca(nodes[ra].par, b);
else return lca(a, nodes[rb].par);
}
ll query(ll a, ll b){ // b is
the ancestor
if(nodes[a].chain == nodes[b].chain){
if(nodes[b].pos+1 <= nodes[a].pos) return
seg[nodes[b].chain]->range_query(nodes[b].pos+1, nodes[a].pos);
return 0;
}
return query(nodes[segroot[nodes[a].chain]].par, b) +
seg[nodes[a].chain]->range_query(0, nodes[a].pos);
}
void update(ll a, ll b){ // b
is ancestor
if(nodes[a].chain == nodes[b].chain){
if(nodes[b].pos+1 <= nodes[a].pos)
seg[nodes[b].chain]->range_add(nodes[b].pos+1, nodes[a].pos, 1);
return;
}else{
seg[nodes[a].chain]->range_add(0,nodes[a].pos,1);
update(nodes[segroot[nodes[a].chain]].par, b);
}
}
void printchains(){
printf("Chains:\n");
for(ll i = 0; i<=curchain; i++){
printf("%d : ", i);
for(ll j = 0; j<segsize[i]; j++){
printf("%d ",
seg[i]->range_query(j,j));
}
printf("\n");
}
printf("\n");
}
int main(){
freopen("grassplant.1.2.in", "r", stdin);
cin >> n >> q;
for(ll i = 0; i<n-1; i++){
ll a,b; cin >> a >> b;
adjlist[a].push_back(b);
adjlist[b].push_back(a);
}
dfs_size(1, -1);
hld(1, -1);
for(ll i = 0; i<=curchain; i++) seg.push_back(new
node(segsize[i]));
while(q--){
ll a,b;
char qtype; cin >> qtype >> a >> b;
if(qtype == 'P'){ // plant
update(a, lca(a,b));
update(b, lca(a,b));
//printchains();
}else{ // query
cout << query(a, lca(a,b)) + query(b,
lca(a,b)) << "\n";
}
}
//for(ll i = 1; i<=n; i++) printf("%d : %d %d\n",
i, nodes[i].chain, nodes[i].pos);
}
Easy HLD (grassplant)
#include
<bits/stdc++.h>
using namespace std;
int n,q,t=1;
int fw1[100050], fw2[100050],
size[100050], s[100050], e[100050], nxt[100050], rs[100050];
vector<int>
adjlist[100050];
int depth[100050],
par[100050];
void update1(int p, int
newv){
for(;p<=100000;p+=p&(-p)) fw1[p] += newv;
}
void update2(int p, int
newv){
for(;p<=100000;p+=p&(-p)) fw2[p] += newv;
}
void range_update(int x, int
y, int v){
update1(x, v);
update1(y+1, -v);
update2(x, -(x-1)*v);
update2(y+1, y*v);
}
int query1(int p){
int ans = 0;
for(;p;p-=p&(-p)) ans+=fw1[p];
return ans;
}
int query2(int p){
int ans = 0;
for(;p;p-=p&(-p)) ans+=fw2[p];
return ans;
}
int query(int x){
return query1(x)*x + query2(x);
}
int range_query(int x, int
y){
return query(y) - query(x-1);
}
void dfs_size(int x, int p){
size[x] = 1;
for(auto &i : adjlist[x]){
if(i != p){
depth[i] = depth[x]+1;
par[i] = x;
dfs_size(i, x);
size[x] += size[i];
if(size[i] >= size[adjlist[x][0]]) swap(i,
adjlist[x][0]);
}
}
}
void hld(int x, int p){
rs[t] = x; // reverse start
s[x] = t++;
for(auto i : adjlist[x]){
if(i != p){
nxt[i] = (i == adjlist[x][0] ? nxt[x] : i);
hld(i, x);
}
}
e[x] = t;
}
int lca(int a, int b){
if(nxt[a] == nxt[b]) return depth[a] < depth[b] ? a : b; //
same chain, check depth
if(depth[par[nxt[a]]] < depth[par[nxt[b]]]) return lca(a,
par[nxt[b]]); // bring b up if a is higher
else return lca(par[nxt[a]], b); // else bring a up
}
void grow(int a, int b){
assert(b == lca(a, b));
while(nxt[a] != nxt[b]){
range_update(s[nxt[a]], s[a], 1);
a = par[nxt[a]];
}
if(s[b]+1 <= s[a]) range_update(s[b]+1, s[a], 1);
}
int ask(int a, int b){
assert(b == lca(a,b));
int ans = 0;
while(nxt[a] != nxt[b]){
ans += range_query(s[nxt[a]], s[a]);
a = par[nxt[a]];
}
if(s[b]+1 <= s[a]) ans+=range_query(s[b]+1, s[a]);
return ans;
}
int main(){
// freopen(".in", "r", stdin);
cin >> n >> q;
for(int i = 0; i<n-1; i++){
int a,b; cin >> a >> b;
adjlist[a].push_back(b);
adjlist[b].push_back(a);
}
par[1] = 0;
depth[1] = 1; // source of bug !!!! be careful!
nxt[1] = 1;
dfs_size(1, -1);
hld(1, -1);
while(q--){
int a,b;
char qtype; cin >> qtype >> a >> b;
if(qtype == 'P'){ // plant
grow(a, lca(a,b));
grow(b, lca(a,b));
}else{ // query
cout << ask(a, lca(a,b)) + ask(b,
lca(a,b)) << "\n";
}
}
// for(int i = 1; i<=n; i++) printf("%d %d %d %d
%d\n", s[i], e[i], nxt[i], depth[i], par[i]); printf("\n");
}
Modified PushRelabel with
Adjmat
typedef long long ll;
struct Edge{
ll cap, flow;
Edge(){cap = 0, flow = 0;}
Edge(int tar, ll capacity): cap(capacity),
flow(0) {}
ll amt() { return cap-flow; }
};
struct PushRelabel {
int N;
Edge G[105][105];
vector<int> height, cnt;
vector<bool> inq;
vector<ll> excess;
queue<int> q;
PushRelabel(int _N): N(_N), height(_N),
cnt(2*_N), inq(_N), excess(_N){
for(int
i = 0; i<=N; i++){
for(int
j = 0; j<=N; j++) G[i][j].cap = G[i][j].flow = 0;
}
}
void AddEdge(int a, int b, ll c) { //directed edge a -> b with capacity c
if (a == b) return;
G[a][b].cap += c;
}
void Enqueue(int x) {
if (inq[x] || excess[x] == 0) return;
inq[x] = 1;
q.push(x);
}
void Push(int x, Edge *e, Edge *re, int to)
{
int it = to;
if (height[x] <=
height[it]) return;
ll flow = min(excess[x], e->amt());
if (flow == 0) return;
e->flow += flow;
re->flow -=flow;
excess[x] -= flow;
excess[it] += flow;
Enqueue(it);
}
void Relabel(int x) {
if (excess[x] == 0) return;
--cnt[height[x]];
height[x] = 2*N;
for(int i = 0; i<=N; i++){
if(G[x][i].amt()
== 0) continue;
height[x] = min(height[x], height[i]+1);
}
++cnt[height[x]];
Enqueue(x);
}
void GapHeuristic(int g) {
for (int i = 0; i < N; ++i) {
if (height[i] >= g) {
--cnt[height[i]];
height[i] = max(height[i],
N+1);
++cnt[height[i]];
Enqueue(i);
}
}
}
void Discharge(int x) {
for(int
i = 0; i<=N; i++){
Push(x,
&G[x][i], &G[i][x], i);
if(excess[x]
== 0) return;
}
if (cnt[height[x]] == 1)
GapHeuristic(height[x]);
else Relabel(x);
}
ll MaxFlow(int S, int T) {
height[S] = N;
cnt[0] = N-1, cnt[N] = 1;
inq[S] = inq[T] = 1;
for(int i = 0; i<=N; i++){
excess[S]
+= G[S][i].cap;
Push(S,
&G[S][i], &G[i][S], i);
}
while (!q.empty()) {
int x = q.front();
q.pop(), inq[x] = 0;
Discharge(x);
}
return excess[T];
}
vector<int> MinCut(int S, int T) {
MaxFlow(S, T);
int split = N;
vector<int> ans;
for (int i = 1; i <= N; ++i) {
if (cnt[i] == 0) {
split = i;
break;
}
}
for (int i = 0; i < N; ++i) {
if (height[i] > split)
ans.push_back(i);
}
return ans;
}
};
Dinicճ
(untested, from https://gist.github.com/icyrhyme/3177630) O(EV^2)
#define MAXN 500
class Dinic {
int n, m,
head[MAXN], level[MAXN], s, t, work[MAXN];
struct
edge {
int
v, c, f, nxt;
edge()
{}
edge(int
v, int c, int f, int nxt): v(v), c(c), f(f), nxt(nxt) {}
}
e[MAXM];
bool
_bfs() {
static
int q[MAXN];
memset(level,
-1, sizeof(int) * n);
int
le = 0, ri = 0;
q[ri++]
= s;
level[s]
= 0;
while(le
< ri) {
for(int
k = q[le++], i = head[k]; i != -1; i = e[i].nxt) {
if(e[i].f
< e[i].c && level[e[i].v] == -1) {
level[e[i].v]
= level[k] + 1;
q[ri++]
= e[i].v;
}
}
}
return
(level[t] != -1);
}
int _dfs(int
u, int f) {
if(u == t)
return
f;
for(int&
i = work[u]; i != -1; i = e[i].nxt) {
if(e[i].f
< e[i].c && level[u] + 1 == level[e[i].v]) {
int
minf = _dfs(e[i].v, min(f, e[i].c - e[i].f));
if(minf
> 0) {
e[i].f
+= minf;
e[i
^ 1].f -= minf;
return
minf;
}
}
}
return
0;
}
public:
void
init(int nn, int src, int dst) {
n = nn;
s =
src;
t =
dst;
m = 0;
memset(head,
-1, sizeof(int) * n);
}
void
addEdge(int u, int v, int c, int rc) {
assert(u < n);
assert(v
< n);
e[m] = edge(v, c, 0, head[u]);
head[u]
= m++;
e[m]
= edge(u, rc, 0, head[v]);
head[v]
= m++;
assert(m
< MAXM);
}
int
maxFlow() {
int
ret = 0;
while(_bfs())
{
memcpy(work,
head, sizeof(int) * n);
while(true)
{
int
delta = _dfs(s, INF);
if(delta
== 0)
break;
ret
+= delta;
}
}
return
ret;
}
};
DP
LIS O(NlogN)
vector<int> lis;
int main() {
for(int i = 0; i<n; i++){
if(lis.empty() || A[i] > lis.back())
lis.push_back(A[i]);
else *lower_bound(lis.begin(), lis.end(), A[i]) = A[i];
// dp[i] = upper_bound(lis.begin(), lis.end(), A[i]) - lis.begin();
}
cout << lis.size();
}
LIS with Parent Tracking
(poklon)
#include
<bits/stdc++.h>
// *non-decreasing variant
using namespace std;
int n;
typedef pair<int, int>
pi;
pi A[100050];
int dp[100050];
int main(){
freopen("poklon.txt",
"r", stdin);
cin >> n;
for(int i=0; i<n; i++){
cin >> A[i].first >> A[i].second;
}
sort(A, A+n, [](pi a, pi b){ return (a.second==b.second and
a.first<b.first) or a.second > b.second; });
vector<pi> lis; // value, idx from
for(int i = 0; i<n; i++){
int cur = A[i].first;
if(lis.empty() or lis.back().first <= cur){
if(lis.empty()) dp[i] = -1; else dp[i] =
lis.back().second;
lis.push_back(pi(cur, i));
}else{
auto it = lower_bound(lis.begin(), lis.end(),
pi(cur, INT_MAX));
*it = pi(cur, i);
if(it!=lis.begin()) dp[i] = (*prev(it)).second;
else dp[i] = -1;
}
}
cout << lis.size() << endl;
int cur = lis.back().second;
vector<pi> v;
while(cur != -1){
v.push_back(A[cur]);
cur = dp[cur];
}
reverse(v.begin(), v.end());
for(auto i : v) cout << i.first << " "
<< i.second << "\n";
}
#include <bits/stdc++.h>
using namespace std;
int n;
typedef pair<int, int>
pi;
pi A[100050];
int p[100050];
bool cmp(int idx, int val){
return A[idx].first <= val;
}
int main(){
// freopen("poklon.txt", "r", stdin);
cin >> n;
for(int i = 0; i<n; i++) cin >> A[i].first >>
A[i].second;
sort(A, A+n, [](pi a, pi b){ return a.second == b.second ?
a.first < b.first : a.second > b.second; });
vector<int> lis;
for(int i = 0; i<n; i++){
int cur = A[i].first;
if(lis.empty() or A[lis.back()].first <= cur){ //
non decreasing
p[i] = lis.empty() ? -1 : lis.back();
lis.push_back(i);
}else{
int loc = lower_bound(lis.begin(), lis.end(),
cur, cmp) - lis.begin();
p[i] = loc == 0 ? -1 : lis[loc-1];
lis[loc] = i;
}
}
cout << lis.size() << endl;
int cur = lis.back();
vector<int> v;
while(cur != -1){
v.push_back(cur);
cur = p[cur];
}
reverse(v.begin(), v.end());
for(auto i : v) cout << A[i].first << "
" << A[i].second << "\n";
}
Maxsum O(N)
int A[N], maxsum[N];
int ans = maxsum[0] = A[0];
for (int i = 1; i < N;
++i) {
maxsum[i] = max(maxsum[i-1] + A[i], A[i]);
ans = max(ans, maxsum[i]);
}
int A[N];
int ans = A[0], cursum =
A[0];
for (int i = 1; i < N;
++i) {
if (cursum < 0) cursum = 0;
cursum += A[i];
ans = max(ans, cursum);
}
0-1 Knapsack (coinbag) O(NW)
#include
<bits/stdc++.h>
using namespace std;
int x, best[505][505];
int W[505], V[505];
int w;
int main(){
scanf("%d %d", &x, &w);
for(int i = 1; i<=x; i++){
scanf("%d %d", &W[i],
&V[i]);
}
memset(best, 0 , sizeof best);
for(int j = 1; j<=x; j++){
for(int n = 0; n<=w; n++){ // go from W[j] to w for faster
best [j][n] = best[j-1][n];
if(n>=W[j]) best[j][n] =
max(best[j][n], best[j-1][n-W[j]] + V[j]);
if(n > 0) best[j][n] =
max(best[j][n-1], best[j][n]);
}
}
printf("%d", best[x][w]);
}
0-1 Knapsack With Repeated
Items (CS3233 Qn) O(NWlogN)
#include
<bits/stdc++.h>
using namespace std;
typedef unsigned long long
ll;
ll S, N;
typedef pair<ll, ll>
pi;
typedef pair<pi, ll>
iii;
vector<iii> items;
ll dp[10050];
int main(){
while(cin >> S >> N){
ll addon = 0;
if(S == 0 and N == 0) break;
items.clear();
memset(dp, 0, sizeof dp);
for(int i = 0; i<N; i++){
ll v,w,k;
cin >> v >> w >> k;
if(w == 0){
addon += v*k;
continue;
}
int a=0;
while(k >= (1<<a)){
items.push_back(iii(pi(v,w),
(1<<a)));
k -= 1<<a;
a++;
}
if(k != 0) items.push_back(iii(pi(v,w), k));
}
for(auto i : items){
int cnt = i.second;
for(int k = S; k>=cnt*i.first.second; k--){
dp[k] = max(dp[k-1], dp[k]);
dp[k] = max(dp[k],
dp[k-cnt*i.first.second] + cnt*i.first.first);
}
}
cout << dp[S]+addon << "\n";
}
}
Unbounded Knapsack (untested
from geeksforgeeks)
int unboundedKnapsack(int W,
int n, int val[], int wt[])
{
// dp[i] is going to store maximum value
// with knapsack capacity i.
int dp[W+1];
memset(dp, 0, sizeof dp);
int ans = 0;
//
Fill dp[] using above recursive formula
for (int i=0; i<=W; i++)
for (int j=0; j<n; j++)
if (wt[j] <= i)
dp[i] = max(dp[i],
dp[i-wt[j]]+val[j]);
return dp[W];
}
0-1 Knapsack MITM (harddisk)
#include <bits/stdc++.h>
#define INF 10000000000000
using namespace std;
typedef long long ll;
ll n, c;
typedef pair<ll, ll>
pi;
pi A[45];
ll static_max[1100000];
pi one[1100000];
int main(){
freopen("input.txt",
"r", stdin);
cin >> n >> c;
for(int i = 0; i<n; i++) cin >> A[i].first >>
A[i].second;
ll firsthalf = n/2; //
note in actual solution its n/2-1 (to reduce memory)
for(int i = 0; i<(1<<firsthalf); i++){
ll value = 0, weight = 0;
for(int j = 0; j<firsthalf; j++){
if((1<<j) & i){
value += A[j].second;
weight += A[j].first;
}
}
one[i] = pi(weight, value);
}
sort(one, one+(1<<firsthalf));
// for(int i = 0; i<(1<<firsthalf); i++) printf("%d:
%d %d\n", i, one[i].first, one[i].second);
static_max[0] = one[0].second;
for(int i = 1; i<(1<<firsthalf); i++){
static_max[i] = max(static_max[i-1], one[i].second);
}
ll ans = 0;
for(int i = 0; i<(1<<(n-firsthalf)); i++){
ll value = 0, weight = 0;
for(int j = 0; j<n-firsthalf; j++){
if((1<<j) & i){
value += A[j+firsthalf].second;
weight += A[j+firsthalf].first;
}
}
int idx = upper_bound(one, one+(1<<firsthalf),
pi(c-weight, INF))-one-1;
if(idx < 0) continue;
ans = max(ans, static_max[idx] + value);
}
cout << ans;
}
Coin Change (mincoins)
(moneychanger)
#include
<bits/stdc++.h>
using namespace std;
int N, V, coins[10001],
value[10001];
int main()
{
cin >> N >> V;
for(int i = 0; i < N; i++)
{
cin >> coins[i];
}
value[0] = 0;
for(int i = 1; i<=V; i++){
value[i] = INT_MAX;
for(int j = 0; j<N; j++){
if(i>=coins[j] and
value[i-coins[j]]!=INT_MAX)
value[i] =
min(value[i],value[i-coins[j]]+1);
}
}
if(value[V] == INT_MAX) cout << -1;
else
cout<<value[V];
}
Coin Change (ways)
#include
<bits/stdc++.h>
using namespace std;
int n,v, coins[55],
ways[10050]; //value, index of minimum coin
int main(){
scanf("%d %d", &n, &v);
for(int i = 1; i<=n; ++i)
scanf("%d", &coins[i]);
ways[0] = 1;
for(int i = 1; i<=n; i++){
for(int j = 1; j<=v; j++){
if(j>=coins[i])
ways[j]+=ways[j-coins[i]];
ways[j]%=13371337;
}
}
cout << ways[v] % 13371337;
}
2D Maxsum (orchard)
#include
<bits/stdc++.h>
using namespace std;
const int maxh = 155, maxw =
100050;
int h, w;
int grid[maxh][maxw];
int ss[maxh][maxw];
int query(int x, int y1, int
y2){
return ss[y2][x] - ss[y1-1][x];
}
int ctr = 0;
int main(){
scanf("%d %d", &h, &w);
for(int i = 1; i<=h; ++i){
for(int j = 1; j<=w; ++j){
int hi;
scanf("%d", &hi);
if (hi == 0){
grid[i][j] = -1;
}else{
ctr++;
grid[i][j] = 1;
}
}
}
for(int i = 1; i<=w; ++i){
for(int j = 1; j<=h; ++j){
ss[j][i] = ss[j-1][i] + grid[j][i];
}
}
int ans = 0;
for(int i = 1; i<=h; ++i){
for(int j = i; j<=h; ++j){
int cur = 0;
for(int k = 1; k <= w; ++k){
if(cur<0) cur=0;
cur += query(k, i, j);
ans = max(ans, cur);
}
}
}
printf("%d\n", ctr-ans);
}
Maxsum from one corner to
every point (morefun)
cur=best=0;
for(int i = 1; i<=n; i++){
cur += A[i][1]-A[i-1][1];
if(cur < 0) cur = 0;
best = max(best, cur);
fromTL[i][1] = best;
}
for(int j = 2; j<=m; j++){
for(int i = 1; i<=n; i++) fromTL[i][j] = fromTL[i][j-1];
for(int k = 1; k<=j; k++){
cur=0;
best=0;
for(int i = 1; i<=n; i++){
cur += query(i, k, i, j);
if(cur < 0) cur = 0;
best = max(cur, best);
fromTL[i][j] = max(fromTL[i][j], best);
}
}
}
Longest Common Subsequence
int lcs(int x, int y){
if(x == -1 || y == -1) mug[x][y] = 0;
else if(mug[x][y] != -1) return mug[x][y];
else if(a[x] == b[y]) mug[x][y]=lcs(x-1,
y-1)+1;
else mug[x][y] = max(lcs(x, y-1), lcs(x-1,
y));
return mug[x][y];
}
int main() {
scanf("%s %s", &a, &b);
for(int i = 0; i<1005; i++){
for(int j = 0; j<1005; j++){
mug[i][j] = -1;
}
}
cout << lcs(strlen(a), strlen(b))-1
<< endl;
}
Count Subsequences (b in a)
string a,b;
cin>>a>>b;
int n = a.length(); int m =
b.length();
for(int i = 0; i<=n; i++)
dp[i][0] = 1;
for(int j = 1; j<=m; j++){
for(int i = 1; i<=n; i++){
dp[i][j] = 0;
if(a[i-1] == b[j-1]){
dp[i][j] += dp[i-1][j-1];
}
dp[i][j] += dp[i-1][j];
}
//for(int i = 1; i<=n; i++) printf("%d ",
dp[i][j] - dp[i-1][j]);
}
cout << dp[n][m];
Edit distance (untested)
char A[1001], B[1001]; //
null characters, remember
int N, M, edit[1001][1001];
for (int i = 0; i <= N;
++i) {
for (int j = 0; j <= M; ++j) {
if (i == 0 || j == 0) edit[i][j] = max(i, j);
if (A[i - 1] == B[j - 1]) edit[i][j] = edit[i - 1][j -
1];
else edit[i][j] = edit[i - 1][j - 1] + 1; //
substitution
edit[i][j] = min(edit[i][j], edit[i - 1][j]); //
insertion
edit[i][j] = min(edit[i][j], edit[i][j - 1]); //
deletion
}
}
L Hull (Max) (Increasing
Gradient, Increasing Query)
deque<pi> dq;
int y(pi line, int x){
return line.first * x + line.second;
}
int query(int x){
while(dq.size()>1){
if(y(dq[0],x) < y(dq[1],x)) dq.pop_front();
else return y(dq[0], x);
}
return y(dq[0],x);
}
double intersect(int m1, int
c1, int m2, int c2){
return (double)(c2-c1)/(m1-m2);
}
double intersect(pi p1, pi
p2){
return intersect(p1.first, p1.second, p2.first, p2.second);
}
void insert(int m, int c){
pi line = pi(m,c);
while(dq.size()>1){
int s = dq.size();
if(intersect(dq[s-1], line)<=intersect(dq[s-2],
line)) dq.pop_back();
else break;
}
dq.push_back(line);
}
Hull (Min) (Decreasing
Gradient, Increasing Query)
deque<pi> dq;
int y(pi line, int x){
return line.first * x + line.second;
}
int query(int x){
while(dq.size()>1){
if(y(dq[0],x) >= y(dq[1],x)) dq.pop_front();
else break;
}
return y(dq[0], x);
}
double intersect(int m1, int
c1, int m2, int c2){
return (double) (c2-c1)/(m1-m2);
}
double intersect(pi p1, pi
p2){
return intersect(p1.first, p1.second, p2.first, p2.second);
}
void insert(int m, int c){
pi line = pi(m,c);
while(dq.size()>1){
int s = dq.size();
if(intersect(dq[s-1], line) <= intersect(dq[s-2],
line)) dq.pop_back();
else break;
}
dq.push_back(line);
}
General Convex Hull
struct Line{
ll m, c;
long double left;
enum Type {line, query} type;
ll x; // for query
Line(){}
Line(ll mm, ll cc){ m = mm; c = cc; left = 0.0;}
friend ll val(Line a, ll x){ return x*a.m + a.c; }
friend void printline(Line a){
printf("%d x + %d, %0.1f\n", a.m, a.c,
a.left);
}
friend long double intersect(Line a, Line b){
if(a.m == b.m) return inf;
return (long double) (a.c-b.c)/ (long double)
(b.m-a.m);
}
bool operator<(const Line &a) const{
if(a.type == line) return this->m < a.m; // sort
by ascending gradient
else return this->left < (long double) a.x;
}
};
struct ConvexHull{
typedef set<Line>::iterator sit;
set<Line> ch;
bool hasPrev(sit it){ return it != ch.begin(); }
bool hasNext(sit it){ return it != ch.end() and it !=
prev(ch.end()); }
bool use(Line a, Line b, Line c){ return intersect(a,b) <=
intersect(a,c); } // B is useful or not
bool use(sit a){ return !hasPrev(a) or !hasNext(a) or
use(*prev(a), *a, *next(a)); }
sit updateLeft(sit a){
Line copy = *a;
if(a == ch.begin()) copy.left = -dinf;
else{
copy.left = intersect(*prev(a), *a);
}
auto it = ch.erase(a);
it = ch.insert(it, copy);
return it;
}
void printlines(){
for(auto i : ch) printline(i); printf("\n");
}
void addLine(Line a){
if(debug) printf("adding %d x + %d\n", a.m,
a.c);
auto it = ch.lower_bound(Line(a.m, -inf));
if(it!=ch.end() and it->m == a.m){
if(it->c > a.c) ch.erase(it); // tainter
one delete
else return;
}
it = ch.insert(it, a);
if(!use(it)){ ch.erase(it); return; }
while(hasPrev(it) and !use(prev(it)))
ch.erase(prev(it));
while(hasNext(it) and !use(next(it)))
ch.erase(next(it));
it = updateLeft(it);
if(hasPrev(it)) updateLeft(prev(it));
if(hasNext(it)) updateLeft(next(it));
if(debug) printlines();
}
ll query(ll x){
Line q;
q.x = x;
q.type = Line::Type::query;
sit it = ch.lower_bound(q);
if(hasPrev(it)) it=prev(it);
return val((*it), x);
}
};
Divide and Conquer (e.g.
guards) O(N log N) per row
void dnc(int s, int e, int x,
int y, int k){
int m = (s+e)/2;
dp[m][k]
= INF;
for(int i = x; i<=y; i++){
if(dp[m][k]>dp[i][k-1] + cost(i+1,m)){
dp[m][k] = dp[i][k-1]+cost(i+1, m);
opt[m][k] = i;
}
}
if(s<m) dnc(s, m-1, x, opt[m][k], k);
if(m<e) dnc(m+1, e,
opt[m][k], y, k);
}
// usage: for each k, call
dnc(1,n,1,n,k)
Sliding Set (diversity)
#include
<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,k,A[5000050];
int main(){
// freopen("input.txt", "r", stdin);
cin >> n >> k;
for(int i = 0; i<n; i++){
cin >> A[i];
}
ll ans = 0;
multiset<int> ss;
int s = 0, e = 0;
while(e<n){
while((ss.empty() or *(ss.rbegin()) - *(ss.begin())
< k) and e<n){
// printf("e : %d\n", e);
ss.insert(A[e++]);
}
if(e >= n) break;
while(s < e and !ss.empty() and *(ss.rbegin()) -
*(ss.begin()) >= k){
// printf("s : %d\n", s);
ans+=n-e+1;
ss.erase(ss.find(A[s++]));
}
}
while(s<n){
if(*(ss.rbegin()) - *(ss.begin()) >= k) ans++;
ss.erase(ss.find(A[s++]));
}
cout << ans;
}
Sliding Deque (min and max)
deque<int> dmin, dmax;
void insert(int val){
while(!dmin.empty() and dmin.back() > val) dmin.pop_back(); // note Ҧgt;ӡ!!
dmin.push_back(val);
while(!dmax.empty() and dmax.back() < val) dmax.pop_back();
dmax.push_back(val);
}
void erase(int val){
if(!dmin.empty() and dmin.front() == val) dmin.pop_front();
if(!dmax.empty() and dmax.front() == val) dmax.pop_front();
}
int mmin(){
return dmin.front();
}
int mmax(){
return dmax.front();
}
bool empty(){ return dmax.empty()
and dmin.empty(); }
Kth Lexicographical
(z-01paths)
string ans;
void calc(){
char cur = 'A';
for(ll i = n; i>=1; i--){
for(ll j = 0; j<=1; j++){
char temp = cur;
if(j == 0){
if(cur == 'A') temp = 'C';
else if(cur == 'B') temp = 'D';
else if(cur == 'C') temp = 'A';
else if(cur == 'D') temp = 'B';
}else{
if(cur == 'A') temp = 'B';
else if(cur == 'B') temp = 'A';
else if(cur == 'C') temp = 'D';
else if(cur == 'D') temp = 'C';
}
ll ret = count(temp, i-1);
ret = ret==0?-1:ret;
if(ret == -1) continue;
if(k <= ret){
ans += (char) (j+'0');
cur = temp;
break;
}else k-=ret;
}
}
}
Data Structures
Fenwick Tree PURQ
Update: O(log N)
Query: O(log N)
int fw[N+1];
void update(int p, int v){
for(;p<=n;p+=p&(-p)) fw[p] += v;
}
int query(int p){
int ans = 0;
for(;p;p-=p&(-p)) ans+=fw[p];
return ans;
}
Fenwick Tree RUPQ
void rangeUpdate(int a, int
b, int v){
update(a, v);
update(b+1, -v);
}
int pointQuery(int p){
return query(p);
}
Fenwick Tree RURQ!
int fw[N+1], fw2[N+1];
int n,q;
void update(int * A, int p,
int v){
for(;p<=n;p+=p&(-p)) A[p] += v;
}
int query(int * A, int p){
int ans = 0;
for(;p;p-=p&(-p)) ans+=A[p];
return ans;
}
int prefixSum(int p){
return query(fw, p)*p + query(fw2, p);
}
void rangeUpdate(int a, int
b, int v){
update(fw, a, v);
update(fw, b+1, -v);
update(fw2, a, -v*(a-1));
update(fw2, b+1, v*b);
}
int rangeQuery(int a, int b){
return prefixSum(b) - prefixSum(a-1);
}
2D Fenwick
int fw[2005][2005];
int n,m,q;
void update(int x, int y, int
v){
for(int tx=x; tx<=n; tx+=tx&(-tx)){
for(int ty=y; ty<=m; ty+=ty&(-ty)){
fw[tx][ty] += v;
}
}
}
int query(int x, int y){
int ans = 0;
for(int tx=x; tx; tx-=tx&(-tx)){
for(int ty=y; ty; ty-=ty&(-ty)){
ans+=fw[tx][ty];
}
}
return ans;
}
int rangequery(int x1, int
y1, int x2, int y2){
return query(x2,y2)-query(x2,y1-1)-query(x1-1,y2)+query(x1-1,y1-1);
}
Standard Segment Tree
#include
<bits/stdc++.h>
using namespace std;
struct node{
int s, e, m, maxv, minv;
node *l, *r;
node(int ss, int ee){
s = ss; e = ee;
minv = maxv = 0;
m = (s+e)/2;
if(s != e){
l = new node(s,m);
r = new
node(m+1, e);
}
}
void update(int p, int nv){
if(s == e){
minv = maxv = nv;
return;
}
if(p <= m) l->update(p, nv);
else r->update(p, nv);
maxv = max(l->maxv,
r->maxv);
minv
= min(l->minv, r->minv);
}
int querymin(int x, int y){
if(x == s and e == y) return minv;
if(x > m) return r->querymin(x,y);
if(y <= m) return l->querymin(x,y);
return min(l->querymin(x,m), r->querymin(m+1,y));
}
int querymax(int x, int y){
if(x == s and e == y) return maxv;
if(x > m) return r->querymax(x,y);
if(y <= m) return l->querymax(x,y);
return max(l->querymax(x,m), r->querymax(m+1,
y));
}
} *root;
int main(){
root = new node(0, N-1); // init
root -> update(1,5); // update
cout << root -> querymin(1,3) << Ҝnӻ // query
}
OR
struct SegmentTree{ // RMQ ST
int A[200050]; // careful about array bounds!
(2*2^ceil(log2(N))+1)
int n;
SegmentTree(int nn){
n = nn;
}
void update_r(int s, int e, int p, int v, int i){
if(p<s or p>e) return;
if(s==e){
A[i] = v;
return;
}
int m = (s+e)/2;
update_r(s,m,p,v,2*i+1);
update_r(m+1,e,p,v,2*i+2);
A[i] = min(A[2*i+1], A[2*i+2]);
}
int query_r(int s, int e, int x, int y, int i){
if(x <= s and y >= e) return A[i];
if(x > e or y < s) return inf;
int m = (s+e)/2;
return min(query_r(s,m,x,y,2*i+1),
query_r(m+1,e,x,y,2*i+2));
}
void update(int p, int v){
update_r(0, n, p, v, 1);
}
int query(int x, int y){
return query_r(0, n, x, y, 1);
}
};
Lazy Propogation ST
struct node{
int s, e, m, v, lazyadd;
node *l, *r;
node(int _s, int _ e): s(_s), e(_e),
m((_s+_e)/2), v(0){
if(s!=e){
l = new node(s, m); r = new node (m+1,
e);
}
}
int value(){
if(s == e){
v += lazyadd;
lazyadd = 0;
return v;
}
r -> lazyadd += lazyadd; l -> lazyadd
+= lazyadd;
v+=lazyadd;
lazyadd = 0;
return v;
}
void add(int x, int y, int val){
if(s == x and e == y) lazyadd += val;
else{
if(x > m) r-> add(x, y, val);
else if(y <= m) l -> add(x,y, val);
else l -> add(x,m,val),
r->add(m+1,y,val);
v = max(l->value(), r->value());
}
}
int rmq(int x, int y){
value();
if(s == x and e == y) return value();
if(x > m) return r->rmq(x,y);
else if(y <= m) return l->rmq(x, y);
return max(l->rmq(x,m),
r->rmq(m+1,y));
}
} * root;
Memory Efficient ST
struct node{
int v;
node *l, *r;
node(int s, int e): v(0){
int m = (s+e)/2;
if(s!=e){
l = new node(s, m);
r = new
node(m+1, e);
}
}
void update(int s, int e, int x, int nv){
int m = (s+e)/2;
if(s == e){
v =
nv;
return;
}
if(x <= m) l->update(s, m, x, nv);
else
r->update(m+1, e, x, nv);
v = min(l->v, r->v);
}
int rmq(int s, int e, int x, int y){
// printf("%d %d %d %d\n", s, e,
x, y);
if(s
== x and e == y) return v;
int m = (s+e)/2;
if(x > m){
return r->rmq(m+1, e, x, y);
}else if(y <= m){
return l->rmq(s,m, x, y);
}
return min(l->rmq(s,m,x,m),
r->rmq(m+1,e,m+1,y));
}
} * root;
Bananafarm Segment Tree
#include
<bits/stdc++.h>
using namespace std;
int A[200050];
struct node{
int s, e, m;
vector<int> v;
node *l, *r;
node(int _s, int _e): s(_s), e(_e),
m((_s+_e)/2), v(0){
if(s == e){
v.push_back(A[s]);
return;
}
l = new node(s, m); r = new node (m+1, e);
int i = 0, j = 0;
vector<int> left = l->v;
vector<int> right = r->v;
while(i < left.size() or j <
right.size()){
if(i == left.size()){
v.push_back(right[j++]);
}else if(j == right.size()){
v.push_back(left[i++]);
}else{
if(left[i] < right[j]){
v.push_back(left[i++]);
}else{
v.push_back(right[j++]);
}
}
}
}
int countabove(int x, int y, int k){
if(s == x and e == y) return
v.end()-lower_bound(v.begin(),v.end(),k);
if(x > m) return
r->countabove(x,y,k);
if(y <= m) return
l->countabove(x,y,k);
return l->countabove(x,m,k) +
r->countabove(m+1,y,k);
}
} * root;
int n, biggestguy;
int getplace(int x, int y,
int p){ // in range [x,y], get the p-th biggest guy
int s = 0; int e = biggestguy + 1;
int m;
while(m = (s+e)/2, e-s>1){
if(root -> countabove(x,y,m) >= p) s
= m;
else e = m;
}
return s;
}
int main(){
int q;
cin >> n >> q;
for(int i = 0; i<n; i++){
cin >> A[i];
biggestguy = max(biggestguy, A[i]);
}
root = new node(0,n-1);
// root -> printst();
while(q--){
int a,b,c;
cin >> a >> b >> c;
a--;b--;
cout << getplace(a,b,c) <<
"\n";
}
}
Range Set Point Query (from
bstmaintenance)
*Take note: lazy propagate
before updating! (was a bug)
bool lazyprop = 1;
struct node{
int s,e,m,v,lazy;
node *l, *r;
node(int ss, int ee){
s = ss, e = ee; m = (s+e)/2;
v = 0;
lazy = -1;
if(s == e) return;
l = new node(s, m);
r = new node(m+1, e);
}
int value(){
if(s == e){
v=lazy;
lazy=-1;
}
if(lazy == -1) return v;
l->lazy = lazy;
r->lazy = lazy;
v = lazy;
lazy = -1;
return v;
}
void pointupdate(int x, int nv){
if(s == e){
v = nv;
return;
}
if(x <= m) l->pointupdate(x, nv);
else r->pointupdate(x, nv);
}
void update(int x, int y, int nv){
if(!lazyprop) for(int i = x; i<=y; i++)
pointupdate(i, nv);
if(lazyprop){
value();
if(s == x and e == y){
lazy = nv;
return;
}
if(y<=m) l->update(x,y,nv);
else if(x>m) r->update(x,y,nv);
else{
l->update(x,m,nv);
r->update(m+1,y,nv);
}
}
}
int query(int p){
if(lazyprop) value();
if(s == e){
if(!lazyprop) return v;
return value();
}
if(p <= m) return l->query(p);
else return r->query(p);
}
} * root;
Range Set Range Sum Query
#include
<bits/stdc++.h>
using namespace std;
// a range set range sum
query segment tree
struct node{
int s, e, v, lazy, m;
node *l, *r;
node(int ss, int ee){
s = ss, e = ee;
m = (s+e)/2;
v = lazy = 0;
if(s == e) return;
l = new node(s, m);
r = new node(m+1, e);
}
int value(){
if(lazy == 0) return v;
if(s == e){
v = lazy;
lazy = 0;
return v;
}
v = (e-s+1) * lazy;
l->lazy = lazy;
r->lazy = lazy;
lazy = 0;
return v;
}
void range_set(int x, int y, int newv){
value();
if(s == x and e == y){
lazy = newv;
return;
}
if(y <= m) l->range_set(x,y,newv);
else if(x > m) r->range_set(x,y,newv);
else{
l->range_set(x,m,newv);
r->range_set(m+1,y,newv);
}
v = l->value()+r->value();
}
int range_query(int x, int y){
value();
if(x == s and e == y) return value();
if(y <= m) return l->range_query(x,y);
else if(x > m) return r->range_query(x,y);
return l->range_query(x,m) +
r->range_query(m+1,y);
}
} * root;
ST from Noiref (untested):
typedef long long ll;
struct node {
int s, e;
ll mn, mx, sum;
bool lset;
ll add_val, set_val;
node *l, *r;
node (int _s, int _e, int A[] = NULL):
s(_s), e(_e), mn(0), mx(0), sum(0), lset(0), add_val(0), set_val(0), l(NULL),
r(NULL) {
if (A == NULL) return;
if (s == e) mn = mx = sum = A[s];
else {
l = new node(s, (s+e)>>1, A),
r = new node((s+e+2)>>1, e, A);
combine();
}
}
void create_children() {
if (s == e) return;
if (l != NULL) return;
int m = (s+e)>>1;
l = new node(s, m);
r = new
node(m+1, e);
}
void self_set(ll v) {
lset = 1;
mn = mx = set_val = v;
sum = v * (e-s+1);
add_val = 0;
}
void self_add(ll v) {
if (lset) { self_set(v + set_val);
return; }
mn += v, mx += v, add_val += v;
sum += v*(e-s+1);
}
void lazy_propagate() {
if (s == e) return;
if (lset) {
l->self_set(set_val),
r->self_set(set_val);
lset = set_val = 0;
}
if (add_val != 0) {
l->self_add(add_val),
r->self_add(add_val);
add_val = 0;
}
}
void combine() {
if (l == NULL) return;
sum = l->sum + r->sum;
mn =
min(l->mn, r->mn);
mx = max(l->mx, r->mx);
}
void add(int x, int y, ll v) {
if (s == x && e == y) {
self_add(v); return; }
int m = (s+e)>>1;
create_children(); lazy_propagate();
if (x <= m) l->add(x, min(y, m),
v);
if (y > m) r->add(max(x, m+1), y,
v);
combine();
}
void set(int x, int y, ll v) {
if (s == x && e == y) {
self_set(v); return; }
int m = (s+e)>>1;
create_children(); lazy_propagate();
if (x <= m) l->set(x, min(y, m),
v);
if (y > m) r->set(max(x, m+1), y,
v);
combine();
}
ll range_sum(int x, int y) {
if (s == x && e == y) return
sum;
if (l == NULL || lset) return (sum / (e-s+1))
* (y-x+1);
int m = (s+e)>>1;
lazy_propagate();
if (y <= m) return
l->range_sum(x, y);
if (x > m) return r->range_sum(x,
y);
return l->range_sum(x, m) +
r->range_sum(m+1, y);
}
ll range_min(int x, int y) {
if (s == x && e == y) return
mn;
if (l == NULL || lset) return mn;
int m = (s+e)>>1;
lazy_propagate();
if (y <= m) return
l->range_min(x, y);
if (x > m) return r->range_min(x,
y);
return min(l->range_min(x, m),
r->range_min(m+1, y));
}
ll range_max(int x, int y) {
if (s == x && e == y) return
mx;
if (l == NULL || lset) return mx;
int m = (s+e)>>1;
lazy_propagate();
if (y <= m) return
l->range_max(x, y);
if (x > m) return r->range_max(x,
y);
return max(l->range_max(x, m),
r->range_max(m+1, y));
}
~node() {
if (l != NULL) delete l;
if (r != NULL) delete r;
}
} *root;
root = new node(0, N-1,
array); //creates a segment tree with elements 0 to N - 1. The array parameter
is optional.
root = new node(0,
1000000000); //this tree supports lazy node creation and propagation too,
declare as much as you like :)
root->add(0, 5000,
3); //add 3 to range [0, 5000]
root->add(3000, 9000, -2);
//minus 2 to range [3000, 9000]
root->set(7000, 10000,
5); //set range [7000, 10000] to 5
/* at this point, 0 to 2999 is
3, 3000 to 5000 is 1, 5001 to 6999 is -2, 7000 to 10000 is 5 */
root->range_max(0,
10000); //returns 5
root->range_min(0,
10000); //returns -2
root->range_sum(0,
10000); //returns 22008#include
<iostream>
int main() {
std::cout << "Hello World!\n";
}
Suffix Array
#include
<bits/stdc++.h>
#define csize 100050
using namespace std;
int sa[100050], ra[100050];
int tempsa[100050],
tempra[100050];
string suffix[100050];
int n;
string s;
void printtable(int k){
// print i, sa[i], suffix, ra[sa[i]], ra[sa[i]+k]
cout.width(6); cout<<left<<"";
cout.width(6); cout<<left<<"i";
cout.width(6); cout<<left<<"sa[i]";
cout.width(20); cout<<left<<"suffix[i]";
cout.width(10); cout<<left<<"ra[sa[i]]";
cout.width(10);
cout<<left<<"ra[sa[i]+k]";
cout << endl;
for(int i = 0; i<n; i++){
cout.width(6); cout<<"";
cout.width(6); cout<<left<<i;
cout.width(6); cout<<left<<sa[i];
cout.width(20); cout<<left<<suffix[sa[i]];
cout.width(10); cout<<left<<ra[sa[i]];
cout.width(10); cout<<left<<ra[sa[i]+k];
cout << endl;
}
}
int c[csize];
void countingsort(int k){
memset(c, 0, sizeof c);
for(int i = 0; i<n; i++){
c[sa[i]+k < n ? ra[sa[i]+k] : 0]++;
}
int sum=0;
for(int i = 0; i<csize; i++){
int t = c[i];
c[i] = sum;
sum += t;
}
for(int i = 0; i<n; i++){
tempsa[c[sa[i]+k < n ? ra[sa[i]+k] : 0]++] = sa[i];
}
for(int i = 0; i<n; i++) sa[i] = tempsa[i];
}
void builtsa(){
for(int k = 1; k<n; k<<=1){
countingsort(k);
countingsort(0);
int r=0;
tempra[0] = 0;
for(int i = 1; i<n; i++){
tempra[sa[i]] = (ra[sa[i]] == ra[sa[i-1]] and
ra[sa[i]+k] == ra[sa[i-1]+k] ? r : ++r);
}
for(int i = 0; i<n; i++) ra[i] = tempra[i];
if(ra[sa[n-1]] == n-1) break;
//printtable(k);
}
}
int main(){
s = "abaaabaaabaaabbbb";
s+="$";
n = s.length();
for(int i = 0; i<n; i++){
suffix[i] = s.substr(i, n-i);
sa[i] = i;
ra[sa[i]] = suffix[i][0];
}
builtsa();
for(int i = 0; i<n; i++){
int k = 4;
cout.width(10); cout<<"";
cout.width(20); cout<<left<<suffix[sa[i]];
cout.width(10); cout<<left<<ra[sa[i]];
cout.width(10); cout<<left<<ra[sa[i]+k];
cout.width(10); cout<<left<<ra[sa[i]+2*k];
cout << endl;
}
// printtable(4);
}
LCP Array (untested)
#include
<bits/stdc++.h>
#define csize 100050
using namespace std;
int sa[100050], ra[100050];
int tempsa[100050],
tempra[100050];
int lcp[100050], phi[100050];
string suffix[100050];
int n;
string s;
bool debug_lcp = 0;
void printtable(int k){
// print i, sa[i], suffix, ra[sa[i]], ra[sa[i]+k]
cout.width(6); cout<<left<<"";
cout.width(6); cout<<left<<"i";
cout.width(6); cout<<left<<"sa[i]";
cout.width(20); cout<<left<<"suffix[i]";
cout.width(9); cout<<left<<"lcp[i]";
if(debug_lcp){
cout.width(6); cout<<left<<"|";
cout.width(6); cout<<left<<"i";
cout.width(9);
cout<<left<<"phi[i]";
cout.width(20);
cout<<left<<"suffix[i]";
}
cout << endl;
for(int i = 0; i<n; i++){
cout.width(6); cout<<"";
cout.width(6); cout<<left<<i;
cout.width(6); cout<<left<<sa[i];
cout.width(20);
cout<<left<<suffix[sa[i]];
cout.width(9); cout<<left<<lcp[i];
if(debug_lcp){
cout.width(6);
cout<<left<<"|";
cout.width(6); cout<<left<<i;
cout.width(9); cout<<left<<phi[i];
cout.width(20);
cout<<left<<suffix[i];
}
cout << endl;
}
}
int c[csize];
void countingsort(int k){
memset(c, 0, sizeof c);
for(int i = 0; i<n; i++){
c[sa[i]+k < n ? ra[sa[i]+k] : 0]++;
}
int sum=0;
for(int i = 0; i<csize; i++){
int t = c[i];
c[i] = sum;
sum += t;
}
for(int i = 0; i<n; i++){
tempsa[c[sa[i]+k < n ? ra[sa[i]+k] : 0]++] = sa[i];
}
for(int i = 0; i<n; i++) sa[i] = tempsa[i];
}
int plcp[100050];
void builtsa(){
for(int k = 1; k<n; k<<=1){
countingsort(k);
countingsort(0);
int r=0;
tempra[0] = 0;
for(int i = 1; i<n; i++){
tempra[sa[i]] = (ra[sa[i]] == ra[sa[i-1]] and
ra[sa[i]+k] == ra[sa[i-1]+k] ? r : ++r);
}
for(int i = 0; i<n; i++) ra[i] = tempra[i];
if(ra[sa[n-1]] == n-1) break;
//printtable(k);
}
for(int i = 0; i<n; i++) phi[sa[i]] = (i==0?-1:sa[i-1]);
int l = 0;
for(int i = 0; i<n; i++){
if(phi[i] == -1){ plcp[i] = 0; continue; }
while(s[i+l] == s[phi[i]+l]) ++l;
plcp[i] = l;
l = max(l-1, 0);
}
for(int i = 0; i<n; i++) lcp[i] = plcp[sa[i]];
}
int main(){
s = "abaaabaaabaaabbbb";
s+="$";
n = s.length();
for(int i = 0; i<n; i++){
suffix[i] = s.substr(i, n-i);
sa[i] = i;
ra[sa[i]] = suffix[i][0];
}
builtsa();
printtable(0);
}
Persistent UFDS (fatnode)
typedef pair<int,int>
pi;
vector<pi> p[100050];
vector<pi>
size[100050];
int par(int x, int t){
auto it = prev(upper_bound(p[x].begin(), p[x].end(),
pi(t,inf)));
if(x == (*it).second) return x;
return par((*it).second,t);
}
int getsize(int x, int t){
x = par(x,t);
auto it = prev(upper_bound(size[x].begin(), size[x].end(),
pi(t,inf)));
return (*it).second;
}
void merge(int a, int b, int
t){
int ap = par(a,t), bp = par(b,t);
int as = getsize(ap,t), bs=getsize(bp,t);
if(as > bs) swap(ap, bp); // union by rank (impt!)
p[ap].push_back(pi(t,bp));
size[bp].push_back(pi(t,bs+as));
}
bool sameset(int a, int b,
int t){
return par(a,t) == par(b,t);
}
Persistent ST (mkthnum)
#include
<bits/stdc++.h>
using namespace std;
struct node{
int s,e,m,v;
node *l, *r;
node(int ss, int ee, bool prop){
l = NULL;
r = NULL;
s = ss;
e = ee;
m = (s+e)/2;
v=0;
if(s == e){
return;
}
if(prop){
l = new node(s,m,prop);
r = new node(m+1,e,prop);
}
}
node * update(int p, int newv){
node * ret = new node(s,e,false);
if(s == e){
ret->v = newv;
return ret;
}
if(p <= m){
ret->l = l->update(p, newv);
ret->r = r;
}else{
ret->l = l;
ret->r = r->update(p, newv);
}
ret->v = ret->l->v + ret->r->v;
return ret;
}
} * root[100050];
int n,q,A[100050];
int query(int x, int y, int
k){
node * yroot = root[y];
node * xroot = root[x];
int s=0, e=n-1, m;
while(m=(s+e)/2,s!=e){
int frontval = yroot->l->v;
int backval = xroot->l->v;
int leftval = frontval-backval;
if(k <= leftval){ // k is in the left subtree
yroot = yroot->l;
xroot = xroot->l;
e=m;
}else{
k -= leftval;
yroot = yroot->r;
xroot = xroot->r;
s=m+1;
}
}
return s;
}
int main(){
cin >> n >> q;
vector<int> pos;
for(int i = 1; i<=n; i++){
cin >> A[i];
pos.push_back(A[i]);
}
sort(pos.begin(), pos.end());
root[0] = new node(0, n-1, true);
for(int i = 1; i<=n; i++){
int idx = lower_bound(pos.begin(), pos.end(),
A[i])-pos.begin();
root[i] = root[i-1]->update(idx, 1);
}
while(q--){
int a,b,k;
cin >> a >> b >> k;
cout << pos[query(a-1,b,k)] << '\n';
}
}
With arrays (stockexchange)
#include
<bits/stdc++.h>
using namespace std;
int n,m,A[100009];
int nn=1;
struct node{
int l,r,v;
} tree[100009*20]; // N log N
int root[100005];
int create(int ll, int rr,
int vv){
tree[nn].l = ll;
tree[nn].r = rr;
tree[nn].v = vv;
return nn++;
}
void insert(int &root,
int proot, int s, int e, int p){
root = create(tree[proot].l, tree[proot].r, tree[proot].v+1);
int m = (s+e)/2;
if(s == e) return;
if(p<=m) insert(tree[root].l, tree[proot].l, s, m, p);
else insert(tree[root].r, tree[proot].r, m+1, e, p);
}
int query(int t1, int t2, int
p){
if(p == -1) return 0;
int s = 0, e = n, m;
int ans = 0;
int one = root[t1], two = root[t2];
while(true){
m = (s+e)/2;
if(s == e){
ans += tree[two].v - tree[one].v;
break;
}
if(p <= m){
e = m;
one = tree[one].l, two = tree[two].l;
}else{
ans += tree[tree[two].l].v -
tree[tree[one].l].v;
one = tree[one].r, two = tree[two].r;
s = m+1;
}
}
return ans;
}
int main(){
// freopen("stockexchange.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
vector<int> discrete;
cin >> n >> m;
// how to settle init tree?
// ans: solved implicitly because of 0-self reference, gug
zhencongming :o
for(int i = 1; i<=n; i++){
cin >> A[i];
discrete.push_back(A[i]);
}
sort(discrete.begin(), discrete.end());
for(int i = 1; i<=n; i++){
int p = lower_bound(discrete.begin(), discrete.end(),
A[i]) - discrete.begin();
insert(root[i], root[i-1], 0, n, p);
}
int ans = 0;
while(m--){
int a,b,c,d;
cin >> a >> b >> c >> d;
c += ans, d+=ans;
a--;
int ci=lower_bound(discrete.begin(), discrete.end(),
c)-discrete.begin()-1;
int di=upper_bound(discrete.begin(), discrete.end(),
d)-discrete.begin()-1;
ans = query(a,b,di)-query(a,b,ci);
cout << ans << "\n";
}
}
Sparse Table <O(NlogN),
O(1)>
int st[11][505];
void build(int n){
int h = floor(log2(n));
for(int j = 0; j<n; j++) st[0][j] = A[j]; //array
for(int i = 1; i<=h; i++)
for(int j = 0; j+(1<<i)<=n; j++) // 0-indexed
st[i][j] = min(st[i-1][j],
st[i-1][j+(1<<(i-1))]);
}
int rangemin(int l, int r){
// [l, r)
int p = 31-__builtin_clz(r-l);
return min(st[p][l], st[p][r-(1<<p)]);
}
Wavelet Tree : query(range,
kth number) (mkthnum)
#include <bits/stdc++.h>
#define inf INT_MAX
using namespace std;
int A[100050];
struct wavelet{
int s,e;
vector<int> b;
wavelet *l, *r;
wavelet(int *from, int *to, int x, int y){
s = x, e = y;
if(s == e or from>=to) return;
int m = (s+e)/2;
auto f = [m](int x){ return x <= m; };
b.push_back(0);
for(auto i = from; i<to; i++){
b.push_back(b.back() + f(*i));
}
auto split = stable_partition(from, to, f);
l = new wavelet(from, split, x, m);
r = new wavelet(split, to, m+1, y);
}
int query(int x, int y, int k){
if(x > y) return 0;
if(s == e) return s;
int inleft = b[y] - b[x-1];
if(inleft >= k){
// go left
// place in left == no. elements left of me (in
array) that go left + 1
//
== b[x-1] + 1
return
l->query(b[x-1]+1, b[y], k);
}else{
// go right
// place in right == no. elements left of me
(in array) that go right + 1
// == index - 1 - b[i-1] + 1
// == index - b[i-1]
return r->query(x-b[x-1], y-b[y], k-inleft);
}
}
};
int n, q;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
freopen("mkthnum.txt", "r", stdin);
cin >> n >> q;
for(int i = 1; i<=n; i++) cin >> A[i];
vector<int> discrete;
for(int i = 1; i<=n; i++) discrete.push_back(A[i]);
sort(discrete.begin(), discrete.end());
for(int i = 1; i<=n; i++) A[i] =
lower_bound(discrete.begin(), discrete.end(), A[i]) - discrete.begin();
wavelet *root = new wavelet(A+1, A+n+1, 0, n-1);
while(q--){
int a,b,c; cin >> a >> b >> c;
cout << discrete[root->query(a,b,c)] <<
"\n";
}
}
Wavelet Tree : query(LTE,
SLTE) (fastsort)
#include
<bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long ll;
ll A[100050];
ll B[100050];
vector<ll> discrete;
ll n,q;
// self-implemented: slte
(sum less than equal)
// we hence needed to use
extra array B to store the original non-discretize value
struct wavelet{
ll s,e;
vector<ll> b;
vector<ll> ss;
wavelet *l, *r;
wavelet(ll *from, ll *to, ll x, ll y){
s = x, e = y;
ss.push_back(0);
if(s == e or from >= to){ // either single value, or
out of range
for(auto i = from; i<to; ++i)
ss.push_back((ss.back() + B[i-A]));
return;
}
ll m = (s+e)/2;
auto f = [m](ll x){ return x <= m; };
auto f2 = [m](ll x){ return x<=discrete[m]; };
b.push_back(0);
for(auto i = from; i<to; ++i){
b.push_back(b.back() + f(*i));
}
for(auto i = from; i<to; ++i){
ss.push_back((ss.back() + B[i - A]));
}
// printf("A : "); for(auto i = from; i<to;
i++) printf("%d ", *i); printf("\n");
// printf("B : "); for(auto i = from; i<to;
i++) printf("%d ", B[i-A]); printf("\n");
// printf("SS: "); for(ll i = 1; i<ss.size();
i++) printf("%d ", ss[i]); printf("\n");
auto split = stable_partition(from, to, f);
stable_partition(&B[from-A], &B[to-A], f2); //
B is a poller, from is poller, A is poller
l = new wavelet(from, split, x, m);
r = new wavelet(split, to, m+1, y);
}
ll lte(ll l, ll r, ll k){
if(l > r or k < s) return 0;
if(k >= e) return r-l+1;
ll lb = b[l-1];
ll rb = b[r];
return (this->l->lte(lb+1, rb, k) +
this->r->lte(l-lb, r-rb, k));
}
ll slte(ll l, ll r, ll k){
if(l > r or k < s) return 0;
if(k >= e) return (ss[r] - ss[l-1]);
ll lb = b[l-1];
ll rb = b[r];
ll ans = (this->l->slte(lb+1, rb, k) % mod +
this->r->slte(l-lb, r-rb, k) % mod);
return ans % mod;
}
};
ll dp[5005][5005];
ll copyA[100050],
copyB[100050];
ll ss[100005];
ll modify(ll x){
while(x < 0) x+=mod;
return x % mod;
}
int main(){
freopen("fastsort_2.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
if(n > 100000) assert(false);
for(ll i = 1; i<=n; ++i){
cin >> A[i];
ss[i] = ss[i-1] + A[i];
B[i] = A[i];
discrete.push_back(A[i]);
}
sort(discrete.begin(), discrete.end());
for(ll i = 1; i<=n; ++i) A[i] =
lower_bound(discrete.begin(), discrete.end(), A[i]) - discrete.begin();
// for(ll i = 1; i<=n; i++) printf("%d ", A[i]);
printf("\n");
// for(ll i = 1; i<=n; i++) printf("%d ", B[i]);
printf("\n");
for(ll i = 1; i<=n; ++i) copyA[i] = A[i];
for(ll i = 1; i<=n; ++i) copyB[i] = B[i];
wavelet *root = new wavelet(A+1, A+n+1, 0, n-1);
for(ll i = 1; i<=n; ++i){
dp[i][i] = (copyB[i] + mod) % mod;
for(ll j = i+1; j<=n; ++j){
ll add1 = (ss[j-1] - ss[i-1] - root->slte(i,
j-1, copyA[j]) + mod) % mod;
dp[i][j] = dp[i][j-1] + add1 + (((copyB[j] +
mod) % mod) * (root->lte(i, j-1, copyA[j]) + 1));
dp[i][j] += mod;
dp[i][j] %= mod;
}
}
while(q--){
ll a,b;
cin >> a >> b;
cout << (dp[a][b]) << "\n";
}
}
From noiref:
struct SparseTable {
vector<vector<int> > ST;
int N, K;
SparseTable(int _N, int a[]): N(_N) {
K = MSB(N);
ST.resize(K);
ST[0] = vector<int>(a, a+N);
for (int k = 1; k < K; ++k)
for (int i = 0; i+(1<<k)
<= N; ++i)
ST[k].push_back(
min(ST[k-1][i], ST[k-1][i+(1<<(k-1))]) ); //min
}
/* returns most significant bit of an
integer */
inline int MSB(unsigned int x) { return
32-__builtin_clz(x); }
/* Min of range (x, x + 2^k-1) and
(y-2^k+1, y) */
int query(int x, int y) { // [x, y]
int k = MSB(y-x+1) - 1;
return min(ST[k][x],
ST[k][y-(1<<k)+1]); //min
}
};
//usage: SparseTable *x = new
SparseTable(n, A); x -> functionToCall();
2D Sparse Table <O(NM log
M log N), O(1)>
struct SparseTable2D{
vector<vector<vector<vector<int>>>>
ST2;
// n, m, logn, logm
int n, m, logn, logm;
inline int MSB(unsigned int x) { return 32-__builtin_clz(x); }
inline int func(int x, int y){
return max(x,y);
}
SparseTable2D(int nn, int mm, vector<vector<int>>
v){
n = nn;
m = mm;
ST2.resize(n);
logn = MSB(n);
logm = MSB(m);
for(int i = 0; i<n; ++i){
ST2[i].resize(m);
for(int j = 0; j<m; ++j){
ST2[i][j].resize(logn);
ST2[i][j][0].push_back(v[i][j]);
}
}
for(int logj = 1; logj<logm; ++logj){
for(int i = 0; i<n; ++i){
for(int j = 0; j+(1<<logj)<=m;
++j){
ST2[i][j][0].push_back(func(ST2[i][j][0][logj-1],
ST2[i][j+(1<<(logj-1))][0][logj-1]));
}
}
}
for(int logi = 1; logi<logn; ++logi){
for(int logj = 0; logj<logm; ++logj){
for(int i = 0; i+(1<<logi)<=n;
++i){
for(int j = 0; j+(1<<logj)<=m;
++j){
int x =
ST2[i][j][logi-1][logj];
int y =
ST2[i+(1<<(logi-1))][j][logi-1][logj];
ST2[i][j][logi].push_back(func(x,
y));
}
}
}
}
}
int query(int x1, int y1, int x2, int y2){ // [x1,y1] to
[x2,y2] (inclusive)
x2++; y2++;
int xd = x2-x1;
int kxd = MSB(xd) - 1;
int yd = y2-y1;
int kyd = MSB(yd) - 1;
int ans = 0; // change to INT_MAX for min
ans = func(ans, ST2[x1][y1][kxd][kyd]);
ans = func(ans, ST2[x2-(1<<kxd)][y1][kxd][kyd]);
ans = func(ans, ST2[x1][y2-(1<<kyd)][kxd][kyd]);
ans = func(ans,
ST2[x2-(1<<kxd)][y2-(1<<kyd)][kxd][kyd]);
return ans;
}
};
// usage: SparseTable2D *s =
new SparseTable2D(n,m,A);
Minstack
stack<int> s;
stack<int> ss; //stores
the minimum top stuff
void push(int X) {
s.push(X); //add X to normal stack
if(ss.empty() or ss.top()>=X) ss.push(X);
}
void pop() {
if(s.top() == ss.top()) ss.pop();
s.pop();
}
int top() {
return s.top();
}
int getMin() {
return ss.top();
}
PBDS
#include
<bits/stdc++.h>
#include
<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using pbds_set = tree<T,
null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename K,
typename V>
using pbds_map = tree<K,
V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
int main(){
pbds_set<int> s;
s.insert(1);
s.insert(20);
s.insert(7);
s.insert(9);
for(auto i : s) printf("%d ", i);
printf("\n");
cout << *s.find_by_order(2) << endl; // prints 9
cout << s.order_of_key(11) << endl; // prints 3
pbds_map<int, string> m;
m[1] = "Ryan";
m[4] = "Heeeen";
m[3] = "Moon";
for(auto i : m) printf("%d %s\n", i.first,
i.second.c_str()); printf("\n");
pbds_map<int, string>::iterator x;
x = m.find_by_order(1);
cout << (*x).first << " " <<
(*x).second << endl; // prints "3 Moon"
cout << m.order_of_key(2) << endl; // prints 1
}
Math
GCD
int gcd(int x, int y){
if(y == 0) return x;
return gcd(y, x%y);
}
Euclidean, Inverse (binomial)
#include
<bits/stdc++.h>
#define mod 1000000007
typedef long long ll;
using namespace std;
ll gcd(ll a, ll b, ll &x,
ll &y){ // ax + by = gcd
if(a % b == 0){
x = 0, y = 1;
return b;
}
ll x1, y1;
// x1*b + y1*(a%b) = gcd
// a%b = a - a/b * b
// a(y1) + b(x1-a/b*y1) = gcd
ll ans = gcd(b, a%b, x1, y1);
x = y1;
y = x1 - y1*(a/b);
return ans;
}
ll inv(ll a, ll m){
ll x, y;
if(gcd(a, m, x, y) != 1) return -1;
return (x+m)%m;
}
int main(){
ll n,k;
cin >> n >> k;
ll ans = 1;
for(ll i = 0; i<k; i++){
ans *= n-i;
ans %= mod;
ans *= inv(i+1, mod);
ans %= mod;
}
cout << ans;
}
LCM
int lcm (int a, int b) {
return (a/gcd(a, b))*b; //Divide before
multiplying to prevent overflow
}
Quick Exponentiation and
Multiplication
ll qmult(ll a, ll b){
if(b == 0) return 0;
ll half = qmult(a, b/2);
half %= mod;
half += half;
half %= mod;
if(b % 2 == 1) half += a;
half %= mod;
return half;
}
ll qexp(ll b, ll e){
if(e == 0) return 1;
ll half = qexp(b, e/2);
half %= mod;
half = qmult(half, half); // or half*=half;
half %= mod;
if(e % 2 == 0) return half;
else return (half*b) % mod;
}
Fibo_ex
If n is even then
k = n/2:
F(n) = [2*F(k-1) +
F(k)]*F(k)
If n is odd then k
= (n + 1)/2
F(n) = F(k)*F(k) +
F(k-1)*F(k-1)
Matrix Exponentiation
(fibo_ex)
#include
<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod;
int tc;
struct matrix{
ll m[2][2];
matrix(){}
matrix(ll a, ll b, ll c, ll d){
m[0][0] = a;
m[0][1] = b;
m[1][0] = c;
m[1][1] = d;
}
matrix clone(){ return matrix(m[0][0], m[0][1], m[1][0], m[1][1]);
}
matrix operator* (matrix b){
matrix a = (*this).clone(), o;
o.m[0][0] = (a.m[0][0]*b.m[0][0] + a.m[0][1]*b.m[1][0])
% mod;
o.m[1][0] = (a.m[0][1]*b.m[0][0] + a.m[1][1]*b.m[1][0])
% mod;
o.m[0][1] = (a.m[0][0]*b.m[0][1] + a.m[0][1]*b.m[1][1])
% mod;
o.m[1][1] = (a.m[1][0]*b.m[0][1] + a.m[1][1]*b.m[1][1])
% mod;
return o;
}
};
matrix qfib(int n){
if(n == 1) return matrix(1,1,1,0);
matrix half = qfib(n/2);
half = half*half;
if(n%2 == 1) half = half*matrix(1,1,1,0);
return half;
}
int main(){
cin >> tc;
while(tc--){
int a,m;
cin >> a >> m;
mod = m;
cout << qfib(a).m[0][1] << "\n";
}
}
Sieve
#include
<bits/stdc++.h>
#define MAX 30000000
using namespace std;
bitset<MAX+50> isPrime;
vector<int> primes;
int n;
int main(){
scanf("%d", &n);
isPrime.reset(); isPrime.flip();
isPrime[0] = isPrime[1] = false;
for(int i = 4; i<=MAX; i+=2){
isPrime[i] = false;
}
primes.push_back(2);
for(int i = 3; i<=MAX; i+=2){
if(isPrime[i]) primes.push_back(i);
else continue;
for(int j = 2; j<=MAX/i; j++){
isPrime[j*i] = false;
}
}
// primes is a vector of primes
// isPrime is a Boolean array
}
Prime Factorization
int m;
vector<int> primes;
map<int, int>
primeFactors;
bool isPrime[MAX];
void primeFactorise(ull n){
for(auto i:primes){
if(n == 1) return;
primeFactors[i] = 0;
while(n%i == 0){
n/=i;
primeFactors[i]++;
}
}
primeFactors[n]++;
}
From Noiref (untested):
vector<int> primeList;
vector<int>
primeFactorize(int X) {
vector<int> result;
for (vector<int>::iterator it =
primeList.begin(); it != primeList.end(); ++it) {
if (*it > X/(*it)) break; //Check if
prime exceeds sqrt(X)
while (X % *it == 0) { //When it is
divisible, divide as many times as possible
X /= *it;
result.push_back(*it);
}
}
if (X != 1) result.push_back(X); //The last
factor above sqrt(X)
return result;
}
Common Prime Factors (Noiref,
untested)
int gcd (int a, int b) {
vector<int> factorized_a =
primeFactorize(a);
vector<int> factorized_b =
primeFactorize(b);
int i = 0, j = 0, result = 1;
while (i < factorized_a.size()
&& j < factorized_b.size()) {
if (factorized_a[i] <
factorized_b[j]) ++i;
else if (factorized_a[i] >
factorized_b[j]) ++j;
else {
result *= factorized_a[i];
++i, ++j;
}
}
return result;
}
int to string
string intToString(int x){
string ans = "";
while(x){
ans += (char) ((x%base) + '0');
x /= base;
}
reverse(ans.begin(), ans.end());
return ans;
}
string to int (problem: base)
#include
<bits/stdc++.h>
using namespace std;
char n[100];
unsigned long long nn;
int a,b;
char ans[100];
int main() {
scanf("%s", &n);
scanf("%d %d", &a, &b);
for(int i = 0; i<strlen(n); ++i){
nn*=a;
if(n[i] >= 'A' &&
n[i]<='Z') nn+=n[i]-'A'+10;
else nn+=n[i]-'0';
}
int i = 0;
while(nn>0){
if(nn%b < 10) ans[i] = nn%b+'0';
else ans[i] = nn%b-10+'A';
nn/=b;
i++;
}
reverse(ans, ans+strlen(ans));
printf("%s", ans);
}
Big integers (stored with
strings) (problem: Looongnumbers)
#include
<bits/stdc++.h>
using namespace std;
string a,b;
int main(){
cin >> a >> b;
int carry = 0;
if(a.length() < b.length()){
int leadingzeros = b.length()-a.length();
string addon;
while(leadingzeros--){
addon += "0";
}
a = addon+a;
}
if(b.length() < a.length()){
int leadingzeros = a.length()-b.length();
string addon;
while(leadingzeros--){
addon += "0";
}
b = addon + b;
}
// cout << a << endl << b;
string ans;
for(int i = a.length()-1; i>=0; i--){
int add = a[i]+b[i]-'0'-'0';
add += carry; carry = 0;
if(add >= 10){
carry = 1; add-=10;
}
ans = (char) (add+'0') + ans;
}
if(carry != 0) ans = "1" + ans;
cout << ans;
}
isPrime
bool isPrime(long long int N)
{
if(N==2 || N==3) return true;
if(N%2 == 0||N%3==0) return false;
for(int i = 5; i<=N/i; i+=6){
if(N%i==0 || N%(i+2)==0) return false;
}
return true;
}
From noiref:
bool isPrime(int x) {
if (x < 2) return false; //All primes
are above 2
else if (x == 2) return true; //If its 2,
its a prime
else if (x % 2 == 0) return false; //If its
even (other than 2), its not a prime -> used for speedup
for (int i = 3; i <= x/i; i+=2) {
//Trial divide all odd numbers > 2 up till the square root of x
if (x % i == 0) return false; //If a
factor is found, x is not prime
}
return true; //If no factors are found, x
is a prime
}
Bruteforce O(n!)
sort(nodes.begin(),
nodes.end()); // important!!
do{
}while(next_permutation(nodes.begin(),
nodes.end()));
Bruteforce O(2^N)
for(int i = 1;
i<(1<<n); i++){
for(int j = 0; j<n; j++){
if((1<<j) & i){
printf("1");
}else{
printf("0");
}
}
printf("\n");
}
Basic Mod properties
(A+B) % M = ((A % M) + (B %
M)) % M
(A-B) % M = ((A % M) - (B %
M) + M) % M
(A*B) % M = ((A % M) * (B %
M)) % M
Misc.
Printing tables
void printtable(int k){
// print i, sa[i], suffix, ra[sa[i]], ra[sa[i]+k]
cout.width(6); cout<<left<<"";
cout.width(6); cout<<left<<"i";
cout.width(6); cout<<left<<"sa[i]";
cout.width(20); cout<<left<<"suffix[i]";
cout.width(10); cout<<left<<"ra[sa[i]]";
cout.width(10); cout<<left<<"ra[sa[i]+k]";
cout << endl;
for(int i = 0; i<n; i++){
cout.width(6); cout<<"";
cout.width(6); cout<<left<<i;
cout.width(6); cout<<left<<sa[i];
cout.width(20); cout<<left<<suffix[i];
cout.width(10); cout<<left<<ra[sa[i]];
cout.width(10); cout<<left<<ra[sa[i]+k];
cout << endl;
}
}
(Mo’s)
Sliding Thing
if(cl < l){
while(cl < l) remove(cl++);
}else{
while(cl > l) add(--cl);
}
if(cr < r){
while(cr < r) add(++cr);
}else{
while(cr > r) remove(cr--);
}
Median of Median DNC
(untested from geeksforgeeks)
// C++ implementation of
worst case linear time algorithm
// to find k'th smallest
element
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
int partition(int arr[], int
l, int r, int k);
// A simple function to find
median of arr[]. This is called
// only for an array of size
5 in this program.
int findMedian(int arr[], int
n)
{
sort(arr, arr+n); // Sort the array
return arr[n/2]; // Return middle element
}
// Returns k'th smallest
element in arr[l..r] in worst case
// linear time. ASSUMPTION:
ALL ELEMENTS IN ARR[] ARE DISTINCT
int kthSmallest(int arr[],
int l, int r, int k)
{
// If k is smaller than number of elements
in array
if (k > 0 && k <= r - l + 1)
{
int n = r-l+1; // Number of elements in
arr[l..r]
// Divide arr[] in groups of size 5,
calculate median
// of every group and store it in
median[] array.
int i, median[(n+4)/5]; // There will
be floor((n+4)/5) groups;
for (i=0; i<n/5; i++)
median[i] = findMedian(arr+l+i*5,
5);
if (i*5 < n) //For last group with
less than 5 elements
{
median[i] = findMedian(arr+l+i*5,
n%5);
i++;
}
// Find median of all medians using
recursive call.
// If median[] has only one element,
then no need
// of recursive call
int medOfMed = (i == 1)? median[i-1]:
kthSmallest(median, 0, i-1, i/2);
// Partition the array around a random
element and
// get position of pivot element in
sorted array
int pos = partition(arr, l, r,
medOfMed);
// If position is same as k
if (pos-l == k-1)
return arr[pos];
if (pos-l > k-1) // If position is more, recur for left
return kthSmallest(arr, l, pos-1,
k);
// Else recur for right subarray
return kthSmallest(arr, pos+1, r,
k-pos+l-1);
}
// If k is more than number of elements in
array
return INT_MAX;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// It searches for x in
arr[l..r], and partitions the array
// around x.
int partition(int arr[], int
l, int r, int x)
{
// Search for x in arr[l..r] and move it to
end
int i;
for (i=l; i<r; i++)
if (arr[i] == x)
break;
swap(&arr[i], &arr[r]);
// Standard partition algorithm
i = l;
for (int j = l; j <= r - 1; j++)
{
if (arr[j] <= x)
{
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[r]);
return i;
}
// Driver program to test
above methods
int main()
{
int arr[] = {12, 3, 5, 7, 4, 19, 26};
int n = sizeof(arr)/sizeof(arr[0]), k = 3;
cout << "K'th smallest element
is "
<< kthSmallest(arr, 0, n-1, k);
return 0;
}
Ternary Search O(log N)
(untested)
while (abs(hi - lo) >
1e-9) {
long double left = lo + (hi - lo) / 3;
long double right = hi - (hi - lo) / 3;
if (f(left) < f(right)) lo = left;
else hi = right;
}
Discrete (tested):
ll s=-1, e=1000000001;
while(e-s>2){
ll high = e-(e-s)/3;
ll low = s+(e-s)/3;
if(compute(low) > compute(high)) s=low; // swap signs for
frowning curve
else e=high;
}
cout << (s+e)/2
<< ' '; // average!
Discretization
sort(discrete.begin(),
discrete.end());
discrete.resize(unique(discrete.begin(),
discrete.end())-discrete.begin());
~/.vimrc
set is
set nu
set autoindent
syntax on
colorscheme desert
set background=dark
highlight Normal ctermfg=grey
ctermbg=black
set novb
Minimalistic
set nu
set autoindent
syntax on
colorscheme desert
highlight Normal ctermfg=grey
set novb
Useful vim
Copy into Clipboard: ҫy
View reg: :reg
Paste from reg 7: ҷp
Substitute: :8,10
s/search/replace/g
Substitute word:
:%s/\<word\>/replace/g
Split: vsplit, vertical
resize +5, vertical resize 60
Autoindent: gg=G
Folding:
:set foldmethod=manual
visual highlight the lines,
:fold
Recording:
vim *.cpp
qx # start recording to register x
:%s/OldString/NewString/g
:wnext
q # stop recording
@x # playback to see if it works
correctly
999@x # repeat 999 times to complete the job
Using gcc to compile
gcc гtd=c++11 poop.cpp;
./a.out;
Using gdb to debug
gcc Ч Я programName programName.cpp
sudo gdb programName
commands: start, control-x-a
(tui), control-l (tui refresh), break
printf float
printf("%0.10lf\n",a/b);
Grader
#include
<bits/stdc++.h>
using namespace std;
vector<string> v;
vector<string> v2;
int main(){
string s;
ifstream input; input.open("output.txt");
ifstream input2; input2.open("answer.txt"); //
expected answer
while(getline(input, s)) if(s != "") v.push_back(s);
while(getline(input2, s)) if(s != "")
v2.push_back(s);
if(v.size() != v2.size()){
cout << "Error: Different sizes"
<< endl;
return 0;
}
for(int i = 0; i<v.size(); i++){
if(v[i] != v2[i]){
cout << "Error: mismatch on line
" << i << endl;
cout << "Expected " <<
v2[i] << " got " << v[i] << endl;
return 0;
}
}
cout << "All Correct";
}