这里是一些简单的算法模板，没有编译过.（编译过的话会做特殊说明）
目录：
1.最近公共祖先
2.CDQ分治
1.最近公共祖先
namespace LCA{
#define LOG 21
int cnt;
int f[22][maxn],dep[maxn];
int head[maxn],to[maxn],nex[maxn];
void addedge(int u,int v){
nex[++cnt] = head[u],head[u]=cnt,to[cnt] = v;
}
void dfs(int u,int fa){
dep[u] = dep[fa] + 1;
f[0][u]=fa;
for(int i=1;i<LOG;++i) f[i][u]=f[i-1][f[i-1][u]];
for(int i=head[u];i;i=nex[i])
if(to[i]!=fa)dfs(to[i],u);
}
int query(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
if(dep[x]!=dep[y]){
for(int i=LOG-1;i>=0;--i)
if(dep[f[i][y]]<=dep[x]) y=f[i][y];
}
if(x==y) return x;
for(int i=LOG-1;i>=0;--i)
if(f[i][x]!=f[i][y])
x=f[i][x],y=f[i][y];
return f[0][x];
}
};
2.CDQ分治（二维 LIS）
//CDQ分治 --- 3维LIS
namespace CDQ{
#define maxn 500060
#define ll long long
#define nex (oo = (oo * A) % mod)
#define setIO(s) freopen(s".in","r",stdin)
int n,cnt,fin,ans[maxn];
long long mod,oo = 1,A,H[maxn];
void getmax(int &a,int b){ if(b > a) a = b; }
struct Node{
long long x,y,z;
int id;
}node[maxn],arr[maxn];
int cmpx(Node a,Node b){
if(a.x == b.x && a.y == b.y) return a.z < b.z;
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
int cmpy(Node a,Node b){
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
int equal(Node a,Node b) {
return (a.x == b.x && a.y == b.y && a.z == b.z);
}
struct BIT{
int C[maxn];
int lowbit(int x){
return x & (-x);
}
void update(int p,int x){
while(p < maxn){
C[p] = max(C[p],x);
p += lowbit(p);
}
}
int query(int p){
if(p <= 0) return 0;
int ss = 0;
while(p > 0) {
ss = max(ss,C[p]), p -= lowbit(p);
}
return ss;
}
void del(int p){
while(p < maxn) C[p] = 0,p += lowbit(p);
}
}tree;
void solve(int l,int r){
if(l >= r) return ;
int mid = (l + r) >> 1,tl = l,tr = mid + 1;
solve(l,mid);
sort(arr+l,arr+mid+1,cmpy),sort(arr+mid+1,arr+r+1,cmpy);
while(tl <= mid && tr <= r){
if(arr[tl].y < arr[tr].y){
tree.update(arr[tl].z,ans[arr[tl].id]);
++tl;
}
else {
getmax(ans[arr[tr].id],tree.query(arr[tr].z - 1) + 1);
++tr;
}
}
for(int i = tr;i <= r; ++i) getmax(ans[arr[i].id],tree.query(arr[i].z-1) + 1);
for(int i = l;i <= mid; ++i) tree.del(arr[i].z);
sort(arr+mid+1,arr+1+r,cmpx),solve(mid+1,r);
};
};