ZOJ 3635 Cinema in Akiba(线段树)

ZOJ 3635 Cinema in Akiba(线段树)

大家好,又见面了,我是全栈君。

Cinema in Akiba (CIA) is a small but very popular cinema in Akihabara. Every night the cinema is full of people. The layout of CIA is very interesting, as there is only one row so that every audience can enjoy the wonderful movies without any annoyance by other audiences sitting in front of him/her.

The ticket for CIA is strange, too. There are n seats in CIA and they are numbered from 1 to n in order. Apparently, n tickets will be sold everyday. When buying a ticket, if there are k tickets left, your ticket number will be an integer i (1 ≤ i ≤ k), and you should choose the ith empty seat (not occupied by others) and sit down for the film.

On November, 11th, n geeks go to CIA to celebrate their anual festival. The ticket number of the ith geek is ai. Can you help them find out their seat numbers?

Input

The input contains multiple test cases. Process to end of file.
The first line of each case is an integer n (1 ≤ n ≤ 50000), the number of geeks as well as the number of seats in CIA. Then follows a line containing n integers a1a2, …, an (1 ≤ ai ≤ n – i + 1), as described above. The third line is an integer m (1 ≤ m ≤ 3000), the number of queries, and the next line is m integers, q1q2, …, qm (1 ≤ qi ≤ n), each represents the geek’s number and you should help him find his seat.

Output

For each test case, print m integers in a line, seperated by one space. The ith integer is the seat number of the qith geek.

Sample Input

3
1 1 1
3
1 2 3
5
2 3 3 2 1
5
2 3 4 5 1

Sample Output

1 2 3
4 5 3 1 2
题意:就是一排人看电影,票上安排给某人的位置是第几个空位。让你找出某些人的相应座位号。
线段树保存空位个数进行处理。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<limits.h>
typedef long long LL;
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
const int maxn=50000+100;
int sum[maxn<<2];
int ans[maxn];
int n,m;
void pushup(int rs)
{
    sum[rs]=sum[rs<<1]+sum[rs<<1|1];
}
void build(int rs,int l,int r)
{
    sum[rs]=r-l+1;
    if(l==r)  return ;
    int mid=(l+r)>>1;
    build(rs<<1,l,mid);
    build(rs<<1|1,mid+1,r);
    pushup(rs);
}
int update(int rs,int l,int r,int x)
{
 //    cout<<"2333 "<<l<<" "<<r<<endl;
     if(l==r)
     {
         sum[rs]=0;
         return l;
     }
     int ret;
     int mid=(l+r)>>1;
     if(x<=sum[rs<<1])  ret=update(rs<<1,l,mid,x);
     else            ret=update(rs<<1|1,mid+1,r,x-sum[rs<<1]);
     pushup(rs);
     return ret;
}
int main()
{
    int x;
    while(~scanf("%d",&n))
    {
        CLEAR(sum,0);
        CLEAR(ans,0);
        build(1,1,n);
        REPF(i,1,n)
        {
            scanf("%d",&x);
            ans[i]=update(1,1,n,x);
        }
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d",&x);
            printf(m==0?"%d\n":"%d ",ans[x]);
        }
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/116482.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • 解决NVIDIA显卡驱动 图形驱动程序安装失败 问题

    解决NVIDIA显卡驱动 图形驱动程序安装失败 问题本教程是在当你尝试一般的教程都无法解决问题的前提下使用,比如使用DDU工具卸载原显卡驱动后重新安装无效,找不到独立显卡的情况。退出火绒等杀毒软件win+R输入services.msc进入服务。将WindowsUpdata启动类型改为自动,并启动服务。win+R输入gpedit.msc进入本地策略编辑器。在计算机配置-模板管理-系统-设备安装-设备安装限制中双击图中第三个将其改为未配置或禁用重新安装显卡驱动即可…

    2022年5月6日
    837
  • 使用GTalk服务

    使用GTalk服务Normal07.8磅02falsefalsefalseEN-USZH-CNX-NONEMicrosoftInternetExplorer4在你访问GTalk服务之前,你需要

    2022年7月2日
    23
  • DELL服务器数据恢复成功案例

    DELL服务器数据恢复成功案例DELLEqualLogicPS6100采用虚拟ISCSISAN阵列,为远程或分支办公室、部门和中小企业存储部署带来企业级功能、智能化、自动化和可靠性。以简化的管理、快速的部署及合理的价格满足了分支办公室和中小企业的存储需求,同时提供全套企业级数据保护和管理功能、可靠的性能、可扩展性和容错功能,是中型企业级存储的起点产品,但某些物理故障或其他操作都可能会对卷或存储造成破坏,因此对系列存储的数…

    2022年6月30日
    27
  • 2022idea激活码【2021.10最新】

    (2022idea激活码)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容https://javaforall.net/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~3YVYA7ZZGQ-eyJsaWNlb…

    2022年3月30日
    95
  • 将方波转化为三角波电路图(简易波形发生器)

    单片机课设波形发生器,产生方波、三角波、正弦波、锯齿波波形幅度可调、频率可调。

    2022年4月16日
    85
  • Win7 下安装Vagrant错误排查

    Win7 下安装Vagrant错误排查

    2021年9月12日
    42

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号