摘要:珂朵莉树上进行尺取法

luogu5251[LnOI2019]第二代图灵机

题面

题目分析

《高中没学过图灵机,写过了第二代图灵机的信息题,可以去拿图灵奖吗》

维护颜色段的信息,大胆一点直接想出珂朵莉树.

对于修改操作的维护就非常简单了,单点修改区间求和数值可以使用树状数组,区间修改颜色段在珂朵莉树上分裂后再插入即可.

操作3是求区间内包含所有颜色的数字和最小的子区间,显然这个操作可以进行尺取法,在当前区间还未包含所有颜色之前,将区间的右端点向右移,一旦满足了包含所有颜色,更新答案后将左端点向右移动以保证答案最小,因为在珂朵莉树上做所以这样就可以$O(\sqrt n)$地遍历出所有有可能成为最优子区间的区间.

操作4是求区间内不包含重复颜色的数字和最大子区间,同样使用尺取法,在未出现重复颜色之前将区间右端点向右移使得答案更大,一旦出现了重复的颜色,就将区间的左端点向右移来满足条件.

根据珂朵莉树的性质,进行操作4时如果有长度大于一的节点那么就对这个节点的操作就只能取左端点后更新答案然后在右端点重新开始尺取法,并且算上中间的单点最大值,单点最大值预先用线段树将整个查询区间处理好即可.

具体实现特别恶心,看代码吧.

代码

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
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
#define IT std::set<_Chtholly>::iterator
#define lowbit(x) (x&-x)
typedef long long lxl;
const lxl big=100010,small=110;
lxl n,m,_c,ColorCnt;
lxl a[big],b[big],rem[small],t[big];
lxl root,NodeCnt;
lxl c[2][big<<2],max[big<<2];
struct _Chtholly
{
lxl l,r;
mutable lxl v;
_Chtholly(lxl _l,lxl _r=-1,lxl _v=0):l(_l),r(_r),v(_v){}
bool operator <(const _Chtholly &another)const{return l<another.l;}
};
std::set<_Chtholly>s;
inline IT spilt(lxl pos)
{
IT it=s.lower_bound(_Chtholly(pos));
if(it!=s.end()&&it->l==pos)return it;
--it;
lxl _l=it->l,_r=it->r;
lxl _v=it->v;
s.erase(it);
s.insert(_Chtholly(_l,pos-1,_v));
return s.insert(_Chtholly(pos,_r,_v)).first;
}
inline void assign(lxl l,lxl r,lxl val)
{
IT it2=spilt(r+1),it1=spilt(l);
s.erase(it1,it2);
s.insert(_Chtholly(l,r,val));
}
inline void modify(lxl x,lxl val)
{
for(;x<big;x+=lowbit(x))t[x]+=val;
}
inline lxl ask(lxl x)
{
lxl sum(0);
for(;x;x-=lowbit(x))sum+=t[x];
return sum;
}
inline lxl query(lxl l,lxl r){return ask(r)-ask(l-1);}
void BuildTree(lxl &t,lxl l,lxl r)
{
if(!t)t=++NodeCnt;
if(l==r){max[t]=a[l];return;}
lxl mid((l+r)>>1);
BuildTree(c[0][t],l,mid),BuildTree(c[1][t],mid+1,r);
max[t]=std::max(max[c[0][t]],max[c[1][t]]);
}
void change(lxl t,lxl l,lxl r,lxl x,lxl k)
{
if(l==r){max[t]=k;return;}
lxl mid((l+r)>>1);
if(x<=mid)change(c[0][t],l,mid,x,k);
else change(c[1][t],mid+1,r,x,k);
max[t]=std::max(max[c[0][t]],max[c[1][t]]);
}
lxl SegMax(lxl t,lxl l,lxl r,lxl x,lxl y)
{
if(x<=l&&y>=r)return max[t];
lxl tmax(-INF),mid((l+r)>>1);
if(x<=mid)tmax=std::max(tmax,SegMax(c[0][t],l,mid,x,y));
if(y>mid)tmax=std::max(tmax,SegMax(c[1][t],mid+1,r,x,y));
return tmax;
}
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline lxl GetMin(lxl l,lxl r)
{
IT itl=s.upper_bound(_Chtholly(l)),itr=s.upper_bound(_Chtholly(r));
--itl,--itr;
return query(itl->r,itr->l);
}
inline lxl GetMax(lxl l,lxl r)
{
return query(l,r);
}
int main(void)
{
n=read(),m=read(),_c=read();
for(R int i(1);i<=n;++i)a[i]=read(),modify(i,a[i]);
for(R int i(1);i<=n;++i)b[i]=read();
BuildTree(root,1,n);
s.insert(_Chtholly(n+1,n+1,0)),s.insert(_Chtholly(0,0,0));
for(R int l(1);l<=n;)
{
lxl r(l);
while(b[r]==b[r+1]&&r<=n)++r;
s.insert((_Chtholly){l,r,b[l]}),l=r+1;
}
for(R int i(1);i<=m;++i)
{
lxl opt=read();
if(opt==1)
{
lxl x=read(),y=read();
modify(x,-a[x]),modify(x,a[x]=y);
change(root,1,n,x,a[x]);
}
if(opt==2)
{
lxl l=read(),r=read(),color=read();
assign(l,r,color);
}
if(opt==3)
{
memset(rem,0,sizeof rem),ColorCnt=0;
lxl x=read(),y=read(),ans(INF);
lxl l(x),r(x);
spilt(y+1),spilt(x);
while(r<=y)
{
IT it=s.lower_bound(_Chtholly(r));
// debug(it->l),debug(it->r),debug(l),debug(r),endl;
if(!rem[it->v])++ColorCnt;
++rem[it->v],r=it->r;
if(ColorCnt<_c){++r;continue;}
else
{
IT it2=s.upper_bound(_Chtholly(l));--it2;
while(ColorCnt==_c)
{
ans=std::min(GetMin(l,r),ans);
if(!(rem[it2->v]-1))--ColorCnt;
--rem[it2->v],l=it2->r+1;
++it2;
}
if(it2->l!=it2->r)l=it2->r;
++r;
}
}
if(ans==INF)printf("-1\n");
else printf("%lld\n",ans);
}
if(opt==4)
{
memset(rem,0,sizeof rem),ColorCnt=0;
lxl x=read(),y=read(),ans=SegMax(root,1,n,x,y);
lxl l(x),r(x);
spilt(y+1),spilt(x);
while(r<=y)
{
IT it=s.lower_bound(_Chtholly(r));
if(!(rem[it->v]-1))++ColorCnt;
++rem[it->v];
if(!ColorCnt)ans=std::max(ans,GetMax(l,r));
// debug(it->l),debug(it->r),debug(l),debug(r),debug(rem[2]),endl;
if(it->l==it->r&&rem[it->v]==1)r=it->r+1;
else
{
IT it2=s.upper_bound(_Chtholly(l));--it2;
// debug(it2->l),debug(it2->r),debug(l),endl;
while(ColorCnt)
{
--rem[it2->v];
if(!(rem[it2->v]-1))--ColorCnt;
// debug(l),debug(ColorCnt),debug(rem[it2->v]);
l=it2->r+1,++it2;
}
ans=std::max(ans,GetMax(l,r));
if(it->l!=it->r)
{
l=it->r,r=l+1;
memset(rem,0,sizeof rem),ColorCnt=0;
++rem[it->v];
}
else r=it->r+1;
}
}
printf("%lld\n",ans);
}
}
return 0;
}
/*
8 1 4
1 2 3 4 5 6 7 8
2 3 1 2 3 4 1 2
4 2 8
*/