首页 > 代码库 > [bzoj4241][历史研究] (分块)

[bzoj4241][历史研究] (分块)

2024-09-01 20:50:55   219人阅读

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 59 8 7 8 91 23 44 41 42 4

Sample Output

9881616

HINT

1<=N<=10^5

1<=Q<=10^5

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

Source

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

Solution

时限很仁慈，毕竟这题正解就是分块（～常数大的写法慢成狗）

对序列分块，离散化一下，用桶记录出现次数，用块做一个前缀和，再用块的数量的平方的时间跑一个o(x^2)的暴力rmq，就可以预处理所有的初值。

最后对每个询问还是一样的套路，整块的就不枚，直接调用，不完整块的就暴力求解(~你的程序怎么越来越丑(man)了)

//Kaiba_Seto 20170120//orz cjkmao#include <math.h>#include <stdio.h>#include <memory.h>#include <algorithm>#define MaxN 100010#define MaxS 350#define RG register#define inline __inline__ __attribute__((always_inline))#define L long long#define dmin(a,b) ((a)<(b)?(a):(b))#define dmax(a,b) ((a)>(b)?(a):(b))namespace io{#define MaxBuf 1<<22#define _getc() ((S==T&&(T=(S=B)+fread(B,1,MaxBuf,stdin),S==T))?0:*S++)  char B[MaxBuf],*S=B,*T=B;  template<class Type>inline void Rin(RG Type &x){    x=0;RG int c=getchar();RG bool b=0;    for(;c<48||c>57;c=getchar())      if(c==45)b=1;    for(;c>47&&c<58;c=getchar())      x=(x<<1)+(x<<3)+c-48;    if(b)x=-x;  }};int n,_q,a[MaxN],_reflection[MaxN],block_size,block_cnt[MaxS][MaxN],belong[MaxN],lef[MaxS],rig[MaxS];L block_rmq[MaxS][MaxS];struct _pair{  int first,*second;  bool operator < (const _pair &other) const {    return first < other.first;  }}c[MaxN];inline L query(RG int x,RG int y){  static int tmp_tim[MaxN],tmp_cnt[MaxN],T=0;  RG int _l=belong[x],_r=belong[y];  RG L res=block_rmq[_l+1][_r-1]; ++T;  if(_l == _r){    for(RG int i=x;i<=y;i++){      if(tmp_tim[a[i]] != T){    tmp_tim[a[i]]=T; tmp_cnt[a[i]]=0;      }      ++tmp_cnt[a[i]];      res=dmax(res,(L) _reflection[a[i]] * tmp_cnt[a[i]]);    }    return res;  }  for(RG int i=x;i<=:: rig[_l];i++){    if(tmp_tim[a[i]] != T){      tmp_tim[a[i]]=T; tmp_cnt[a[i]]=block_cnt[_r-1][a[i]]-block_cnt[_l][a[i]];    }    ++tmp_cnt[a[i]];    res=dmax(res,(L) _reflection[a[i]] * tmp_cnt[a[i]]);  }  for(RG int i=:: lef[_r];i<=y;i++){    if(tmp_tim[a[i]] != T){      tmp_tim[a[i]]=T; tmp_cnt[a[i]]=block_cnt[_r-1][a[i]]-block_cnt[_l][a[i]];    }    ++tmp_cnt[a[i]];    res=dmax(res,(L) _reflection[a[i]] * tmp_cnt[a[i]]);  }  return res;}int main(){  io::Rin(n),io::Rin(_q);  block_size=static_cast<int>(sqrt(n)+1e-6);  for(RG int i=1;i<=n;i++)    io::Rin(c[i].first),c[i].second=&a[i];  std::sort(c+1,c+1+n);  for(RG int i=1,m=0;i<=n;i++){    if(i==1 || c[i].first != c[i-1].first)      _reflection[++m]=c[i].first;    *c[i].second=m;  }  for(RG int i=1;i<=n;i++)    belong[i]=(i-1)/block_size+1;  for(RG int i=1;i<=n;i++)    block_cnt[belong[i]][a[i]]++;  for(RG int i=1;(i-1)*block_size+1<=n;i++)    lef[i]=(i-1)*block_size+1,rig[i]=dmin(i*block_size,n);  for(RG int i=1;:: lef[i];i++)    for(RG int j=1;j<=n;j++)      block_cnt[i][j]+=block_cnt[i-1][j];  for(RG int i=1;lef[i];i++){    static int tmp_cnt[MaxN]; RG L ans=0LL;    memset(tmp_cnt,0,sizeof tmp_cnt);    for(RG int j=lef[i];j<=n;j++){      ++tmp_cnt[a[j]];      ans=dmax(ans,(L) _reflection[a[j]] * tmp_cnt[a[j]]);      if(j == rig[belong[j]])    :: block_rmq[i][belong[j]]=ans;    }  }  while(_q--){    RG int x,y;    io::Rin(x),io::Rin(y);    printf("%lld\n",query(x,y));  }  fclose(stdin);  return 0;}

 

[bzoj4241][历史研究] (分块)


联系
我们