当前位置：首页 > news >正文

P4168

news 2026/6/1 19:28:37

P4168

题意简述

给定一个长度为 $ n $ 的序列 $a_i$

强制在线区间求众数

如果有多个众数,求其中最小的

$m$ 次询问

$1≤n≤40000$，$ 1≤m≤50000 $,$1≤a_i≤10^9$

Solution

首先值域与 $ n $ 的大小相差极大

离散化是必然的

已知区间 $[x,y]$ 的众数与区间 $[y+1,z]$ 的众数难以推出 $[x,z]$ 的众数,因此不好使用线段树或树状数组等维护

~~分块连接大脑,卡常代替思考~~

容易想到分块,预处理出以每一个块的右边界为右端点的前缀的桶.

for(int i = 1;i<=cntb;i++){memcpy(cnt[i],cnt[i-1],sizeof(cnt[i]));//继承上一个桶for(int j = L[i];j<=R[i];j++){//本块内出现的数cnt[i][a[j]]++;//维护以本块右边界为右端点的前缀的桶}
}
for(int i = 1;i<=cntb;i++){for(int j = i;j<=cntb;j++){//md即为众数//新的区间的众数只有可能是上一个区间的众数或新块内的数md[i][j] = md[i][j-1];//继承上一个众数区间for(int k = L[j];k<=R[j];k++){//新的块int t1 = a[k];int t2 = md[i][j];if((cnt[j][t1]-cnt[i-1][t1]>cnt[j][t2]-cnt[i-1][t2])||((cnt[j][t1]-cnt[i-1][t1]==cnt[j][t2]-cnt[i-1][t2]) && (t1<t2))){md[i][j] = t1;//计算众数}}}
}

对于每一次询问,答案显然只有可能是连续整块的众数或是散块内出现的数

整块直接查询.散块暴力即可.

分析复杂度:

设块长为 $B$ ,则块数为 $\frac{n}{B}$ ,预处理 $O(\frac{n}{B}*\frac{n}{B} * B) = O(\frac{n^2}{B})$

单次询问 $O(B)$, $m$ 次即为 $O(mB)$

总复杂度 $O(\frac{n^2}{B}+mB)$

为平衡这两项,$B$ 应取 $\frac{n}{\sqrt{m}}$

此时复杂度 $O(n \sqrt{m})$

足以通过此题

Code

#include <bits/stdc++.h>
#define rg register
#define il inline
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using namespace std;
namespace myspace{const char endl = '\n';const int maxn = 4e4+50;const int B = 512;const int maxb = maxn/B+50;int b[maxn],a[maxn];int cnt[maxb][maxn];int tmp[maxb][maxn];int md[maxb][maxb];int n,m;int cntb;int bel[maxn];int L[maxn],R[maxn];void init(){cntb = (n-1)/B+1;for(int i = 1;i<=n;i++){bel[i] = (i-1)/B+1;}for(int i = 1;i<=cntb;i++){L[i] = B*(i-1)+1;R[i] = min(B*i,n);}for(int i = 1;i<=cntb;i++){memcpy(cnt[i],cnt[i-1],sizeof(cnt[i]));memcpy(tmp[i],tmp[i-1],sizeof(tmp[i]));for(int j = L[i];j<=R[i];j++){cnt[i][a[j]]++;tmp[i][a[j]]++;}}for(int i = 1;i<=cntb;i++){for(int j = i;j<=cntb;j++){md[i][j] = md[i][j-1];for(int k = L[j];k<=R[j];k++){int t1 = a[k];int t2 = md[i][j];if((cnt[j][t1]-cnt[i-1][t1]>cnt[j][t2]-cnt[i-1][t2])||((cnt[j][t1]-cnt[i-1][t1]==cnt[j][t2]-cnt[i-1][t2]) && (t1<t2))){md[i][j] = t1;}}}}}il int qry(int l,int r){if(l>r){swap(l,r);}int bl = bel[l];int br = bel[r];int ans = md[bl+1][br-1];if(br-bl<=1){for(int i = l;i<=r;i++){cnt[0][a[i]]++;if(cnt[0][a[i]]>cnt[0][ans] || (cnt[0][a[i]] == cnt[0][ans] && a[i]<ans)){ans = a[i];}}for(int i = l;i<=r;i++){cnt[0][a[i]]--;}return ans;}for(int i = l;i<=R[bl];i++){cnt[br-1][a[i]]++;if((cnt[br-1][a[i]]-tmp[bl][a[i]]>cnt[br-1][ans]-tmp[bl][ans]) || (((cnt[br-1][a[i]]-tmp[bl][a[i]]==cnt[br-1][ans]-tmp[bl][ans])) && (a[i]<ans))){ans = a[i];}}for(int i = L[br];i<=r;i++){cnt[br-1][a[i]]++;if((cnt[br-1][a[i]]-tmp[bl][a[i]]>cnt[br-1][ans]-tmp[bl][ans]) || (((cnt[br-1][a[i]]-tmp[bl][a[i]]==cnt[br-1][ans]-tmp[bl][ans])) && (a[i]<ans))){ans = a[i];}}for(int i = l;i<=R[bl];i++){cnt[br-1][a[i]]--;}for(int i = L[br];i<=r;i++){cnt[br-1][a[i]]--;}return ans;}int x;signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for(int i = 1;i<=n;i++){cin >> b[i];a[i] = b[i];}sort(b+1,b+1+n);int tn = unique(b+1,b+1+n)-b-1;for(int i = 1;i<=n;i++){a[i] = lower_bound(b+1,b+1+tn,a[i])-b;}init();for(int i = 1;i<=m;i++){int l,r;cin >> l >> r;l = (l+x-1)%n+1;r = (r+x-1)%n+1;x = b[qry(l,r)];cout << x << endl;}return 0;}
}
signed main(){#ifdef ONLINE_JUDGE#elsefreopen("in.in","r",stdin);freopen("out.out","w",stdout);#endifmyspace::main();return 0;
}

查看全文

http://www.jsqmd.com/news/917081/