题解：P14311 【MX-S8-T4】平衡三元组

前言

唯一一次以为可以场切的 T4，但是过程中 push_up 把懒标记抹掉了，又少判断了一种情况，查询又忘记 push_down 了，最终把正解 Hack 掉了。暴力的 push_down 又常数太大，两秒多的代码跑到了四秒，赛后还卡了好久的常……

（论写法的重要性）

分析

Subtask 1

枚举每一个区间的

x,y,z

，复杂度

\operatorname{O}(q\times n^3)

。

Subtask 2

考虑固定一个点。考虑到不等式可以变形成

2\times B_y\le B_x+B_z

，发现

x

和

z

其实等价，所以考虑固定点

y

，左边寻找最大的

x

，右边寻找最大的

y

。

这个听讲评的时候发现讲评用的是前缀后缀

\max

，但是我的代码用的是线段树，然后 push_down 写法常数太大被卡掉了。

Subtask 3

A_i\le 20

，

o=1

，也就是说没有修改操作。

这一个 Subtask 我一开始觉得是离线算法（莫队，整体二分），里面我觉得最正常的其实是莫队。然后看时限四秒，我觉得还是值得一试的。

考虑维护

id_i

表示

i

这个值里面的下标。

发现

这个是赛后看讲评才看到的，

A_x,A_y,A_z

里面必包含这个区间的最大值。

若 $A_y$ 为最大值，则必须要有 $A_x$ 和 $A_z$ 也为最大值。
否则，最大值要么在 $y$ 左，要么在 $y$ 右，不论在哪一边，都会变成 $A_x$ 或者 $A_z$ 。

所以，从大往小遍历每一个

id

，找出最大值（若最大值的个数大于等于三则直接返回），分别对该值为

A_x

和

A_y

计算贡献。

由于两种方法都是一样的，所以这里只说一种：

已知 $A_x$ 为最大值，那么需要找的就是右边第一个可以作为 $y$ 或者 $z$ 的次大值，并考虑两种情况：
作为 $y$ 时，则需要往右找 $z$ ，并判断。如果判断成功，则直接返回。
作为 $z$ 时，在里面 $[x+1,z-1]$ 里面找区间最大值贡献。

这就是这一个方法。虽然还没有写代码，也没有验证正确性，但不过这确实是通向正解的道路。

Subtask 4

不好意思，不知道怎么在 Subtask 3 上面继续优化。

讲评里面的说法好像是维护前

\log

大值也可以，那么也说得过去，如果有大佬能够听明白希望能够私信本蒟蒻讲一下。

Subtask 5

A_i

单调不减，就是说选的数一定为

A_x,A_{x+1},A_z

。其中，

A_z

一定为右端点，所以只需要考虑

A_x

就可以了。而且，发现我们只要取最靠近

r

的就好了。

既然有

2\times A_x\le A_{x-1}+A_r

，那么直接先选择

x=r-1

，尝试这一种。

如果成功，则直接返回。
否则，继续尝试？

尝试的次数可能很多，这是我当时想的。但不过看到了不等式之后，发现最坏情况有有

A_{x-1}> 2\times A_x-A_r

，

A_{x-2}>2\times A_{x-1}-A_r>4\times A_x-3\times A_r

。

由于

A_i

最大

10^9+q\times x_{max}

，不会超过

3\times 10^9

，最大只会失败

\log

次，每一次失败往左移就可以了。

到了这里基本和正解无异了。

Subtask 6 & 7

不太懂设置这个的意义是什么，可能是用来分块或者

q\log^2n\log V

的。

Subtask 8

继承 Subtask 3 和 Subtask 5 的思想，发现可以优化成这个样子：

每一次失败跳掉左边的次大值。
因为 Subtask 5 有 $x$ 和 $y$ 必定相邻，所以还要考虑 $x$ 和 $z$ 之间取一个最大值判断，具体参考样例。

证明：

