# [洛谷 4168][Violet 6] 蒲公英【普通分块】

• 2018-02-12
• 0
• 0

## Problem:

### 题目背景

Azure 读完这封信之后微笑了一下。

“蒲公英吗……”

6 3
1 2 3 2 1 2
1 5
3 6
1 5

1
2
1

## Solution:

# 蛤？洛谷上难度竟然有 NOI/NOI+/CTSC。。吓人的吧。。 #

• 对于可重集合 A 和 B，若 A 中众数为 a，则 A ∪ B 的众数只可能为 a 或某个 b ∈ B

## Code: O(n1.5+mn0.5) [21085K, 5832MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

template<typename T>
inline void getint(T &num){
char ch;
while(!isdigit(ch = getchar()));
num = ch - '0';
while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int n, m, a[40002], blocksz, blockcnt, l, r, ans;
int bl[40002], disc[40002];
int cnt[202][40002], sum[202][40002], mas[202][202];
int qnum[402], topq, qcnt[40002];

inline int query(int l, int r){
topq = 0, memset(qcnt, 0, sizeof(qcnt));
if(bl[l] == bl[r]){
for(register int i = l; i <= r; i++)
if(++qcnt[a[i]] == 1) qnum[++topq] = a[i];
}
else{
for(register int i = bl[l] * blocksz; i >= l; i--)
if(++qcnt[a[i]] == 1) qnum[++topq] = a[i];
for(register int i = (bl[r] - 1) * blocksz + 1; i <= r; i++)
if(++qcnt[a[i]] == 1) qnum[++topq] = a[i];
for(register int i = 1; i <= topq; i++)
qcnt[qnum[i]] += sum[bl[r] - 1][qnum[i]] - sum[bl[l]][qnum[i]];
if(bl[l] + 1 < bl[r]){
int &midmas = mas[bl[l] + 1][bl[r] - 1];
if(qcnt[midmas] == 0){
qnum[++topq] = midmas;
qcnt[midmas] = sum[bl[r] - 1][midmas] - sum[bl[l]][midmas];
}
}
}
int id = 0;
for(register int i = 1; i <= topq; i++)
if(qcnt[qnum[i]] > qcnt[id] || (qcnt[qnum[i]] == qcnt[id] && qnum[i] < id))
id = qnum[i];
return disc[id];
}

int main(){
getint(n), getint(m);
blocksz = (int)ceil(sqrt(n)), blockcnt = (n - 1) / blocksz + 1;
for(register int i = 1; i <= n; i++) bl[i] = (i - 1) / blocksz + 1;
for(register int i = 1; i <= n; i++) getint(a[i]), disc[i] = a[i];
sort(disc + 1, disc + n + 1);
int d = unique(disc + 1, disc + n + 1) - disc - 1;
for(register int i = 1; i <= n; i++)
a[i] = lower_bound(disc + 1, disc + d + 1, a[i]) - disc;
// Discretization
for(register int i = 1; i <= n; i++) cnt[bl[i]][a[i]]++;
for(register int i = 1; i <= blockcnt; i++)
for(register int j = 1; j <= d; j++)
sum[i][j] = sum[i - 1][j] + cnt[i][j];
for(register int i = 1; i <= blockcnt; i++){
mas[i][i] = 0;
for(register int j = 1; j <= d; j++)
if(cnt[i][j] > cnt[i][mas[i][i]]) mas[i][i] = j;
}
for(register int i = 1; i < blockcnt; i++)
for(register int j = i + 1; j <= blockcnt; j++){
int &curmas = mas[i][j];
curmas = mas[i][j - 1];
int mxmas = sum[j][mas[i][j]] - sum[i - 1][mas[i][j]];
for(register int k = (j - 1) * blocksz + 1; k <= j * blocksz; k++){
int kmas = sum[j][a[k]] - sum[i - 1][a[k]];
if(kmas > mxmas || (kmas == mxmas && a[k] < curmas))
curmas = a[k], mxmas = kmas;
}
}
for(register int i = 1; i <= m; i++){
int l_, r_;
getint(l_), getint(r_);
l = (l_ + ans - 1) % n + 1, r = (r_ + ans - 1) % n + 1;
if(l > r) swap(l, r);
ans = query(l, r);
printf("%d\n", ans);
}
return 0;
}

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai