首页 > 代码库 > bzoj4241 历史研究
bzoj4241 历史研究
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
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4
Sample Output
9
8
8
16
16
8
8
16
16
HINT
1<=N<=10^5
1<=Q<=10^5
1<=Xi<=10^9 (1<=i<=N)
正解：分块。
一开始看错题，觉得这题好水。。然后花20分钟写了个错的。。不过看清题以后好像还是很水啊。。
我们记录两个东西，$w[i][j]$表示前$i$个块内$j$出现的次数，这个可以在$O(n\sqrt{n})$的时间内用前缀和解决。
$f[i][j]$表示第$i$个块到第$j$个块的重要度最大值，因为指针往后移动时，最大值只会越来越大，所以这个也可以根据单调性在$O(n\sqrt{n})$的时间内解决。
然后我们就可以愉快地查询了。如果$l$和$r$在同一个块，那么我们直接暴力搞搞。
如果$l$和$r$不在同一个块，那么我们就要先把$l$的后一个块和$r$的前一个块的最大值取出来。然后指针从$r$所在的块的右端点往左移，更新最大值；指针再从$l$所在的块的左端点往右移，更新最大值。
于是我们就完美地解决了这道题。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <cmath>10 #include <queue>11 #include <stack>12 #include <map>13 #include <set>14 #define inf (1<<30)15 #define N (100010)16 #define il inline17 #define RG register18 #define ll long long19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)20 21 using namespace std;22 23 //w[i][j]表示前i个块j事件个数,前缀和O(nsqrt(n))24 //f[i][j]表示第i个块到j个块重要度最值,单调扫扫O(nsqrt(n))25 26 int w[320][N],a[N],bl[N],LL[N],RR[N],n,q,tot,totb,block;27 ll f[320][320],c[N],hsh[N],ans;28 29 il int gi(){30 RG int x=0,q=1; RG char ch=getchar();31 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();32 if (ch==‘-‘) q=-1,ch=getchar();33 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();34 return q*x;35 }36 37 il void work(){38 n=gi(),q=gi(),block=sqrt(n),totb=(n-1)/block+1;39 for (RG int i=1;i<=n;++i){40 a[i]=gi(),hsh[++tot]=a[i],bl[i]=(i-1)/block+1;41 if (!LL[bl[i]]) LL[bl[i]]=i; RR[bl[i]]=i;42 }43 sort(hsh+1,hsh+tot+1),tot=unique(hsh+1,hsh+tot+1)-hsh-1;44 for (RG int i=1;i<=n;++i) a[i]=lower_bound(hsh+1,hsh+tot+1,a[i])-hsh;45 for (RG int i=1;i<=totb;++i){46 for (RG int j=1;j<=tot;++j) w[i][j]+=w[i-1][j];47 for (RG int j=LL[i];j<=RR[i];++j) w[i][a[j]]++;48 memset(c,0,sizeof(c)); ans=0;49 for (RG int j=i;j<=totb;++j){50 for (RG int k=LL[j];k<=RR[j];++k) c[a[k]]++,ans=max(ans,c[a[k]]*hsh[a[k]]);51 f[i][j]=ans;52 }53 }54 RG int l,r; memset(c,0,sizeof(c));55 while (q--){56 l=gi(),r=gi(),ans=0;57 if (bl[l]==bl[r]){58 for (RG int i=l;i<=r;++i) c[a[i]]++,ans=max(ans,c[a[i]]*hsh[a[i]]);59 for (RG int i=l;i<=r;++i) c[a[i]]--;60 } else{61 ans=f[bl[l]+1][bl[r]-1];62 for (RG int i=RR[bl[l]];i>=l;--i)63 c[a[i]]++,ans=max(ans,(ll)(c[a[i]]+w[bl[r]-1][a[i]]-w[bl[l]][a[i]])*hsh[a[i]]);64 for (RG int i=LL[bl[r]];i<=r;++i)65 c[a[i]]++,ans=max(ans,(ll)(c[a[i]]+w[bl[r]-1][a[i]]-w[bl[l]][a[i]])*hsh[a[i]]);66 for (RG int i=RR[bl[l]];i>=l;--i) c[a[i]]--;67 for (RG int i=LL[bl[r]];i<=r;++i) c[a[i]]--;68 }69 printf("%lld\n",ans);70 }71 return;72 }73 74 int main(){75 File("research");76 work();77 return 0;78 }
bzoj4241 历史研究
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。