hyz's blog
0%

Gym 101755G: Underpalindromity

发表于

题目链接

Gym101755G

分析

首先来考虑一下这个样例：
8 4
8 8 7 6 9 5 8 2

我们列出所有对答案产生贡献的元素对：

1-4
2-3, 2-5
3-2, 3-4, 3-6
4-1, 4-3, 4-5, 4-7
…

经过观察，我们发现对于某一个元素，它的贡献是有规律的。令i表示该元素的下标，则该元素对于[i-k+1, i+k-1]这个区间，每隔两个数就有一次贡献。因此，我们就将n*n个区间的贡献值转化为了n个点的贡献值。举个例子，上面那个样例中，第2个元素的贡献就是(8-7) + (9-8)。

为了能够快速查询某一点的贡献值，我们必须用到某种数据结构来优化，对于区间问题，容易想到用线段树或者树状数组。为了能够用数据结构优化，我们需要将数组从小到大排序。排序后，当我们计算某一点的贡献时，这个点对于比这个点小的元素的贡献。举个例子，上面第2个元素的贡献就是(8-7)，至于(9-8)，就留给第5个元素才计算。因此，树状数组需要的维护的东西有元素个数以及区间和。

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
#define x first
#define y second
#define ok puts("ok");
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=2e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

ll sum[4][N], n, k, ans;
pii a[N];

ll query(int p, int id) {
    ll ans = 0;
    while(p > 0) {
        ans += sum[id][p];
        p -= p & -p;
    }
    return ans;
}

void add(int p, int v, int id) {
    while(p <= n) {
        sum[id][p] += v;
        p += p & -p;
    }
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(cin >> n >> k) {
        ans = 0;
        memset(sum, 0, sizeof sum);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i].x);
            a[i].y = i;
        }
        sort(a+1, a+n+1);
        for(int i = 1; i <= n; i++) {
            int id = a[i].y & 1;
            int r = a[i].y + k - 1;
            int l = a[i].y - k + 1;
            //边界情况的处理
            if(l < 1)
                l = k - a[i].y + 1;
            if(r > n)
                r = 2*n - a[i].y - k + 1;

            //计算某点对答案的贡献
            if(k & 1)
                ans += 1LL * a[i].x * (query(r, id+2) - query(l-1, id+2)) - (query(r, id) - query(l-1, id));
            else
                ans += 1LL * a[i].x * (query(r, (id+2)^1) - query(l-1, (id+2)^1)) - (query(r, id^1) - query(l-1, id^1));

            //用该点更新树状数组
            add(a[i].y, a[i].x, id);
            add(a[i].y, 1, id + 2);
        }
        printf("%lld\n", ans);
    }
    return 0;
}