bzoj4241 历史研究

题目描述

IOI国历史研究的第一人——JOI教授,最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活,开始着手调查日记中记载的事件。

日记中记录了连续N天发生的时间,大约每天发生一件。

事件有种类之分。第i天(1<=i<=N)发生的事件的种类用一个整数Xi表示,Xi越大,事件的规模就越大。

JOI教授决定用如下的方法分析这些日记:

  1. 选择日记中连续的一些天作为分析的时间段

  2. 事件种类t的重要度为t*(这段时间内重要度为t的事件数)

  3. 计算出所有事件种类的重要度,输出其中的最大值

现在你被要求制作一个帮助教授分析的程序,每次给出分析的区间,你需要输出重要度的最大值。

输入格式

第一行两个空格分隔的整数N和Q,表示日记一共记录了N天,询问有Q次。

接下来一行N个空格分隔的整数X1...XN,Xi表示第i天发生的事件的种类

接下来Q行,第i行(1<=i<=Q)有两个空格分隔整数Ai和Bi,表示第i次询问的区间为[Ai,Bi]。

输出格式

输出Q行,第i行(1<=i<=Q)一个整数,表示第i次询问的最大重要度

样例输入

5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4

样例输出

9
8
8
16
16

说明

1<=N<=10^5

1<=Q<=10^5

1<=Xi<=10^9 (1<=i<=N)


分析

题意:一个数在一个区间内的价值定义为【这个数的值乘上它在这个区间内的出现次数】,求区间内数的最大价值。

看上去可以用莫队乱搞一下:如果只有插入(区间扩展)操作是非常容易维护的,维护一下每个数出现次数的桶,每次插入的时候更新一下答案即可。

关键是好像没法删除,因为没法求删除以后的答案。

这里介绍一个新操作:回滚莫队。它可以解决只能插入不能删除的莫队问题,思路非常简单。

具体操作:还是先与普通莫队一样对询问按左端点所在的块和右端点排序,然后对每一块分开做。

对于长度小于$\sqrt n$的询问,先暴力做掉。

设当前块的右端点为$t$,则对于每个询问,我们先用普通莫队求出$(t,r]$的答案,把这个答案$tmp$记录下来,然后再插入$[l,t]$,求出最终答案。最后回滚,恢复到$(t,r]$的状态。因为我们已经先记录了$(t,r]$的答案,就可以解决删除时无法求答案的问题。

复杂度与普通莫队相同。

代码

#include <bits/stdc++.h>
typedef long long ll;

const int N = 1e5+50;
const int M = 1e5+50;

int n, m;
int disc[N];
int bsiz, bl[N];
int a[N];
int buc[N];
ll ans, out[M];

struct Query {
    int l, r, id;
} q[M];

bool cmp(const Query &t1, const Query &t2) {
    int b1 = bl[t1.l], b2 = bl[t2.l];
    if (b1 == b2) return t1.r < t2.r;
    return b1 < b2;
}

void getDisc() {
    std::sort(disc+1, disc+n+1);
    int dif = std::unique(disc+1, disc+n+1) - 1 - disc;
    for (int i = 1; i <= n; i++)
        a[i] = std::lower_bound(disc+1, disc+dif+1, a[i]) - disc;
}

void add(int x) {
    buc[x]++;
    ans = std::max(ans, (ll)disc[x] * buc[x]);
}

void del(int x) {
    buc[x]--;
}

ll brute(int l, int r) {
    static int cnt[N];
    for (int i = l; i <= r; i++)
        cnt[a[i]] = 0;
    ll rtn = 0;
    for (int i = l; i <= r; i++) {
        cnt[a[i]]++;
        rtn = std::max(rtn, (ll)disc[a[i]] * cnt[a[i]]);
    }
    return rtn;
}

int solve(int cur, int b) {
    int right = std::min(b*bsiz, n), L = right + 1, R = L - 1;
    ans = 0;
    memset(buc, 0, sizeof buc);
    for (; bl[q[cur].l] == b; cur++) {
        int l = q[cur].l, r = q[cur].r, id = q[cur].id;
        if (r-l+1 <= bsiz) {
            out[id] = brute(l, r);
            continue;
        }
        while (R < r) add(a[++R]);
        ll tmp = ans;
        while (L > l) add(a[--L]);
        out[id] = ans;
        while (L < right + 1) del(a[L++]);
        ans = tmp;
    }
    return cur;
}

void moDui() {
    int cur = 1;
    for (int b = 1; b <= bl[n]; b++)
        cur = solve(cur, b);
}


int main() {
    scanf("%d%d", &n, &m);
    bsiz = sqrt(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        disc[i] = a[i];
        bl[i] = (i - 1) / bsiz + 1;
    }
    getDisc();
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    std::sort(q+1, q+m+1, cmp);
    moDui();
    for (int i = 1; i <= m; i++)
        printf("%lld\n", out[i]);
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论