Constant Palindrome Sum
题目链接：https://codeforces.com/problemset/problem/1343/D
题意：
给你一个全是偶数的数组(每个数的值都不超过K)
现在每次你可以将任意 Ai 改变为[1 , K]的值
要求改变后的数组必须满足Ai + A(n - i + 1) = X (i∈[1 , n / 2] , x∈[2 , 2 * K])
问你最少需要改变几次
分析：
计算 Ai + A(n - i + 1) = [2 , 2 * K] 分别需要改变的次数
定义 ma = max(Ai , A(n - i + 1)) , mi = min(Ai , A(n - i + 1))
①、Ai + A(n - i + 1) = ma + mi 需要改变的次数为 0
②、Ai + A(n - i + 1) = [2 , mi] 需要改变的次数为 2
③、Ai + A(n - i + 1) = [mi + 1 , mi + ma - 1] 需要改变的次数为 1
④、Ai + A(n - i + 1) = [mi + ma + 1 , ma + K] 需要改变的次数为 1
⑤、Ai + A(n - i + 1) = [ma + K + 1 , 2 * K] 需要改变的次数为 2
等我们更新完[2 , 2 * K]内所有点需要改变的次数后，输出最小的即可。
至于更新我们可以用差分 or 线段树来操作
差分:
#include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define int long long using namespace std; const int N = 4e5 + 10; int a[N] , sum[N]; signed main() { int t; cin >> t; while(t --) { int n , k ; cin >> n >> k ; rep(i , 1 , k << 1) sum[i] = 0; rep(i , 1 , n) cin >> a[i] ; rep(i , 1 , n / 2) { int ma = max(a[i] , a[n - i + 1]); int mi = min(a[i] , a[n - i + 1]); sum[2] += 2 ; sum[mi + 1] -- ; sum[mi + ma] -- ; sum[mi + ma + 1] ++ ; sum[ma + k + 1] ++ ; } int ans = n / 2; rep(i , 2 , k << 1) { sum[i] += sum[i - 1] ; ans = min(ans , sum[i]); } cout << ans << ' '; } return 0; }
线段树:
#include <bits/stdc++.h> #define rep(i, a, n) for (int i = a; i <= n; i++) #define per(i, n, a) for (int i = n; i >= a; i--) #define int long long #define ll long long #define il inline using namespace std; struct Tree { ll l, r, sum, lazy, maxn, minn; } tree[2000000]; il void push_up(ll rt) { tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum; tree[rt].maxn = max(tree[rt << 1].maxn, tree[rt << 1 | 1].maxn); tree[rt].minn = min(tree[rt << 1].minn, tree[rt << 1 | 1].minn); } il void push_down(ll rt, ll length) { if (tree[rt].lazy) { tree[rt << 1].lazy += tree[rt].lazy; tree[rt << 1 | 1].lazy += tree[rt].lazy; tree[rt << 1].sum += (length - (length >> 1)) * tree[rt].lazy; tree[rt << 1 | 1].sum += (length >> 1) * tree[rt].lazy; tree[rt << 1].minn += tree[rt].lazy; tree[rt << 1 | 1].minn += tree[rt].lazy; tree[rt << 1].maxn += tree[rt].lazy; tree[rt << 1 | 1].maxn += tree[rt].lazy; tree[rt].lazy = 0; } } il void build(ll l, ll r, ll rt, ll *aa) { tree[rt].lazy = 0; tree[rt].l = l; tree[rt].r = r; if (l == r) { tree[rt].sum = aa[l]; tree[rt].minn = tree[rt].sum; tree[rt].maxn = tree[rt].sum; return; } ll mid = (l + r) >> 1; build(l, mid, rt << 1, aa); build(mid + 1, r, rt << 1 | 1, aa); push_up(rt); } il void update_range(ll L, ll R, ll key, ll rt) { if (tree[rt].r < L || tree[rt].l > R) return; if (L <= tree[rt].l && R >= tree[rt].r) { tree[rt].sum += (tree[rt].r - tree[rt].l + 1) * key; tree[rt].minn += key; tree[rt].maxn += key; tree[rt].lazy += key; return; } push_down(rt, tree[rt].r - tree[rt].l + 1); ll mid = (tree[rt].r + tree[rt].l) >> 1; if (L <= mid) update_range(L, R, key, rt << 1); if (R > mid) update_range(L, R, key, rt << 1 | 1); push_up(rt); } il ll query_min(ll L, ll R, ll rt) { if (L <= tree[rt].l && R >= tree[rt].r) { return tree[rt].minn; } push_down(rt, tree[rt].r - tree[rt].l + 1); ll mid = (tree[rt].r + tree[rt].l) >> 1; ll ans = (0x3f3f3f3f3f3f3f3fll); if (L <= mid) ans = min(ans, query_min(L, R, rt << 1)); if (R > mid) ans = min(ans, query_min(L, R, rt << 1 | 1)); return ans; } const int N = 4e5 + 10; int a[N] , zero[N]; signed main() { int t ; cin >> t ; while(t --) { int n , k ; cin >> n >> k ; build(1 , 2 * k , 1 , zero); rep(i , 1 , n) cin >> a[i]; rep(i , 1 , n / 2) { int mi = min(a[i] , a[n - i + 1]); int ma = max(a[i] , a[n - i + 1]); update_range(2 , mi , 2 , 1); update_range(mi + 1 , mi + ma - 1 , 1 , 1); update_range(mi + ma + 1 , ma + k , 1 , 1); update_range(ma + k + 1 , 2 * k , 2 , 1); } cout << query_min(2 , 2 * k , 1) << ' '; } return 0; }