【UOJ #29】【IOI 2014】holiday

时间：2023-01-15 22:59:54

http://uoj.ac/problem/29

cdq四次处理出一直向左， 一直向右， 向左后回到起点， 向右后回到起点的dp数组，最后统计答案。

举例：\(fi\)表示一直向右走i天能参观的最多景点数。

其中有一个很重要的条件\(fi≤fi+1fi≤fi+1\)，这个条件是分治的前提。

关于这个条件的证明，我想了好久才想出来，用反证法证明一下就行。

分治时需要用主席树维护路径上的前k大和。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include"holiday.h"

using namespace std;

typedef long long ll;

const int N = 100003;

const int M = 250003;

struct node {

    int l, r, s;

    ll sum;

    node() {l = r = s = sum = 0;}

} T[N * 20];

int a[N], H[N], cnt = 0, root[N], top, st;

ll f[M], g[M], f1[M], g1[M];

void update(int &pos, int l, int r, int key) {

    T[++cnt] = T[pos]; pos = cnt;

    ++T[pos].s; T[pos].sum += H[key];

    if (l == r) return;

    int mid = (l + r) >> 1;

    if (key <= mid) update(T[pos].l, l, mid, key);

    else update(T[pos].r, mid + 1, r, key);

}

ll query(int tl, int tr, int l, int r, int num) {

    if (l == r) {return min(T[tr].sum - T[tl].sum, 1ll * H[l] * num);}

    int mid = (l + r) >> 1, s = T[T[tr].r].s - T[T[tl].r].s;

    if (s >= num)

        return query(T[tl].r, T[tr].r, mid + 1, r, num);

    else

        return T[T[tr].r].sum - T[T[tl].r].sum + query(T[tl].l, T[tr].l, l, mid, num - s);

}

void cdq_f(int l, int r, int tmp_l, int tmp_r) {

    if (l > r) return;

    int mid = (l + r) >> 1, pos = tmp_l;

    ll t;

    for(int i = tmp_l; i - st <= mid && i <= tmp_r; ++i)

        if ((t = query(root[st - 1], root[i], 1, top, mid - i + st)) > f[mid])

            f[mid] = t, pos = i;

    cdq_f(l, mid - 1, tmp_l, pos);

    cdq_f(mid + 1, r, pos, tmp_r);

}

void cdq_f1(int l, int r, int tmp_l, int tmp_r) {

    if (l > r || tmp_l > tmp_r) return;

    int mid = (l + r) >> 1, pos = tmp_l;

    ll t;

    for(int i = tmp_l; ((i - st) << 1) <= mid && i <= tmp_r; ++i)

        if ((t = query(root[st], root[i], 1, top, mid - ((i - st) << 1))) > f1[mid])

            f1[mid] = t, pos = i;

    cdq_f1(l, mid - 1, tmp_l, pos);

    cdq_f1(mid + 1, r, pos, tmp_r);

}

void cdq_g(int l, int r, int tmp_l, int tmp_r) {

    if (l > r) return;

    int mid = (l + r) >> 1, pos = tmp_r;

    ll t;

    for(int i = tmp_r; st - i <= mid && i >= tmp_l; --i) {

        if ((t = query(root[i - 1], root[st], 1, top, mid - st + i)) > g[mid])

            g[mid] = t, pos = i;

    }

    cdq_g(l, mid - 1, pos, tmp_r);

    cdq_g(mid + 1, r, tmp_l, pos);

}

void cdq_g1(int l, int r, int tmp_l, int tmp_r) {

    if (l > r || tmp_l > tmp_r) return;

    int mid = (l + r) >> 1, pos = tmp_r;

    ll t;

    for(int i = tmp_r; ((st - i) << 1) <= mid && i >= tmp_l; --i) {

        if ((t = query(root[i - 1], root[st - 1], 1, top, mid - ((st - i) << 1))) > g1[mid])

            g1[mid] = t, pos = i;

    }

    cdq_g1(l, mid - 1, pos, tmp_r);

    cdq_g1(mid + 1, r, tmp_l, pos);

}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {

    for(int i = 0; i < n; ++i) H[++cnt] = attraction[i];

    sort(H + 1, H + cnt + 1);

    cnt = unique(H + 1, H + cnt + 1) - H;

    for(int i = 1; i <= n; ++i) a[i] = lower_bound(H + 1, H + cnt, attraction[i - 1]) - H;

    top = cnt - 1; cnt = 0;

    for(int i = 1; i <= n; ++i) {

        root[i] = root[i - 1];

        update(root[i], 1, top, a[i]);

    }

    st = start + 1;

    cdq_f(0, d, st, n);

    cdq_f1(0, d, st + 1, n);

    cdq_g(0, d, 1, st);

    cdq_g1(0, d, 1, st - 1);

    ll ans = max(f[d], g[d]);

    for(int i = 1; i <= d; ++i)

        ans = max(ans, max(f[i] + g1[d - i], g[i] + f1[d - i]));

    return ans;

}

UOJ上是交互题的形式

相关文章