三维偏序：对于每个点P(x,y,z), 统计所有P‘(x‘<=x,y‘<=y,z‘<=z)的某些信息
动态开点树套树确实比较强大，既能做三维偏序的求最值，又能做三维偏序求和
求最值 题目链接 https://acm.ecnu.edu.cn/contest/273/problem/C/
#include <bits/stdc++.h> using namespace std; #define ll unsigned long long const int N = 2e7 + 5e6; struct Pt { ll a, b, c, ans; int id; bool operator<(const Pt &x) const { if(a!=x.a)return a < x.a; if(b!=x.b)return b<x.b; return c<x.c; } } p[N]; ll v[N],cnt; int aa[N], ab[N], ac[N]; int ida, idb, idc; int n; int ans[N]; namespace segc { int val[N], ch[N][2], root[N], ind; void pushup(int p) { val[p] = max(val[ch[p][0]] , val[ch[p][1]]); } void modify(int p, int l, int r, int pos,int v) { if (l == r) { val[p]=v; } else { if (pos <= (l + r) / 2) { if (!ch[p][0]){ ch[p][0] = ++ind; val[ind]=-0x3f3f3f3f; } modify(ch[p][0], l, (l + r) / 2, pos, v); } else { if (!ch[p][1]){ ch[p][1] = ++ind; val[ind]=-0x3f3f3f3f; } modify(ch[p][1], (l + r) / 2 + 1, r, pos, v); } pushup(p); } } void modify(int ver, int pos,int v) { if (!root[ver]) root[ver] = ++ind; modify(root[ver], 1, cnt, pos, v); } int query(int p, int l, int r, int ql, int qr) { if (l > qr || r < ql || p == 0) return -0x3f3f3f3f; if (l >= ql && r <= qr) return val[p]; return max(query(ch[p][0], l, (l + r) / 2, ql, qr) , query(ch[p][1], (l + r) / 2 + 1, r, ql, qr)); } int query(int ver, int ql, int qr) { return query(root[ver], 1, cnt, ql, qr); } } namespace segb { void modify(int p, int l, int r, int pos, int posi, int v) { segc::modify(p, posi, v); if (l != r) { if (pos <= (l + r) / 2) segb::modify(p * 2, l, (l + r) / 2, pos, posi, v); else segb::modify(p * 2 + 1, (l + r) / 2 + 1, r, pos, posi, v); } } void modify(int pos, int posi,int v) { modify(1, 1, cnt, pos, posi, v); } int query(int p, int l, int r, int ql, int qr, int iql, int iqr) { if (l > qr || r < ql)return -0x3f3f3f3f; if (l >= ql && r <= qr)return segc::query(p, iql, iqr); return max(query(p * 2, l, (l + r) / 2, ql, qr, iql, iqr), query(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr, iql, iqr)); } int query(int ql, int qr, int iql, int iqr) { return query(1, 1, cnt, ql, qr, iql, iqr); } } int k; ll k1,k2; unsigned long long CoronavirusBeats() { unsigned long long k3 = k1, k4 = k2; k1 = k4; k3 ^= k3 << 23; k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26); return k2 + k4; } signed main() { scanf("%d", &n);cin>>k1>>k2; for(int i=1;i<=n;i++){ p[i].a=CoronavirusBeats(); p[i].b=CoronavirusBeats(); p[i].c=CoronavirusBeats(); v[++cnt]=p[i].a; v[++cnt]=p[i].b; v[++cnt]=p[i].c; p[i].id=i; } sort(v+1,v+1+cnt); cnt=unique(v+1,v+1+cnt)-v+1; for(int i=1;i<=n;i++){ p[i].a=lower_bound(v+1,v+1+cnt,p[i].a)-v; p[i].b=lower_bound(v+1,v+1+cnt,p[i].b)-v; p[i].c=lower_bound(v+1,v+1+cnt,p[i].c)-v; } sort(p + 1, p + n + 1); int mx=0; for(int i=1;i<=n;i++){ int res=segb::query(1,p[i].b,1,p[i].c); if(res>=0)res++; else res=0; p[i].ans=res; mx=max(mx,res+1); segb::modify(p[i].b,p[i].c,p[i].ans); } cout<<mx<<‘\n‘; for(int i=1;i<=n;i++)ans[p[i].id]=p[i].ans; for (int i = 1; i <= n; i++) printf("%d\n", ans[i]); }
求和 题目：bzoj陌上花开(老经典题了)
/*常规操作是每个结点动态开一个线段树，线段树的域维护的是集合的的域，即这个结点对应的集合信息存在该线段树里， 当合并两个结点时，只要合并两棵线段树即可*/ struct Node { ll ls,rs,ans,sum; }T[N<<6]; void update(ll &now,int l,int r,int pos){ if(!now)now=++tot; if(l==r){ T[now].ans=l; T[now].sum++; return; } int mid=l+r>>1; if(pos<=mid)update(T[now].ls,l,mid,pos); else update(T[now].rs,mid+1,r,pos); pushup(now); } int merge(int x,int y,int l,int r){ if(!x||!y)return x|y; int z=++tot; if(l==r){ T[z].sum=T[x].sum+T[y].sum; T[z].ans=l; return z; } int mid=l+r>>1; T[z].ls=merge(T[x].ls,T[y].ls,l,mid); T[z].rs=merge(T[x].rs,T[y].rs,mid+1,r); pushup(z); return z; } int dfs(int u,int pre){ update(rt[u],1,100000,c[u]); for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==pre)continue; dfs(v,u); rt[u]=merge(rt[u],rt[v],1,100000); } ans[u]=T[rt[u]].ans; }
cdq分治+线段树做三维偏序，由于cdq分治本身的特性，只能将左区间的贡献统计到右区间中，所以不能用来求最值，只能求和
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<cmath> using namespace std; typedef long long ll; const int maxn = 200010; int n,k,cnt,ans=0; struct Node{ int a,b,c,v,id; }a[maxn],b[maxn],lc[maxn],rc[maxn]; int s[maxn],f[maxn],d[maxn]; void add(int x,int v){ for(int i=x;i<=k;i+=i&(-i)) s[i]+=v; } int sum(int x){ int res=0; for(int i=x;i>0;i-=i&(-i)) res+=s[i]; return res; } void clear(int x){ for(int i=x;i<=k;i+=i&(-i)) s[i]=0; } bool cmpx(Node a,Node b){ return a.a!=b.a?a.a<b.a:a.b!=b.b?a.b<b.b:a.c<b.c; } bool cmpy(Node a,Node b){ return a.b!=b.b?a.b<b.b:a.c<b.c; } void cdq(int l,int r){ if(l==r) return; int mid=(l+r)/2; cdq(l,mid),cdq(mid+1,r); for(int i=l;i<=mid;i++) lc[i]=b[i]; for(int i=mid+1;i<=r;i++) rc[i]=b[i]; sort(lc+l,lc+1+mid,cmpy); sort(rc+mid+1,rc+r+1,cmpy); int p=l,q=mid+1; while(p<=mid&&q<=r){ if(lc[p].b<=rc[q].b){ add(lc[p].c,lc[p].v); ++p; } else{ f[rc[q].id]+=sum(rc[q].c); ++q; } } while(q<=r){ f[rc[q].id]+=sum(rc[q].c); ++q; } for(int i=l;i<=mid;i++){ clear(lc[i].c); } } ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<‘0‘ || ch>‘9‘){ if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘ && ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); } return s*f;} int main(){ n=read(),k=read(); for(int i=1;i<=n;i++){ a[i].a=read(),a[i].b=read(),a[i].c=read(),a[i].id=i; } sort(a+1,a+1+n,cmpx); for(int i=1;i<=n;i++){ if(a[i].a==a[i-1].a&&a[i].b==a[i-1].b&&a[i].c==a[i-1].c){ ++b[cnt].v; }else{ b[++cnt].a=a[i].a,b[cnt].b=a[i].b,b[cnt].c=a[i].c,b[cnt].id=a[i].id; b[cnt].v=1; } } cdq(1,cnt); for(int i=1;i<=cnt;i++){ d[f[b[i].id]+b[i].v-1]+=b[i].v; } for(int i=0;i<=n-1;i++){ printf("%d\n",d[i]); } return 0; }
原文：https://www.cnblogs.com/zsben991126/p/12943930.html
