BZOJ 2724:[Violet 6]タンポポ

6073 ワード

裸のブロック
cljの書いた区間の衆数を見に行くことができることを知りません
自分定数が大きい感じでコードもブスでダメ..
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
int Size;
int Bl_len;
using namespace std;
char c;
inline void read(int &a)
{
	a=0;do c=getchar();while(c<'0'||c>'9');
	while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();
}
int Of[402][402];
int tp[402][402];
vector<int> Add[40001];
int A[40001],B[40001];
int T[40001]; 
struct asd
{int Fr,Ba;	inline friend bool operator <(asd a,asd b){return a.Fr<b.Fr;}};
set <asd> tran;
int Back[40001];
int main()
{
	int n,m;
    read(n),read(m);
	for(int i=1;i<=n;i++)
	  read(A[i]),B[i]=A[i];	
	sort(B+1,B+1+n);
	B[0]=-1;
	int con=0;
	for(int i=1;i<=n;i++)
	 if(B[i]!=B[i-1])
		tran.insert((asd){B[i],++con}),Back[con]=B[i];
	Size=sqrt(n)/2;
	for(int i=1;i<=n;i++)
	  {
	  	int tp=(*tran.find((asd){A[i]})).Ba;
	  	T[i]=tp;
	    Add[tp].push_back(i);
	  }
	Bl_len=n/Size+(n%Size?1:0);
	for(int i=1;i<=Bl_len;i++)
	   {
	   	int begin=Size*(i-1)+1,end=Size*i;
	   	end=min(end,n);
	    int data;
		for(int j=1;j<=min(Size,n-Size*(i-1));j++)
	       {
	    	  //data=(*tran.find((asd){A[j+begin-1]})).Ba;
	    	  data=T[j+begin-1];
			  int l,r;
		      int lleft=0,lmid,lright=Add[data].size()-1;
		      while(lleft<lright)
		        {
		        	lmid=(lleft+lright)>>1;
				    if(Add[data][lmid]<begin)
				       lleft=lmid+1;
				    else
				       lright=lmid;
				}
				l=lleft;
			  int rleft=0,rmid,rright=Add[data].size()-1;
		      while(rleft<rright)
		        {
		        	rmid=(rleft+rright)>>1;
				    if(Add[data][rmid]<end)
				       rleft=rmid+1;
				    else
				       rright=rmid;
				}
			  r=Add[data][rleft]<=end?rleft:rleft-1;
			  if((r-l+1)>tp[i][i]||((r-l+1)==tp[i][i]&&Of[i][i]>data))
			     Of[i][i]=data,tp[i][i]=(r-l+1);	
		   }
	   }
	
	for(int k=2;k<=Bl_len;k++)
	  for(int i=1;i<Bl_len;i++)
	    if(k+i-1<=Bl_len)
	     {
	   	 int begin=Size*(i-1)+1,end=Size*(i+k-1);
	   	 end=min(end,n);
	     int data;
	     Of[i][k+i-1]=Of[i+1][k+i-1];
	     tp[i][k+i-1]=tp[i+1][k+i-1];
	     
		 for(int j=1;j<=Size;j++)
	       {
	    	  //data=(*tran.find((asd){A[j+begin-1]})).Ba;
	    	  data=T[j+begin-1];
			  int l,r;
		      int lleft=0,lmid,lright=Add[data].size()-1;
		      while(lleft<lright)
		        {
		        	lmid=(lleft+lright)>>1;
				    if(Add[data][lmid]<begin)
				       lleft=lmid+1;
				    else
				       lright=lmid;
				}
				l=lleft;
			  int rleft=0,rmid,rright=Add[data].size()-1;
		      while(rleft<rright)
		        {
		        	rmid=(rleft+rright)>>1;
				    if(Add[data][rmid]<end)
				       rleft=rmid+1;
				    else
				       rright=rmid;
				}
			  r=Add[data][rleft]<=end?rleft:rleft-1;
			  if((r-l+1)>tp[i][k+i-1]||((r-l+1)==tp[i][k+i-1]&&Of[i][k+i-1]>data))
			     Of[i][k+i-1]=data,tp[i][k+i-1]=(r-l+1);	
		   }
		 }
		 int last=0;
	while(m--)
	{
		int L,R;
		read(L),read(R);
		L+=last-1;R+=last-1;
		L%=n;
		L++;
		R%=n;
		R++;
		if(L>R)
		swap(L,R);
		int Bl_L=L/Size+(L%Size?1:0),Bl_R=R/Size+(R%Size?1:0);
		int begin=L,end=R;
		if(Bl_R-Bl_L<=1)
		  {
		  	int data,tp=0,ans=1000000;
		   for(int j=1;j<=R-L+1;j++)
	       {
	    	  //data=(*tran.find((asd){A[j+begin-1]})).Ba;
	    	  data=T[j+begin-1];
			  int l,r;
		      int lleft=0,lmid,lright=Add[data].size()-1;
		      while(lleft<lright)
		        {
		        	lmid=(lleft+lright)>>1;
				    if(Add[data][lmid]<begin)
				       lleft=lmid+1;
				    else
				       lright=lmid;
				}
				l=lleft;
			  int rleft=0,rmid,rright=Add[data].size()-1;
		      while(rleft<rright)
		        {
		        	rmid=(rleft+rright)>>1;
				    if(Add[data][rmid]<end)
				       rleft=rmid+1;
				    else
				       rright=rmid;
				}
			  r=Add[data][rleft]<=end?rleft:rleft-1;
			  if((r-l+1)>tp||((r-l+1)==tp&&ans>data))
			     ans=data,tp=(r-l+1);	
		   }
		  	printf("%d
",last=Back[ans]); continue; } int ans=Of[L%Size==1?Bl_L:Bl_L+1][R%Size?Bl_R-1:Bl_R],tpp=tp[L%Size==1?Bl_L:Bl_L+1][R%Size?Bl_R-1:Bl_R]; int data; for(int j=1;j<=(Size+1-(L%Size==0?Size:L%Size))%Size;j++) { //data=(*tran.find((asd){A[j+begin-1]})).Ba; data=T[j+begin-1]; int l,r; int lleft=0,lmid,lright=Add[data].size()-1; while(lleft<lright) { lmid=(lleft+lright)>>1; if(Add[data][lmid]<begin) lleft=lmid+1; else lright=lmid; } l=lleft; int rleft=0,rmid,rright=Add[data].size()-1; while(rleft<rright) { rmid=(rleft+rright)>>1; if(Add[data][rmid]<end) rleft=rmid+1; else rright=rmid; } r=Add[data][rleft]<=end?rleft:rleft-1; if((r-l+1)>tpp||((r-l+1)==tpp&&ans>data)) ans=data,tpp=(r-l+1); } int E=Size*(Bl_R-1); for(int j=1;j<=R%Size;j++) { //data=(*tran.find((asd){A[Size*(Bl_R-1)+j]})).Ba; data=T[E+j]; int l,r; int lleft=0,lmid,lright=Add[data].size()-1; while(lleft<lright) { lmid=(lleft+lright)>>1; if(Add[data][lmid]<begin) lleft=lmid+1; else lright=lmid; } l=lleft; int rleft=0,rmid,rright=Add[data].size()-1; while(rleft<rright) { rmid=(rleft+rright)>>1; if(Add[data][rmid]<end) rleft=rmid+1; else rright=rmid; } r=Add[data][rleft]<=end?rleft:rleft-1; if((r-l+1)>tpp||((r-l+1)==tpp&&ans>data)) ans=data,tpp=(r-l+1); } printf("%d
",last=Back[ans]); } return 0; }