题解：P1110 [ZJOI2007] 报表统计

nnn233 · 2024-10-12 07:55:10 · 题解

题解：P1110 [ZJOI2007] 报表统计

看到题解区没有我这种做法，于是来写一发题解。

开两棵 FHQ Treap，一棵使用排名分裂，用来维护操作二查询相邻最小差，我们将其称为 排名树；另一棵使用权值分裂，维护操作三全局最小差，我们将其称为权值树。

备注

本人编码习惯，有看不懂的代码应该是这里来的。

#define lc t[u].ls
#define rc t[u].rs

操作三

先讲操作三是因为这个是最好处理的，使用权值树，每次插入一个数的时候就查询这个数的前驱和后继，然后尝试更新答案，查询时直接输出当前答案即可。

操作一

我们主要来讲排名树如何插入，其他题解几乎没有使用排名分裂的，原因大概是排名树不能查找指定编号在中序遍历中的位置。

之前在做 P2596 [ZJOI2006] 书架恰好就学到一种办法，只要知道数 x 在 Treap 中的节点编号，就能找到它在中序遍历中的位置。

在建树的时候我们记录原数列第 i 数在 Treap 中的节点编号是 id_i，再维护每个节点的父亲 fa_u。

每个节点的父亲我们顺手在 update 合并节点信息时维护一下就行。

当我们要插入一个数 k 到原数列第 i 个数后面时，我们通过 id_i 找到 Treap 中对应原数列第 i 数的节点 u，然后每次将它向树根跳,如果它是右儿子,那么就将它父亲的左子树的值以及父亲的大小计入结果。

我们用一个函数来实现这个功能。

inline int id(int u){
    int res=t[t[u].ls].siz+1;
    while(u!=root){
        if(t[t[u].fa].rs==u)res+=t[t[t[u].fa].ls].siz+1;
        u=t[u].fa;
    }
    return res;
}

题目中还说

如果原数列的第 i 个元素已经添加了若干元素，则添加在这些元素的最后（见样例说明）。

我们用一个数组 cntt_i 表示原数列第 i 个元素后面已经插入了 cntt_i 个元素。

在执行操作一时，我们先找到原数列的第 i 个元素在中序遍历中的位置，再加上 cntt_i 即是我们要插入的位置。

对于权值树就相对简单的多，直接插入即可。

操作一代码

if(s[0]=='I'){
    scanf("%d%d",&i,&k);
    j=id(i);//寻找原数列的第i个数在排名树中的位置
    j+=cntt[i];
    ++cntt[i];
    //操作排名树
    split(root,j,L,R);
    root=merge(merge(L,newnode(k)),R);
    //操作权值树
    vsplit(vroot,k,L,R);
    mini=min(mini,abs(kth(L,t[L].siz)-k));//查询前驱尝试更新答案
    mini=min(mini,abs(kth(R,1)-k));//查询后继尝试更新答案
    vroot=merge(merge(L,newnode(k)),R);
}

操作二

我们在排名树中来维护相邻最小差，因为排名树有个性质，一个节点的子树所有节点是一段连续的区间，我们可以维护区间最左点的值和区间最右点的值,再维护区间相邻最小差。

节点 u 的这个区间的相邻最小差一定是一下四种

