事关TLE

这题给我 火卓 了很久的复杂度，人都快麻了。

后来发现：

加上如下

if(fro+1<=to)
        {
                ans=0;
                for(int i=ql;i<=qr;i++)
                {
                        rec[a[i]]++;
                        if(rec[a[i]]>rec[ans] || (rec[a[i]]==rec[ans] && a[i]<ans)) ans=a[i];
                }
                if(qr-ql+1>=kinds) for(int i=1;i<=kinds;i++) rec[i]=0,vis[i]=0;
                else for(int i=ql;i<=qr;i++) rec[a[i]]=0;
                return mapping[ans];
        }

就会TLE,注释掉就过了。

太离谱了。

本来是注释着看一看哪里超时了的，没想到就过了。

而且注释掉的话，如果两个端点在同一个块内的话还多记录了东西。

求问:

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
const int range=40005;
const int tem_ran=205;
bool vis[range];
int n,m,l,r,a[range],mapping[range];
int num,len,ans,kinds,b[tem_ran],e[tem_ran],bel[range],rec[range],sum[range][tem_ran],mode[tem_ran][tem_ran];
struct unit{int val,pos;}tem[range];
inline bool cmp(unit a,unit b){return a.val<b.val;}
inline int get_time(int col,int ql,int qr){return sum[col][qr]-sum[col][ql-1];}
inline void devide()
{
    len=sqrt(n);
    kinds=a[tem[n].pos];
    for(int i=1;i<=n;i++)
    {
        int id=(i+len-1)/len;
        bel[i]=id;
        if(!b[id]) b[id]=i;
        if(i%len==0 || i==n) e[id]=i;
        sum[a[i]][id]++;
    }
    num=bel[n];
    for(int i=1;i<=num;i++)
    {
        for(int j=1;j<=kinds;j++) sum[j][i]+=sum[j][i-1];
        for(int j=i;j>=1;j--)
        {
            if(j!=i) mode[j][i]=mode[j][i-1];
            for(int k=b[i];k<=e[i];k++) if(get_time(a[k],j,i)>get_time(mode[j][i],j,i) || (get_time(a[k],j,i)==get_time(mode[j][i],j,i) && a[k]<mode[j][i])) mode[j][i]=a[k];
        }
    }
}
inline int get_mode(int ql,int qr)
{
    int ans,fro=bel[ql],to=bel[qr];
    /*
    if(fro+1<=to)
    {
        ans=0;
        for(int i=ql;i<=qr;i++)
        {
            rec[a[i]]++;
            if(rec[a[i]]>rec[ans] || (rec[a[i]]==rec[ans] && a[i]<ans)) ans=a[i];
        }
        if(qr-ql+1>=kinds) for(int i=1;i<=kinds;i++) rec[i]=0,vis[i]=0;
        else for(int i=ql;i<=qr;i++) rec[a[i]]=0;
        return mapping[ans];
    }
    *//此处为被注释（和谐）掉的内容。
    ans=mode[fro+1][to-1];
    vis[ans]=1;
    rec[ans]+=get_time(ans,fro+1,to-1);
    //cout << ans << endl;
    for(int i=b[to];i<=qr;i++)
    {
        rec[a[i]]++;
        if(!vis[a[i]]) rec[a[i]]+=get_time(a[i],fro+1,to-1),vis[a[i]]=1;
        if(rec[a[i]]>rec[ans] || (rec[a[i]]==rec[ans] && a[i]<ans)) ans=a[i];
    }
    //cout << ql << " " << e[fro] << "|" << b[to] << " " << qr << endl;;
    for(int i=ql;i<=e[fro];i++)
    {
        rec[a[i]]++;
        if(!vis[a[i]]) rec[a[i]]+=get_time(a[i],fro+1,to-1),vis[a[i]]=1;
        if(rec[a[i]]>rec[ans] || (rec[a[i]]==rec[ans] && a[i]<ans)) ans=a[i];
    }
    if(qr-b[to]+1+e[fro]-ql+1>=kinds) for(int i=1;i<=kinds;i++) rec[i]=0,vis[i]=0;
    else
    {
        rec[mode[fro+1][to-1]]=vis[mode[fro+1][to-1]]=0;
        for(int i=b[to];i<=qr;i++) rec[a[i]]=vis[a[i]]=0;
        //cout << ql << " " << e[fro] << "|" << b[to] << " " << qr << endl;;
        for(int i=ql;i<=e[fro];i++) rec[a[i]]=vis[a[i]]=0;
    }
    return mapping[ans];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&tem[i].val),tem[i].pos=i;
    sort(tem+1,tem+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        a[tem[i].pos]=a[tem[i-1].pos];
        if(i==1 || tem[i-1].val!=tem[i].val) a[tem[i].pos]++;
        mapping[a[tem[i].pos]]=tem[i].val;
    }
    devide();
    while(m--)
    {
        scanf("%d%d",&l,&r);
        l=(l+ans-1)%n+1,r=(r+ans-1)%n+1;
        if(r<l) swap(l,r);
        ans=get_mode(l,r);
        printf("%d\n",ans);
    }
    return 0;
}