Reincarnation

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

P6780 [Ynoi2009] pmrllcsrms

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

首杀。

题目简介

题目名称：

题目来源：

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

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

  1. 将 ；
  2. 求：
    。

数据范围：

时空限制：

先做不卡常版。

这个查询看起来很头大，但实际上就是在 内找到一个长度不超过 的子区间，使其区间和最大。

做 ，那就得分块！我们将序列分为很多个长度为 的段，则答案的贡献就在一个段内或者两个段之间。

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

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

以上是不卡常情况下的思路。至此，你已经口胡过了这道题。

现在我们来卡常，非加强版我就做了 ，码了 9k，而这道题呢？

至今未过。不要举办我卡评测。

对于玄学部分：

  • 多开 inline，但是 register 要谨慎考虑之后再开；
  • 快读快输，超快的那种；
  • 能不开 long long 尽量不开；
  • 能尽量不递归，就递推；
  • 能逻辑运算尽量不 if/else；
  • 能压到一个 for 里就尽量不开多个 for；
  • 尽量减少运算。
  • 可以尝试手写 stl。
  • struct 里写构造好像会慢一点（存疑。
  • 每个人最快的 C++ 版本不同，自己试试。

对于正经操作：

容易知道 的常数要比普通线段树小很多，所以对于维护区间最大值单点修改的这种就可以写 。而在开了 后 stl 与手写差距不大，且这道题还卡空间，所以线段树都可以用 std::vector 来实现。

而对于合并区间最大子段和这种，能单边递归就不要 merge，实在不行可以改 ，但是会多出一个 std::queue 和 std::stack，所以似乎并没有快多少。

Maybe 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
// ----- Eternally question-----
// Problem: P6780 [Ynoi2009] pmrllcsrms
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6780
// Memory Limit: 512 MB
// Time Limit: 4500 ms
// Written by: Eternity
// Time: 2023-01-29 12:05:12
// ----- Endless solution-------

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#define re register
typedef long long ll;
namespace FIO
{
	const int Len=1<<15;
    int l=0;
    char buf[Len|100],out[Len|100],*S,*E;
    #define gh() (S==E?E=(S=buf)+fread(buf,1,Len,stdin),(S==E?EOF:*S++):*S++)
    inline void flus(){ fwrite(out,1,l,stdout),l=0; }
    struct Fluser{ ~Fluser(){ flus(); } }fluser;
    inline void putc(char x)
    {
        out[l++]=x;
        if(!(l^Len)) flus();
    }
    template<typename T>
    inline void read(T &x)
    {
        char ch=gh(),t=0;
        for(;ch<'0'||ch>'9';ch=gh()) t|=ch=='-';
        for(x=0;ch>='0'&&ch<='9';ch=gh()) x=(x<<3)+(x<<1)+(ch^48);
        if(t) x=-x;
    }
    template<typename T>
    inline void write(T x)
    {
        if(x<0) x=-x,putc('-');
        static char buf_num[20];int n=0;
        do{ buf_num[n++]=x%10+48; }while(x/=10);
        while(n--) putc(buf_num[n]);
	}
    inline void write(char c){ putc(c); }
    inline void write(const char *s){ while(*s) putc(*s++); }
    template<typename T,typename ...Args>
	void read(T &x,Args &...args){ read(x),read(args...); }
    template<typename T,typename ...Args>
	void write(T x,Args ...args){ write(x),write(args...); }
    #undef gh
}
using FIO::read;
using FIO::write;
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=2e6+10;
const ll INF=1e18,MAX=1e10;
int N,Q,C;
ll a[MAXN];
int Lst[MAXN],Rst[MAXN],Bck[MAXN],Boc,trans[MAXN];
struct SegmentIn
{
	struct ZkwSegment
	{
		int Length;
		std::vector<ll>val;
		inline void pushUp(int p)
		{ val[p]=std::max(val[p<<1],val[p<<1|1]); }
		inline void build(int n)
		{
			Length=1;
			while(Length<=Boc+1) Length<<=1;
			val.resize(Length<<1);	
		}
		inline void modifyX(int x,ll v)
		{
			val[x+Length]=v;
			for(int i=(x+Length)>>1;i;i>>=1) pushUp(i);
		}
		inline 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 St
		{
			ll lx,rx,val,sum;
			St(ll lx=0,ll rx=0,ll val=0,ll sum=0):
				lx(lx),rx(rx),val(val),sum(sum){}
		};
		std::vector<St>Tr;
		std::queue<int>pre;
		std::stack<int>suf;
		inline St merge(St ls,St rs)
		{
			St p;
			p.lx=std::max(ls.lx,ls.sum+rs.lx),p.rx=std::max(rs.rx,rs.sum+ls.rx);
			p.val=std::max(std::max(ls.val,rs.val),ls.rx+rs.lx),p.sum=ls.sum+rs.sum;
			return p;
		}
		inline void build(int l,int r)
		{
			int n=r-l+1;Len=1;
			while(Len<=n+1) Len<<=1;
			Tr.resize(Len<<1);
			for(int i=1;i<=n;++i) Tr[i+Len]=St(a[i+l-1],a[i+l-1],a[i+l-1],a[i+l-1]);
			for(int i=Len-1;i;--i) Tr[i]=merge(Tr[i<<1],Tr[i<<1|1]);
		}
		inline void modifyX(int x,int v)
		{
			Tr[x+Len]=St(v,v,v,v);
			for(int i=(x+Len)>>1;i;i>>=1) Tr[i]=merge(Tr[i<<1],Tr[i<<1|1]);
		}
		inline ll querySum(int l,int r)
		{
			for(l+=Len-1,r+=Len+1;l^r^1;l>>=1,r>>=1)
			{
				if(~l&1) pre.push(l^1);
				if(r&1) suf.push(r^1);
			}
			St res=St(-INF,-INF,-INF,0);
			while(!pre.empty())
			{
				res=merge(res,Tr[pre.front()]);
				pre.pop();
			}
			while(!suf.empty())
			{
				res=merge(res,Tr[suf.top()]);
				suf.pop();
			}
			return res.val;
		}
		inline ll query()
		{ return querySum(1,Len); }
	};
	std::vector<InBlock>Tr;
	inline 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);
	}
	inline void modifyX(int x,int v)
	{
		Tr[Bck[x]].modifyX(trans[x],v);
		val.modifyX(Bck[x],Tr[Bck[x]].query());
	}
	inline 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;
