题目：

Description

 

Input

修正一下

l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1

Output

Sample Input

6 3

1 2 3 2 1 2

1 5

3 6

1 5

Sample Output

1

2

1

HINT

 

修正下：

n <= 40000, m <= 50000

 

Source

题解：

 

题解如上·····一个分块模板题打了我2个小时·····不得不说代码能力和专注度还不够·····另外还学到了节约复杂度和空间的好方法···（具体见getans中的tot是如何每次重新变为1的）

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int N=4e4+5;int visit[N],tim,n,m,num[N],cnt[N][205],ans[205][205],tot[N],temp[N],id[N],s,idx[N],len,tots,Left[N],Right[N];bool jud[N];inline int R(){ char c;int f=0; for(c=getchar();c<'0'||c>'9';c=getchar()); for(;c<='9'&&c>='0';c=getchar()) f=(f<<3)+(f<<1)+c-'0'; return f;}inline void pre(){ sort(temp+1,temp+n+1); len=unique(temp+1,temp+n+1)-temp-1; for(int i=1;i<=n;i++) { int t=num[i]; num[i]=lower_bound(temp+1,temp+len+1,num[i])-temp; idx[num[i]]=t; } //离散化------------------------------------------------------- s=(int)sqrt(n); tots=0; for(int i=1;i<=n;i++) { if(i%s==0) id[i]=tots,Right[tots]=i,jud[i]=true; else if(i%s==1) id[i]=++tots,Left[tots]=i; else id[i]=tots; } Right[tots]=n,jud[n]=1; //分块------------------------------------------------ for(int i=1;i<=n;i++) cnt[num[i]][id[i]]++; for(int i=2;i<=tots;i++) for(int j=1;j<=len;j++) cnt[j][i]+=cnt[j][i-1]; //统计cnt------------------------------------------ for(int i=1;i<=tots;i++) { int maxx=0,anss=1e+8; memset(tot,0,sizeof(tot)); for(int j=Left[i];j<=n;j++) { tot[num[j]]++; if(tot[num[j]]>maxx||(tot[num[j]]==maxx&&num[j]
              
               maxx||((tot[num[i]]==maxx)&&num[i]
               
                maxx||((tot[num[i]]+cnt[num[i]][rights]-cnt[num[i]][lefts-1]==maxx)&&num[i]
                
                 maxx||((tot[num[i]]+cnt[num[i]][rights]-cnt[num[i]][lefts-1]==maxx)&&num[i]
                 
                  b) swap(a,b); t=getans(a,b); printf("%d\n",t); } return 0;}