棋子

 

时间限制： 1.0 秒

空间限制： 512 MB

相关文件： 题目目录

题目描述

棋盘从左到右被分割成 n(n≤1000) 个格子，从左到右编号为1,2,...,n。棋盘上有 m(m≤n) 个棋子，编号为 1,2,...,m ，编号为i的棋子刚开始摆放在编号为 pi 的格子上，一个格子最多摆放一个棋子。每次操作小R可以选择一个棋子，将它移动到它右边第一个空着的格子中，如果它右边没有空着的格子了，那么这就是一个非法操作，执行一次非法操作不会对棋盘有任何改变。小R依次做了k次操作，如果一次操作是合法的，你需要输出这颗棋子移动到的格子的编号，如果是非法的，你需要输出"error!"。

输入格式

从标准输入读入数据。

第一行三个整数 n、m、k ，表示格子数、棋子数和操作数。

第二行 m 个正整数，第 i 个正整数表示 pi ，即第 i 个棋子的初始位置。

第三行 k 个正整数，第 i 个正整数表示 xi ，即第 i 次操作选定的棋子的编号。

输出格式

输出到标准输出。

输出 k 行，第i行表示第i次操作的结果。对于合法操作，输出棋子移动到的位置，对于非法操作，输出一行"error!"。

思路：

1000x10000暴力都能做，然而我看成了10000x10000

写了个超级麻烦的线段树

线段树怎么做呢？

首先，开一颗线段树

每个节点维护他的子树里面的0的个数

我们同时开一个映射数组

ys[i]表示当前编号为i的数在ys[i]这个位置

然后查询ys[i]~n这些位置的第一个0的位置

输出即可

如果一个没有

那就是不合法

合法的话更新线段树和映射数组即可

代码：

#include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define rs 1024#define rii register int i#define rij register int jusing namespace std;struct tree{ int cnt,val,wz;}x[5005];int n,m,k,ys[1005];void mem(int l,int r,int bh){ x[bh].cnt=(r-l+1); if(l==r) { x[bh].wz=l; return; } int mid=(l+r)/2; mem(l,mid,bh*2); mem(mid+1,r,bh*2+1);}void add(int wz,int nl,int nr,int val,int bh){ if(nl==wz&&nr==wz) { if(val==0) { x[bh].cnt=1; } else { x[bh].cnt=0; } return; } int mid=(nl+nr)/2; if(wz<=mid) { add(wz,nl,mid,val,bh*2); } else { add(wz,mid+1,nr,val,bh*2+1); } x[bh].cnt=x[bh*2].cnt+x[bh*2+1].cnt;}int query(int l,int r,int nl,int nr,int bh){ if(l
                 
                  nr) { r=nr; } if(l==nl&&nr==nl) { return x[bh].wz; } int re=0; int mid=(nl+nr)/2; if(l<=mid) { if(x[bh*2].cnt!=0) { re=query(l,r,nl,mid,bh*2); } } if(r>mid&&re==0) { if(x[bh*2+1].cnt!=0) { re=query(l,r,mid+1,nr,bh*2+1); } } return re;}int main(){// freopen("1.in","r",stdin); scanf("%d%d%d",&n,&m,&k); mem(1,rs,1); for(rii=1;i<=m;i++) { int val; scanf("%d",&val); ys[i]=val; add(val,1,rs,i,1); } for(rii=1;i<=k;i++) { int bh; scanf("%d",&bh); int wz=ys[bh]; if(wz+1>n) { puts("error!"); continue; } int ltt=query(wz+1,n,1,rs,1); if(ltt==0) { puts("error!"); continue; } else { printf("%d\n",ltt); } add(ltt,1,rs,bh,1); add(wz,1,rs,0,1); ys[bh]=ltt; }}