BZOJ4241题解历史研究--回滚莫队

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=4241

分析

这题就是求区间权值乘以权值出现次数的最大值,一看莫队法块可搞,但仔细想想,莫队的加入很容易,但是删除需要维护许多东西,非常麻烦,于是就有dalao想出了一个新科技—回滚莫队.回滚莫队能使操作全部变成加入或全部变成删除.这道题我们需要全部变成加入.

怎么做呢？我们对询问进行处理,左端点在一个块中的先归在一起,然后以右端点为关键字进行排序,使得右端点靠前的在前.然后依次处理按左端点归好后每个块中的询问,我们找到块中最靠后的左端点,和最靠前的右端点(其实就是块中第一个询问的右端点),统计区间信息。

对于每一个询问,先移动右端点加入元素,然后左端点左移得到询问答案后再向右移撤销,由于不需要维护什么信息撤销变得非常容易.简单来说,总的思路就是先找出最“窄”的区间,然后不断加入补全到询问区间.

当然,如果询问的左端点和右端点在一个块中就直接暴力处理

代码

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
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define LL long long 
#define ri register int 
using std::min;
using std::max;
using std::vector;
using std::map;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;
    return ;
}
struct Qur{
    int l,r,id;
    Qur(int a,int b,int c){l=a,r=b,id=c;}
    bool operator <(const Qur & b)const {
        return r<b.r;
    }
};
const int maxn=100005;
const int maxb=355;
const int inf=0x7fffffff;
int n,w[maxn],pos[maxn];
int blo,mxl[maxb];
map <int,int> g;int tot=0,f[maxn];
int cnt[maxn];
LL res=inf,ans[maxn];
vector <Qur> qry[maxb];
inline void add(int x){
    cnt[x]++;
    res=max(res,1ll*cnt[x]*f[x]);
}
int main(){
    int l,r,q;
    read(n);read(q);
    blo=sqrt(n+0.5);
    memset(mxl,0,sizeof(mxl));
    for(ri i=1;i<=n;i++){
        read(w[i]);
        if(!g[w[i]]){
            g[w[i]]=++tot;
            f[tot]=w[i];
        }w[i]=g[w[i]];
        pos[i]=(i-1)/blo+1;
    }
    for(ri i=1;i<=q;i++){
        read(l),read(r);
        if(pos[l]==pos[r]){//左端点右端点在一个块中
            res=-inf;
            memset(cnt,0,sizeof(cnt));
            for(ri j=l;j<=r;j++)add(w[j]);
            for(ri j=l;j<=r;j++)cnt[j]--;
            ans[i]=res; 
        }
        else{
            qry[pos[l]].push_back(Qur(l,r,i));
            mxl[pos[l]]=max(mxl[pos[l]],l);//记录询问块中的最后左端点
        }
    }
    int ll,rr;LL last;
    for(ri i=1;i<=pos[n];i++){//处理每个询问块
        if(qry[i].empty())continue;
        memset(cnt,0,sizeof(cnt));res=-inf;
        sort(qry[i].begin(),qry[i].end());
        l=mxl[i],r=qry[i][0].r;
        for(ri j=l;j<=r;j++)add(w[j]);
        for(ri j=0;j<qry[i].size();j++){
            ll=qry[i][j].l,rr=qry[i][j].r;
            while(r<rr)r++,add(w[r]);
            last=res;//记录下右端点操作后信息
            for(ri k=ll;k<l;k++)add(w[k]);
            ans[qry[i][j].id]=res,res=last;//左端点左移后撤回
            for(ri k=ll;k<l;k++)cnt[w[k]]--;//已经得到答案,撤回非常容易
        }
    }
    for(ri i=1;i<=q;i++)printf("%lld\n",ans[i]);
    return 0;
}

后记

关于这题的离散化处理,我还进行了一些比较,在这篇博客中

https://rye-catcher.github.io/2018/07/15/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0-%E5%87%A0%E7%A7%8D%E7%A6%BB%E6%95%A3%E5%8C%96%E6%96%B9%E5%BC%8F/

推荐学习博客

http://isrothy.blog.uoj.ac/blog/3673