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;
}