CF-1024-E. 23 Kingdom · znzryb
## 思路讲解
不难注意到，你所选择的区间之中，不允许出现两个区间相离的情况。
因为这两个区间如果变为相交的话，贡献的答案值一定更大。
由这个结论，那么新加入的区间的 $右端点>以前的所有左端点$，并且 $左端点<以前的所有右端点$，因此，所有的左右端点就会分居两端，因为起始的 $右端点>左端点$，新加入的 $右端点>以前的所有左端点$，左端点反之亦然。
那么贪心地，我们其实就是想让 $\sum{i_l}$ 最小， $\sum{i_r}$ 最大，那么左端点只要贪心地选择下标小的，右端点我们只要贪心地选择下标大的。
最后一个问题，就是当我们拿到一个序列，如 $2，2，3，4$，我们如何知道他是否可以映射到$1，2，3，4$ 只通过减法。
那么这个其实有一个小的 trick，如果说用加入元素的方法判断，大抵是要用到树状数组或者线段树，但如果使用删除的方法，就可以只用 set 实现。
```cpp
set<ll> st;
auto init=[&](){ // 初始化函数
st.clear();
FOR(i,0,N+1){
st.insert(i);
}
};
auto proc=[&](ll x){ // 处理函数
auto it=st.upper_bound(x);
--it;
if(*it==0){
return false;
}else{
st.erase(it);
return true;
}
};
```
## AC代码
[https://codeforces.com/contest/2101/submission/319792559](https://codeforces.com/contest/2101/submission/319792559)
::: 源代码
```cpp
// Problem: C. 23 Kingdom
// Contest: Codeforces - Codeforces Round 1024 (Div. 1)
// URL: https://codeforces.com/contest/2101/problem/C
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
do { \
std::cerr << #variable << ":"; \
for (const auto& elem : variable) { \
std::cerr << elem << " "; \
} \
std::cerr << "\n"; \
} while (0)
#define uniVec(var) \
do { \
sort(var.begin(),var.end());\
var.resize(unique(var.begin(),var.end())-var.begin());\
} while (0)
#define debugN(var,N) \
do{ \
std::cerr<<#var<<":"; \
FOR(i,1,N){ \
std::cerr<<var[i]<<" "; \
} \
std::cerr<<"\n"; \
}while(0)
#define debugMap(variable) \
do { \
std::cerr << #variable << ":\n"; \
for (const auto& pair : variable) { \
std::cerr << " " << pair.first << " => " << pair.second << "\n"; \
} \
std::cerr << std::endl; \
} while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,K,T,A[MAXN];
/*
根据题意，A就代表了B数组的上界。
1 5 2 8 4 1 4 2
1 4 2 3 3 1 4 2
*/
ll Pre[MAXN],Suf[MAXN],sufSum[MAXN],preSum[MAXN];
inline void solve(){
cin>>N;
FOR(i,0,N+5){
Pre[i]=0;
Suf[i]=0;
sufSum[i]=0;
preSum[i]=0;
}
set<ll> st;
auto init=[&](){
st.clear();
FOR(i,0,N+1){
st.insert(i);
}
};
auto proc=[&](ll x){
auto it=st.upper_bound(x);
--it;
if(*it==0){
return false;
}else{
st.erase(it);
return true;
}
};
init();
ll ind=0;
vector<ll> mp(N+5,0),mp2(N+5,0);
FOR(i,1,N){
cin>>A[i];
if(proc(A[i])){
++ind;
mp[ind]=mp[ind-1]+i;
}
Pre[i]=ind;
}
mp[0]=0;
ind=0;
init();
ROF(i,N,1){
if(proc(A[i])){
++ind;
mp2[ind]=mp2[ind-1]+i;
}
Suf[i]=ind;
}
#ifdef LOCAL
debugN(preSum,N);
debugN(sufSum,N);
debugN(Pre,N);
debugN(Suf,N);
DEBUG(mp);
DEBUG(mp2);
#endif
ll ans=0,up=0;
FOR(i,1,N-1){
up=max(up,min(Pre[i],Suf[i+1]));
}
#ifdef LOCAL
debug(up);
#endif
FOR(i,1,up){
ans=max(ans,mp2[i]-mp[i]);
}
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
#ifdef LOCAL
cerr << "---------------" << '\n';
#endif
}
// solve();
return 0;
}
/*
hack:
1
10
1 1 2 2 3 3 4 4 5 5
ans:
18
AC https://codeforces.com/contest/2101/submission/319792559
*/
```
:::
## 心路历程（WA，TLE，MLE……）
其实我们的要求是没有任意两个区间相离，这个用线段树判断是有点问题的。
一个比较好的近似解
```cpp
hack:
1
10
1 1 2 2 3 3 4 4 5 5
ans:
18
```
[https://codeforces.com/contest/2101/submission/319732582](https://codeforces.com/contest/2101/submission/319732582)
::: 源代码
```cpp
// Problem: C. 23 Kingdom
// Contest: Codeforces - Codeforces Round 1024 (Div. 1)
// URL: https://codeforces.com/contest/2101/problem/C
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
do { \
std::cerr << #variable << ":"; \
for (const auto& elem : variable) { \
std::cerr << elem << " "; \
} \
std::cerr << "\n"; \
} while (0)
#define uniVec(var) \
do { \
sort(var.begin(),var.end());\
var.resize(unique(var.begin(),var.end())-var.begin());\
} while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,K,T,A[MAXN];
ll posMatch[MAXN];
/*
根据题意，A就代表了B数组的上界。
1 5 2 8 4 1 4 2
1 4 2 3 3 1 4 2
*/
vector<ll> pos[MAXN];
struct Tree{
ll l,r,sum,add;
}tr[MAXN];
void build(ll node,ll l,ll r){
tr[node].sum=0,tr[node].add=0;
tr[node].l=l,tr[node].r=r;
if(tr[node].l>=tr[node].r) return;
tr[lson(node)].l=l;
tr[lson(node)].r=l+(r-l)/2;
tr[rson(node)].r=r;
tr[rson(node)].l=tr[lson(node)].r+1;
build(lson(node),tr[lson(node)].l,tr[lson(node)].r);
build(rson(node),tr[rson(node)].l,tr[rson(node)].r);
}
inline void pushdown(ll node){
if(tr[node].l==tr[node].r) return;
tr[lson(node)].sum+=tr[node].add*(tr[lson(node)].r-tr[lson(node)].l+1);
tr[rson(node)].sum+=tr[node].add*(tr[rson(node)].r-tr[rson(node)].l+1);
tr[lson(node)].add+=tr[node].add;
tr[rson(node)].add+=tr[node].add;
tr[node].add=0;
}
inline void pushup(ll node,ll val){
node>>=1;
while(node){
tr[node].sum+=val;
node>>=1;
}
}
inline bool isInter(ll l,ll r,ll l1,ll r2){
if(l>r2) return false;
if(r<l1) return false;
return true;
}
void add(ll node,ll l,ll r,ll val){
pushdown(node);
if(tr[node].l>=l && tr[node].r<=r){
ll num=tr[node].r-tr[node].l+1;
tr[node].sum+=val*num;
tr[node].add+=val;
pushup(node,val*num);
return;
}
if(isInter(tr[lson(node)].l,tr[lson(node)].r,l,r)) add(lson(node),l,r,val);
if(isInter(tr[rson(node)].l,tr[rson(node)].r,l,r)) add(rson(node),l,r,val);
}
ll query(ll node,ll l,ll r){
pushdown(node);
if(tr[node].l>=l && tr[node].r<=r){
return tr[node].sum;
}
ll res=0;
if(isInter(tr[lson(node)].l,tr[lson(node)].r,l,r)) res+=query(lson(node),l,r);
if(isInter(tr[rson(node)].l,tr[rson(node)].r,l,r)) res+=query(rson(node),l,r);
return res;
}
inline void solve(){
cin>>N;
FOR(i,0,N+5){
posMatch[i]=0;
}
FOR(i,1,N){
pos[i].clear();
}
FOR(i,1,N){
cin>>A[i];
pos[A[i]].pb(i);
}
build(1,1,N);
set<ll> st,stEd; // st保存的是现在可用的，stEd是已经用过的。
ll ans=0;
ROF(i,N,1){
st.insert(pos[i].begin(),pos[i].end());
if(SZ(st)>=2){
ll beg=*st.begin(),ed=*st.rbegin();
ll res=query(1,beg,ed);
if(res>0){ // 只要有区间相交，那么就取用最大区间即可
add(1,beg,ed,1);
ans+=ed-beg;
stEd.insert(beg); // 已经用过，在已经用过中增加
stEd.insert(ed);
posMatch[beg]=ed;
posMatch[ed]=beg;
st.erase(st.begin()); // 已经用过了，在可用中删除
st.erase(--st.end());
}else{ // 没有与其他区间相交，那么就需要上一点手段了
if(SZ(stEd)>=2){ // 理论上来说stEd不是空的就是
// stEd不是空的，那我们就需要让区间们相交
ll mnEd=*stEd.begin(),mxEd=*stEd.rbegin();
ll len1=ed-mnEd,len2=mxEd-beg,oldLen1=posMatch[mnEd]-mnEd,
oldLen2=mxEd-posMatch[mxEd];
ll eff1=len1-oldLen1,eff2=len2-oldLen2;
if(eff1>eff2 && eff1>0){
add(1,mnEd,ed,1);
st.erase(ed);
ans+=eff1;
stEd.erase(posMatch[mnEd]);
st.insert(posMatch[mnEd]);
posMatch[mnEd]=ed;
posMatch[ed]=mnEd;
stEd.insert(ed);
}else if(eff2>0){
// 有一段重复加了？没关系，这个值只是表示这段区间有东西。
add(1,beg,mxEd,1);
st.erase(beg);
ans+=eff2;
stEd.erase(posMatch[mxEd]);
st.insert(posMatch[mxEd]);
posMatch[mxEd]=beg;
posMatch[beg]=mxEd;
stEd.insert(beg);
}
}else{ // stEd是空的，和res>0一样处理
add(1,beg,ed,1);
ans+=ed-beg;
stEd.insert(beg); // 已经用过，在已经用过中增加
stEd.insert(ed);
posMatch[beg]=ed;
posMatch[ed]=beg;
st.erase(st.begin()); // 已经用过了，在可用中删除
st.erase(--st.end());
}
}
}else if(SZ(st)==1){
ll ed=*st.begin(),beg=*st.begin();
if(SZ(stEd)>=2){ // 理论上来说stEd不是空的就是
// stEd不是空的，那我们就需要让区间们相交
ll mnEd=*stEd.begin(),mxEd=*stEd.rbegin();
ll len1=ed-mnEd,len2=mxEd-beg,oldLen1=posMatch[mnEd]-mnEd,
oldLen2=mxEd-posMatch[mxEd];
ll eff1=len1-oldLen1,eff2=len2-oldLen2;
if(eff1>eff2 && eff1>0){
add(1,mnEd,ed,1);
st.erase(ed);
ans+=eff1;
stEd.erase(posMatch[mnEd]);
st.insert(posMatch[mnEd]);
posMatch[mnEd]=ed;
posMatch[ed]=mnEd;
stEd.insert(ed);
}else if(eff2>0){
// 有一段重复加了？没关系，这个值只是表示这段区间有东西。
add(1,beg,mxEd,1);
st.erase(beg);
ans+=eff2;
stEd.erase(posMatch[mxEd]);
st.insert(posMatch[mxEd]);
posMatch[mxEd]=beg;
posMatch[beg]=mxEd;
stEd.insert(beg);
}
}
}
}
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
#ifdef LOCAL
cerr << "---------------" << '\n';
#endif
}
// solve();
return 0;
}
/*
*/
```
:::