Reincarnation

正因为梦易碎，才格外美好。

CFG103861F Vacation

发表于 更新于 分类于
本文字数： 11k 阅读时长 ≈ 10 分钟

你码量大跌！

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/gym/103861/problem/F

形式化题意：给定一个长度为 的序列， 次操作和参数 ：

  1. 将 ；
  2. 求：
    。

数据范围：

时空限制：

这个查询看起来很头大，但实际上就是在 内找到一个长度不超过 的子区间，使其区间和最大。这样的话，这道题就有点像前两天在 上做过的一道的加强版。

我们就沿用那一道题的思路，将序列分为很多个长度为 的段，则答案的贡献就在一个段内或者两个段之间。

对于一个段内的答案，就是一个固定区间的最大子段和，详见小白逛公园和 。然后用一个大的线段树来统计答案即可，这里避免常数过大，统计答案的线段树可以用 。

对于段间答案，记 为后缀和， 为前缀和，我们需要在左段 和右端 中找到两个下标 满足 ，这个是可以使用线段树来维护的，但考虑到单调修改对于 都是 级别的，所以我们直接用线段树维护 ，区间修改即可，然后对于所有的段间线段树在建一棵 来统计答案即可。写了 9k 左右，调了 天。

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
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
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
// ----- Eternally question-----
// Problem: F. Vacation
// Contest: Codeforces - 2021 ICPC Asia East Continent Final
// URL: https://codeforces.com/gym/103861/problem/F
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
// Written by: Eternity
// Time: 2023-01-28 14:17:52
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=4e5+10;
const ll INF=2e18,MAX=0x3f3f3f3f3f;
int N,Q,C;
ll a[MAXN];
int Lst[MAXN],Rst[MAXN],Bck[MAXN],Boc;
inline int trans(int x){ return x-Lst[Bck[x]]+1; }
struct SegmentIn
{
	struct ZkwSegment
	{
		int Length;
		std::vector<ll>val;
		void pushUp(int p)
		{ val[p]=std::max(val[p<<1],val[p<<1|1]); }
		void build(int n)
		{
			Length=1;
			while(Length<=Boc+1) Length<<=1;
			val.resize(Length<<1);	
		}
		void modifyX(int x,ll v)
		{
			val[x+Length]=v;
			for(int i=(x+Length)>>1;i;i>>=1) pushUp(i);
		}
		ll queryMax(int l,int r)
		{
			ll res=-INF;
			if(l>r) return res;
			for(l+=Length-1,r+=Length+1;l^r^1;l>>=1,r>>=1)
			{
				if(~l&1) checkMax(res,val[l^1]);
				if(r&1) checkMax(res,val[r^1]);
			}
			return res;
		}	
	}val;
	struct InBlock
	{
		int Len;
		struct Node
		{
			ll lx,rx,val,sum;
			Node(ll lx=0,ll rx=0,ll val=0,ll sum=0):
				lx(lx),rx(rx),val(val),sum(sum){}
		};
		struct St
		{ int l,r;Node val; };
		std::vector<St>Tr;
		std::vector<ll>b;
		#define ls (p<<1)
		#define rs (p<<1|1)
		Node merge(Node l,Node r)
		{
			Node p;
			p.lx=std::max(l.lx,l.sum+r.lx);
			p.rx=std::max(r.rx,r.sum+l.rx);
			p.val=std::max(std::max(l.val,r.val),l.rx+r.lx);
			p.sum=l.sum+r.sum;
			return p;
		}
		void pushUp(int p)
		{ Tr[p].val=merge(Tr[ls].val,Tr[rs].val); }
		void build(int p,int l,int r)
		{
			Tr[p].l=l,Tr[p].r=r;
			if(l==r) return Tr[p].val=(Node){b[l],b[l],b[l],b[l]},void();
			int mid=(l+r)>>1;
			build(ls,l,mid),build(rs,mid+1,r);
			pushUp(p);
		}
		void modifyX(int p,int x,ll v)
		{
			if(Tr[p].l==Tr[p].r) return Tr[p].val=(Node){v,v,v,v},void();
			int mid=(Tr[p].l+Tr[p].r)>>1;
			if(x<=mid) modifyX(ls,x,v);
			else modifyX(rs,x,v);
			pushUp(p);
		}
		Node querySum(int p,int l,int r)
		{
			if(l>r) return -INF;
			if(Tr[p].r<l||r<Tr[p].l) return -INF;
			if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
			int mid=(Tr[p].l+Tr[p].r)>>1;
			if(r<=mid) return querySum(ls,l,r);
			if(l>mid) return querySum(rs,l,r);
			Node res=merge(querySum(ls,l,r),querySum(rs,l,r));
			return res;
		}
		ll querySum(int l,int r)
		{ return querySum(1,l,r).val; }
		ll query()
		{ return querySum(1,1,Len).val; }
		void build(int l,int r)
		{
			Len=C;
			b.resize(Len+2),Tr.resize(Len<<2);
			for(int i=1;i<=Len;++i) b[i]=a[i+l-1];
			build(1,1,Len);
		}
	};
	std::vector<InBlock>Tr;
	void build()
	{
		Tr.resize(Boc+1);val.build(Boc+1);
		for(int i=1;i<=Boc;++i) Tr[i].build(Lst[i],Rst[i]);
		for(int i=1;i<=Boc;++i) val.val[i+val.Length]=Tr[i].query();
		for(int i=val.Length-1;i;--i) val.pushUp(i);
	}
	void modifyX(int x,ll v)
	{
		Tr[Bck[x]].modifyX(1,trans(x),v);
		val.modifyX(Bck[x],Tr[Bck[x]].query());
	}
	ll query(int l,int r)
	{
		ll res=-INF;
		if(Bck[l]==Bck[r]) return Tr[Bck[l]].querySum(trans(l),trans(r));
		checkMax(res,Tr[Bck[l]].querySum(trans(l),C));
		checkMax(res,Tr[Bck[r]].querySum(1,trans(r)));
		checkMax(res,val.queryMax(Bck[l]+1,Bck[r]-1));
		return res;
	}
}In;
std::vector<ll>pt,st;
struct SegmentOut
{
	struct ZkwSegment
	{
		int Length;
		std::vector<ll>val;
		void pushUp(int p)
		{ val[p]=std::max(val[p<<1],val[p<<1|1]); }
		void build(int n)
		{
			Length=1;
			while(Length<=Boc+1) Length<<=1;
			val.resize(Length<<1);	
		}
		void modifyX(int x,ll v)
		{
			val[x+Length]=v;
			for(int i=(x+Length)>>1;i;i>>=1) pushUp(i);
		}
		ll queryMax(int l,int r)
		{
			ll res=-INF;
			if(l>r) return res;
			for(l+=Length-1,r+=Length+1;l^r^1;l>>=1,r>>=1)
			{
				if(~l&1) checkMax(res,val[l^1]);
				if(r&1) checkMax(res,val[r^1]);
			}
			return res;
		}	
	}val;
	struct OutBlock
	{
		int Len;
		struct St
		{ int l,r;ll av,bv,la,lb,val; };
		std::vector<St>Tr;
		#define ls (p<<1)
		#define rs (p<<1|1)
		void pushUp(int p)
		{
			Tr[p].av=std::max(Tr[ls].av,Tr[rs].av);
			Tr[p].bv=std::max(Tr[ls].bv,Tr[rs].bv);
			Tr[p].val=std::max(std::max(Tr[ls].val,Tr[rs].val),Tr[ls].bv+Tr[rs].av);
		}
		void upDate(int p,ll a,ll b)
		{
			Tr[p].av+=a,Tr[p].la+=a;
			Tr[p].bv+=b,Tr[p].lb+=b;
			Tr[p].val+=a+b;
			return ;
		}
		void pushDown(int p)
		{
			if(!Tr[p].la&&!Tr[p].lb) return ;
			upDate(ls,Tr[p].la,Tr[p].lb),
			upDate(rs,Tr[p].la,Tr[p].lb);
			Tr[p].la=Tr[p].lb=0;
		}
		void build(int p,int l,int r)
		{
			Tr[p].l=l,Tr[p].r=r,Tr[p].la=0,Tr[p].lb=0;
			if(l==r)
			{
				Tr[p].av=st[r],Tr[p].bv=pt[l],Tr[p].val=-MAX;
				return ;
			}
			int mid=(l+r)>>1;
			build(ls,l,mid),build(rs,mid+1,r);
			pushUp(p);
		}
		// a:0 b:1
		void modifyAdd(int p,int l,int r,bool op,ll v)
		{
			if(l<=Tr[p].l&&Tr[p].r<=r)
			{
				if(!op) Tr[p].av+=v,Tr[p].la+=v;
				else Tr[p].bv+=v,Tr[p].lb+=v;
				Tr[p].val+=v;
				return ;
			}
			pushDown(p);
			int mid=(Tr[p].l+Tr[p].r)>>1;
			if(l<=mid) modifyAdd(ls,l,r,op,v);
			if(mid<r) modifyAdd(rs,l,r,op,v);
			pushUp(p);
		}
		ll querySum(int p,int l,int r,bool op)
		{
			if(l>r) return -INF;
			if(l<=Tr[p].l&&Tr[p].r<=r) return op?Tr[p].bv:Tr[p].av;
			pushDown(p);
			int mid=(Tr[p].l+Tr[p].r)>>1;ll res=-INF;
			if(l<=mid) checkMax(res,querySum(ls,l,r,op));
			if(mid<r) checkMax(res,querySum(rs,l,r,op));
			return res;
		}
		ll res,pref;
		void query(int p,int l,int r)
		{
			if(l>r) return ;
			if(l<=Tr[p].l&&Tr[p].r<=r)
			{
				checkMax(res,Tr[p].av+pref),checkMax(res,Tr[p].val);
				checkMax(pref,Tr[p].bv);
				return ;
			}
			int mid=(Tr[p].l+Tr[p].r)>>1;
			pushDown(p);
			if(l<=mid) query(ls,l,r);
			if(mid<r) query(rs,l,r);
			return ;
		}
		#undef ls
		#undef rs
		ll query(int l,int r)
		{
			res=0,pref=-INF;
			query(1,l,r);
			return res;
		}
		void build(int l,int r)
		{
			Tr.resize((r-l+1)<<2);
			build(1,l,r);
		}
	};
	std::vector<OutBlock>Tr;
	void build()
	{
		val.build(Boc+2);Tr.resize(Boc+2);
		pt.resize(C+3),st.resize(C+3);
		for(int i=1;i<Boc;++i)
		{
			for(int j=1;j<=C;++j) pt[j]=pt[j-1]+a[j+Lst[i+1]-1];
			for(int j=C;j>=1;--j) st[j]=st[j+1]+a[j+Lst[i]-1];
			Tr[i].build(1,C);
		}
		for(int i=1;i<Boc;++i) val.modifyX(i,Tr[i].Tr[1].val);
	}
	void modifyX(int x,ll v)
	{
		int id=Bck[x];
		if(id>1) Tr[id-1].modifyAdd(1,trans(x),C,1,v-a[x]);
		if(id<Boc) Tr[id].modifyAdd(1,1,trans(x),0,v-a[x]);
		if(id>1) val.modifyX(id-1,Tr[id-1].Tr[1].val);
		if(id<Boc) val.modifyX(id,Tr[id].Tr[1].val);
		a[x]=v;
	}
	ll query(int l,int r)
	{
		ll res=-INF;
		if(Bck[l]==Bck[r]) return -INF;
		if(Bck[l]==Bck[r]-1)
		{
			int cl=trans(l),cr=trans(r),id=Bck[l];
			if(cl>cr) return Tr[id].querySum(1,cl,C,0)+Tr[id].querySum(1,1,cr,1);
			checkMax(res,Tr[id].querySum(1,1,cl-1,1)+Tr[id].querySum(1,cl,C,0));
			checkMax(res,Tr[id].querySum(1,1,cr,1)+Tr[id].querySum(1,cr+1,C,0));
			checkMax(res,Tr[id].query(cl,cr));
			return res;
		}
		checkMax(res,val.queryMax(Bck[l]+1,Bck[r]-2));
		checkMax(res,Tr[Bck[l]].query(trans(l),C));
		checkMax(res,Tr[Bck[r]-1].query(1,trans(r)));
		if(trans(l)!=1) checkMax(res,Tr[Bck[l]].querySum(1,1,trans(l)-1,1)+Tr[Bck[l]].querySum(1,trans(l),C,0));
		if(trans(r)!=C) checkMax(res,Tr[Bck[r]-1].querySum(1,1,trans(r),1)+Tr[Bck[r]-1].querySum(1,trans(r)+1,C,0));
		return res;
	}
}Out;
void debug(int l,int r)
{
	printf("query[%d,%d]:In:%lld Out:%lld\n",l,r,In.query(l,r),Out.query(l,r));
	return ;
}
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q,C);Boc=N/C;
	for(int i=1;i<=Boc;++i) Lst[i]=Rst[i-1]+1,Rst[i]=Lst[i]+C-1;
	if(Rst[Boc]<N){ ++Boc;Lst[Boc]=Rst[Boc-1]+1,Rst[Boc]=N; }
	for(int i=1;i<=Boc;++i) for(int j=Lst[i];j<=Rst[i];++j) Bck[j]=i;
	for(int i=1;i<=N;++i) read(a[i]);
	for(int i=N+1;i<=Lst[Boc]+C-1;++i) a[i]=-MAX;
	In.build();Out.build();
	for(int opt,ql;Q--;)
	{
		ll qr;read(opt,ql,qr);
		if(opt==1) In.modifyX(ql,qr),Out.modifyX(ql,qr);
		else write(std::max(0ll,std::max(In.query(ql,qr),Out.query(ql,qr))),'\n');
	}
	return 0;
}
/*

*/

这题不卡常，但有加强版。

题目简介

题目名称：

题目来源：

评测链接：https://www.luogu.com.cn/problem/P6780

形式化题意：同上题。

数据范围：

时空限制：

数据范围 ，时间 ，空间 ，肉眼可见卡常。

相关文章