BZOJ 2724:[Violet 6]タンポポ
6073 ワード
裸のブロック
cljの書いた区間の衆数を見に行くことができることを知りません
自分定数が大きい感じでコードもブスでダメ..
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;
}