Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog cdq 三维偏序 #include<bits/stdc++.h> using namespace std; const int maxn= 2e5+5; struct node{int x,y,z,w,ct;}a[maxn],b[maxn]; int ans[maxn],BIT[maxn],B; bool cmp(node a,node b){ if(a.x!=b.x)return a.x<b.x; if(a.y!=b.y)return a.y<b.y; return a.z<b.z; } bool equal(node a,node b){ return a.x==b.x&&a.y==b.y&&a.z= ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog kdTree        kd树是平衡树的多维拓展，说白了就是多维平衡树，它 和普通的的区别就在于，它是按照深度决定以哪个维度 作为建树划分标准的。（优化算法另当别论）          算法在注释里面已经很清楚了。 #define pow2(x) ((x)*(x)) struct kd ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog link cut tree link cut tree是什么         link cut tree是一种维护动态森林的数据结构,但我们常常用它来维护 一颗动态的树，维护这些动态树上路径的信息。         在本质上他属于一种树剖分，将树剖成链，但是由于树是动态的，所以无法使用轻重剖分 ，因为重儿子可能会变化为轻儿子，轻儿子也可能变成重儿子，这里采取虚实剖分，按照虚链实链剖成链。 树的虚实剖分  &n ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog map struct mymap { static const int N=(1<<22); int key[N], val[N]; int query(int x) { int i = x & (N - 1); while (key[i] != -1 && key[i] != x) i = (i + 1) & (N - 1); return val[i]; } void update(int x, int id) {// can't find then return -1 int i = x & (N - 1); while (key[i] != ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog rmq倍增 struct RMQ{ static const int maxn=1000,lgmaxn=12; static int lg[maxn]; int mx[maxn][lgmaxn]; RMQ(){//构造函数 if(lg[2]!=1){ for(int i=2;i<maxn;i++){ //因为lg(1)=0 lg[i]=(i&-i)==i?lg[i-1]+1:lg[i-1]; } } } void build(int n,int *a){ for(int i=0;i<=n;i++)mx[i][0] ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog splay struct splay_tree{ static const int maxn=2e6+10; int ch[maxn][2],fa[maxn]; int miv[maxn],val[maxn],add[maxn],rev[maxn],siz[maxn]; int rub[maxn],rub_;//回收池 int rt,tot; //数据结束 void pushup(int h){//维持，回溯 int l=ch[h][0],r=ch[h][1]; miv[h]=va ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog 主席树 ------ 2019.4.30 什么是主席树         主席树是可持久化权值线段树,支持点修改,区间查询。 静态数组区间第k大         先来个题，给一个数组，多组询问，每次询问区间第k大(小), 为数组的每一个前缀建立一颗线段树         但是这样子，空间会爆炸，时间也一样爆炸，但是我们发现前缀 之间是有联系的，两个相邻的前缀之间只有 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog 划分树 hahahahahaha

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog 线段树 typedef long long ll; #define ls (rt<<1) #define rs (ls|1) #define ml ((l+r)>>1) #define mr (ml+1) const ll maxn=1e5+55; ll mod=123456789; ll mul[maxn<<2],add[maxn<<2],sum[maxn<<2],a[maxn]; void push_down(ll rt,ll l,ll r){ // if(l!=r) push_down(ls,l,ml),push_down(rs,mr,r); if(mul[rt]!=1){ mul[ls]=mul[ls]*mu ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog 线段树 //hdu 4578 #define ls (rt<<1) #define rs (ls|1) #define ml ((l+r)>>1) #define mr (ml+1) const int maxn=1e5+55; int mod=10007; int mul[maxn<<2],add[maxn<<2],cov[maxn<<2],sum[3][maxn<<2],a[maxn]; inline int modmul(int a,int b){return a*b%mod;} inline int modmul(int a,int b,int c){return modmul(modmul(a,b), ...