loj#6285. 数列分块入门 9

#6285. 数列分块入门 9

题目：传送门

简要题意：

　　给出一个长为

题解：

　　很开心，最后一题...分块刷的非常高（恶）兴（心）！

　　据说原题是一道超级大难题...还是先做做简单的吧...

　　首先用dp求出第i块到第j块的最小众数...

　　然后神奇的stl开始来袭...

　　依旧分情况走一波...

　　对于我们需要处理的其中一段小区间，那么可以用一个vector将不同种类的数所出现的位置先存起来，那么就可以用upper_bound右端点-lower_bound左端点...（具体的就看代码吧）

　　大槽点：对于不会用stl的蒟蒻...以为upper_bound如果找不到答案就会返回最后一个位置...自信的认为hzwer的代码是错的...结果...手测一波，发现返回的是末尾指针加1？？？好的hzwer大佬我错了ORZ

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<map>
 7 #include<vector>
 8 using namespace std;
 9 int n,id,a[110000],ba[110000],cnt[51000];
10 int block,pos[110000];
11 int f[510][510];//第i块到第j块的最小众数是第几种数
12 map<int,int>mp;
13 vector<int>w[51000];
14 void dp(int x)
15 {
16     memset(cnt,0,sizeof(cnt));
17     int mx=0,ans=0;
18     for(int i=(x-1)*block+1;i<=n;i++)
19     {
20         int cc=++cnt[a[i]];int k=pos[i];
21         if(cc>mx || (cc==mx && ba[a[i]]<ba[ans]))mx=cc,ans=a[i];
22         f[x][k]=ans;
23     }
24 }
25 int getlong(int l,int r,int x)
26 {
27     int ans=upper_bound(w[x].begin(),w[x].end(),r)-lower_bound(w[x].begin(),w[x].end(),l);
28     return ans;
29 }
30 int sol(int l,int r)
31 {
32     int ans=0,mx=0;
33     ans=f[pos[l]+1][pos[r]-1];
34     mx=getlong(l,r,ans);
35     for(int i=l;i<=min(pos[l]*block,r);i++)        
36     {
37         int cc=getlong(l,r,a[i]);
38         if(cc>mx || (cc==mx && ba[a[i]]<ba[ans]))mx=cc,ans=a[i];
39     }
40     if(pos[l]!=pos[r])
41         for(int i=(pos[r]-1)*block+1;i<=r;i++)
42         {
43             int cc=getlong(l,r,a[i]);
44             if(cc>mx || (cc==mx && ba[a[i]]<ba[ans]))mx=cc,ans=a[i];
45         }
46     return ans;
47 }
48 int main()
49 {
50     memset(ba,63,sizeof(ba));
51     scanf("%d",&n);block=sqrt(n);id=0;
52     for(int i=1;i<=n;i++)pos[i]=(i-1)/block+1;
53     for(int i=1;i<=n;i++)
54     {
55         scanf("%d",&a[i]);
56         if(!mp[a[i]])
57         {
58             mp[a[i]]=++id;
59             ba[id]=a[i];
60         }
61         a[i]=mp[a[i]];
62         w[a[i]].push_back(i);
63     }
64     for(int i=1;i<=pos[n];i++)dp(i);
65     for(int i=1;i<=n;i++)
66     {
67         int l,r;
68         scanf("%d%d",&l,&r);
69         if(l>r)swap(l,r);
70         printf("%d
",ba[sol(l,r)]);
71     }
72     return 0;
73 }