题目链接
题目大意：就算给你一序列，按照顺序出若干个数组成一个的序列，然后对这个序列定义一个权值就算奇数位置的和减去偶数位置的和，问你能的到的最大的权值是多少？
**a1 - a2 + a3 - a4 + a5 … **
解题思路：1.就是我们观擦一下：就任意多个ai - aj的组合；最后的就是an - 0;
2.我们可以用差分的思想：ai就是差分数组前i位的前缀和，那么ai-aj就是差分数组的区间和，就是贪心挑出任意多个差分大于0的区间求他们的和
3.我们发现如果这个区间内部有出现+配-配+但是总的sum还是+,那么我们最优还可以直接列成两个全是正的小区间，那么最优
4.那么综上所述：我们那么其实就算把差分任意两个相邻的ai-ai+1的大于0的和
5.那么对于交换操作：我们知道改变的只有两个数，那么对差分数组的影响只有4位置，那么就可以O(1)更新答案
注意一点就是：a[n+1] = 0,因为最后一定是+一个数而已相当于-0
代码：
#include <iostream>
#include <cstdio>
#include <stack>
#include <sstream>
#include <limits.h>
#include <vector>
#include <map>
#include <cstring>
#include <deque>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <set>
#define mid ((l + r) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define _for(i,a,b) for( int i = (a); i < (b); ++i)
#define _rep(i,a,b) for( int i = (a); i <= (b); ++i)
#define for_(i,a,b) for( int i = (a); i >= (b); -- i)
#define rep_(i,a,b) for( int i = (a); i > (b); -- i)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define hash Hash
#define next Next
#define pb push_back
#define f first
#define s second
#define y1 Y
using namespace std;
const int N = 3e5 + 10, MOD = 1e9 + 7;
const int maxn = 2e5;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x)
{x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args)
{read(first);read(args...);
}
ll a[N], b[N];
int T;
int n, q;
ll ans;inline void work(int pos, ll & ans)
{if(pos - 1 >= 1 && b[pos - 1] > 0) ans -= b[pos - 1];if(pos - 1 >= 1) b[pos - 1] = a[pos - 1] - a[pos];if(pos - 1 >= 1 && b[pos - 1] > 0) ans += b[pos - 1];if(b[pos] > 0) ans -= b[pos];b[pos] = a[pos] - a[pos + 1];if(b[pos] > 0) ans += b[pos];
}int main()
{IOS;cin >> T;while(T --){ans = 0;cin >> n >> q;a[n + 1] = 0;for(int i = 1; i <= n; ++ i)cin >> a[i];for(int i = 1; i <= n; ++ i)b[i] = a[i] - a[i + 1], ans += b[i] * (b[i] > 0);cout << ans << endl;while(q --){int l, r;cin >> l >> r;swap(a[l],a[r]);work(l,ans);work(r,ans);cout << ans << endl;}}return 0;
}
