> //居然1Y了,,,我。。。
> #include <iostream>
> #include <cstdio>
> #include <串>
使用命名空间 std >;
> int m，n;
> int a[60000];
>枚举颜色
> {
>红色，黑色
> };
>结构体红黑
> {
>颜色颜色;
> int l;
> int r;
> int p;
> int 键;
> int cnt;
> };
> 红黑树[60000];
> int lt;
>根;
> void RB_Init（）
> {
>树[0].颜色=黑色;
>树[0].key=-1;
>根=1;
>树[1].l=0;
>树[1].r=0;
>树[1].p=0;
>树[1].cnt=0;
>树[1].key=-1;
> }
> 无效RB_KeyC_Fixup（整数 x）
> {
>树[x].cnt=tree[tree[x].l].cnt+tree[tree[x].r].cnt+1;
> }
> 无效RB_Left_Rotate（整数 x）
> {
> int y;
> y=树[x].r;
>树[x].r=树[y].l;
> if （tree[y].l ！= 0）
> {
>树[树[y].l].p=x;
> }
>树[y].p=树[x].p;
> if （tree[x].p == 0）
> {
>根=y;
> }
> else if （tree[x].p ！= 0 && x == tree[tree[x].p].l）
> {
>树[树[x].p].l=y;
> }
> else if （tree[x].p ！= 0 && x ！= tree[tree[x].p].l）
> {
>树[树[x].p].r=y;
> }
>树[y].l=x;
>树[x].p=y;
> RB_KeyC_Fixup（x）;
> RB_KeyC_Fixup（y）;
> }
> 无效RB_Right_Rotate（int y）
> {
> int x;
> x=树[y].l;
>树[y].l=树[x].r;
> if （tree[x].r ！= 0）
> {
>树[树[x].r].p=y;
> }
>树[x].p=树[y].p;
> if （tree[y].p == 0）
> {
>根=x;
> }
> else if （tree[y].p ！= 0 && y == tree[tree[y].p].l）
> {
>树[树[y].p].l=x;
> }
> else if （tree[y].p ！= 0 && y ！= tree[tree[y].p].l）
> {
>树[树[y].p].r=x;
> }
>树[x].r=y;
>树[y].p=x;
> RB_KeyC_Fixup（y）;
> RB_KeyC_Fixup（x）;
> }
> 无效RB_Insert_Fixup（int z）
> {
> int y;
> while （tree[tree[z].p].color == red）
> {
> if （tree[z].p == tree[tree[z].p].p].l）
> {
> y=tree[tree[tree[z].p].p].r;
> if （tree[y].color == red）
> {
>树[树[z].p].颜色=黑色;
>树[y].颜色=黑色;
>树[树[z].p].p].颜色=红色;
> z=tree[tree[z].p].p;
> }
> else if （tree[y].color ！= red && z == tree[tree[z].p].r）
> {
> z=树[z].p;
> RB_Left_Rotate（z）;
> }
> else if （tree[y].color ！= red && z == tree[tree[z].p].l）
> {
>树[树[z].p].颜色=黑色;
>树[树[z].p].p].颜色=红色;
> RB_Right_Rotate（tree[z].p].p）;
> }
> }
>
> {
> y=tree[tree[tree[z].p].p].l;
> if （tree[y].color == red）
> {
>树[树[z].p].颜色=黑色;
>树[y].颜色=黑色;
>树[树[z].p].p].颜色=红色;
> z=tree[tree[z].p].p;
> }
> else if （tree[y].color ！= red && z == tree[tree[z].p].l）
> {
> z=树[z].p;
> RB_Right_Rotate（z）;
> }
> else if （tree[y].color ！= red && z == tree[tree[z].p].r）
> {
>树[树[z].p].颜色=黑色;
>树[树[z].p].p].颜色=红色;
> RB_Left_Rotate（tree[tree[z].p].p）;
> }
> }
> }
>树[根].颜色=黑色;
> }
> 无效RB_Insert（int n）
> {
> int x，y;
> y=0;
> x=根;
> while （tree[x].key ！= -1）
> {
> y=x;
>树[x].cnt++;
> if （n <树[x].key）
> {
> x=树[x].l;
> }
>
> {
> x=树[x].r;
> }
> }
>树[lt].p=y;
> if （y == 0）
> {
>根=lt;
> }
> else if （y ！= 0 && n < tree[y].key）
> {
>树[y].l=lt;
> }
> else if （y ！= 0 && n >= tree[y].key）
> {
>树[y].r=lt;
> }
>树[lt].l=0;
>树[lt].r=0;
>树[lt].颜色=红色;
>树[lt].key=n;
>树[lt].cnt=1;
> RB_Insert_Fixup（中）;
> lt++;
> }
> int RB_Query（int k）
> {
> int x，y;
> x=根;
> while （k ！= 1 || tree[x].cnt ！= 1）
> {
> // printf（“->%d %d\n”，k，tree[x].key）;
> if （k <= tree[tree[x].l].cnt && tree[x].l ！= 0）
> {
> x=树[x].l;
> }
> else if （k == tree[tree[x].l].cnt+1）
> {
>返回树[x].key;
> }
> else if （k > tree[x].l].cnt+1）
> {
> k-=tree[tree[x].l].cnt+1;
> x=树[x].r;
> }
> //printf（“->%d %d %d\n”，k，tree[x].key，tree[x].cnt）;
> }
>返回树[x].key;
> }
> void printTree（int x）
> {
> if （tree[x].l ！= 0）
> printTree（tree[x].l）;
> printf（“[%d %d]\n”，tree[x].key，tree[x].cnt）;
> if （tree[x].r！= 0）
> printTree（tree[x].r）;
> }
> int main（）
> {
> int i，j，pr，t，p;
> scanf（“%d%d”，&m，&n）;
> for （i=1; i<=m; i++）
> {
> scanf（“%d”，a+i）;
> }
> pr=1;
> p=1;
> lt=1;
> RB_Init（）;
> while （n--）
> {
> scanf（“%d”，&t）;
> for （i=pr; i<=t; i++）
> {
> // printf（“i=%d\n”，i）;
> RB_Insert（a[i]）;
> }
> // 打印树（根）;
> pr=t+1;
> printf（“%d\n”，RB_Query（p））;
> p++;
> }
> }