Black box

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int m,n,k;
int a[N],b[N],u[N];
struct MM{
    int l,r,s;
}tree[N<<2];
inline void build(int root,int L,int R)
{
    tree[root].l=L;
    tree[root].r=R;
    if(L==R) return;
    int mid=(L+R)>>1;
    build(root<<1,L,mid);
    build(root<<1|1,mid+1,R);
}
inline void update(int root,int t)
{
    if(tree[root].l==tree[root].r)
    {
        tree[root].s++;//个数加一
        return;
    }
    int mid=(tree[root].l+tree[root].r)>>1;
    if(t<=mid) 
       update(root<<1,t);
    else 
          update(root<<1|1,t);
    tree[root].s=tree[root<<1].s+tree[root<<1|1].s;
}
inline int query(int root,int t)
{
    if(tree[root].l==tree[root].r)
        return tree[root].l;
    if(t<=tree[root<<1].s) 
	    return query(root<<1,t);
    else 
	     return query(root<<1|1,t-tree[root<<1].s);
}
int main()
{
    cin>>m>>n;//m个数字,n个询问 
    for(int i=1;i<=m;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    for(int i=1;i<=n;i++)
        cin>>u[i];
    sort(b+1,b+m+1);
    int s=unique(b+1,b+m+1)-(b+1);
   //离散化,s是数组b中不重复的数的个数
    build(1,1,s);//依s建树
    int h=0;
    while(n!=h)//依次查询 
    {
        h++;
        for(int i=u[h-1]+1;i<=u[h];i++)//将指定区间数字加入权值线段树 
        {
            int v=lower_bound(b+1,b+s+1,a[i])-b;
   	         //v是a[i]在数组b中所处的位置(注意之前数组b排了序)
            update(1,v);
        }
        cout<<b[query(1,++k)]<<endl;
    }
    return 0;
}

  

上一篇:CSS 技巧一则 -- 在 CSS 中使用三角函数绘制曲线图形及展示动画


下一篇:Codeforces Round #597 (Div. 2) A. Good ol' Numbers Coloring