(JOISC2014C)历史的研究 发表于 2020-11-02 | 分类于 solution , 莫队 原题链接(luogu) 思路:回滚莫队 直接使用回滚莫队, 离散化后用数组记录每个数字的出现次数, 每次增加一个元素出现次数+1同时更新答案. 代码:123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121#include <cstdio>#include <cstring>#include <cctype>#include <cmath>#include <algorithm>using namespace std;const int Mn(100500),Mm(100500);void qrd(int& x) { //快读 x = 0; char c = getchar(); while(!isdigit(c)) { c = getchar(); } while(isdigit(c)) { x = x*10 + c-'0'; c = getchar(); }}int a[Mn],shf[Mn],ind[Mn]; //原数组, 离散化后的数组, a到shf的映射struct Que { int l,r,id;}q[Mm];int blk[Mn],blkR[Mn]; //分块编号与分块右端点bool cmp(const Que& x,const Que& y) { //查询区间排序 return blk[x.l]==blk[y.l] ? x.r<y.r : blk[x.l]<blk[y.l];}long long ans[Mm]; //每个查询的答案int cnta[Mn],cntr[Mn]; //数字出现次数, 右区间数字出现次数int main() { int n,m; qrd(n); qrd(m); for(int i(1);i<=n;++i) { qrd(a[i]); shf[i] = a[i]; } /* 离散化 */ sort(shf+1,shf+n+1); int sn = unique(shf+1,shf+n+1) - shf - 1; /* 预处理ind方便查询 */ for(int i(1);i<=n;++i) { ind[i] = lower_bound(shf+1,shf+sn+1,a[i])-shf; } /* 给分块编号并处理出每个分块的右端点 */ int bsz = ceil(sqrt(n)); //分块大小 for(int i(1);i<=n;++i) { blk[i] = blk[i-1]; if(blk[i]*bsz < i) { blkR[blk[i]] = i-1; ++blk[i]; } } for(int i(1);i<=m;++i) { qrd(q[i].l), qrd(q[i].r); q[i].id = i; } sort(q+1,q+m+1,cmp); //查询区间排序 long long tra(0),tca(0); //右区间答案, 总体答案 for(int i(1);i<=m;++i) { Que &x(q[i]),&lx(q[i-1]); /* 左右区间分块相同暴力处理 */ if(blk[x.l]==blk[x.r]) { memset(cnta+1,0,sizeof(int)*sn); tca = 0; for(int j(x.l);j<=x.r;++j) { ++cnta[ind[j]]; tca = max(tca,1ll*cnta[ind[j]]*a[j]); } ans[x.id] = tca; continue; } /* 左端点分块号不同直接重置 */ if(blk[x.l]!=blk[lx.l] || blk[lx.l]==blk[lx.r]) { memset(cnta+1,0,sizeof(int)*sn); memset(cntr+1,0,sizeof(int)*sn); tca = tra = 0; for(int j(blkR[blk[x.l]]);j>=x.l;--j) { ++cnta[ind[j]]; tca = max(tca,1ll*cnta[ind[j]]*a[j]); } for(int j(blkR[blk[x.l]]+1);j<=x.r;++j) { ++cnta[ind[j]]; ++cntr[ind[j]]; tra = max(tra,1ll*cntr[ind[j]]*a[j]); tca = max(tca,1ll*cnta[ind[j]]*a[j]); } } else { /* 左端点大于左指针(即上次查询的左端点)回滚 */ if(x.l>lx.l) { memcpy(cnta+1,cntr+1,sizeof(int)*sn); tca = tra; for(int j(blkR[blk[x.l]]);j>=x.l;--j) { ++cnta[ind[j]]; tca = max(tca,1ll*cnta[ind[j]]*a[j]); } /* 否则向左增加元素 */ } else { for(int j(lx.l-1);j>=x.l;--j) { ++cnta[ind[j]]; tca = max(tca,1ll*cnta[ind[j]]*a[j]); } } /* 向右增加元素并保存右区间查询 */ for(int j(lx.r+1);j<=x.r;++j) { ++cnta[ind[j]]; ++cntr[ind[j]]; tca = max(tca,1ll*cnta[ind[j]]*a[j]); tra = max(tra,1ll*cntr[ind[j]]*a[j]); } } ans[x.id] = tca; } for(int i(1);i<=m;++i) { //打印答案 printf("%lld\n",ans[i]); } return 0;}