给定一个长度为n的序列，m个询问
每次给出一个区间，查找区间内x*cnt[x] 的最大值
由于题目的限制，下一次询问的区间会受到上一次查询结果的影响，所以必须要进行强制在线处理
首先将数列分成ceil(n/blk+1) 块，对于询问中b[l] + 1 -> b[r] - 1这一块中的答案我们可以通过预处理得到，这里的写法类似数列分块入门中的第九题查询区间众数
然后需要做的就是暴力计算左右两边的小块的贡献
在这个数据范围下，先进行离散化处理比较好，对于查询的结果可能比较大，所以数据类型上一定要开long long
ll n,m,a[maxn],b[maxn]; ll blk,mx[357][357],sum[357][maxn],id[maxn],c[357][maxn],cnt[maxn]; vector<ll> vet; int get(ll x) { return lower_bound(vet.begin(),vet.end(),x) - vet.begin() + 1; } void pre(int i) { ll t = 0; Clear(cnt,0); for(int j = (i-1) * blk + 1; j<=n; j++) { cnt[id[j]] ++; t = max(t,cnt[id[j]] * a[j] * 1LL); mx[i][b[j]] = t; } } ll query(int l,int r) { ll ret = 0; if(b[l] == b[r]) { // in the same blk for(int i=l; i<=r; i++) cnt[id[i]] = 0; for(int i=l; i<=r; i++) cnt[id[i]] ++,ret = max(ret,cnt[id[i]] * a[i]); for(int i=l; i<=r; i++) cnt[id[i]] = 0; return ret; } if(b[l] + 1 <= b[r] - 1) ret = mx[b[l] + 1][b[r] - 1]; for(int i=l; i<=min(n,b[l]*blk); i++) cnt[id[i]] = 0; for(int i=(b[r] - 1) * blk + 1; i<=r; i++) cnt[id[i]] = 0; for(int i=l; i<=min(n,b[l]*blk); i++) { cnt[id[i]] ++; ret = max(ret,cnt[id[i]]*a[i] + sum[b[r] - 1][id[i]] - sum[b[l]][id[i]]); } for(int i=(b[r]-1) * blk + 1; i<=r; i++) { cnt[id[i]] ++; ret = max(ret,cnt[id[i]]*a[i] + sum[b[r] - 1][id[i]] - sum[b[l]][id[i]]); } return ret; } int main() { n = read,m = read; blk = sqrt(n); for(int i=1; i<=n; i++) a[i] = read,vet.push_back(a[i]); sort(vet.begin(),vet.end()); vet.erase(unique(vet.begin(),vet.end()),vet.end()); int siz = vet.size(); for(int i=1; i<=n; i++) { b[i] = (i - 1) / blk + 1; id[i] = get(a[i]); c[b[i]][id[i]] += a[i]; } int lim = ceil(1.0 * n / blk);/// amt of the blks for(int i=1; i<=lim; i++) { for(int j = 1; j<=siz; j++) { sum[i][j] = sum[i-1][j]; sum[i][j] += c[i][j]; } } /// pre init for(int i=1; i<=lim; i++) pre(i); Clear(cnt,0); ll lastans = 0LL; for(int i=1; i<=m; i++) { ll l = read,r = read; l = (l ^ lastans) % n + 1; r = (r ^ lastans) % n + 1; if(l > r) swap(l,r); lastans = query(l,r); cout << lastans << endl; } return 0; } /** 5 5 9 8 7 8 9 0 1 10 11 9 9 11 9 16 19 9 8 8 16 16 **/
在这个题的预处理过程中，写法参考求众数的时候的方法
