2223: [Coci 2009]PATULJCI
Description
Input
Output
10 3 1 2 1 2 1 2 3 2 3 3 8 1 2 1 3 1 4 1 5 2 5 2 6 6 9 7 10
Sample Input
no
yes 1
no
yes 1
no
yes 2
no
yes 3
yes 1
no
yes 1
no
yes 2
no
yes 3
Sample Output
HINT
Notice:输入第二个整数是序列中权值的范围Lim，即1<=ai(1<=i<=n)<=Lim。
1<=Lim<=10000
这是一道主席树的题。。。
#include<cstdio>
#define MaxN 300010
#define MaxT 10000010
int N,M,Q,tot;
int Ans;
struct point{
int l,r,sum;
point (int x=0,int y=0,int s=0){
l=x; r=y; sum=s;
}
}P[MaxT];
int root[MaxN];
int Get(){
char Ch;
while ((Ch=getchar())<'0'||Ch>'9');
int Num=Ch-'0';
while ((Ch=getchar())>='0'&&Ch<='9')
Num=Num*10+Ch-'0';
return Num;
}
void Insert(const int &y,int &x,const int &l,const int &r,const int &p){
P[x=++tot]=P[y];
++P[x].sum;
if (l==r) return;
int mid=(l+r)/2;
if (p<=mid) Insert(P[y].l,P[x].l,l,mid,p);
else Insert(P[y].r,P[x].r,mid+1,r,p);
}
void find(const int &y,const int &x,const int &l,const int &r,const int &c){
if (l==r){
if (P[x].sum-P[y].sum>c) Ans=l;
return;
}
int tmp=P[P[x].l].sum-P[P[y].l].sum;
int mid=(l+r)/2;
if (tmp>c) find(P[y].l,P[x].l,l,mid,c);
else find(P[y].r,P[x].r,mid+1,r,c);
}
int main(){
N=Get(); M=Get();
for (int i=1;i<=N;++i)
Insert(root[i-1],root[i],1,M,Get());
Q=Get();
for (;Q--;){
int l=Get(),r=Get();
Ans=0;
find(root[l-1],root[r],1,M,(r-l+1)/2);
if (Ans) printf("yes %d\n",Ans);
else printf("no\n");
}
}
评论 (0)
