首页 > 分享 > 【Nowcoder】武汉大学2020年新生程序设计竞赛E 仓鼠与珂朵莉

【Nowcoder】武汉大学2020年新生程序设计竞赛E 仓鼠与珂朵莉

萌宠菠菠乐园
2024-12-09 07:17

题目链接

补了一个鸽了好久的题目.

题目大意：

进行强制在线的 Q Q Q 次询问，每次询问区间 [ l , r ] [l,r] [l,r] 内最大的 k ∗ ∑ l ≤ i ≤ r [ a i = = k ] k*sum_{l le i le r}{[a_i==k]} k∗∑l≤i≤r[ai==k] ，即一个数的重要程度是该数*该数在区间内出现的次数，询问区间内最大重要程度。

题目思路：

首先类比区间众数的写法，无非求区间众数时，权值是 1 1 1，该题的权值不同而已。

考虑用分块进行维护权值，首先将询问分成 s q r t ( n ) sqrt(n) sqrt(n)个块：

对于每次询问，只需要处理两边的块，因为中间块的块间的最大值，是可以通过预处理得出的：固定一个端点，向右扩展就好了，复杂度 O ( n ∗ s q r t ( n ) ) O(n*sqrt(n)) O(n∗sqrt(n))。

预处理以后，就可以直接枚举两边块中的值，查看这些值是否可以成为新的最大值即可。

建议洛谷搜一下区间众数配套。

Code:

/*** keep hungry and calm CoolGuang! ***/ //#pragma GCC optimize(3) #include <bits/stdc++.h> #include<stdio.h> #include<queue> #include<algorithm> #include<string.h> #include<iostream> #define debug(x) cout<<#x<<":"<<x<<endl; #define dl(x) printf("%lldn",x); #define di(x) printf("%dn",x); typedef long long ll; typedef unsigned long long ull; using namespace std; const ll INF= 1e18+7; const ll maxn = 1e5+700; const ll mod= 998244353; const double eps = 1e-9; const double PI = acos(-1); template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;} ll n,m,p; ll a[maxn]; vector<int>v; int nn = 0; int getid(ll x){return lower_bound(v.begin(),v.end(),x) - v.begin()+1;} int b[maxn],idx[maxn]; ll sum[320][maxn],c[320][maxn],mx[320][320]; ll sz[maxn]; int block = 0; ll query(int l,int r){if(l>r) swap(l,r);ll ans = 0;int s = b[l],t = b[r];int id = 0;if(s == t){for(int i=l;i<=r;i++) sz[idx[i]] = 0;for(int i=l;i<=r;i++) sz[idx[i]]++,ans = max(ans,sz[idx[i]]*a[i]);for(int i=l;i<=r;i++) sz[idx[i]] = 0;return ans;}if(s+1<=t-1) ans = mx[s+1][t-1];for(int i=l;i<=min(n,s*block*1ll);i++) sz[idx[i]] = 0;for(int i=(t-1)*block+1;i<=r;i++) sz[idx[i]] = 0;for(int i=l;i<=min(n,s*block*1ll);i++){sz[idx[i]]++;ans = max(ans,sz[idx[i]]*a[i]+sum[t-1][idx[i]]-sum[s][idx[i]]);}for(int i=(t-1)*block+1;i<=r;i++){sz[idx[i]]++;ans = max(ans,sz[idx[i]]*a[i]+sum[t-1][idx[i]]-sum[s][idx[i]]);}return ans; } int main(){read(n);read(m);block = sqrt(n);for(int i=1;i<=n;i++){read(a[i]);v.push_back(a[i]);}sort(v.begin(),v.end());v.erase((unique(v.begin(),v.end())),v.end());nn = v.size();for(int i=1;i<=n;i++) b[i] = (i-1)/block+1,idx[i] = getid(a[i]);for(int i=1;i<=n;i++) c[b[i]][idx[i]] += a[i];for(int i=1;i<=(n+block+1)/block;i++){for(int k=1;k<=nn;k++) sum[i][k] = sum[i-1][k];for(int k=1;k<=nn;k++) sum[i][k] += c[i][k];}for(int i=1;i<=(n+block+1)/block;i++){ll temp = 0;memset(sz,0,sizeof(sz));for(int k=(i-1)*block+1;k<=n;k++){sz[idx[k]]++;temp = max(temp,sz[idx[k]]*a[k]*1ll);mx[i][b[k]] = temp;}}memset(sz,0,sizeof(sz));ll lastans = 0;for(int i=1;i<=m;i++){ll l,r;read(l);read(r);l = (l^lastans)%n+1ll;r = (r^lastans)%n+1ll;lastans = query(l,r);printf("%lldn",lastans);}return 0; } /** 10 10 1000000 1 2 1 8 3 7 6 9 1 10 4 9 **/

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101