CF-1024-E. 23 Kingdom

思路讲解

不难注意到，你所选择的区间之中，不允许出现两个区间相离的情况。

因为这两个区间如果变为相交的话，贡献的答案值一定更大。

由这个结论，那么新加入的区间的 $右端点>以前的所有左端点$，并且 $左端点<以前的所有右端点$，因此，所有的左右端点就会分居两端，因为起始的 $右端点>左端点$，新加入的 $右端点>以前的所有左端点$，左端点反之亦然。

那么贪心地，我们其实就是想让 $\sum{i_l}$ 最小， $\sum{i_r}$ 最大，那么左端点只要贪心地选择下标小的，右端点我们只要贪心地选择下标大的。

最后一个问题，就是当我们拿到一个序列，如 $2，2，3，4$，我们如何知道他是否可以映射到$1，2，3，4$ 只通过减法。

那么这个其实有一个小的 trick，如果说用加入元素的方法判断，大抵是要用到树状数组或者线段树，但如果使用删除的方法，就可以只用 set 实现。

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

源代码

// 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……）

其实我们的要求是没有任意两个区间相离，这个用线段树判断是有点问题的。

一个比较好的近似解

hack:
1
10
1 1 2 2 3 3 4 4 5 5
ans:
18

https://codeforces.com/contest/2101/submission/319732582

源代码

// 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;
}
/*

*/