블록 9: 구간 중 수 를 구하 십시오.

경계: 앞으로 강제 온라인 을 보지 못 한 것 과 같은 바보 같은 실 수 는 절대 범 하지 마 세 요.
 
 
질문 설명:
시골의 작은 길 옆 에 많은 민들레 가 심 어 져 있 는데, 우리 의 문 제 는 바로 이 민들레 와 관련 이 있다.
간소화 하기 위해 서 우 리 는 모든 민 들 레 를 n 의 길이 로 보 았 다. (a_1,a_2..a_n)(a1​,a2​..an​) ，그 속 a_iai​ 정수 로 i 번 민들레 의 종류 번 호 를 표시 합 니 다.
한 구간 [l, r] 에 물 어 볼 때마다 구간 에서 가장 많이 나 오 는 민들레 가 어떤 민들레 인지 대답 해 야 합 니 다. 몇 가지 민들레 가 똑 같이 나 오 면 수출 종류 번호 가 가장 작은 것 이 있 습 니 다.
주의 하 세 요. 당신 의 알고리즘 은 반드시 온라인 이 어야 합 니 다.
입 출력 형식
입력 형식:
 
첫 번 째 줄 의 정수 n, m 는 n 그루 의 민들레 가 있다 는 것 을 나타 내 고 m 차 질문 을 한다.
다음 줄 n 개의 빈 칸 으로 구 분 된 정수 a_iai​ ，민들레
그다음에 m 줄 당 두 개의 정수. l_0,r_0l0​,r0​ ，우 리 는 지난번 에 물 어 본 결 과 를 x (이것 이 첫 번 째 질문 이 라면 x = 0) 로 합 니 다.
령. l=(l_0+x-1)\bmod n + 1,r=(r_0+x-1) \bmod n + 1l=(l0​+x−1)modn+1,r=(r0​+x−1)modn+1 ，l > r 이면 l, r 를 교환 합 니 다.
최종 문의 구간 은 [l, r] 이다.
 
출력 형식:
 
출력 m 줄.각 줄 의 정 수 는 매번 문의 한 결 과 를 나타 낸다.
 
 
분석:
   이전에 나무 모양 의 배열 대신 블록 을 나 누 어 구간 과 예 를 들 어 우 리 는 블록 을 나 누 는 것 이 하나의 구간 을 몇 개의 작은 구간 으로 분해 하 는 것 임 을 알 수 있다. 먼저 예비 처 리 를 통 해 이 동네 간 의 일부 값 을 구하 고 공간 을 통 해 시간 을 바 꾸 어 시공 간 균형 을 이 루 는 것 이다.
   트 리 배열 을 대체 하 는 사고방식 은 매우 간단 하 다. 우 리 는 n 개 수 를 T 개 구간 으로 나 눈 다음 에 각 구간 에 대해 구간 과, 그리고 하나의 배열 add 를 열 어 전체 구간 에 추가 해 야 할 값 을 저장한다.만약 에 우리 가 전체 구간 을 수정 해 야 한다 면 구간 에 포 함 된 완전한 블록 을 add 배열 에 하나의 값 을 추가 하고 불완전한 블록 에 대해 우 리 는 직접 폭 리 를 매 거 하 며 a 배열 을 바탕 으로 추가 하고 자 하 는 값 을 추가 합 니 다.만약 에 우리 덩어리의 길이 가 근호 n 이 라면 한 번 구간 에 하나의 수 를 더 하면 복잡 도 는 O (sqrt (n) 이 고 당연히 조회 할 때 도 O (sqrt (n) 이다.
    그러나 이 문 제 는 구간 의 중 수 를 구 했 기 때문에 구간 의 중 수 는 더 줄 일 수 없다.우 리 는 만약 에 우리 가 한 덩어리의 중수 (이 덩어리의 크기 는 먼저 말 하지 않 는 다) 를 알 고 이 덩어리 가 대표 하 는 구간 안의 모든 수가 나타 나 는 횟수 를 알 게 된다 면 우리 가 l, r 간 의 중 수 를 조회 할 때 이 중 수 는 두 가지 상황 이 아니 라 한 덩어리의 수 이 고 하 나 는 덩어리 밖의 작은 범위 의 수 이다.우리 가 하 는 일 은 모든 조각 이 하나의 배열 을 가지 고 나타 난 수의 횟수 를 저장 한 다음 에 작은 범 위 를 폭리 적 으로 매 거 하여 덩어리의 배열 에 넣 은 다음 에 여러 수 를 구 한 후에 원상 태 로 회복 하 는 것 이다.우리 의 정 보 를 보호 하기 위해 서 만약 에 우리 가 n 을 t 블록 으로 나눈다 면 우 리 는 이 t 블록 을 유지 할 뿐만 아니 라 이 블록 으로 구 성 된 큰 덩어리 도 유지 해 야 한다.
   그러면 우리 가 미리 처리 한 복잡 도 는 n * t * t 이 고 매번 문의 하 는 복잡 도 는 n / t 이 며 모든 문 의 는 m * n / t 입 니 다.우 리 는 이 두 개의 복잡 도 를 같 게 하여 이때 t 개 월 의 세제곱 근 을 발견 하 게 했다.전체 알고리즘 은 A 로 문 제 를 풀 수 있다.
   그리고 가장 어 리 석 은 것 은 내 가 이 문 제 를 오전 에 판, 판 문 제 를 써 서 하루 의 시간 을 썼 다 는 것 이다.나 는 문제 출력 요 구 를 보지 못 했 기 때문에 이것 은 강제 온라인 문제, 즉 답 이 이전 과 관계 가 있다 는 것 이다!
   아, 피곤 해.

#include
#include
#include
#include
#include
#include
using namespace std;
int p,q,t,n,m,l,r,L,lan,pos,most[1600],maxn[1600],sum[1600][41000],a[41000],b[40],temp[41000],c[41000];
void discrete()
{
	sort(c+1,c+n+1);
	int sz=unique(c+1,c+n+1)-c-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(c+1,c+sz+1,a[i])-c;
}
int ask(int l,int r)
{
	l=(l+lan-1)%n+1;
	r=(r+lan-1)%n+1;
	if(l>r) swap(l,r);
	p=l/L;q=r/L;
	if(l%L==1)p++;
	else if(l%L) p+=2;
	else p++;
	int ans;
	if(q-p<0){
		int maxx=0;
		for(int i=l;i<=r;i++){ 
			temp[a[i]]++;
			if(temp[a[i]]>maxx)
				maxx=temp[a[i]],ans=a[i];
			if(temp[a[i]]==maxx&&c[a[i]]maxx)
				maxx=sum[pos][a[i]],ans=a[i];
			if(sum[pos][a[i]]==maxx&&c[a[i]]maxx)
				maxx=sum[pos][a[i]],ans=a[i];
			if(sum[pos][a[i]]==maxx&&c[a[i]]maxx)
					maxx=sum[pos][a[k]],ans=a[k];
				if(sum[pos][a[k]]==maxx&&c[a[k]]