欢迎访问~原文出处——

 

 

Description

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

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

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

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

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

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

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

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

Input

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

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

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

Output

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

Sample Input

5 5

9 8 7 8 9

1 2

3 4

4 4

1 4

2 4

Sample Output

9

8

8

16

16

HINT

1<=N<=10^5

1<=Q<=10^5

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

Source

JOI 2013~2014 春季training合宿 竞技1 By PoPoQQQ

 

 

题目概括

　　给出一个序列，其中有n个数字。

　　现在给出m个询问，每次询问格式为L  R。我们设一个值在L~R范围内的重要度为该值乘上该值在L~R范围内出现过的次数。求L~R范围内重要度最大的数值的重要度。

Sample Input

5 5

9 8 7 8 9

1 2

3 4

4 4

1 4

2 4

Sample Output

9

8

8

16

16

样例解释

对于询问1，1~2范围内，9出现了1次，重要度为9；8出现了1次，重要度为8；所以该区间内重要度最大为9；

对于询问2，3~4范围内，7出现了1次，重要度为7；8出现了1次，重要度为8；所以该区间内重要度最大为8；

对于询问3，4~4范围内，8出现了1次，重要度为8；所以该区间内重要度最大为8；

对于询问4，1~4范围内，7出现了1次，重要度为7；8出现了2次，重要度为16；9出现了1次，重要度为9；所以该区间内重要度最大为8；

对于询问5，2~4范围内，7出现了1次，重要度为7；8出现了2次，重要度为16；所以该区间内重要度最大为8；

 

题解

　　首先，无可置疑，离散化总要做的，闭着眼睛先做了。

　　假设我们对于一个数值，设置其哈希值为棋离散化后的位置。

 

　　然后思考，在线不会做，那么离线；

　　那么就可以使用莫队算法——不会，没事，现学~

　　

　　然后我还是来概括一下。

　　

　　我们把询问按照一定的顺序排列，然后大暴力修改边界值（比如从Li~Li-1，Ri~Ri-1这种段的修改），那么时间复杂度为Σ(|Li-Li-1|+|Ri-Ri-1|)  (1<i<=m)

　　我们要使得这个值最小，可以采用分块的方法。

　　我们把整个区间（共n）分成每 sqrt(n) 一份，然后把询问以 L 所在的块的位置为第一关键字，把R作为第二关键字排序，然后就可以得到一个大约是 m sqrt(n) 的时间复杂度。

　　

　　不要把莫队之后的处理看的很麻烦，其实就是大暴力！

　　

　　关键在于莫队的排序。

　　

　　而本题要求的是最大值，所以要开一个堆来维护（要打线段树也可以，我不拦你，有可能是被卡常~）

　　这个堆不简单~

　　

　　它要支持寻找一个数值所对应的位置。

　　

　　一开始打成了一边交换值，一边交换位置的，实际上是有些漏洞的。

　　

　　对于我的算法，我的堆要保存3个量：

　　1.堆中元素的值（在L和R移动的时候，进入一个就在其哈希值的位置上加上其值，减掉的话就反一反）。

　　2.堆中某一哈希值的元素所在位置。

　　3.这样还是不够的，还要给每个元素配上一个它所对应的哈希值。

 

　　至于具体怎么维护~看代码。

　　这题我没写过线段树，不知道怎样。

 

　　反正我的堆是跑了46.7秒，写线段树就自己估计一下吧……也许不是所有的线段树都可以过的（要卡常？）……

　　再在提醒一下，在改变区间范围时候的大暴力时，对于L、R分别要分两种情况讨论。

 

　　具体还是看代码呗~

 

代码

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;const int N=100000+5;int n,m,bag_size;int pos[N],hs,b[N],pv[N];LL a[N],hash[N],v[N];struct Query{    int L,R,bh;    LL ans;}q[N];bool cmp(Query a,Query b){    int La=a.L/bag_size,Lb=b.L/bag_size;    if (La==Lb)        return a.R
          
           >1; if (hash[mid]==x) return mid; if (hash[mid]
           
            >1; while (i>1&&v[i]>v[j]){ pos[pv[i]]=j,pos[pv[j]]=i; swap(pv[i],pv[j]); swap(v[i],v[j]); i=j,j=i>>1; }}void down_sift(int x){ int i=x,j=i<<1; while (j<=hs){ if (j
            
             
              =v[j]) break; pos[pv[i]]=j,pos[pv[j]]=i; swap(pv[i],pv[j]); swap(v[i],v[j]); i=j,j=i<<1; }}int main(){// freopen("mode.in","r",stdin);// freopen("mode.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%lld",&a[i]),hash[i]=a[i]; sort(hash+1,hash+n+1); hs=1; for (int i=2;i<=n;i++) if (hash[i-1]!=hash[i]) hash[++hs]=hash[i]; for (int i=1;i<=n;i++) b[i]=find(a[i]); for (int i=1;i<=hs;i++) pos[i]=i,v[i]=0,pv[i]=i; for (int i=1;i<=m;i++){ scanf("%d%d",&q[i].L,&q[i].R); q[i].bh=i; } bag_size=sqrt((double)n)+0.5; sort(q+1,q+m+1,cmp); int L=q[1].L,R=q[1].L-1; for (int i=1;i<=m;i++){ while (R
              
               q[i].R){ v[pos[b[R]]]-=a[R]; down_sift(pos[b[R]]); R--; } while (L
               
                q[i].L){ L--; v[pos[b[L]]]+=a[L]; up_sift(pos[b[L]]); } q[i].ans=v[1]; } sort(q+1,q+m+1,cmpbh); for (int i=1;i<=m;i++) printf("%lld\n",q[i].ans); return 0;}