(JOISC2014C) 历史的研究

发表于 分类于 ，

原题链接 (luogu)

思路:

回滚莫队

直接使用回滚莫队，离散化后用数组记录每个数字的出现次数， 每次增加一个元素出现次数 + 1 同时更新答案.

代码:

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
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
const int Mn(100500),Mm(100500);
void qrd(int& x) {  //快读
    x = 0;
    char c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c-'0';
        c = getchar();
    }
}

int a[Mn],shf[Mn],ind[Mn];  //原数组, 离散化后的数组, a到shf的映射

struct Que {
    int l,r,id;
}q[Mm];
int blk[Mn],blkR[Mn];   //分块编号与分块右端点
bool cmp(const Que& x,const Que& y) {   //查询区间排序
    return blk[x.l]==blk[y.l] ? x.r<y.r : blk[x.l]<blk[y.l];
}

long long ans[Mm];  //每个查询的答案
int cnta[Mn],cntr[Mn];  //数字出现次数, 右区间数字出现次数

int main() {
    int n,m;
    qrd(n);
    qrd(m);
    for(int i(1);i<=n;++i) {
        qrd(a[i]);
        shf[i] = a[i];
    }
    /* 离散化 */
    sort(shf+1,shf+n+1);
    int sn = unique(shf+1,shf+n+1) - shf - 1;
    /* 预处理ind方便查询 */
    for(int i(1);i<=n;++i) {
        ind[i] = lower_bound(shf+1,shf+sn+1,a[i])-shf;
    }
    /* 给分块编号并处理出每个分块的右端点 */
    int bsz = ceil(sqrt(n));    //分块大小
    for(int i(1);i<=n;++i) {
        blk[i] = blk[i-1];
        if(blk[i]*bsz < i) {
            blkR[blk[i]] = i-1;
            ++blk[i];
        }
    }
    for(int i(1);i<=m;++i) {
        qrd(q[i].l), qrd(q[i].r);
        q[i].id = i;
    }
    sort(q+1,q+m+1,cmp);    //查询区间排序
    long long tra(0),tca(0);    //右区间答案, 总体答案
    for(int i(1);i<=m;++i) {
        Que &x(q[i]),&lx(q[i-1]);
        /* 左右区间分块相同暴力处理 */
        if(blk[x.l]==blk[x.r]) {
            memset(cnta+1,0,sizeof(int)*sn);
            tca = 0;
            for(int j(x.l);j<=x.r;++j) {
                ++cnta[ind[j]];
                tca = max(tca,1ll*cnta[ind[j]]*a[j]);
            }
            ans[x.id] = tca;
            continue;
        }
        /* 左端点分块号不同直接重置 */
        if(blk[x.l]!=blk[lx.l] || blk[lx.l]==blk[lx.r]) {
            memset(cnta+1,0,sizeof(int)*sn);
            memset(cntr+1,0,sizeof(int)*sn);
            tca = tra = 0;
            for(int j(blkR[blk[x.l]]);j>=x.l;--j) {
                ++cnta[ind[j]];
                tca = max(tca,1ll*cnta[ind[j]]*a[j]);
            }
            for(int j(blkR[blk[x.l]]+1);j<=x.r;++j) {
                ++cnta[ind[j]];
                ++cntr[ind[j]];
                tra = max(tra,1ll*cntr[ind[j]]*a[j]);
                tca = max(tca,1ll*cnta[ind[j]]*a[j]);
            }
        } else {
            /* 左端点大于左指针(即上次查询的左端点)回滚 */
            if(x.l>lx.l) {
                memcpy(cnta+1,cntr+1,sizeof(int)*sn);
                tca = tra;
                for(int j(blkR[blk[x.l]]);j>=x.l;--j) {
                    ++cnta[ind[j]];
                    tca = max(tca,1ll*cnta[ind[j]]*a[j]);
                }
            /* 否则向左增加元素 */
            } else {
                for(int j(lx.l-1);j>=x.l;--j) {
                    ++cnta[ind[j]];
                    tca = max(tca,1ll*cnta[ind[j]]*a[j]);
                }
            }
            /* 向右增加元素并保存右区间查询 */
            for(int j(lx.r+1);j<=x.r;++j) {
                ++cnta[ind[j]];
                ++cntr[ind[j]];
                tca = max(tca,1ll*cnta[ind[j]]*a[j]);
                tra = max(tra,1ll*cntr[ind[j]]*a[j]);
            }
        }
        ans[x.id] = tca;
    }
    for(int i(1);i<=m;++i) {    //打印答案
        printf("%lld\n",ans[i]);
    }
    return 0;
}