luogu P4168 [Violet]蒲公英

分块经典题竟然是一道黑题……

分块求区间众数的大体思想是对于询问区间[L, R]，预处理出这中间的整块的众数，然后统计两边零散的数在[L, R]中出现的次数，最后取出现次数最多且最小的数。

因此需要一个sum[i][j]表示前 i 块中数字 j 出现的次数，ans[i][j]表示块 i 到 j 的众数。预处理sum用前缀和的思想，O(n√n)可完成。预处理ans就是枚举左端点是第几个块，然后每一次从这个块的左端点O(n)扫一遍，复杂度也是O(n√n)。

查询的时候，整块的众数即其个数分别是pos = ans[l + 1][r - 1]，Max = sum[r - 1][pos] - sum[l][pos]。然后零散的数我们单独开一个数组记录一下，同时记录他在零三部分出现的次数num[i]，这样这个数在[L, R]中出现的次数就是sum[r - 1][x] - sum[l][x] + num[x]。最后比较取大。

本题a_i较大，所以要离散化，这并不影响众数。

采纳lba大佬的意见，为了避免重复运算从而降低常数，多开了三个数组分别记录每一个数属于哪个块，以及每一个块的左右端点是多少。

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #include<cctype>

 #include<vector>

 #include<stack>

 #include<queue>

 using namespace std;

 #define enter puts("")

 #define space putchar(' ')

 #define Mem(a, x) memset(a, x, sizeof(a))

 #define rg register

 typedef long long ll;

 typedef double db;

 const int INF = 0x3f3f3f3f;

 const db eps = 1e-;

 const int maxn = 4e4 + ;

 inline ll read()

 {

     ll ans = ;

     char ch = getchar(), last = ' ';

     while(!isdigit(ch)) {last = ch; ch = getchar();}

     while(isdigit(ch)) {ans = ans *  + ch - ''; ch = getchar();}

     if(last == '-') ans = -ans;

     return ans;

 }

 inline void write(ll x)

 {

     if(x < ) x = -x, putchar('-');

     if(x >= ) write(x / );

     putchar(x %  + '');

 }

 int n, m, a[maxn], t[maxn];

 int S, Cnt = , blo[maxn], lb[], rb[];

 int sum[][maxn], ans[][], num[maxn];

 void init()

 {

     S = sqrt(n);

     Cnt = (n % S) ? n / S : n / S + ;

     for(int i = ; i <= Cnt; ++i) lb[i] = (i - ) * S, rb[i] = i * S - ;

     rb[Cnt] = n;   //一定要有，否则会gg

     for(int i = , j = ; i <= n; ++i) blo[i] = j, j += (i == rb[j]);

     for(int i = ; i <= Cnt; ++i)

     {

         for(int j = ; j <= n; ++j) sum[i][j] += sum[i - ][j];

         for(int j = lb[i]; j <= rb[i]; ++j) sum[i][a[j]]++;

     }

     for(int i = ; i <= Cnt; ++i)

     {

         Mem(num, ); int Max = -, pos;

         for(int j = lb[i], k = i; j <= n; ++j)

         {

             if(++num[a[j]] > Max) Max = num[a[j]], pos = a[j];

             if(num[a[j]] == Max && a[j] < pos) pos = a[j];

             if(j == rb[k]) ans[i][k] = pos, k++;

         }

     }

 }

 int temp[], cp = ;

 int query(int L, int R)

 {

     Mem(num, ); cp = ;

     int l = blo[L], r = blo[R];

     int Max = -, pos;

     if(l == r)

     {

         for(int i = L; i <= R; ++i)

         {

             if(++num[a[i]] > Max) Max = num[a[i]], pos = a[i];

             if(num[a[i]] == Max && a[i] < pos) pos = a[i];

         }

         return pos;

     }

     pos = ans[l + ][r - ]; Max = sum[r - ][pos] - sum[l][pos];

     for(int i = L; i <= rb[l]; ++i)

     {

         if(!num[a[i]]) temp[++cp] = a[i];

         num[a[i]]++;

     }

     for(int i = lb[r]; i <= R; ++i)

     {

         if(!num[a[i]]) temp[++cp] = a[i];

         num[a[i]]++;

     }

     for(int i = ; i <= cp; ++i)

     {

         int tp = sum[r - ][temp[i]] - sum[l][temp[i]] + num[temp[i]];

         if(tp > Max) Max = tp, pos = temp[i];

         if(tp == Max && temp[i] < pos) pos = temp[i];

     }

     return pos;

 }

 int Ans = ;

 int main()

 {

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

     for(int i = ; i <= n; ++i) t[i] = a[i] = read();

     sort(t + , t + n + );

     int _n = unique(t + , t + n + ) - t - ;

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

         a[i] = lower_bound(t + , t + _n + , a[i]) - t;

     init();

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

     {

         int L = read(), R = read();

         L = (L + Ans - ) % n + ; R = (R + Ans - ) % n + ;

         if(L > R) swap(L, R);

         Ans = t[query(L, R)];   //别忘了输出原数

         write(Ans), enter;

     }

     return ;

 }

巴特西

luogu P4168 [Violet]蒲公英

最新文章

热门文章