C2. Pokémon Army (hard version)
题意
给出两两互不相同的数组a (长度<3e5)
要求从a中取出一个长度为k子序列b
使得val=b1-b2+b3-b4…bk 的值最大
多组询问 每次交换两个位置上的数
输出交换后最大的val
题解
easy version 解决后 发现能构成最大val的子序列b
一定是取数组a中连续出现的极大值，极小值，极大值…..
那么这个val值它的含义就变成了 所有谷底到峰顶的高度差之和
即 $∑_{i=1}^nmax(0,a[i]-a[i-1])$
将某个数组a抽象成上图连续曲线
那么val=红线处高度差之和
那么多组询问交换两个位置(L,R)上的数 输出val就容易操作了
减去a[L]和a[R]的贡献 交换后在加上各自的贡献
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=3e5+5;
const ll Mod=998857459;
ll data[Max];
int main() {
Turnoff;
int t;cin>>t;
while(t--){
int n,q;cin>>n>>q;
data[n+1]=0;
for(int i=1;i<=n;i++)cin>>data[i];
ll ans=0;data[0]=0;
for(int i=1;i<=n;i++)ans+=max(0ll,data[i]-data[i-1]);
cout<<ans<<endl;
while(q--){
int L,R;cin>>L>>R;
if(L==R){
cout<<ans<<endl;
continue;
}
ans-=max(0ll,data[L]-data[L-1]);
ans-=max(0ll,data[L+1]-data[L]);
if(R>L+1)ans-=max(0ll,data[R]-data[R-1]);
ans-=max(0ll,data[R+1]-data[R]);
swap(data[L],data[R]);
ans+=max(0ll,data[L]-data[L-1]);
ans+=max(0ll,data[L+1]-data[L]);
if(R>L+1)ans+=max(0ll,data[R]-data[R-1]);
ans+=max(0ll,data[R+1]-data[R]);
cout<<ans<<endl;
}
}
}
|