维修数列

Posted by Songtoy on 2017-09-04
#Splay #Data Structure

关键在于：

（1）$Splay$，$Rotate$，$RotateTo$($Find$)是核心

（2）要思考好$Up$，$Down$要维护什么

（3）0，n+1作为初始节点，能避免一些特判

（4）空节点、0、n+1的值不能影响最终答案.

*（5）区间翻转会不一定对最终答案造成一定的影响，但在求解答案的过程中如果用到了诸如L,R顺序的值注意随区间翻转而翻转

*（5）更新节点$u$时是否可能对祖先的某些值(不一定是最终答案)造成影响

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long
#define keyTree (son[son[rt][1]][0])
static const int M = 500000 + 5;
static const int INF = 700000000;
struct SplayTree{
    int fa[M],son[M][2],sz[M];
    int val[M],sum[M];
    int L_max[M],R_max[M],sum_max[M];
    bool lazy_rev[M];
    int lazy_num[M];
    int tot,rt;
    int rub[M],top;
    SplayTree(){
        tot=rt=0;
        L_max[0]=R_max[0]=sum_max[0]=-INF;
        top=0;
        for(int i=1;i<M;++i)rub[++top]=M-i;
        Newnode(rt,0,-INF);
        Newnode(son[rt][1],rt,-INF);
        Up(rt);
    }
    void Newnode(int &u,int f,int x){
        u=rub[top--];
        ++tot;//注意回收内存
        fa[u]=f;
        son[u][0]=son[u][1]=0;
        sz[u]=1;
        val[u]=sum[u]=x;
        L_max[u]=R_max[u]=sum_max[u]=x;
        lazy_rev[u]=false;
        lazy_num[u]=INF;
    }
    void Rotate(int p){
        int F=fa[p];
        int d=son[F][1]==p;
        son[F][d]=son[p][!d];
        if(son[p][!d])fa[son[p][!d]]=F;
        fa[p]=fa[F];
        son[fa[p]][son[fa[p]][1]==F]=p;
        fa[F]=p;
        son[p][!d]=F;
        //
        Up(F);
    }
    void Splay(int p,int goal){
        /*
        Down from Root to P
        */
        while(fa[p]!=goal){
            int F=fa[p];
            if(fa[F]!=goal){
                if(son[F][1]==p^son[fa[F]][1]==F)Rotate(p);
                else Rotate(F);
            }
            Rotate(p);
        }
        Up(p);
        if(!goal)rt=p;
    }
    void RotateTo(int k,int goal){
        int p=Find(k);
        Splay(p,goal);
    }
    void Rev(int p){
        lazy_rev[p]^=true;
        int t=son[p][0];
        son[p][0]=son[p][1];
        son[p][1]=t;
        t=L_max[p];
        L_max[p]=R_max[p];
        R_max[p]=t;
    }
    void Clr(int p,int c){
        val[p]=c;
        sum[p]=sz[p]*c;
        lazy_num[p]=c;
        sum_max[p]=L_max[p]=R_max[p]=max(c,sum[p]);
    }
    void Up(int p){
        sz[p]=1+sz[son[p][0]]+sz[son[p][1]];
        sum[p]=val[p]+sum[son[p][0]]+sum[son[p][1]];
        sum_max[p]=max(sum_max[son[p][0]],sum_max[son[p][1]]);
        
        L_max[p]=max(L_max[son[p][0]],sum[son[p][0]]+val[p]+max(0,L_max[son[p][1]]));
        R_max[p]=max(R_max[son[p][1]],sum[son[p][1]]+val[p]+max(0,R_max[son[p][0]]));
        sum_max[p]=max(sum_max[p],val[p]+max(0,R_max[son[p][0]])+max(0,L_max[son[p][1]]));
    }
    void Down(int p){
        if(lazy_rev[p]){
            if(son[p][0])Rev(son[p][0]);
            if(son[p][1])Rev(son[p][1]);
            lazy_rev[p]=false;
        }
        if(lazy_num[p]<=1000){
            if(son[p][0])Clr(son[p][0],lazy_num[p]);
            if(son[p][1])Clr(son[p][1],lazy_num[p]);
            lazy_num[p]=INF;
        }
    }
    int Find(int k){
        int p=rt;Down(p);
        while(sz[son[p][0]]!=k){
            if(sz[son[p][0]]>k)p=son[p][0];
            else{
                k-=sz[son[p][0]]+1;
                p=son[p][1];
            }
            Down(p);
        }
        return p;
    }
    void build(int &u,int f,int L,int R,int num[]){
        int mid=L+R>>1;
        Newnode(u,f,num[mid]);
        if(L<mid)build(son[u][0],u,L,mid-1,num);
        if(mid<R)build(son[u][1],u,mid+1,R,num);
        Up(u);
    }
    void Insert(int L,int len,int num[]){
        RotateTo(L,0);
        RotateTo(L+1,rt);
        build(keyTree,son[rt][1],1,len,num);
        Up(son[rt][1]);
        Up(rt);
    }
    void recur(int p){
        //
        rub[++top]=p;
        --tot;
        //
        if(son[p][0])recur(son[p][0]);
        if(son[p][1])recur(son[p][1]);
    }
    void Del(int L,int len){
        int R=L+len-1;
        RotateTo(L-1,0);
        RotateTo(R+1,rt);
        recur(keyTree);
        son[son[rt][1]][0]=0;
        Up(son[rt][1]);
        Up(rt);
    }
    void Fill(int L,int len, int x){
        RotateTo(L-1,0);
        RotateTo(L+len,rt);
        Clr(keyTree,x);
        Up(son[rt][1]);
        Up(rt);
    }
    void Reverse(int L,int len){
        RotateTo(L-1,0);
        RotateTo(L+len,rt);
        Rev(keyTree);
        Up(son[rt][1]);
        Up(rt);
    }
    void Get_sum(int L,int len){
        RotateTo(L-1,0);
        RotateTo(L+len,rt);
        printf("%d\n",sum[keyTree]);
    }
    void Max_sum(){
        printf("%d\n",sum_max[rt]);
    }
    void debug(int p){
        printf("v: %d , sz: %d , val: %d , sum: %d , lazy_rev: %d , lazy_sum: %d , L_max[p]: %d , R_max[p]: %d , sum_max: %d\n"
                                    ,p,sz[p],val[p],sum[p],lazy_rev[p],lazy_num[p],L_max[p],R_max[p],sum_max[p]);
        printf("%d %d\n",son[p][0],son[p][1]);
        Down(p);
        if(son[p][0])debug(son[p][0]);
//		printf("%d ",val[p]);
        if(son[p][1])debug(son[p][1]);
    }
}Tree;
int A[M];
char str[50];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&A[i]);
    Tree.Insert(0,n,A);
    while(m--){
        scanf("%s",str);
        int pos,len,c;
        if(str[0]=='I'){
            scanf("%d%d",&pos,&len);
            for(int i=1;i<=len;++i)scanf("%d",&A[i]);
            Tree.Insert(pos,len,A);
        }else if(str[0]=='D'){
            scanf("%d%d",&pos,&len);
            Tree.Del(pos,len);
        }else if(str[0]=='R'){
            scanf("%d%d",&pos,&len);
            Tree.Reverse(pos,len);
        }else if(str[0]=='G'){
            scanf("%d%d",&pos,&len);
            Tree.Get_sum(pos,len);
        }else if(str[0]=='M'&&str[2]=='K'){
            scanf("%d%d%d",&pos,&len,&c);
            Tree.Fill(pos,len,c);
        }else{
            Tree.Max_sum();
        }
    }
    return 0;
}

$By SongToy$