【BZOJ 2724】 2724: [Violet 6]蒲公英 （区间众数不带修改版本）

【分析】

　　区间众数见：http://www.docin.com/p-679227660.html

　　

　　

　　我这道题的就是打这个做法【实际上是膜hzwer的代码

　　【关于[l,r]之间有多少个x，是把位置存在数值的vector里面，然后lower_bound(l)~upper_bound(r)有多少个数

　　然后分块一下就好了。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<vector>

 #include<map>

 using namespace std;

 #define Maxn 50010

 #define Maxm 510

 int a[Maxn],f[Maxn],bl[Maxn],mode[Maxm][Maxm];

 map<int,int> mp;int id;

 vector<int > v[Maxn];

 int blo,n;

 int cnt[Maxn];

 void pre(int x)

 {

     memset(cnt,,sizeof(cnt));

     int mx=,ans=;

     for(int i=(x-)*blo+;i<=n;i++)

     {

         cnt[a[i]]++;

         int t=bl[i];

         if(cnt[a[i]]>mx||(cnt[a[i]]==mx&&f[a[i]]<f[ans]))

             ans=a[i],mx=cnt[a[i]];

         mode[x][t]=ans;

     }

 }

 int get_(int l,int r,int x)

 {

     return upper_bound(v[x].begin(),v[x].end(),r)-lower_bound(v[x].begin(),v[x].end(),l);

 }

 int query(int l,int r)

 {

     int ans,mx=;

     if(bl[l]==bl[r])

     {

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

         {

             int t=get_(l,r,a[i]);

             if(t>mx||(t==mx)&&f[a[i]]<f[ans]) ans=a[i],mx=t;

         }

     }

     else

     {

         ans=mode[bl[l]+][bl[r]-],mx=get_(l,r,ans);

         for(int i=l;i<=bl[l]*blo;i++)

         {

             int t=get_(l,r,a[i]);

             if(t>mx||(t==mx)&&f[a[i]]<f[ans]) ans=a[i],mx=t;

         }

         for(int i=(bl[r]-)*blo+;i<=r;i++)

         {

             int t=get_(l,r,a[i]);

             if(t>mx||(t==mx&&f[a[i]]<f[ans])) ans=a[i],mx=t;

         }

     }

     return ans;

 }

 int main()

 {

     int m;

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

     blo=;

     int ans=;id=;

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

     {

         scanf("%d",&a[i]);

         if(!mp[a[i]]) mp[a[i]]=++id,f[id]=a[i];

         a[i]=mp[a[i]];

         v[a[i]].push_back(i);

     }

     for(int i=;i<=n;i++) bl[i]=(i-)/blo+;

     for(int i=;i<=bl[n];i++) pre(i);

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

     {

         int l,r;

         scanf("%d%d",&l,&r);

         l=(l+ans-)%n+,r=(r+ans-)%n+;

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

         ans=f[query(l,r)];

         printf("%d\n",ans);

     }

     return ;

 }

【不行了 我也用map了。。。。

　　然后其实有更快的方法，然后我尝试了一下就放弃了。。【感觉是用空间和代码量换时间啊好恶心、、

　　

然后带修改这样【其实我没看。。

2017-04-23 21:21:48