Eternity

Until The End

P1110 [ZJOI2007] 报表统计

发表于 分类于
本文字数： 3.9k 阅读时长 ≈ 4 分钟

做很久没有手搓的平衡树惹。

原题指路

双 $\text{Fhq-Treap}$ 大常数写法。

题解

我们会发现，所有的操作都是基于原数列的，且没有删除操作。

考虑把三个操作分别维护。

操作二

首先考虑相邻绝对小值，如果当前位置为 $x$ ，插入 $a_x$ ，则在答案备选里添加了 $|a_x-a_{x-1}|$ 和 $|a_{x+1}-a_x|$ ，而去掉了 $|a_{x+1}-a_{x-1}|$ 。即删除了一个数，加上了两个数。而我们第二个操作需要的就是答案备选里的最小值。

本来考虑是维护最小值和次小值，结果发现这样不可做。

然后发现，我们需要求的是一个动态序列的最小值，支持插入和删除操作，结果发现就是个平衡树的板子，直接一波带走。

对于如何记录 $a_{x-1},a_{x+1}$ 并 $\mathcal O(1)$ 查询的话，记录一个数组 $Nxt[x]$ 表示加在 $x$ 之后的当前最后一个数的值，也就是原数列中第 $x+1$ 个数现在前面一个数。那么就有 $a_{x-1}=Nxt[x],a_{x+1}=Val[x+1]$ 。

操作三

然后考虑第三个操作，求一个序列的最小差值，由智慧法可以得到：如果 $x$ 有贡献，则与 $x$ 一同贡献的一定是 $x$ 的前驱后继。所以，考虑维护一棵平衡树，每插入一个数，就查找其前驱后继，并更新答案。

特判

刚开始使用的是 $\text{FHQ-Treap}$ ，交上去一发 $\textcolor{red}{\text{Wrong Answer}}$ 只有 $14pts$ ，除了板子写挂了之外，发现了这道题的一个特点，这个数列里有重复元素，而我们知道，$\text{FHQ-Treap}$ 的查找的是严格的前驱后继，但这道题所定义的前驱后继非严格，答案可能为 $1$ 。

所以需要特判。

还有平衡树的常规操作：安置哨兵。因为 $a_i,x\leq 5\times10^8$ ，所以 INF=0x3f3f3f3f 可过。

优化

在保证代码无误后，交上一发，得到 $\textcolor{darkblue}{\text{Time Limit Exceeded}}$ ，然后自嘲地开 $\text{O}_2$ ，结果还是 $\textcolor{darkblue}{\text{T}}$ 掉了一个点，我们分析一下这个做法的时间复杂度：

对于第二个操作，是 $\mathcal O(3\log n)$ ，而第三个操作是 $\mathcal O(2\log n)$，加上预处理的 $\mathcal O(2n\log n)$ ，最后得到，是一个常数巨大的 $\mathcal O(q\log n)$ ，导致了理论可过，实际 $\text{T}$ 飞的结果。

所以考虑卡常小技巧。

从刚刚的特判得知，因为没有删除操作，势能分析一波，发现操作三（操作二不行的原因是因为有删除）的答案尽可能越来越小，直到 $0$ ，那么，当最小值达到 $0$ 的时候，我们就根本不需要再维护操作三了，直接带过。

加上这个优化，吸个氧，就过了。

实现

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
const int MAXN=1e6+10;
const int INF=0x3f3f3f3f;
int N,Q,Val[MAXN],Nxt[MAXN];
struct BT
{
    int Idx=0,Rt=0,x,y,z;
    struct Fhq
    {
        int siz,val,rd,chi[2];
    }Tr[MAXN];
    #define ls(p) Tr[p].chi[0]
    #define rs(p) Tr[p].chi[1]
    inline int newNode(int v)
    {
        Tr[++Idx]={1,v,rand()};
        return Idx;
    }
    inline void upDate(int p)
    {
        Tr[p].siz=Tr[ls(p)].siz+Tr[rs(p)].siz+1;
    }
    void split(int p,int k,int &u,int &v)
    {
        if(!p) u=v=0;
        else
        {
            if(Tr[p].val<=k) u=p,split(rs(p),k,rs(p),v);
            else v=p,split(ls(p),k,u,ls(p));
            upDate(p);
        }
        return ;
    }
    int merge(int u,int v)
    {
        if(!u||!v) return u+v;
        if(Tr[u].rd<Tr[v].rd)
        {
            rs(u)=merge(rs(u),v);
            upDate(u);return u;
        }
        else
        {
            ls(v)=merge(u,ls(v));
            upDate(v);return v;
        }
    }
    inline void insert(int v)
    {
        split(Rt,v,x,y);
        Rt=merge(merge(x,newNode(v)),y);
    }
    inline void del(int v)
    {
        split(Rt,v,x,y),split(x,v-1,x,z);
        z=merge(ls(z),rs(z));
        Rt=merge(merge(x,z),y);
    }
    inline int size(int v)
    {
        split(Rt,v-1,x,y),split(y,v,y,z);
        int res=Tr[y].siz;
        Rt=merge(merge(x,y),z);
        return res;
    }
    inline int kth(int p,int k)
    {
        while(true)
        {
            if(k<=Tr[ls(p)].siz) p=ls(p);
            else if(k==Tr[ls(p)].siz+1) return p;
            else k-=Tr[ls(p)].siz+1,p=rs(p);
        }
    }
    inline int pre(int v)
    {
        if(size(v)>1) return v;
        split(Rt,v-1,x,y);
        int res=Tr[kth(x,Tr[x].siz)].val;
        Rt=merge(x,y);
        return res;
    }
    inline int nxt(int v)
    {
        if(size(v)>1) return v;
        split(Rt,v,x,y);
        int res=Tr[kth(y,1)].val;
        Rt=merge(x,y);
        return res;
    }
}Tree,Gap;
int Minn=INF;
char opt[20];
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,Q);
    for(int i=1;i<=N;++i) read(Val[i]),Nxt[i]=Val[i],Tree.insert(Val[i]);
    for(int i=2;i<=N;++i) Gap.insert(abs(Val[i]-Val[i-1]));
    Tree.insert(INF),Tree.insert(-INF),Gap.insert(INF),Gap.insert(-INF),Val[N+1]=INF;
    for(int i=1;i<=N;++i) checkMin(Minn,std::min(Val[i]-Tree.pre(Val[i]),Tree.nxt(Val[i])-Val[i]));
    for(int qx,qk;Q--;)
    {
        scanf("%s",opt+1);
        if(opt[1]=='I')
        {
            read(qx,qk);
            Gap.del(abs(Val[qx+1]-Nxt[qx]));
            Gap.insert(abs(Val[qx+1]-qk)),Gap.insert(abs(qk-Nxt[qx]));
            Nxt[qx]=qk;
            if(Minn)
            {
                Tree.insert(qk);
                checkMin(Minn,std::min(Tree.nxt(qk)-qk,qk-Tree.pre(qk)));
            }
        }
        else
        {
            if(opt[5]=='S') write(Minn,'\n');
            else write(Gap.Tr[Gap.kth(Gap.Rt,2)].val,'\n');
        }
    }
    return 0;
}
/*
3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP
3 2
1 2 3
INSERT 2 2 
MIN_SORT_GAP
*/
相关文章