[BZOJ2724][Violet 6] The dandelion

** Test description **

** Input **

Fix it

l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1

** Output **

** Input example **

** Output example **

** Data scale and agreement **

Fix it ：

n <= 40000, m <= 50000

** Answer key **

Block , Preprocess first f[i][j] It means the first one i Block to j The mode of the block , Enumeration starting point i And then just sweep it .

The second is to ask , For an inquiry [ql, qr], among ql Belong to block l,qr Belong to block r, The mode is either f[l+1][r-1], Or numbers in incomplete blocks , So we need to build a calc(l, r, x) function , Asking [l, r] in x Number of occurrences , With this function, you can initially set the answer to f[l+1][r-1]（O(1)）, then O(sqrt(n)) Brute force enumeration of numbers in incomplete blocks , If it happens more than the current one , Just update the answer .

This calc() Functions can do this ： Discrete all the numbers , Write down the position of each number , And then when you ask calc(l, r, x) stay x It can be calculated by bisecting the position sequence of .

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std; const int BufferSize = 1 << 16;

char buffer[BufferSize], *Head, *Tail;

inline char Getchar() {

if(Head == Tail) {

int l = fread(buffer, 1, BufferSize, stdin);

Tail = (Head = buffer) + l;

}

return *Head++;

}

int read() {

int x = 0, f = 1; char c = Getchar();

while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }

while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }

return x * f;

} #define maxn 40010

#define maxq 210

int n, m, num[maxn], A[maxn], st[maxq], en[maxq], bl[maxn], cntb, f[maxq][maxq], cntn[maxn]; vector <int> pos[maxn];

int calc(int l, int r, int x) {

return upper_bound(pos[x].begin(), pos[x].end(), r) - lower_bound(pos[x].begin(), pos[x].end(), l);

}

int query(int ql, int qr) {

int l = bl[ql], r = bl[qr];

if(r - l <= 1) {

int ans = A[ql], mx = calc(ql, qr, ans);

for(int i = ql + 1; i <= qr; i++) {

int tmp = calc(ql, qr, A[i]);

if(mx < tmp || (mx == tmp && ans > A[i])) ans = A[i], mx = tmp;

}

return ans;

}

int ans = f[l+1][r-1], mx = calc(ql, qr, ans);

for(int i = ql; i <= en[l]; i++) {

int tmp = calc(ql, qr, A[i]);

if(mx < tmp || (mx == tmp && ans > A[i])) ans = A[i], mx = tmp;

}

for(int i = st[r]; i <= qr; i++) {

int tmp = calc(ql, qr, A[i]);

if(mx < tmp || (mx == tmp && ans > A[i])) ans = A[i], mx = tmp;

}

return ans;

} int main() {

n = read(); m = read();

int siz = (int)sqrt(n + .5);

for(int i = 1; i <= n; i++) {

num[i] = A[i] = read();

int p = (i - 1) / siz + 1; cntb = p;

if(!st[p]) st[p] = i;

en[p] = i;

bl[i] = p;

} sort(num + 1, num + n + 1);

for(int i = 1; i <= n; i++) A[i] = lower_bound(num + 1, num + n + 1, A[i]) - num;

for(int i = 1; i <= cntb; i++) {

memset(cntn, 0, sizeof(cntn));

for(int j = st[i]; j <= n; j++) {

cntn[A[j]]++;

int r = bl[j];

if(r > i && !f[i][r]) f[i][r] = f[i][r-1];

if(!f[i][r] || cntn[f[i][r]] < cntn[A[j]] || (cntn[f[i][r]] == cntn[A[j]] && f[i][r] > A[j]))

f[i][r] = A[j];

}

}

for(int i = 1; i <= n; i++) pos[A[i]].push_back(i); int x = 0;

while(m--) {

int l = (read() + x - 1) % n + 1, r = (read() + x - 1) % n + 1;

if(l > r) swap(l, r);

int tmp = query(l, r);

printf("%d\n", num[tmp]);

x = num[tmp];

} return 0;

}

## [BZOJ2724][Violet 6] More about dandelion

- BZOJ2724 [Violet 6] The dandelion Block
Link to the original text https://www.cnblogs.com/zhouzhendong/p/BZOJ2724.html Subject portal - BZOJ2724 The question Find the minimum mode of the interval , Forced Online . $n$ Number ,$m ...

