题目
思路来源
hhoppitree代码 + 官方题解
题解
注意到最大值一定会被取到，
对于最小值固定的话，对于1 2 3 4 5的连续段，要么贪心地取1 3 5，要么取2 4
如果最大值被包含在1 3 5里显然取1 3 5，否则换成2 4一定能取到最大值，是不劣的，
所以并查集维护每段奇数位置都取/偶数位置都取能否取到最大值
从大到小枚举最小值，把数逐渐加入并查集，实际相当于维护若干段链表
如果存在一个连续段，使得选这个连续段中较多的那一半（奇数唯一，偶数均可）能取到最大值
则答案不需要减1，否则为了取到最大值需要反选，将答案减1
代码1（并查集）
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int t,n,a[N],par[N],sz[N],x[N],c,mx,can,cnt,ans;
vector<int>pos[N];
bool ok[2][N];
int find(int x){return par[x]==x?x:par[x]=find(par[x]);
}
bool has(int x){if(sz[x]&1)return ok[0][x];return ok[0][x] || ok[1][x];
}
void init(int x){par[x]=x;sz[x]=1;if(a[x]==mx)ok[0][x]=1;can+=has(x);cnt++;
}
void op(int x,int v){can+=v*has(x);cnt+=v*(sz[x]+1)/2;
}
void merge(int x,int y){//x<yif(!par[x] || !par[y])return;x=find(x),y=find(y);if(x==y)return;//printf("x:%d y:%d\n",x,y);op(x,-1),op(y,-1);int z=sz[x]&1;ok[0][x]|=ok[z][y];ok[1][x]|=ok[z^1][y];sz[x]+=sz[y];op(x,1);par[y]=x;
}
int main(){sci(t);while(t--){sci(n);ans=mx=c=cnt=can=0;rep(i,1,n){sci(a[i]);x[c++]=a[i];par[i]=0;sz[i]=0;ok[0][i]=ok[1][i]=0;mx=max(mx,a[i]);pos[i].clear();}sort(x,x+c);c=unique(x,x+c)-x;rep(i,1,n){int v=lower_bound(x,x+c,a[i])-x+1;pos[v].pb(i);}per(i,c,1){if(!SZ(pos[i]))continue;for(auto &v:pos[i]){init(v);if(v)merge(v-1,v);if(v+1<=n)merge(v,v+1);}//printf("i:%d x:%d mx:%d can:%d cnt:%d\n",i,x[i-1],mx,can,cnt);ans=max(ans,x[i-1]+mx+cnt-(!can));}pte(ans);}return 0;
}代码2（动态dp 线段树维护状态合并）
不用观察到任何性质，像维护动态dp那样，直接暴力合并
f[x][i][j][k]表示线段树的x节点，最大值有没有取到，左端点有没有选，右端点有没有选，
相当于有8个状态，线段树维护状态合并即可
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")using namespace std;const int N = 2e5 + 5;int a[N], f[1 << 19][2][2][2];void upd(int k, int l) {for (int i = 0; i < 2; ++i) {for (int j = 0; j < 2; ++j) {for (int K = 0; K < 2; ++K) {f[k][i][j][K] = -1e9;}}}f[k][0][0][0] = 0;if (a[l] < 0) return;f[k][0][1][1] = 1;f[k][1][1][1] = a[l] + 1;
}void pushup(int k) {for (int i = 0; i < 2; ++i) {for (int j = 0; j < 2; ++j) {for (int K = 0; K < 2; ++K) {f[k][i][j][K] = -1e9;}}}for (int a = 0; a < 2; ++a) {for (int b = 0; b < (a ? 1 : 2); ++b) {for (int i = 0; i < 2; ++i) {for (int j = 0; j < 2; ++j) {for (int x = 0; x < (j ? 1 : 2); ++x) {for (int y = 0; y < 2; ++y) {f[k][a + b][i][y] = max(f[k][a + b][i][y], f[k << 1][a][i][j] + f[k << 1 | 1][b][x][y]);}}}}}}
}void build(int k, int l, int r) {if (l == r) {upd(k, l);return;}int mid = (l + r) >> 1;build(k << 1, l, mid);build(k << 1 | 1, mid + 1, r);pushup(k);
}void update(int k, int l, int r, int x) {if (l == r) {upd(k, l);return;}int mid = (l + r) >> 1;if (x <= mid) update(k << 1, l, mid, x);else update(k << 1 | 1, mid + 1, r, x);pushup(k);
}signed main() {int T; scanf("%d", &T);while (T--) {int n; scanf("%d", &n);vector< pair<int, int> > vec;for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), vec.push_back({a[i], i});build(1, 1, n);sort(vec.begin(), vec.end());int res = 0;for (auto [x, y] : vec) {res = max(res, x + max({f[1][1][0][0], f[1][1][0][1], f[1][1][1][0], f[1][1][1][1]}));a[y] = -1e7;update(1, 1, n, y);}printf("%d\n", res);}return 0;
}
