数据结构
下标池 IdPool template<typename T> struct IdPool { map<T, int> idmap; vector<T> items; void clear() { idmap.clear(); items.clear(); } int getid(const T &t) { auto it = idmap.find(t); if (it != idmap.end()) return it->second; int ans = items.size(); items.push_back(t); idmap[t] = ans; return ans; } T& operator[](int i) { return items[i]; } int size() { return items.size(); } }; IdPool<int> idp;
…
离散化 Discretization template<typename T, int IdFrom=0, typename OpLs=less<T>, typename OpEq=equal_to<T>> struct Dctz { static OpLs ls; static OpEq eq; vector<T> x; void clear() { x.clear(); } void add(T v) { x.push_back(v); } void init() { sort(x.begin(),x.end(),ls); x.erase(unique(x.begin(),x.end(),eq),x.end()); } int size() { return x.size(); } int id(const T &v) { return lower_bound(x.begin(),x.end(),v,ls)-x.begin()+IdFrom; } T& operator[](int id) { return x[id-IdFrom]; }; }; Dctz<> dc;
…
树状数组 Binary Index Tree/Fenwick Tree 1d 单点修改，区间询问 // T must + - // id 1~n template<typename T,size_t M,typename OpPlus=plus<T>,typename OpMinus=minus<T>> struct BIT { static int lowbit(int x) { return x&(-x); } constexpr static OpPlus opp{}; constexpr static OpMinus opm{}; static T tmp[M+1]; T tree[M+1]; // tree[i] -> sum of [i-lowbit(i)+1,i] int n; void init(int n_) { n=n_; for(int i=1;i<=n;i++) tree[i]=T(0); } void init(int n_,T v[]) // v[0 ~ n_-1] { n=n_; tmp[0]=T(0); for(int i=1;i<=n;i++) tmp[i]=opp(tmp[i-1],v[i]); for(int i=1;i<=n;i++) tree[i]=opm(tmp[i],tmp[i-lowbit(i)]); // for(int i=0;i<n;i++) add(i,v[i]); } void add(int p,T V) { for(;p<=n;p+=lowbit(p))
…
左偏树 Leftist Tree // min leftist tree // T must define < // M: the size of the heap template<typename T,size_t M,typename Cmp=less<T>> struct Leftist { static Cmp cmp; T val[M]; int l[M],r[M],d[M]; int nn; // number of node void init() { nn=0; } // using val to build a leftist tree // return the id of the root int build(int n,T val_[]) { queue<int> qu; for(int i=1;i<=n;i++) qu.push(i); int u,v; while(qu.size()>1) { u=qu.front(); qu.pop(); v=qu.front(); qu.pop(); merge(u,v); qu.push(u); } return qu.front(); } int newtree(T v) { val[++nn]=v; r[nn]=l[nn]=d[nn]=0; return nn; } void merge(int &x,int y) // merge
…
并查集 Union Find / Disjoint Set Union 路径压缩和按 size 合并 Union by Size // M: max number of set // id is in [0~M-1] template<size_t M> struct UF { int uf[M],sz[M]; int n; int ns; // number of set void init(int n_) { n=ns=n_; for(int i=0;i<n;i++) uf[i]=i,sz[i]=1; } int find(int x) { return x==uf[x]?x:uf[x]=find(uf[x]); } bool same(int x,int y) { return find(x)==find(y); } bool merge(int x,int y) { x=find(x); y=find(y); if(x==y) return false; if(sz[x]>sz[y]) swap(x,y); sz[y]+=sz[x]; uf[x]=y; ns--; return true; } }; Debug: void show() { cerr<<"UnionFind:----------------------\n"; cerr<<"id:"; for(int i=0;i<n;i++) cerr<<'\t'<<i; cerr<<'\n';
…
二叉堆 Binary Heap 模板：普通二叉堆 Heap // T must define < // min heap // M: max size of heap template<typename T,size_t M,typename Cmp=less<T>> struct Heap { static Cmp cmp; T h[M+1]; int n; void init() { n=0; } void init(T h_[],int n_) // h[0~n-1] { n=n_; for(int i=1;i<=n;i++) h[i]=h_[i-1]; for(int i=n/2;i;i--) sink(i); // O(n) } void push(T x) { h[++n]=x; swim(n); } T pop() { T res=h[1]; h[1]=h[n--]; sink(1); return res; } T top() { return h[1]; } // check n>=1 int size() { return n; } bool empty() { return
…