题解 Luogu P1110 【[ZJOI2007]报表统计】

阳光穿透心脏的1/2处 2023-06-01 12:42 9阅读 0赞

感谢 @[cmy962085349][] 提供的hack数据，已经改对了。

--------------------

先声明，我好像是题解里写双$fhq$ $treap$里唯一能过的...（最后两个点啊）

--------------------

思路:首先看题目，$MIN\_GAP\_SORT$ 明显是求它的前驱与后继(可能有相同的)，所以就用平衡树，但是又要求两个相邻的数的差，就可以有再开一个平衡树存放差值

实现:抛开奇奇怪怪的的题面，主要考虑这三个操作：

1、$INSERT$ $i$ $k$:

这个很简单，用链表就行了（数组模拟的），但是要注意，插入的时候，要接着上一个在这插入的，还要做双向链表，数组要记得开两倍

最重要的是，插入了以后，这个数的前一个数与后一个数的差要在存放相邻两个数的差的$fhq$ $treap$里删除，并插入这个数与前一个数的差和这个数与后一个数的差要存进去

2、$MIN\_GAP$:

做完插入，就在存差的$fhq$ $treap$查$rank$$1$好了(最左边的那个节点)

3、$MIN\_SORT\_GAP$:

为了避免查前驱与后继时出现自己(不是另一个与自己相同的数)，所以插入时(分裂后，合并前，这样正好符合查前驱与后继的标准)就比较取小，询问时直接输出就好了

P.S. 似乎经过 @[cmy962085349][] 的 $hack$ 数据更正以后，似乎并不需要过于卡常了（原来代码需要疯狂卡常）（说明题解里双平衡树还是因为写错了而 $Tle$ 了后面两个点），似乎不用 $cin$ 与 $cout$ 就能过，不需要加什么 $register$ 了（虽然我还是加了）

附上AC代码:

#include<cstdio>
    #include<cstdlib>
    #include<ctime>
    #include<iostream>
    using namespace std;
    
    struct tree{//存每个值的数(不是差)
        int size,val,dat,l,r;
    }tr[1000005];//数组记得开两倍
    
    int s_tr,root,n,m,x,y,z,a[1000005],b[1000005],c[1000005];
    
    int min_sort_gap;//MIN_SORT_GAP的答案
    
    inline int abs(int a){
        return a<0?-a:a;
    }
    
    inline int min(int a,int b){
        return a<b?a:b;
    }
    
    //fhq treap常规操作
    
    inline int new_tr(int val){
        tr[++s_tr].val=val;
        tr[s_tr].size=1;
        tr[s_tr].dat=rand();
        return s_tr;
    }
    
    inline void update(int p){
        tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+1;
    }
    
    void split(int p,int k,int &x,int &y){
        if(!p){
            x=y=0;
            return;
        }
        if(tr[p].val<=k)x=p,split(tr[p].r,k,tr[p].r,y);
        else y=p,split(tr[p].l,k,x,tr[p].l);
        update(p);
    }
    
    int merge(int x,int y){
        if(!x||!y)return x+y;
        if(tr[x].dat>tr[y].dat){
            tr[x].r=merge(tr[x].r,y);
            update(x);
            return x;
        }
        else {
            tr[y].l=merge(x,tr[y].l);
            update(y);
            return y;
        }
    }
    
    inline int Max(int x){//一棵fhq(可能是分裂后)中最大的
        while(tr[x].r)x=tr[x].r;
        return tr[x].val;
    }
    
    inline int Min(int y){//一棵fhq(可能是分裂后)中最大的
        while(tr[y].l)y=tr[y].l;
        return tr[y].val;
    }
    
    inline void insert(int val){
        split(root,val,x,y);
        if(tr[x].size)//要有才行
            min_sort_gap=min(min_sort_gap,abs(val-Max(x)));
        if(tr[y].size)//要有才行
            min_sort_gap=min(min_sort_gap,abs(Min(y)-val));
        root=merge(merge(x,new_tr(val)),y);
    }
    
    //存差值的fhq treap
    
    struct tree1{
        int size,val,dat,l,r;
    }tr1[1000005];
    
    int s_tr1,root1;
    
    inline int new_tr1(int val){
        tr1[++s_tr1].val=val;
        tr1[s_tr1].size=1;
        tr1[s_tr1].dat=rand();
        return s_tr1;
    }
    
    inline void update1(int p){
        tr1[p].size=tr1[tr1[p].l].size+tr1[tr1[p].r].size+1;
    }
    
    void split1(int p,int k,int &x,int &y){
        if(!p){
            x=y=0;
            return;
        }
        if(tr1[p].val<=k)x=p,split1(tr1[p].r,k,tr1[p].r,y);
        else y=p,split1(tr1[p].l,k,x,tr1[p].l);
        update1(p);
    }
    
    int merge1(int x,int y){
        if(!x||!y)return x+y;
        if(tr1[x].dat>tr1[y].dat){
            tr1[x].r=merge1(tr1[x].r,y);
            update1(x);
            return x;
        }
        else {
            tr1[y].l=merge1(x,tr1[y].l);
            update1(y);
            return y;
        }
    }
    
    inline void insert1(int val){
        split1(root1,val,x,y);
        root1=merge1(merge1(x,new_tr1(val)),y);
    }
    
    inline void delete_val(int val){//这棵fhq要能支持删除
        split1(root1,val,x,z);
        split1(x,val-1,x,y);
        y=merge1(tr1[y].l,tr1[y].r);
        root1=merge1(merge1(x,y),z);
    }
    
    inline int Min1(int y){
        while(tr1[y].l)y=tr1[y].l;
        return tr1[y].val;
    }
    
    char s[101];//卡常
    
    inline int read(){//卡常
        int r=0,f=1;
        char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+c-'0',c=getchar();
        return r*f;
    }
    
    int main(){
        srand(time(0));
        n=read(),m=read();
        min_sort_gap=1e9+10;
        for(register int i=1;i<=n;i++){//卡常
            a[i]=read();
            insert(a[i]);
        }
        for(register int i=1;i<n;i++)//卡常减少if
            insert1(abs(a[i+1]-a[i])),c[i]=i+1;
        for(register int i=2;i<=n;i++)//卡常减少if，n+1是因为可能在第n个后面插入
            b[i]=i-1;
        b[n+1]=n;
        int cnt=n;
        for(register int i=1;i<=m;i++){//卡常
            scanf("%s",s);
            if(s[0]=='I'){
                int j=read(),k=read();
                delete_val(abs(a[j+1]-a[b[j+1]]));//因为插入后不在一起了，删除
                insert1(abs(a[b[j+1]]-k));//插入后多了两个差值(不算删除的)
                if(j<n)insert1(abs(k-a[j+1]));//可能插在第n个的后面
                a[++cnt]=k;//放进数组，这件事一定要在上述操作以后做，不然若连续插入在第n个数以后就挂了，因为第一次cnt+1后会直接取代n+1,b[n+1]也就没什么用了
                b[cnt]=b[j+1];//数组模拟链表
                c[cnt]=j+1;
                c[b[j+1]]=cnt;//记得修改前一个与后一个的指向
                b[j+1]=cnt;
                insert(k);
            }
            else {
                if(s[4]=='G')printf("%d\n",Min1(root1));//整棵fhq里最小的
                else printf("%d\n",min_sort_gap);
            }
        }
        return 0;
    }

再次感谢 @[cmy962085349][]

完结偷偷撒花!(✿✿ヽ(°▽°)ノ✿)

转载于:https://www.cnblogs.com/wyzwyz/p/11236071.html

[cmy962085349]: https://www.luogu.org/space/show?uid=32483