Codeforces Round 915 (Div. 2) A-F(补题&补写法)

发布时间:2023年12月18日

A.??Constructive Problems(签到)

题解

输出max(x,y)

t = int(input())
for _ in range(t):
    u, v = map(int,input().split())
    print(max(u,v))

B.?Begginer's Zelda(统计树的叶子)

题解

输出叶子个数除以2上取整

// Problem: B. Begginer's Zelda
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
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<ll,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 scll(a) scanf("%lld",&(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=1e5+10;
int t,n,u,v;
vector<int>e[N];
void sol(){
	sci(n);
	rep(i,1,n)e[i].clear();
	int lf=0;
	rep(i,2,n){
		sci(u),sci(v);
		e[u].pb(v);e[v].pb(u);
	}
	rep(i,1,n)lf+=(SZ(e[i])==1);
	pte((lf+1)/2);
}
int main(){
	sci(t); // t=1
	while(t--){
		sol();
	}
	return 0;
}

C.?Largest Subsequence(模拟)

题解

注意到初始序列里的字典序最大的子序列是非严格递减的,记为x

并且循环移位一个字母之后,后面变成的子序列也只是x去掉最后一个字母的子序列

所以最终操作完就是相当于将x排序(将x反转)

特别地,当x只剩全由一种字母组成时,无需再操作了,所以判一下和第一个字母相同的个数

// Problem: C. Largest Subsequence
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
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<ll,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 scll(a) scanf("%lld",&(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,suf[N];
void sol(){
	string s,ss;
	vector<int>pos;
	sci(n);
	cin>>s;
	ss=s;
	sort(ss.begin(),ss.end());
	if(s==ss){
		puts("0");
		return;
	}
	suf[n]=0;
	int cnt=0;
	per(i,n-1,0){
		int v=s[i]-'a';
		suf[i]=max(v,suf[i+1]);
	}
	rep(i,0,n-1){
		int v=s[i]-'a';
		if(v==suf[i]){
			pos.pb(i);
			if(suf[pos[0]]==v)cnt++;
		}
	}
	int sz=SZ(pos);
	rep(i,0,sz/2-1)swap(s[pos[i]],s[pos[sz-1-i]]);
	//cout<<"s:"<<s<<" ss:"<<ss<<endl;
	if(s==ss)pte(sz-cnt);
	else puts("-1");
}
int main(){
	sci(t); // t=1
	while(t--){
		sol();
	}
	return 0;
}

D.?Cyclic MEX(线段树/单调栈)

题意

给定长为n(n<=1e6)的一个排列p,

对前缀依次求mex得到数组a,再对a内所有值求和,得到代价cost

求p的所有循环排列中,cost最大时对应的值

t(t<=1e5)组样例,sumn不超过1e6

题解

先循环移位,使得0在最后,

然后每把一个数字v拽到最后,就会新增一个mex值n

并且会使得之前大于v的mex值变为v,所以可以线段树区间覆盖和单点修改区间加

倘若注意到mex是非严格单调递增的,可能存在每个值对应一段的情形,

那么可以向左不断弹栈弹出大于v的所有位置,

具体来说维护一个单调栈,放入(值,值对应的一段区间的最右位置)

赛后补的(单调栈)

注意到一定是小的值把大的值踢出来,

所以维护一个单调栈,弹出和置入的时候算贡献改变量

// Problem: D. Cyclic MEX
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
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<ll,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 scll(a) scanf("%lld",&(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=1e6+10;
P stk[N];
int t,n,a[N],c;
void sol(){
	sci(n);
	int st;
	rep(i,0,n-1){
		sci(a[i]);
		if(a[i]==0)st=(i+1)%n;
	}
	stk[c=0]=P(0,0);
	//stk[++c]=P(n,1);
	ll ans=n,now=0;
	rep(i,0,n-1){
		int r=i+1;
		while(c && a[st]<=stk[c].fi){
			now-=1ll*stk[c].fi*(stk[c].se-stk[c-1].se);
			c--;
		}
		now+=1ll*a[st]*(r-stk[c].se);
		stk[++c]=P(a[st],r);
		ans=max(ans,now+n);
		st=(st+1)%n;
	}
	ptlle(ans);
}
int main(){
	sci(t); // t=1
	while(t--){
		sol();
	}
	return 0;
}

赛中写的(线段树)

线段树对应单点修改,区间覆盖,区间询问求和

// Problem: D. Cyclic MEX
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
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<ll,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 scll(a) scanf("%lld",&(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=1e6+10;
struct segtree2{
	int n;
	struct node{int l,r,c,w;ll v;}e[N<<2];
	#define l(p) e[p].l
	#define r(p) e[p].r
	#define v(p) e[p].v
	#define w(p) e[p].w
	#define c(p) e[p].c
	void up(int p){
		v(p)=v(p<<1)+v(p<<1|1);
		w(p)=max(w(p<<1),w(p<<1|1));
	}
	void bld(int p,int l,int r){
		l(p)=l;r(p)=r;
		if(l==r){v(p)=c(p)=w(p)=0;return;}
		int mid=l+r>>1;
		bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);
		up(p);
	}
	void psd(int p){
		if(c(p)){
			v(p<<1)=1ll*(r(p<<1)-l(p<<1)+1)*c(p);
			c(p<<1)=c(p);
			w(p<<1)=c(p);
			v(p<<1|1)=1ll*(r(p<<1|1)-l(p<<1|1)+1)*c(p);		
			c(p<<1|1)=c(p);
			w(p<<1|1)=c(p);
			c(p)=0; 
		}
	}
	void init(int _n){n=_n;bld(1,1,n);}
	void chg(int p,int x,int v){
		if(l(p)==r(p)){v(p)=w(p)=v;return;}
		int mid=l(p)+r(p)>>1;
		psd(p);
		chg(p<<1|(x>mid),x,v);
		up(p);
	}
	void cov(int p,int ql,int qr,int v){
		if(ql<=l(p)&&r(p)<=qr){
			v(p)=1ll*(r(p)-l(p)+1)*v;
			c(p)=v;
			w(p)=v;
			return;
		}
		psd(p);
		int mid=l(p)+r(p)>>1;
		if(ql<=mid)cov(p<<1,ql,qr,v);
		if(qr>mid)cov(p<<1|1,ql,qr,v);
		up(p);
	}
	ll cnt(int p,int ql,int qr){
		if(ql<=l(p)&&r(p)<=qr)return v(p);
		int mid=l(p)+r(p)>>1;
		ll res=0;
		psd(p);
		if(ql<=mid)res+=cnt(p<<1,ql,qr);
		if(qr>mid)res+=cnt(p<<1|1,ql,qr);
		return res;
	}
	int f(int p,int v){
		if(w(p)<=v)return -1;
		if(l(p)==r(p))return l(p);
		if(w(p<<1)>v)return f(p<<1,v);
		return f(p<<1|1,v);
	}
}seg;
int t,n,a[N];
void sol(){
	sci(n);
	int st;
	rep(i,0,n-1){
		sci(a[i]);
		if(a[i]==0)st=(i+1)%n;
	}
	seg.init(n);
	seg.chg(1,1,n);
	ll ans=n;
	rep(i,0,n-1){
		int r=i+1;
		int p=seg.f(1,a[st]);
		seg.cov(1,p,r,a[st]);
		seg.chg(1,r+1,n);
		ans=max(ans,seg.cnt(1,1,r+1));
		st=(st+1)%n;
	}
	ptlle(ans);
}
int main(){
	sci(t); // t=1
	while(t--){
		sol();
	}
	return 0;
}

E.?One-X(递推/记忆化搜索/bfs)

题意

给一棵[1,n](n<=1e18)完整建好的线段树,

对于点i,左儿子2*i,右儿子2*i+1,根是1,

n个叶子节点,取若干个叶子结点得到一个集合,对这个集合求lca得到一个点号,

求所有非空情况(即2^n-1种情况)下lca点号的和,答案对998244353取模

题解

尝试递推,即尝试缩小规模,

第i层的子树大小只有三种值,x和x-1都需要除以2,

即x/2上取整,x/2下取整,(x-1)/2上取整,(x-1)/2下取整,

所以记忆化搜索子树大小对应的答案即可,

此外,还有根id的变化,

即一棵大小为n的根id=1的树,变为大小为n的根id=2的树(或变为根id=3的树)时,

对应的贡献增加了多少

手玩不难发现,根id每增加1,总贡献增加:

系数=lca在第一层方案数*1+lca在第二层方案数*2+lca在第三层方案数*4+...

暴力维护这个方案数是一个长为log的vector,每次算的时候现乘,复杂度O(nlogn^2)

但是注意到可以直接把这个系数加一起,每次乘以2,再把第一层的方案数加上即可,

复杂度O(nlogn)

赛后补的(1log)

// Problem: E. One-X
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/E
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
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<ll,ll> 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 scll(a) scanf("%lld",&(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 mod=998244353;
int t;
ll n;
map<ll,array<int,3> >mp;
int modpow(int x,ll n,int mod){
	int res=1;
	for(;n;n>>=1,x=1ll*x*x%mod){
		if(n&1)res=1ll*res*x%mod;
	}
	return res;
}
//(答案,系数,叶子数)
//系数=lca在第一层路径数*1+lca在第二层路径数*2+lca在第三层路径数*4+...
array<int,3> dfs(ll x){
	if(x==1)return {1,1,1};
	if(mp.count(x))return mp[x];
	auto [ansL,wL,lfL]=dfs((x+1)/2);
	auto [ansR,wR,lfR]=dfs(x/2);
	array<int,3>res;
	auto &[ans,w,lf]=res;
	int cnt=1ll*(modpow(2,lfL,mod)+mod-1)%mod*(modpow(2,lfR,mod)+mod-1)%mod;
	ans=(ansL+ansR)%mod;
	ans=(ans+1ll*wL%mod)%mod;//1->2 lson add 1
	ans=(ans+2ll*wR%mod)%mod;//1->3 rson add 2
	ans=(ans+cnt)%mod;
	w=(2ll*wL%mod+2ll*wR%mod)%mod;
	w=(w+cnt)%mod;
	lf=(lfL+lfR)%(mod-1);
	return mp[x]=res;
}
void sol(){
	scll(n);
	mp.clear();
	pte(dfs(n)[0]);
}
int main(){
	sci(t); // t=1
	while(t--){
		sol();
	}
	return 0;
}

赛中写的(2log)

// Problem: E. One-X
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/E
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
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<ll,ll> 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 scll(a) scanf("%lld",&(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 mod=998244353;
int t;
ll n;
map<ll,vector<int> >mp;
map<ll,int>mp2;
int modpow(int x,ll n,int mod){
	int res=1;
	for(;n;n>>=1,x=1ll*x*x%mod){
		if(n&1)res=1ll*res*x%mod;
	}
	return res;
}
vector<int> dfs(ll x){
	if(mp.count(x))return mp[x];
	if(x==1){
		vector<int>ans;
		ans.pb(1);
		return ans;
	}
	//printf("x:%lld\n",x);
	ll ls=(1+x)/2,rs=x-ls;
	vector<int>l=dfs(ls),r=dfs(rs);
	int sz=max(SZ(l),SZ(r));
	vector<int>now(sz+1,0);
	rep(i,1,sz){
		now[i]=0;
		if(i-1<SZ(l))now[i]=(now[i]+l[i-1])%mod;
		if(i-1<SZ(r))now[i]=(now[i]+r[i-1])%mod;
	}
	now[0]=1ll*(modpow(2,ls,mod)+mod-1)%mod*(modpow(2,rs,mod)+mod-1)%mod;
	return mp[x]=now;
}
int dfs2(ll x,ll y){
	if(x==1)return y%mod;
	if(y==1){	
		if(mp2.count(x))return mp2[x];
		vector<int>z=dfs(x);
		ll ls=(1+x)/2,rs=x-ls;
		int v1=dfs2(ls,y*2),v2=dfs2(rs,y*2+1);
		v1=(v1+v2)%mod;
		v1=(v1+z[0])%mod;
		return mp2[x]=v1;		
	}
	else{
		int w=dfs2(x,1);
		vector<int>z=dfs(x);
		int add=(y-1)%mod,sz=SZ(z);
		rep(i,0,sz-1){
			w=(w+1ll*z[i]*add%mod)%mod;
			add=2ll*add%mod;
		}
		return w;	
	}
}
void sol(){
	scll(n);
	mp.clear();
	mp2.clear();
	pte(dfs2(n,1));
}
int main(){
	sci(t); // t=1
	while(t--){
		sol();
	}
	return 0;
}

F. (暴力 map+前后缀最大值次大值/线段树/set)

给定长为n(2<=n<=2e5)的一个排列p,

称一个位置x是good的,当且仅当所有y<x都有py<px,且所有y>x都有py>px,

其实就是,将(x,px)看成是二维平面点的时候,左侧的点都在左下方,右侧的点都在右上方

必须交换(全部有序了也得换小)一组值px和py(px!=py),求交换后good位置的最大个数

t(t<=2e4)组样例,但保证sumn不超过2e5

题解写的又是树状数组又是线段树,非常麻烦,补一下jiangly的代码

只需用到前后缀的最大值和次大值,从而判断是否有good位置+1,非常优雅

当然也看了一个set

题解

有贡献的位置,ai=i是其必要条件,

首先,因为只能操作一次,

那么注意到可能新增good位置的手段只有两种(第一步就没注意到)

1. 将ai和i的值交换,令ai归位,这样可能能增加1

2. 看成是二维平面点的时候,(x,px)左上方恰有一个点,右下方恰有一个点,可以交换

就是交换px左侧的最大值,和px右侧的最小值,交换这两个位置

所以,可能产生贡献的位置对,只有2*n个,暴力检查这2*n个,能快速算贡献改变量即可

统计一下序列中已经good的位置,

是ai=i且左侧最大值小于i,右侧最小值大于i的位置

计这个个数是cnt

1. 如果所有位置都归位,那么交换会损失两个,也就是cnt-2

2.?至少有一个没归位的

①换一个归位的和一个没归位的,相邻就可以只损失一个位置,答案至少为cnt-1

但是注意到,没归位的是成对出现的

并且一定存在没归位的两个位置是逆序的(假设都是正序的,那么就都归位了,矛盾)

交换这两个逆序位置,cnt不变,所以答案可以取到cnt

3. 当交换(x,y)(x<y)两个位置时,

[1,x-1]的位置不受影响,[y+1,n]的位置不受影响,

由于想让答案增大,所以px>py一定成立(px<py越换越乱只能减小)

考虑[x+1,y-1]这个区间里的位置i,在(x,y)交换前,是没有good位置的,

因为,将(i,pi)看成是二维平面点的时候,左侧的点都在左下方,右侧的点都在右上方,

也就意味着,当i左侧的值和i右侧的值没有形成逆序对时,才会出现good位置,

而px和py是一对逆序对,所以没有good位置

所以,枚举所有可能增加的位置对,直接将对应贡献加上即可,2*n种情况取max

心得

此外学习到jiangly的最大值次大值的写法,只需要每次和x交换即可

for (int i = 1; i < n; i++) {
? ? ? ? pre[i] = pre[i - 1];
? ? ? ? int x = p[i - 1];
? ? ? ? for (int j = 0; j < 2; j++) {
? ? ? ? ? ? if (x > pre[i][j]) {
? ? ? ? ? ? ? ? std::swap(x, pre[i][j]);
? ? ? ? ? ? }
? ? ? ? }
? ? }

最大值次大值写法

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> p(n), invp(n);
    for (int i = 0; i < n; i++) {
        std::cin >> p[i];
        p[i]--;
        invp[p[i]] = i;
    }
    
    std::vector<std::array<int, 2>> pre(n, {-1, -1}), suf(n, {n, n});
    for (int i = 1; i < n; i++) {
        pre[i] = pre[i - 1];
        int x = p[i - 1];
        for (int j = 0; j < 2; j++) {
            if (x > pre[i][j]) {
                std::swap(x, pre[i][j]);
            }
        }
    }
    for (int i = n - 2; i >= 0; i--) {
        suf[i] = suf[i + 1];
        int x = p[i + 1];
        for (int j = 0; j < 2; j++) {
            if (x < suf[i][j]) {
                std::swap(x, suf[i][j]);
            }
        }
    }
    
    std::vector<int> bad(n);
    int cnt = 0;
    int ans = 0;
    std::map<std::pair<int, int>, int> mp;
    for (int i = 0; i < n; i++) {
        if (p[i] == i) {
            if (pre[i][0] < i && suf[i][0] > i) {//符合条件,不换
                bad[i] = 1;
                cnt += 1;
            } else if (pre[i][1] < i && suf[i][1] > i) {//换i左侧最大的和i右侧最小的,可使i符合条件
                mp[{invp[pre[i][0]], invp[suf[i][0]]}] += 1;
            }
        } else if (invp[i] < i) {
            if (suf[i][0] > i && pre[i][0] == i) {//令i值向后换归位
                mp[{invp[i], i}] += 1;
            }
        } else {
            if (suf[i][0] == i && pre[i][0] < i) {//令i值向前换归位
                mp[{i, invp[i]}] += 1;
            }
        }
    }
    //4 1 3 2
    ans = cnt - 2;//默认会损失两个位置
    if (cnt < n) {//至少有一个没归位的,换相邻就可以只损失一个位置
        ans = cnt;// 一定有至少一对逆序没归位的,换这对不会减少答案
    }
    for (auto [s, c] : mp) {//换(s_x,s_y]能增加c个归位的,换一对(x,y),x以左y以右不会受到影响,但是会减少[bad[x],bad[y]]个归位的
        auto [x, y] = s;
        ans = std::max(ans, cnt + c);
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

set写法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000005;
const int INF = 0x3f3f3f3f;

int n,a[N],pos[N],pre[N];

void solve(){
    int ans = 0;
    cin >> n;
    set <int> ps,vs;
    map <pair <int,int>,int> mp;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        pos[a[i]] = i;
        ps.insert(i);
        vs.insert(i);
        pre[i] = 0;
    }
    for(int mxpos = 0,i = 1;i <= n;i ++){
        if(pos[i] != i){
            if(mxpos <= i){
                mp[make_pair(min(i,pos[i]),max(i,pos[i]))] ++;
            } // swap i to position(i) makes ans ++
        }
        else{
            if(mxpos <= i){
                ans ++; pre[i] = 1;
            } // i already satisfy
            else{
                if(ps.size() >= 2 && (*(++ ps.begin())) == i){
                    int val = *vs.begin();
                    int p = *ps.begin();
                    if(val < i && p < i) mp[make_pair(min(pos[val],p),max(pos[val],p))] ++;
                }
            }
        }
        mxpos = max(mxpos,pos[i]);
        ps.erase(pos[i]);
        vs.erase(a[i]);
    }
    for(int i = 1;i <= n;i ++) pre[i] += pre[i - 1];
    if(ans == n){
        cout << n - 2 << '\n';
        return;
    }
    int mx = 0;
    for(auto it = mp.begin();it != mp.end();it ++){
        int now = it->second;
        //auto [l,r] = it->first;
        //now -= (pre[r] - pre[l - 1]); // um
        // cout << l << ' ' << r << ' ' << now << endl;
        mx = max(mx,now);
    }
    cout << ans + mx << '\n';
    // cout << ans << ' ' << mx << " -> " << ans + mx << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    int TC;
    cin >> TC;
    while(TC --){
        solve();
    }
    return 0;
}

文章来源:https://blog.csdn.net/Code92007/article/details/135053697
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。