左子区间的相邻最小差
右子区间的相邻最小差
![](https://cdn.luogu.com.cn/upload/image_hosting/dx6vihb5.png)

我们在 update 函数中对这些信息进行维护

inline void update(int u){
    t[u].gap=1145141919;//区间相邻最小差
    t[u].siz=1;
    t[u].l=t[u].r=t[u].v;
    if(lc){ 
        t[u].siz+=t[lc].siz;
        t[u].l=t[lc].l;
        t[u].gap=min(t[u].gap,abs(t[u].v-t[lc].r));
        t[u].gap=min(t[u].gap,t[lc].gap);
        t[lc].fa=u;
    }
    if(rc){
        t[u].siz+=t[rc].siz;
        t[u].r=t[rc].r;
        t[u].gap=min(t[u].gap,abs(t[u].v-t[rc].l));
        t[u].gap=min(t[u].gap,t[rc].gap);
        t[rc].fa=u;
    }
}

时间复杂度:所有操作基于 FHQ Treap ，最大的计算次数是树的层数也就是 O(\log n)，总的时间复杂度为 O((n+m)\log n)

至此这道题就差不多解决了，还有不懂的就看代码或者私聊我吧。

AC记录

CODE

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e6+50,M=5e6;
int n,m,q;
#define lc t[u].ls
#define rc t[u].rs
struct FHQtreap{
    int ls,rs;
    int pri;
    int siz,v,fa,l,r,gap;
}t[N];
int cnt,root,vroot,mini=1145141919;
int cntt[N];
inline int newnode(int x){
    t[++cnt]=(FHQtreap){0,0,rand(),1,x,0,x,x,1145141919};
    return cnt;
}
inline void update(int u){
    t[u].gap=1145141919;
    t[u].siz=1;
    t[u].l=t[u].r=t[u].v;
    if(lc){ 
        t[u].siz+=t[lc].siz;
        t[u].l=t[lc].l;
        t[u].gap=min(t[u].gap,abs(t[u].v-t[lc].r));
        t[u].gap=min(t[u].gap,t[lc].gap);
        t[lc].fa=u;
    }
    if(rc){
        t[u].siz+=t[rc].siz;
        t[u].r=t[rc].r;
        t[u].gap=min(t[u].gap,abs(t[u].v-t[rc].l));
        t[u].gap=min(t[u].gap,t[rc].gap);
        t[rc].fa=u;
    }
}
inline void split(int u,int x,int &L,int &R){//排名分裂
    if(u==0)return (void)(L=R=0);
    if(t[t[u].ls].siz+1<=x)L=u,split(t[u].rs,x-t[t[u].ls].siz-1,t[u].rs,R);
    else                   R=u,split(t[u].ls,x,L,t[u].ls);
    update(u);
}

inline void vsplit(int u,int x,int &L,int &R){//权值分裂
    if(u==0)return (void)(L=R=0);
    if(t[u].v<=x)L=u,vsplit(t[u].rs,x,t[u].rs,R);
    else R=u,vsplit(t[u].ls,x,L,t[u].ls);
    update(u);
}
inline int merge(int L,int R){
    if(!L||!R)return L|R;
    if(t[L].pri>t[R].pri){t[L].rs=merge(t[L].rs,R),update(L);return L;}
    else                 {t[R].ls=merge(L,t[R].ls),update(R);return R;}
}
inline int id(int u){
    int res=t[lc].siz+1;
    while(u!=root){
        if(t[t[u].fa].rs==u)res+=t[t[t[u].fa].ls].siz+1;
        u=t[u].fa;
    }
    return res;
}
inline int kth(int u,int k){
    if(!u||t[u].siz<k)return -11451419;
    if(t[lc].siz+1==k)return t[u].v;
    if(t[lc].siz>=k)return kth(lc,k);
    if(t[lc].siz+1<k)return kth(rc,k-t[lc].siz-1);
}
signed main(){
    srand(time(NULL));
    // freopen("in.in","r",stdin);
    // freopen("a.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1,a;i<=n;++i){
        scanf("%d",&a);
        root=merge(root,newnode(a));
    }
    int L,R;
    for(int i=1;i<=n;++i){
        vsplit(vroot,t[i].v,L,R);
        mini=min(mini,abs(kth(L,t[L].siz)-t[i].v));
        mini=min(mini,abs(kth(R,1)-t[i].v));
        vroot=merge(merge(L,newnode(t[i].v)),R);
    }
    int i,k,j;
    char s[20];
    while(m--){
        scanf("%s",s);
        if(s[0]=='I'){
            scanf("%d%d",&i,&k);
            j=id(i);//寻找原数列的第i个数在排名树中的位置
            j+=cntt[i];
            ++cntt[i];
            //操作排名树
            split(root,j,L,R);
            root=merge(merge(L,newnode(k)),R);
            //操作权值树
            vsplit(vroot,k,L,R);
            mini=min(mini,abs(kth(L,t[L].siz)-k));//查询前驱尝试更新答案
            mini=min(mini,abs(kth(R,1)-k));//查询后继尝试更新答案
            vroot=merge(merge(L,newnode(k)),R);
        }
        if(s[4]=='G')cout<<t[root].gap<<"\n";
        if(s[4]=='S')cout<<mini<<"\n";
    }
    return 0;
}
/*
文件名: p1110.cpp
创建时间: 2024-10-11 18:33:41
作者: nnn233
*/