Kanade's sum

Posted on | In , ,

题目链接

题意

定义$f(l, r, k)$为$A[l…r]$的$k-th$大。
计算 .

思路

不妨计算每个数字的贡献，我们求出每个数字的贡献区间即可。
标程是用链表写的。我觉得其实笛卡尔树也是一个不错的选择，每次删的都是根结点，但是会T，因为如果树的形状是第一个元素次小的样子，去找那$k$个区间的时候是$O(n)$的。我还是把它贴在这里吧。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50

const int N = 5e5 + 5;
ll seed = 17124057;
#define ls(x) treap[x].child[0]
#define rs(x) treap[x].child[1]

struct node
{
    int val, key, size;
    int child[2];
}treap[N];

void push_up(int root)
{
    treap[root].size = treap[ls(root)].size + treap[rs(root)].size + 1;
}

void split(int root, int &x, int &y, int val)
{
    return;
}

void merge(int &root, int x, int y)
{
    if (!x || !y)
    {
        root = x + y;
        return;
    }
    if (treap[x].key <= treap[y].key)
    {
        root = x;
        merge(rs(x), rs(x), y);
    }
    else
    {
        root = y;
        merge(ls(y), x, ls(y));
    }
    push_up(root);
}
int tot = 0;
int root;
void insert(int val, int key)
{
    int z = ++tot;
    treap[z].size = 1;
    treap[z].val = val;
    treap[z].key = key;
    ls(z) = 0, rs(z) = 0;
    merge(root, root, z);
}
ll ans = 0;
ll interval[2][100];
int n, k;

void dfs(int dir, int u, int &le)
{
    if (!u)
        return;
    dfs(dir, treap[u].child[!dir], le);
    if (le >= k)
        return;
    interval[dir][++le] = 1ll * treap[u].val;
    if (le >= k)
        return;
    dfs(dir, treap[u].child[dir], le);
}

void solve()
{
    int top = root;
    //dbg(treap[root].val, treap[root].key);
    int le = 0, ri = 0;
    dfs(0, ls(root), le);
    dfs(1, rs(root), ri);
    interval[0][0] = interval[1][0] = treap[root].val;
    if (le < k)
        interval[0][++le] = 0;
    if (ri < k)
        interval[1][++ri] = n + 1;
    for (int i = 1; i <= le; i++)
    {
        if (k - i + 1 > ri)
            continue;
        ans = ans + treap[root].val * 1ll * (interval[0][i - 1] - interval[0][i]) * (interval[1][k - i + 1] - interval[1][k - i]);
    }
    merge(root, ls(root), rs(root));
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &k);
        tot = 0;
        root = 0;
        for (int i = 1; i <= n; i++)
        {
            int x;
            scanf("%d", &x);
            insert(i, x);
        }
        ans = 0;
        for (int i = 1; i <= n; i++)
            solve();
        printf("%lld\n", ans);
    }
    return 0;
}

链表

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
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
typedef long long ll;
int pre[N], nxt[N], v[N], pos[N], n, k;
ll a[N], b[N];

ll solve(int x) {
    int c1 = 0, c2 = 0;
    for(int i = x; i && c1 <= k; i = pre[i])
        a[++c1] = i - pre[i];
    for(int i = x; i <= n && c2 <= k; i = nxt[i])
        b[++c2] = nxt[i] - i;
    ll ans = 0;
    for(int i = 1; i <= c1; i++)
        if(k - i + 1 <= c2 && k - i + 1 >= 1)
            ans += a[i] * b[k-i+1];
    return ans;
}

void del(int x) {
    pre[nxt[x]] = pre[x];
    nxt[pre[x]] = nxt[x];
}

int main() 
{
    int T; 
	scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++) scanf("%d", &v[i]), pos[v[i]] = i;
        for(int i = 0; i <= n + 1; i++) pre[i] = i - 1, nxt[i] = i + 1;
        pre[0] = 0; nxt[n+1] = n + 1;
        ll ans = 0;
        for(int i = 1; i <= n; i++) {
            ans += solve(pos[i]) * i;
            del(pos[i]);
        } printf("%lld\n", ans);
    } return 0;
}

0%