每一次失败取较左的最大值，是因为取左边非最大值不仅可能值域比这个小，还有可能使得式子不成立。值域变大的情况可以由左边最大值的左边最大值一直递归包含，固考虑每一个最大值的断点即可。
在 $x$ 和 $z$ 中只需要考虑取最大值即可，不用考虑因为最大值使得其不成立的情况。令 $y$ 为 $(x,z)$ 中最大值，即使有 $2\times A_y>A_x+A_z$ ，也可能会有 $x$ 前一次递归时有 $y$ 作为该 $x$ 的情况并已经计算了贡献。

所以查询时间复杂度为

\log V\log n

，修改复杂度为

\log n

，总时间复杂度有最劣

q\log V\log n

。

CPP

#include<stdio.h>
#include<ctype.h>
#define MAXN 1000010
#define lson root<<1
#define rson root<<1|1
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define Opt optimize
#define tar target
#pragma GCC Opt(3)
#pragma GCC tar("avx")
#pragma GCC Opt("Ofast")
#pragma GCC Opt("inline")
#pragma GCC Opt("-fgcse")
#pragma GCC Opt("-fgcse-lm")
#pragma GCC Opt("-fipa-sra")
#pragma GCC Opt("-ftree-pre")
#pragma GCC Opt("-ftree-vrp")
#pragma GCC Opt("-fpeephole2")
#pragma GCC Opt("-ffast-math")
#pragma GCC Opt("-fsched-spec")
#pragma GCC Opt("unroll-loops")
#pragma GCC Opt("-falign-jumps")
#pragma GCC Opt("-falign-loops")
#pragma GCC Opt("-falign-labels")
#pragma GCC Opt("-fdevirtualize")
#pragma GCC Opt("-fcaller-saves")
#pragma GCC Opt("-fcrossjumping")
#pragma GCC Opt("-fthread-jumps")
#pragma GCC Opt("-funroll-loops")
#pragma GCC Opt("-fwhole-program")
#pragma GCC Opt("-freorder-blocks")
#pragma GCC Opt("-fschedule-insns")
#pragma GCC Opt("inline-functions")
#pragma GCC Opt("-ftree-tail-merge")
#pragma GCC Opt("-fschedule-insns2")
#pragma GCC Opt("-fstrict-aliasing")
#pragma GCC Opt("-fstrict-overflow")
#pragma GCC Opt("-falign-functions")
#pragma GCC Opt("-fcse-skip-blocks")
#pragma GCC Opt("-fcse-follow-jumps")
#pragma GCC Opt("-fsched-interblock")
#pragma GCC Opt("-fpartial-inlining")
#pragma GCC Opt("no-stack-protector")
#pragma GCC Opt("-freorder-functions")
#pragma GCC Opt("-findirect-inlining")
#pragma GCC Opt("-fhoist-adjacent-loads")
#pragma GCC Opt("-frerun-cse-after-loop")
#pragma GCC Opt("inline-small-functions")
#pragma GCC Opt("-finline-small-functions")
#pragma GCC Opt("-ftree-switch-conversion")
#pragma GCC Opt("-foptimize-sibling-calls")
#pragma GCC Opt("-fexpensive-optimizations")
#pragma GCC Opt("-funsafe-loop-optimizations")
#pragma GCC Opt("inline-functions-called-once")
#pragma GCC Opt("-fdelete-null-pointer-checks")
#pragma GCC Opt(2)
typedef long long ll;
const ll INF=1e17;
struct node{
	int tag,pos;
	ll maxi;
	node(int pos=0,ll maxi=-INF){
		this->tag=0; 
		this->pos=pos;
		this->maxi=maxi;
	}
}tree[MAXN<<2];
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
inline ll max(const ll a,const ll b){
	return a>b?a:b;
}
inline int read(){
	register int res=0,f=1;
	register char c=getchar();
	while(!isdigit(c)){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(isdigit(c)){
		res=(res<<1)+(res<<3)+(c^48);
		c=getchar();
	}
	return res*f;
}
inline node merge(const node &a,const node &b){
	if(a.maxi>b.maxi){
		return a;
	}
	return b;
}
inline void push_up(int root){
	const int tag=tree[root].tag;
	tree[root]=merge(tree[lson],tree[rson]);
	tree[root].tag=tag;
}
inline void push_down(int root){
	tree[lson].tag+=tree[root].tag;
	tree[rson].tag+=tree[root].tag;
	tree[lson].maxi+=tree[root].tag;
	tree[rson].maxi+=tree[root].tag;
	tree[root].tag=0;
//	printf("%d %d\n",tree[lson].maxi,tree[rson].maxi);
}
inline void build(int root,int l,int r){
	if(l==r){
		tree[root].maxi=read();
		tree[root].pos=l;
		return;
	}
	const int mid=(l+r)>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	push_up(root);
}
inline void change(const int root,const int l,const int r,const int L,const int R,const int tag){
	if(L<=l&&r<=R){
		tree[root].tag+=tag;
		tree[root].maxi+=tag;
		return;
	}
	push_down(root);
	const int mid=(l+r)>>1; 
	if(L<=mid){
		change(lson,l,mid,L,R,tag);
	}
	if(mid<R){
		change(rson,mid+1,r,L,R,tag);
	}
	push_up(root);
} 
inline node query(int root,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return tree[root];
	}
//	printf("%d %d\n",l,r);
	push_down(root);
	const int mid=(l+r)>>1;
	if(L>mid){
		return query(rson,mid+1,r,L,R);
	}
	if(mid>=R){
		return query(lson,l,mid,L,R);
	}
	return merge(query(lson,l,mid,L,R),query(rson,mid+1,r,L,R));
}
inline void print(const int root,const int l,const int r){
	if(l==r){
		printf("[%d]:%lld\n",l,tree[root].maxi);
		return;
	}
	push_down(root); 
	printf("[%d,%d]:%lld\n",l,r,tree[root].maxi);
	const int mid=(l+r)>>1;
	print(lson,l,mid);
	print(rson,mid+1,r);
}
int main(){
	const int n=read();
	register int q=read();
	build(1,1,n);
	while(q--){
		const int opt=read(),l=read(),r=read();
		if(opt==1){
			ll ans=-INF;
			node x,z=query(1,1,n,l,r);
			node y=node(z.pos,INF);
			while(y.pos>l){
				x=query(1,1,n,l,y.pos-1);
				if(x.maxi+z.maxi>=(y.maxi<<1)){
					ans=max(ans,x.maxi+y.maxi+z.maxi);
					break;
				}
				if(x.pos<y.pos-1){
					ans=max(ans,x.maxi+z.maxi+query(1,1,n,x.pos+1,y.pos-1).maxi);
				}
				y=x;
			}
			x=z;
			y=node(x.pos,INF);
			while(y.pos<r){
				z=query(1,1,n,y.pos+1,r);
				if(x.maxi+z.maxi>=(y.maxi<<1)){
					ans=max(ans,x.maxi+y.maxi+z.maxi);
					break;
				}
				if(y.pos<z.pos-1){
					ans=max(ans,x.maxi+z.maxi+query(1,1,n,y.pos+1,z.pos-1).maxi);
				}
				y=z;
			}
			if(ans==-INF){
				puts("No");
			}else{
				printf("%lld\n",ans);
			}
		}else{
			change(1,1,n,l,r,read());
		}
//		print(1,1,n);
//		putchar('\n');
	}
	return 0;
}

题解：P14311 【MX-S8-T4】平衡三元组

文章操作

前言

分析

Subtask 1

Subtask 2

Subtask 3

发现

Subtask 4

Subtask 5

Subtask 6 & 7

Subtask 8

相关推荐

评论

题解：P14311 【MX-S8-T4】平衡三元组