题目链接

关于题意的理解

The input of this question is a little strange.
query[i] means that after you add the query[i](th) number, query the ith bigger number in the box.

调试了不少时间，有两个地方写错了，一个是右区间是[SegMid+1,SegR],另一处是get_Nth_num函数传参M错传成N了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN 200100
#define nowp SegT[id]
#define lson SegT[id].lef_id
#define rson SegT[id].rig_id
using namespace std;

struct NumId{
    int num;
    int id;
    bool operator < (NumId o){return num<o.num;}
};
int M, N;
NumId a[MAXN];
int ranks[MAXN];//Ranking/discretized(离散化的) values for each number
int query[MAXN];//Record each query, because they may be the same value
/*
 * The input of this question is a little strange.
 * query[i] means that after you add the query[i](th) number, query the ith bigger number in the box.
*/
struct SegTree{
    int lef_id;
    int rig_id;
    int  val;
};
SegTree SegT[MAXN*4];
int segRoot;
int seg_num;
void build(int &id, int SegL, int SegR)
{
    id = ++seg_num;
    nowp.val = 0;
    if(SegL == SegR)
        return ;
    int SegMid = (SegL+SegR)/2;
    build(lson, SegL, SegMid);
    build(rson, SegMid+1, SegR);
}

void add_num(int id, int num, int SegL, int SegR)
{
    if(SegL == SegR)
    {
        nowp.val++;
        return ;
    }
    int SegMid = (SegL+SegR)/2;
    if(num <= SegMid)
        add_num(lson, num, SegL, SegMid);
    else
        add_num(rson, num, SegMid+1, SegR);
    nowp.val++;
    //nowp.val = SegT[lson].val + SegT[rson].val;//push up
}

int get_Nth_num(int id, int Nth, int SegL, int SegR)
{
    if(SegL == SegR)
        return SegL;
    int SegMid = (SegL+SegR)/2;
    if(SegT[lson].val >= Nth)
        return get_Nth_num(lson, Nth, SegL, SegMid);
    else
        return get_Nth_num(rson, Nth-SegT[lson].val, SegMid+1, SegR);
}

int main()
{
    while(~scanf("%d%d", &M, &N))
    {
        for(int i = 1; i < M+1; i++)
        {
            scanf("%d", &a[i].num);
            a[i].id = i;
        }
        for(int i = 1; i < N+1; i++)
        {
            scanf("%d", &query[i]);
        }
        sort(a+1, a+M+1);
        for(int i = 1; i < M+1; i++)//It's silly for a weight line segment tree/权值线段树 to delete duplicate/相同 elements.
        {
            ranks[a[i].id] = i;//The discretization/离散化 value of element with original subscript/index a[i].id is i
        }
        //Read-in data and discretization/离散化 has been done!

        seg_num = 0;
        build(segRoot, 1, M);
        int cnt = 1;//Record index of query array for current traversal
        for(int i = 1; i < M+1; i++)
        {
            add_num(segRoot, ranks[i], 1, M);
            while(i == query[cnt])//Notice here! Two inquiries may be the same value, but the ith bigger which decided by their index in query array is different.
            {
                printf("%d\n", a[get_Nth_num(segRoot, cnt, 1, M)].num);
                cnt++;
            }
        }
    }
    return 0;
}