首页 > 分享 > 仓鼠与珂朵莉分块+DP

仓鼠与珂朵莉分块+DP

萌宠菠菠乐园
2025-01-06 21:50

题目

(仓鼠与珂朵莉)https://ac.nowcoder.com/acm/problem/213938

思路

我们发现是没有修改的。每次询问一个区间：区间每个数的权值=这个数*区间出现的次数。
问这个区间所有数权值的最大值。强制在线。

把a[i]离散化，我们考虑分块。
并且预处理出：
dp[i][j]" role="presentation">dp[i][j]:块i~块j的答案。
f[i][j]" role="presentation">f[i][j]:块1~块i。数字j出现的次数。

对于每次询问：我们分成3个部分。
要么答案是dp[i][j]，要么这个数在两边的块中。
对于两边块的每个数，我们暴力统计出现的次数就可以了。

cpp

#include <bits/stdc++.h> #define LL long long using namespace std; int a[100005]; struct LSH { int b[100005]; int lsh(int a[], int n) { for(int i=1; i<=n; i++) b[i]=a[i]; sort(b+1, b+n+1); int cnt=unique(b+1, b+n+1)-b-1; for(int i=1; i<=n; i++) { a[i]=lower_bound(b+1, b+cnt+1, a[i])-b; } return cnt; } int id(int x) { return b[x]; } } Lsh; struct Fk{ int id[100005], pos[100005], len; int s[405][100005]; LL dp[405][405]; LL cut[100005]; void init(int n){ len=sqrt(n); for(int i=1; i<=n; i++){ id[i]=(i-1)/len+1; if(!pos[id[i]]) pos[id[i]]=i; } pos[id[n]+1]=n+1; for(int i=1; i<=n; i++){ s[id[i]][a[i]]++; dp[id[i]][id[i]]=max(dp[id[i]][id[i]], 1ll*Lsh.id(a[i])*s[id[i]][a[i]]); } for(int i=1; i<=id[n]; i++){ for(int j=1; j<100005; j++){ s[i][j]+=s[i-1][j]; } } for(int i=1; i<=id[n]; i++){ for(int j=i+1; j<=id[n]; j++){ LL mx=dp[i][j-1]; for(int k=pos[j]; k<min(n+1, pos[j+1]); k++){ cut[a[k]]++; mx=max(mx, Lsh.id(a[k])*(cut[a[k]]+s[j-1][a[k]]-s[i-1][a[k]])); } for(int k=pos[j]; k<pos[j+1]; k++){ cut[a[k]]--; } dp[i][j]=mx; } } } LL qeury(int L, int R){ LL mx=dp[id[L]+1][id[R]-1]; for(int i=L;i<=min(id[L]*len,R);i++){ cut[a[i]]++; if(id[R]>id[L]){ mx=max(mx, Lsh.id(a[i])*(cut[a[i]]+s[id[R]-1][a[i]]-s[id[L]][a[i]])); } else{ mx=max(mx, Lsh.id(a[i])*cut[a[i]]); } } if(id[L]!=id[R]){ for(int i=(id[R]-1)*len+1;i<=R;i++){ cut[a[i]]++; if(id[R]>id[L]){ mx=max(mx, Lsh.id(a[i])*(cut[a[i]]+s[id[R]-1][a[i]]-s[id[L]][a[i]])); } else{ mx=max(mx, Lsh.id(a[i])*cut[a[i]]); } } } for(int i=L;i<=min(id[L]*len,R);i++){ cut[a[i]]--; } if(id[L]!=id[R]){ for(int i=(id[R]-1)*len+1;i<=R;i++){ cut[a[i]]--; } } return mx; } }fk; int main() { int n, m; scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) scanf("%d", &a[i]); Lsh.lsh(a, n); fk.init(n); LL last=0; while(m--){ int L, R; scanf("%d%d", &L, &R); L=(L^last)%n+1; R=(R^last)%n+1; if(L>R) swap(L, R); printf("%lldn", last=fk.qeury(L, R)); } return 0; }

__EOF__