- bzoj2724: [Violet 6] The dandelion ( discretization + Block )
I'm so weak .. This question has been adjusted 2 God QwQ The main idea of the topic : Given a length of n(n<=40000) Sequence ,m(m<=50000) Time to ask l~r The most frequent occurrence between .( Interval mode ) If you use the chairman tree, you don't have to deal with a problem ...

- bzoj2724: [Violet 6] The dandelion Block Interval mode On algorithm And vector The right way to open
This , If you want to deal with the numbers, you have to discrete them first , The bucket I use . Let's first find out the mode in each block and in each block interval , So in the query time , May become [l,r] The number of the mode of an interval is only the mode of the middle interval and the number on both sides . prove : If it's not the majority of the number connected interval here ...

- 【 Block 】bzoj2724 [Violet 6] The dandelion
Block , discretization , Preprocessing : ① front i In block x Number of occurrences ( Difference ): ② The first i Block to j Who is the mode in the block , How many times has it appeared . When asked , For the whole part, get the answer directly : For the scattered parts , Violence counts the number of times each number appears , Plus the differential junction ...

- bzoj2724: [Violet 6] The dandelion （ Block ）
Portal md After adjusting for one night, I finally found that the space was smaller …… It's enough …… To tell you the truth, I didn't think much of partition before , I think this kind of data structure based on violence has no aesthetic feeling at all . Today, however, I did this question to discover the beauty of violence ( If I had space ...

- 【BZOJ2724】[Violet 6] The dandelion Block + Two points
[BZOJ2724][Violet 6] The dandelion Description Input Fix it l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n ...

- BZOJ 2724: [Violet 6] The dandelion
2724: [Violet 6] The dandelion Time Limit: 40 Sec Memory Limit: 512 MBSubmit: 1633 Solved: 563[Submit][Status ...

- BZOJ 2724: [Violet 6] The dandelion ( Block )
although AC But the time is terrible ... Unscientific .... How could it be so slow ... Interval mode without modification .. Block , Preprocessing Mode[i][j] It means the first one i Block to j The mode of the block , sum[i][j] Before presentation i block j Number of occurrences ( The prefix and , ...

- BZOJ_2724_[Violet 6] The dandelion _ Block
BZOJ_2724_[Violet 6] The dandelion _ Block Description Input Fix it l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod ...

## Random recommendation

- hosts manager——hosts Configuration management tools
introduction do web Development related is often used hosts Modified function , Every platform seems to have hosts To configure GUI( as far as I am concerned windows Yes .MAC OX Also have ), But command line configuration hosts I don't think so , Command line configuration, there are several ...

- gerrit-git
Explain why gerrit Medium push It needs to be used refs/for/master http://stackoverflow.com/questions/10461214/why-is-git-push-ger ...

- DB2 Escape characters in
1. Database script )); ,'20%'); ,'OLIVER_QIN'); ,'AA''') 2. Here are DB2 The escape character of 2.1 Yes “%” The escape of SELECT * FROM OLIVER_11 WHER ...

- C++ Function parameter transfer mechanism and parameter type selection
C++primer And the type of parameter One : Basic knowledge of functions (1) Function elements : Return type , Function name , Shape parameter ( Parameters are separated by commas ) (2) Function call mechanism : We do this by calling operators ...

- FastDFS Installation configuration
FastDFS FastDFS Tailor-made for the Internet , Redundant backups are fully considered . Load balancing . Linear capacity expansion mechanism , And focus on high availability . High performance and other indicators , Use FastDFS It is easy to set up a high performance file server cluster for file uploading . Download and other services ...

- Hough Transformation
effect Hough transform is a common image transform , Used to find straight lines in an image . round . Ellipses and other geometric figures with the same characteristics . In many applications , We need to realize the rapid positioning of objects with specific shapes , The Hough transform is insensitive to direction and noise , So in this kind of application ...

- java Download pictures remotely
When copying articles from other websites , To download the pictures to our website , Change the picture address to our website address <img id="mbkenHUwhWeOj9U8K6c8LlAXaes3oXit-M4SnmRvB4 ...

- ML How to use activation function
sigmoid .tanh .ReLu tanh Functions or hyperbolic tangent functions are generally better than sigmoid The activation function of the function . I don't use it anymore sigmoid Activate function ,tanh Function is better than... In all cases sig ...

- Python + Robot Framework Environment building
One .Python install explain : because RIDE Is based on python2.x Development , I didn't do it later python3.x compatible , So here's the installation python2.7. link : https://pan.baidu.com/s/1yf ...

- About Apache Cordova
Apache Cordova is a set of device APIs that allow a mobile app developer to access native device fun ...