这个题目说什么数据库事务原语操作的,那个背景好复杂,但是题目意思还是简单的。

给你一堆数的序列m个,问你n个问题,第i次提问是一个数ui就是问你插入ui个数之后,第i小的数是谁。

我没咋想别的想法,看数据量30000,就知道,排序只能排一次,总时间复杂度不能超过m*log(m)。

排完一次序之后,要怎么查呢。本来,真心想用堆来写的,但是堆排好之后,是没有随机访问能力的,所以放弃。

考虑这个题目很特殊,没次询问之后,下一次就是下一个数了。所以,我从这个地方入手解题。

把所有的数排一边,并得出原来第i个数在排好序之后的位置。

用p指向当前的答案,第一次的是,就是第一个插入的数。

对于已经插入的数,用双向链表标记其左边和右边已经插入的数。

每次插入,如果在p左边,p向左移动一个数,否则,不动。

每一次询问,打印p指向的数,然后,p向右移动。

主要的问题是,在插入一个数的时候,怎么维护双向链表,方法是用二叉树。二叉树每个节点保存的是这个分支上面是否存在已经插入的节点。当插入一个数的时候,就依次开始标记,当得到页节点时,在二叉树上查找在中根遍历的下一个页节点即可(也就是先找到一个有小标记的右兄弟,然后找这个兄弟的最左叶子即可)。

二叉树保存的办法同线段树。父节点[1~x),左节点[1,x»1),右节点[x»1,x)。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 600000

struct Num{
	int value;
	int pos;
};

int m,n;
Num num[MAXN];
int org[MAXN],pos[MAXN],left[MAXN],right[MAXN],insertedNum[MAXN<<2];
bool inserted[MAXN<<2];

int findLargeInserted(int i){
	int tag=-1,pos=i;
	while(pos>1){
		if((pos&1)==0){//在左分支上
			if(inserted[pos|1]){//右边的兄弟,如果他有,那么要找的,仅仅比自己打的叶子就是以他为根的最左叶子
				tag=pos|1;
				break;
			}
		}
		pos>>=1;
	}
	if(tag!=-1){//找到了某个右边的被覆盖的兄弟,开始找最左边的叶子
		while(inserted[tag<<1]||inserted[tag<<1|1]){
			tag<<=1;
			if(!inserted[tag]){
				tag|=1;
			}
		}
		return insertedNum[tag];
	}else{
		return m+1;//没有比自己大的,返回最最右边的
	}
}

int insert(int x,int left,int right,int root){//插入函数,用二叉树保存哪些节点插入了
	if(x==left&&right-1==x){//到叶子了
		inserted[root]=true;//标记插入了
		insertedNum[root]=x;//插入的序号
		return findLargeInserted(root);//返回的是下一个比这个大的序号
	}
	int mid=(left+right)>>1;//中间
	inserted[root]=true;//这个分支节点标记为插入
	if(x<mid){//左支
		return insert(x,left,mid,root<<1);
	}else{//右支
		return insert(x,mid,right,root<<1|1);
	}
}

int cmp(const void *a,const void *b){//比较函数,这个是很多C参考典籍上的经典写法,但是会有一个致命的问题,例如说,如果你排序的是整形,减法是会溢出的,而这个函数只需要返回正数、零、负数即可,直接减法的溢出,可能让你本来想返回的是个正数(a>b)但是溢出之后,却是个负数(表示a<b)然后,就悲剧了。
    if(*(int*)a==*(int*)b)return 0;
	return *(int*)a>*(int*)b?1:-1;
}

int main(){
	int i,j,g,cur,next,p;
	bool end;
	while(~scanf("%d%d",&m,&n)){
		for(i=0;i<m;i++){
			scanf("%d",&num[i].value);
			org[i]=num[i].value;
			num[i].pos=i;//原来的位置
		}
		qsort(num,m,sizeof(Num),cmp);//全部排一次序
		for(i=0;i<m;i++){
			pos[num[i].pos]=i+1;//原来位置上的数要插入的位置
		}
		left[0]=0;//初始化跳链,在原来1~m的基础上,加0和m+1
		left[m+1]=0;
		right[0]=m+1;
		right[m+1]=m+1;
		p=-1;
		memset(inserted,0,sizeof(bool)*(m<<2));//全部没访问过
		j=0;
		scanf("%d",&g);
		end=false;
		for(i=0;i<m;){
			//执行插入操作
			cur=pos[i];//获得现在要插入的位置
			next=insert(cur,1,m+1,1);//插入,并标记插入了二叉树中的节点,返回当前插入的这个数的下一个已经插入的序号

			left[cur]=left[next];//根据当前插入的,和下一个插入的,维护跳链
			right[cur]=next;
			left[next]=cur;
			right[left[cur]]=cur;

			i++;

			//插入完成后,调整偏移
			if(p==-1){//第一次插入,p指向这个,因为第一个查询问的就是第1个
				p=cur;
			}else if(p>cur){//如果在p前面插入的
				p=left[p];//p像左一定一个
			}

			//插入次数满足后,输出结果
			while(i==g){
				printf("%dn",num[p-1].value);//序号出输出
				p=right[p];//下一次输出的就是下一个序号
				j++;
				if(j==n){//处理结束
				    end=true;
					break;
				}
				scanf("%d",&g);
			}
			if(end)break;
		}
	}
	return 0;
}
吐槽和坑爹的地方是,因为快排的问题:

快排的时候,千万不要这么写了:

int compare (const void * a, const void * b){
  return ( *(int*)a - *(int*)b );
}

虽然说,这个是很多C参考典籍上的经典写法,但是会有一个致命的问题,例如说,如果你排序的是整形,减法是会溢出的,而这个函数只需要返回正数、零、负数即可,直接减法的溢出,可能让你本来想返回的是个正数(a>b)但是溢出之后,却是个负数(表示a<b)然后,就悲剧了。例如,a=20 0000 0000,b=-20 0000 0000的时候。