ll pt[MAXN],st[MAXN];
struct SegmentOut
{
	struct ZkwSegment
	{
		int Length;
		std::vector<ll>val;
		inline void pushUp(int p)
		{ val[p]=std::max(val[p<<1],val[p<<1|1]); }
		inline void build(int n)
		{
			Length=1;
			while(Length<=Boc+1) Length<<=1;
			val.resize(Length<<1);	
		}
		inline void modifyX(int x,ll v)
		{
			val[x+Length]=v;
			for(int i=(x+Length)>>1;i;i>>=1) pushUp(i);
		}
		inline 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,la,lb;ll av,bv,val; };
		std::vector<St>Tr;
		#define ls (p<<1)
		#define rs (p<<1|1)
		inline 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);
		}
		inline void upDate(int p,int a,int b)
		{
			Tr[p].av+=a,Tr[p].la+=a;
			Tr[p].bv+=b,Tr[p].lb+=b;
			Tr[p].val+=a+b;
			return ;
		}
		inline 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;
		}
		inline 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
		inline void modifyAdd(int p,int l,int r,bool op,int 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;
		inline 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
		inline ll query(int l,int r)
		{
			res=0,pref=-INF;
			query(1,l,r);
			return res;
		}
		inline void build(int l,int r)
		{
			Tr.resize((r-l+1)<<2);
			build(1,l,r);
		}
	};
	std::vector<OutBlock>Tr;
	inline void build()
	{
		val.build(Boc+2);Tr.resize(Boc+2);
		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.val[i+val.Length]=Tr[i].Tr[1].val;
		for(int i=val.Length-1;i;--i) val.pushUp(i);
	}
	inline void modifyX(int x,int v)
	{
		int id=Bck[x];
		(id>1)&&(Tr[id-1].modifyAdd(1,trans[x],C,1,v-a[x]),val.modifyX(id-1,Tr[id-1].Tr[1].val),1);
		(id<Boc)&&(Tr[id].modifyAdd(1,1,trans[x],0,v-a[x]),val.modifyX(id,Tr[id].Tr[1].val),1);
		a[x]=v;
	}
	inline 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]));
		(trans[l]!=1)&&(checkMax(res,Tr[Bck[l]].querySum(1,1,trans[l]-1,1)+Tr[Bck[l]].querySum(1,trans[l],C,0)));
		(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;
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<=N;++i) Bck[i]=(i-1)/C+1,read(a[i]),a[i+N]=-MAX,trans[i]=i-Lst[Bck[i]]+1;
	In.build();Out.build();
	for(int opt,ql,qr;Q--;)
	{
		read(opt,ql,qr);
		opt==1?(In.modifyX(ql,qr),Out.modifyX(ql,qr)):write(std::max(0ll,std::max(In.query(ql,qr),Out.query(ql,qr))),'\n');
	}
	return 0;
}
/*

*/
相关文章