[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

  1. 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 ...

  2. 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 ...

  3. 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 ...

  4. 【 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 ...

  5. 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 ...

  6. 【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 ...

  7. BZOJ 2724: [Violet 6] The dandelion

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

  8. 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 , ...

  9. 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

  1. 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 ...

  2. 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 ...

  3. 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 ...

  4. 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 ...

  5. 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 ...

  6. 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 ...

  7. 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 ...

  8. 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 ...

  9. 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 ...

  10. About Apache Cordova

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