题目链接

题面：

题意：
给定点 a ( x , y , z ) , 问符合要求的点 b（ xx , yy , zz）的dp最大值，设这个dp最大值为dp [ x ]，那么当前点 a的dp [ a ] = dp [ x ] + 1。
若没有符合要求的点，那么 dp [ a ] = 0。

其中点b符合要求是指 xx<=x && yy<=y && zz<=z 且 （xx < x , yy < y , zz<z）之中至少有一个成立。
这里的点由于是随机生成且随机数较大 点的数量比较少，我们可以认为没有重复的点，那么可以认为 xx<=x && yy<=y && zz<=z 即可。
实际上，若有重复的点，那么对于重复的点，符合要求的点的答案一定是一样的，对于某个重复k次的点，我们只查询一次作为这k的点的答案，插入时插入k次。

题解：写的时候是用线段树+平衡树写的。
sort 一维 x
线段树一维 y
平衡树 一维同时维护dp [ x ] 的最大值
时间复杂度 O（n logn logn）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#define ll long long
#define llu unsigned ll
#define pr make_pair
#define pb push_back
#define llc (cnt<<1)
#define rrc (cnt<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int maxn=100100;


unsigned long long k1, k2;
int n;
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;
}

//平衡树
struct nn
{
    int val;
    int lc,rc;
    int si,cm,mm;
}t[maxn*22];
int tot,root;

struct node
{
    llu x,y,z;
    int id;
}a[maxn];

void pushup(int p)
{
    t[p].si=t[t[p].lc].si+t[t[p].rc].si+1;
    t[p].mm=max(t[p].cm,max(t[t[p].lc].mm,t[t[p].rc].mm));
}

int dp[maxn],maxx=0;
int ans[maxn];

int newnode(int x)
{
    int p=++tot;
    t[p].lc=t[p].rc=0;
    t[p].si=1;
    t[p].val=x;
    t[p].cm=t[p].mm=dp[x];
    return p;
}

void R(int &p)
{
    int q=t[p].lc;
    t[p].lc=t[q].rc;
    t[q].rc=p;
    p=q;
    pushup(t[p].rc);
    pushup(p);

}

void L(int &p)
{
    int q=t[p].rc;
    t[p].rc=t[q].lc;
    t[q].lc=p;
    p=q;
    pushup(t[p].lc);
    pushup(p);
}

void RL(int &p)
{
    R(t[p].rc);
    L(p);
}

void LR(int &p)
{
    L(t[p].lc);
    R(p);
}

void maintain(int &p,bool flag)
{
    if(!flag)
    {
        if(t[t[t[p].lc].lc].si>t[t[p].rc].si)
            R(p);
        else if(t[t[t[p].lc].rc].si>t[t[p].rc].si)
            LR(p);
        else return ;
    }
    else
    {
        if(t[t[t[p].rc].rc].si>t[t[p].lc].si)
            L(p);
        else if(t[t[t[p].rc].lc].si>t[t[p].lc].si)
            RL(p);
        else return ;
    }
    maintain(t[p].lc,false);
    maintain(t[p].rc,true);
    maintain(p,true);
    maintain(p,false);
}

void _insert(int &now,int val)
{
    if(!now)
    {
        now=newnode(val);
        return ;
    }
    if(a[val].z<a[t[now].val].z)
    {
        _insert(t[now].lc,val);
        maintain(now,false);
    }
    else
    {
        _insert(t[now].rc,val);
        maintain(now,true);
    }
    pushup(now);
}


int get_front(int x,int root)
{
    int now=root,ans=-1;
    while(now)
    {
        if(a[t[now].val].z<=a[x].z) ans=max(ans,max(t[now].cm,t[t[now].lc].mm)),now=t[now].rc;
        else
            now=t[now].lc;

    }
    return ans;
}

//线段树
struct tree
{
    int l,r;
    int rt;
}tt[maxn<<2];
llu b[maxn];


bool cmp(const node &a,const node &b)
{
    if(a.x!=b.x) return a.x<b.x;
    else if(a.y!=b.y) return a.y<b.y;
    else return a.z<b.z;
}

void build(int l,int r,int cnt)
{
    tt[cnt].l=l,tt[cnt].r=r;
    tt[cnt].rt=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(l,mid,llc);
    build(mid+1,r,rrc);
}

void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        a[i].x = CoronavirusBeats();
        a[i].y = CoronavirusBeats();
        a[i].z = CoronavirusBeats();
        a[i].id=i;
        b[i]=a[i].y;
    }

    sort(b+1,b+n+1);
    int cp=unique(b+1,b+n+1)-(b+1);
    for(int i=1;i<=n;i++)
    {
     a[i].y=(llu)(lower_bound(b+1,b+cp+1,a[i].y)-b);
    }
    build(1,cp,1);
}
void change(int pos,int cnt)
{
    _insert(tt[cnt].rt,pos);
    if(tt[cnt].l==tt[cnt].r) return ;
    if(a[pos].y<=tt[llc].r) change(pos,llc);
    else change(pos,rrc);
}
void ask(int l,int r,int cnt,int id)
{
    if(l>r) return ;
    if(tt[cnt].rt==0) return ;
    if(l<=tt[cnt].l&&tt[cnt].r<=r)
    {
        dp[id]=max(dp[id],get_front(id,tt[cnt].rt)+1);
        return ;
    }
    if(l<=tt[llc].r) ask(l,r,llc,id);
    if(r>=tt[rrc].l) ask(l,r,rrc,id);
}

int main(void)
{
    scanf("%d%llu%llu",&n,&k1,&k2);
    init(n);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        ask(1,a[i].y,1,i);
        change(i,1);
    }
    for(int i=1;i<=n;i++)
        ans[a[i].id]=dp[i],maxx=max(maxx,dp[i]);
    printf("%d\n",maxx+1);
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}

这个三维偏序好像不能用CDQ分治，因为假设当前处理完了区间 [ l , mid ] , [ mid+1 , r ]
我们现在要合并区间 [ l , mid ] , [ mid+1 , r ]。
现在有一点 x ∈ [ mid+1 , r ] ，区间 [ l , mid ] 对 x 点的总贡献并不好求，单单是区间[ l , mid ] 对x 点的贡献是比较好好求的，一般的三维偏序处理即可。但是 [ l , mid ] 可能会对 xx 点有贡献，进而影响 x 的值。