[嵌入式]Codeforces Round #672 (Div. 2)Pokémon Army(c1+c2)

题目传送门

题目大意：

给出一个序列 a，要求求出一个单调递增的下标序列 b，使得 $$ans=a_{b_1}?a_{b_2}+a_{b_3}?a_{b_4}+\dots$$ 最大，输出这个最大值。

接下来有 q 个操作，每个操作为一个二元组 (l,r)，交换 $a_l与a_r$。求出交换后最大的 ans。
其中c1 c2的区别在于c1操作数为0

解题思路：通过对式子的观察，我们会发现找到一个线段的峰值和谷值，然后用峰值减去谷值即可最大化

于是对于c1我们想到了求出峰值和谷值，然而该过程较为繁琐，并且为C2带来了新问题交换对于峰值谷值的影响是怎样的？
于是我们继续观察式子 $a_3?a_5=a_3?a_4+a_4?a_5$通过对这个的观察我们恍然大悟，原来答案是如此构成的，当我们发现a[i]>a[i+1]时，直接加上a[i]-a[i+1],根据列项相消的原则，自然而然的得到了峰值减去谷值的最大化答案。
在此基础之上，C2也就只需要减去原来的影响然后加上交换之后的影响即可。

小技巧

• 我们可以将a[0]和a[n+1]赋值为0,可以大量简化码量

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define il (id<<1)
#define ir (id<<1)+1
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
const int maxn = 2e5+5;
const ll mod=998244353;
void solve()
{
	int n,q;
	cin>>n>>q;
	vector<int>a(n+2);
	for(int i=1;i<=n;i++)cin>>a[i];
	ll res=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]>a[i+1])res+=a[i]-a[i+1];
	}
	cout<<res<<'\n';
	for(int i=1;i<=q;i++)
	{
		int x,y;
		cin>>x>>y;
		if(x==y){cout<<res<<'\n';continue;}
		if(a[x-1]>a[x])res-=(a[x-1]-a[x]);
		if(a[x]>a[x+1])res-=(a[x]-a[x+1]);
		if(a[y-1]>a[y]&&x+1!=y)res-=(a[y-1]-a[y]);
		if(a[y]>a[y+1])res-=(a[y]-a[y+1]);
		swap(a[x],a[y]);
		if(a[x-1]>a[x])res+=(a[x-1]-a[x]);
		if(a[x]>a[x+1])res+=(a[x]-a[x+1]);
		if(a[y-1]>a[y]&&x+1!=y)res+=(a[y-1]-a[y]);
		if(a[y]>a[y+1])res+=(a[y]-a[y+1]);
		cout<<res<<'\n';
	}
}
int main(void)
{
	ios::sync_with_stdio(false);
	int t=1;
	cin >> t;
    while (t--) solve();
	return 0;
}

超强干货来袭

云风专访：近40年码龄，通宵达旦的技术人生