题解：P14311 【MX-S8-T4】平衡三元组
Hisy
·
·
题解
前言
唯一一次以为可以场切的 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
这一个 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;
}
```