BZOJ 2223 [Coci 2009]PATULJCI 主席树

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

Notice:输入第二个整数是序列中权值的范围Lim，即1<=ai(1<=i<=n)<=Lim。

1<=Lim<=10000

传送门

同bzoj3524~~~

完全一样的题= =

我连数据范围都没改就交了……

注意一下输出的格式两题是不同的。

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int N=500005,logN=25;
int n,LIM,Tcnt;
int root[N];
struct ChairTree{int l,r,num;
}ct[N*logN];
void insert(int L,int R,int &x,int val){ct[Tcnt++]=ct[x];x=Tcnt-1;ct[x].num++;if (L==R) return;int mid=(L+R)>>1;if (val<=mid) insert(L,mid,ct[x].l,val);else insert(mid+1,R,ct[x].r,val);
}
int query(int L,int R,int ll,int rr,int g){if (L==R) return L;int mid=(L+R)>>1,t1=ct[ct[rr].l].num-ct[ct[ll].l].num,t2=ct[ct[rr].r].num-ct[ct[ll].r].num;if (t1>g) return query(L,mid,ct[ll].l,ct[rr].l,g); elseif (t2>g) return query(mid+1,R,ct[ll].r,ct[rr].r,g);else return 0;
}
int main(){n=read(),LIM=read();root[0]=0,Tcnt=1;for (int i=1;i<=n;i++)root[i]=root[i-1],insert(1,LIM,root[i],read());int x,y,m=read();while (m--){x=read(),y=read();int t=query(1,LIM,root[x-1],root[y],(y-x+1)>>1);if (!t) puts("no");else printf("yes %d\n",t);}return 0;
}