题目描述

在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。

为了简化起见，我们把所有的蒲公英看成一个长度为n的序列\((a_1,a_2..a_n)\)，其中 \(a_i\)为一个正整数，表示第i棵蒲公英的种类编号。

而每次询问一个区间 [l,r]，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。

注意，你的算法必须是在线的

Solution

分块

但是要维护些什么呢？

假设我们已经对原序列进行了分块，对于一个询问\([l,r]\),我们所寻求的答案很大概率出现在中间的完整的块中，否则，它就一定在两边离散的数中出现过，而这些数是不超过\(2 \sqrt n\)的。

• 所以，我们只要维护一个 \(ans[i][j]\)表示第i块到第j块的答案，这个初始化时\(O(n \sqrt n)\)的。

• 还有就是每个数的出现次数，\(num[x][i]\)表示数x在前i块出现的次数

不过，如果打得不够优美的话是要TLE的。。。

Code 

#include
    
     #define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 40005int N,M,col[MN],fcol[MN],tt[MN],tot;int T,pos[MN],a[205][205],num[MN][205],L[MN],R[MN];inline void init(){    register int i,j;    std::sort(tt+1,tt+tot+1);    tot=std::unique(tt+1,tt+tot+1)-tt-1;    for(i=1;i<=N;++i)    {        int p=col[i];        col[i]=std::lower_bound(tt+1,tt+tot+1,col[i])-tt;        fcol[col[i]]=p;    }    for(i=N;i>=1;--i)    {        if(pos[i]==pos[i-1]) continue;        L[pos[i]]=i;        register int ans=0,bl=pos[i];        for(j=i;j<=N;++j)        {            num[col[j]][bl]++;            if(num[col[j]][bl]>num[ans][bl]) ans=col[j];            if(num[col[j]][bl]==num[ans][bl]&&col[j]
     
      tmp[ans]||(tmp[ans]==tmp[col[i]]&&col[i]
      
       tmp[ans]||(tmp[ans]==tmp[col[i]]&&col[i]
       
        tmp[ans]||(numo==tmp[ans]&&o
        
         r) std::swap(l,r);//      printf("%d %d\n",l,r);        x=query(l,r);        printf("%d\n",x);    }    return 0;}
        
       
      
     
    

那么，分块还有什么用呢

其实，有些时候，我们可以通过只维护块的信息来省省空间

比如求多维偏序的问题，我们考虑对每一维分别排序，然后分块，每个块维护一个下标集合表示该维比这个块小的所有下标

那么按照分块的老套路，对于每个数查询该维比自己小的数的集合是\(O(n \sqrt n)\)的

剩下的就是求每个维的集合的并了?如果你回bitset，它可以做到 \(O(n^2 k/32)\) k是维度数量。。。

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！