【洛谷 P4168】[Violet]蒲公英（分块）

题目链接

题目大意：给定\(n\)个数和\(m\)个求区间众数的询问，强制在线

这题我\(debug\)了整整一个下午啊。。-_- 从14：30~16：45终于\(debug\)出来了，\(debug\)的难度主要就在\(Luogu\)数据不能下载，然后\(Contest Hunter\)的数据又太大了（最小的\(n=500,m=1000\)），只能人工查错，一行行检查代码，哎。。。写不出正解还是算了吧，考试时可没有这么多时间\(debug\)。

做法：先离散化，然后分块，每块大小\(\sqrt n\)，预处理任意两块之间的众数，每个编号前\(k\)块出现的次数，也就是前缀和，我们就能很快求出任意两块之间\(k\)出现的次数了。

把要求的区间\([l,r]\)分成3个部分，左边不足一块的部分，右边不足一块的部分和中间的很多块，那么众数只可能出现在：

1，左边、右边不足一块的部分

2，中间很多块的众数

也就是说，中间很多块的不是众数又没在左右两部分出现过的，都不可能是\([l,r]\)的众数。

于是暴力扫一边左右两个部分，对于每个数\(i\)，第一次扫到\(i\)的时候把计数器加上中间那些块里面\(i\)的出现次数，不断更新众数。

最后判断一下如果中间那些块的众数没在左右部分出现过，那么再用中间那些块的众数尝试更新答案。

Code:

（保留了debug）

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <cstring>

#define re register

const int MAXN = 40010;

const int MAXSIZE = 800;

using namespace std;

inline int read(){

    int s = 0, w = 1;

    char ch = getchar();

    while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }

    while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }

    return s * w;

}

struct point{

    int id, val;

    point(){ id = val = 0; }

    bool operator < (const point A) const{

        return val < A.val;

    }

}s[MAXN];

int SIZE;

int common[MAXSIZE][MAXSIZE], belong[MAXN], a, b, pos[MAXN], p[MAXN][MAXSIZE], c[MAXN], d[MAXN], cnt, num, ans;

int n, m;

inline int get(int l, int r, int k){

    return p[k][r] - p[k][l - 1];

}

int Solve(int l, int r){

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

    int Com = 0, Max = 0;

    if(belong[l] == belong[r]){

      for(int i = l; i <= r; ++i)

         if(++c[pos[i]] > Max || (c[pos[i]] == Max && pos[i] < Com)) Max = c[pos[i]], Com = pos[i];

      for(int i = l; i <= r; ++i)

         c[pos[i]] = 0;

    }

    else if(belong[r] - belong[l] == 1){

      int e = belong[l] * SIZE;

      for(int i = l; i <= e; ++i)

         if(++c[pos[i]] > Max || (c[pos[i]] == Max && pos[i] < Com)) Max = c[pos[i]], Com = pos[i];

      for(int i = (belong[r] - 1) * SIZE + 1; i <= r; ++i)

         if(++c[pos[i]] > Max || (c[pos[i]] == Max && pos[i] < Com)) Max = c[pos[i]], Com = pos[i];

      for(int i = l; i <= e; ++i)

         c[pos[i]] = 0;

      for(int i = (belong[r] - 1) * SIZE + 1; i <= r; ++i)

         c[pos[i]] = 0;

    }

    else{

      int e = belong[l] * SIZE;

      for(int i = l; i <= e; ++i){

         if(++c[pos[i]] == 1) c[pos[i]] += get(belong[l] + 1, belong[r] - 1, pos[i]);

         if(c[pos[i]] > Max || (c[pos[i]] == Max && pos[i] < Com)) Max = c[pos[i]], Com = pos[i];

      }

      for(int i = (belong[r] - 1) * SIZE + 1; i <= r; ++i){

         if(++c[pos[i]] == 1) c[pos[i]] += get(belong[l] + 1, belong[r] - 1, pos[i]);

         if(c[pos[i]] > Max || (c[pos[i]] == Max && pos[i] < Com)) Max = c[pos[i]], Com = pos[i];

      }

      int L = belong[l] + 1; int R = belong[r] - 1;

      if(!c[common[L][R]]){

        c[common[L][R]] += get(L, R, common[L][R]);

        if(c[common[L][R]] > Max || (c[common[L][R]] == Max && common[L][R] < Com)) Com = common[L][R];

        c[common[L][R]] = 0;

      }

      for(int i = l; i <= e; ++i)

         c[pos[i]] = 0;

      for(int i = (belong[r] - 1) * SIZE + 1; i <= r; ++i)

         c[pos[i]] = 0;

    }

    return d[Com];

}

int main(){

    //freopen("xsxs.txt","r",stdin);

    //freopen("xslb.txt","w",stdout);

    scanf("%d%d", &n, &m);

    SIZE = sqrt(n + 0.5); num = ceil((double)n / SIZE);

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

       belong[i] = (i - 1) / SIZE + 1;    //属于哪块

       s[i].id = i;

       scanf("%d", &s[i].val);

    }

    sort(s + 1, s + n + 1);

    for(int i = 1; i <= n; ++i){    //离散化

       if(s[i].val != s[i - 1].val)

         pos[s[i].id] = ++cnt;

       else pos[s[i].id] = cnt;

       d[cnt] = s[i].val;

    }

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

       ++p[pos[i]][belong[i]];

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

       for(int j = 2; j <= num; ++j)

          p[i][j] += p[i][j - 1];    //前缀和

    for(int i = 1; i <= num; ++i){     //任意两块的众数

       int Max = 0, cm = 0;

       for(int j = i; j <= num; ++j){

          for(int k = (j - 1) * SIZE + 1; k <= SIZE * j; ++k)

             if(++c[pos[k]] > Max || (c[pos[k]] == Max && pos[k] < cm))     //出现次数最多且编号最小的为众数

               Max = c[pos[k]], cm = pos[k];

          common[i][j] = common[j][i] = cm;

       }

       memset(c, 0, sizeof c);

    }

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

       scanf("%d%d", &a, &b);

       printf("%d\n", ans = Solve((a + ans - 1) % n + 1, (b + ans - 1) % n + 1));

    }

    /*int Max = 0;

    for(int i = 60; i <= 362; ++i){

       printf("%d ", d[pos[i]]);

       if(d[pos[i]] == 39881273) printf("\n%d\n", pos[i]);

       if(++c[pos[i]] > Max) Max = c[pos[i]];

    }*/

    //printf("\n%d", d[41]);

    //fclose(stdin);

    //fclose(stdout);

    //system("pause");

    return 0;

}

【洛谷 P4168】[Violet]蒲公英（分块）的相关教程结束。