【AT1219】历史研究

Author Avatar
洛水·锦依卫 1月 26, 2019

题面

题目描述

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

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

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

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

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

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

计算出所有事件种类的重要度,输出其中的最大值 现在你被要求制作一个帮助教授分析的程序,每次给出分析的区间,你需要输出重要度的最大值。

输入输出格式

输入格式

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

接下来一行$N$个空格分隔的整数$X_1…X_N$,$X_i$表示第$i$天发生的事件的种类

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

输出格式

输出$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<=105$

$1<=Q<=105$

$1<=X_i<=109 (1<=i<=N)$

题解

考点

莫队,回滚莫队,离线询问,排序算吗

思路

我们发现对于暴力的数据,我们之所以要套个线段树是因为莫队中的 $Del​$ 操作执行后无法继续保证最大值的维护。那么我们换个思路想一下,我们避免掉 $Del​$ 操作的执行不就好了吗?

这就是回滚莫队的板子了。

对于 $r-l>=块大小$ 的询问,直接暴力处理。

对于左端点在同一个块内的询问,我们在处理之前先令 $l$ 处在下一个块的块首,然后不断 $r++$ 到询问右端点,那么 $r$ 就保证不会执行 $Del$ 操作了。而对于 $l$ ,当前 $r$ 处理完之后,记录下当前的状态(包括最大值和每个种类的照片数量啥的),我们只需要对于每个询问移动到询问左端点,然后得到答案之后 $O(1)$ 跳回之前状态即可。

那么对于记录状态与跳回怎么处理呢?表面上看上去记录每个种类照片数量的状态是 $O(n)$ 的,但是并不是。显然,我们先对于 $r$ 端跳跃的时候使用数组 $a$ 记录下每种照片的数量,$l$ 端跳跃的时候用数组 $b$ 记录下每种照片的数量。

然后,我们使用 $t$ 数组记录 $b$ 中每个元素上次修改是在第几次操作的时候,如果上次修改不是当前操作,那么我们将 $t$ 数组更新为当前操作值,同时将 $b$ 数组中当前元素变更为 $a$ 数组对应下标的元素 。这样我们只要在移动 $l$ 的时候对 $b$ 数组进行判断更新即可。

然后输出答案就好了。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int n,Q,a[100001],cnt,key[100001],book[2][100001],size,t[100001],now,C;
int L,R,lnow;
long long ans,Ans[100001],maxx,nowmax;
void Max(long long &a,long long b){if(b>a)a=b;}
struct Que
{
    int l,r,q,d;
}k[100001];
struct number
{
    int num,d;
}num[100001];
bool cmp(number a,number b){return a.num<b.num;}
bool cmp2(Que a,Que b){return a.q!=b.q?a.q<b.q:a.r<b.r;}
long long Pow(int l,int r)
{
    long long maxx=0;
    int book[100001]={0};
    for(int i=l;i<=r;i++)
        Max(maxx,1ll*(++book[a[i]])*key[a[i]]);
    return maxx;
}
void And(int x)
{
    if(t[a[x]]!=now)
    {
        t[a[x]]=now;
        book[1][a[x]]=book[0][a[x]];
    }
}
void Add(int x)
{
    And(x);
    Max(nowmax,1ll*(++book[1][a[x]])*key[a[x]]);
}
void add(int x)
{
    Max(maxx,1ll*(++book[0][a[x]])*key[a[x]]);
}
int main()
{
    cin>>n>>Q;
    size=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i].num);
        num[i].d=i;
    }
    sort(num+1,num+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(num[i].num!=num[i-1].num)
            key[++cnt]=num[i].num;
        a[num[i].d]=cnt;
    }
    for(int i=1;i<=Q;i++)
    {
        scanf("%d%d",&k[i].l,&k[i].r);
        k[i].d=i,k[i].q=k[i].l/size;
        if(k[i].r-k[i].l<=size)
        {
            Ans[i]=Pow(k[i].l,k[i].r);
            k[i].q=1e9;
            C++;
        }
    }
    sort(k+1,k+Q+1,cmp2);
    k[0].q=-1;
    for(int i=1;i<=Q-C;i++)
    {
        now++;
        if(k[i].q!=k[i-1].q)
        {
            lnow=(k[i].q+1)*size,nowmax=maxx=0,R=(k[i].q+1)*size-1;
            memset(book,0,sizeof(book));
        }
        L=lnow;
        while(R<k[i].r)add(++R);
        nowmax=maxx;
        while(L>k[i].l)Add(--L);
        Ans[k[i].d]=nowmax;
    }
    for(int i=1;i<=Q;i++)
        printf("%lld\n",Ans[i]);
}