poj 2761 线段树做法.txt

ACM资料大集合

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;

//POJ 2761 线段树做法
#define NMAX 900001
#define MMAX 50002
int shuru[NMAX];//原输入数组
int temp[NMAX];
int lisan[NMAX];//离散化后的数组
int ans[MMAX];

typedef struct node
{
	int left,right;
	int mid;//该结点的数值
	int count;//该节点和左右子树的计数
	int has;//该节点自己的计数
}node;

typedef struct oop
{
	int start,end,cixu,yuan,ans;
}oop;

node tree[NMAX];
oop act[MMAX];

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

int cmpoop(const void *a,const void *b)
{
	return (*(oop *)a).start-(*(oop *)b).start;
}

int cmpago(const void *a,const void *b)
{
	return (*(oop *)a).yuan-(*(oop *)b).yuan;
}

int search_key(int key,int num)
{
	int *p;
	p=(int *)bsearch(&key,lisan+1,num,sizeof(int),cmpt);
	if(p==NULL) 	return -1;
	else return p-lisan;

}

void build(int p,int l,int r)
{
	tree[p].left=l;
	tree[p].right=r;
	tree[p].mid=(l+r+1)/2;
	tree[p].count=0;
	if(r-l>=1) build(2*p,l,tree[p].mid-1);
  	if(r-l>=2) build(2*p+1,tree[p].mid+1,r);	
}

void insert(int p,int value)
{	//插入一个值为value的数
	tree[p].count++;
	if(value<tree[p].mid) insert(2*p,value);
	else if(value>tree[p].mid) insert(2*p+1,value);
	else tree[p].has++;
}

void del(int p,int value)
{	//删除一个值为value的数
	tree[p].count--;
	if(value<tree[p].mid) del(2*p,value);
	else if(value>tree[p].mid) del(2*p+1,value);
	else tree[p].has--;
}

int search(int p,int cixu)
{	//查找元素中第k小的数
	if(tree[p].count<cixu) return -1;
	if(tree[p].right-tree[p].left>=1)
	{//有左子树时
	   if(cixu<=tree[2*p].count) return search(2*p,cixu);
	   else if(cixu<=tree[2*p].count + tree[p].has) return tree[p].mid;
	   else return search(2*p+1,cixu-tree[2*p].count-tree[p].has);
	}
	else return tree[p].mid;
}

void solve(int num,int pnum)
{
//假设我们要统计区间（2，5） （4，7），（9 10）的情况，见图：
//序号  1 2 3 4 5 6 7 8 9 10
//统计1   H H H H
//统计2       H H H H
//统计3                 H H
//最原始的想法：每遇到一次区间统计，我们对该区间建一颗树，求树里第K小的数
//但是没必要，注意到统计1和统计2有一些数是重复的
//产生第2个想法：
//先建一颗树，树里有shuru[2..5]的4个数，然后求统计1的第k小数
//从树里删除shuru[2..3]的2个数，添加shuru[6..7]的2个数,然后求统计2的第k小数
//从数里删除shuru[4..7]的4个数，添加shuru[9..10]的2个数，然后求统计3的第k小数
//
//但是！！！！原先题目给我们的操作序列可能是这样的：（情况1）
//序号  1 2 3 4 5 6 7 8 9 10
//统计1   H H H H
//统计2         H H H H
//统计3     H H H H
//遇到这种情况，我们会怎么做呢？
//统计完1后，我们会删除shuru[2..4],添加shuru[6..8]
//统计完2后，我们会删除shuru[7..8],添加shuru[3..4]
//中间做了10次的添加删除操作，但是如果序列是这样的呢？（情况2）
//序号  1 2 3 4 5 6 7 8 9 10
//统计1   H H H H
//统计2     H H H H
//统计3         H H H H
//你会发现中间删除、添加的次数只有6次，比上面那种情况少很多
//情况1和情况2的区别在哪：情况2的统计操作的起始点是有序的！（情况1是2,5,3,情况2是2,3,5）
//因此，我们要对操作进行处理，（PS：又碰到一题需对操作处理的题目）
//
//接下去的事情就简单了，只需构造一种树结构，满足logn时间完成插入，删除，查找第k小数的操作即可
//AVL、线段树都可以解决这个问题
//PS：我是用线段树过的，3000 MS，好长时间啊
//什么，不知道怎么用AVL、线段树解决nlogn时间查找第k小数？
//还记得选拔赛的最后一题“选队长”吗，要想不TLE，就要在logn时间完成删除、查找第k个数的操作.
//这就跟本题的要求很相似了.NOJ论坛里我已经贴出这道题的代码，可以参考一下。 
	int i,j,jnum;
	for(i=1;i<=num;i++) temp[i]=shuru[i];
	qsort(temp+1,num,sizeof(int),cmpt);
	lisan[1]=temp[1];
	for(i=2,j=1;i<=num;i++) 
	{
		if(temp[i]!=temp[i-1]) lisan[++j]=temp[i];
	}
	jnum=j;
	build(1,1,jnum);
	qsort(act+1,pnum,sizeof(act[1]),cmpoop);
	for(j=act[1].start;j<=act[1].end;j++)
		insert(1,search_key(shuru[j],jnum));

	act[1].ans=lisan[search(1,act[1].cixu)];
	for(i=2;i<=pnum;i++)
	{
		if(act[i].start>act[i-1].end)
		{
			for(j=act[i-1].start;j<=act[i-1].end;j++)
				del(1,search_key(shuru[j],jnum));
			for(j=act[i].start;j<=act[j].end;j++)
				insert(1,search_key(shuru[j],jnum));
		}
		else
		{
			for(j=act[i-1].start;j<act[i].start;j++)
				del(1,search_key(shuru[j],jnum));
			for(j=act[i-1].end+1;j<=act[i].end;j++)
				insert(1,search_key(shuru[j],jnum));
		}	
/*		else
		{
			for(j=act[i-1].start;j<act[i].start;j++)
			{
//				printf("del %d\n",j);
				del(1,search_key(shuru[j],jnum));
			}
			for(j=act[i].end+1;j<=act[i-1].end;j++)
			{
//				printf("del %d\n",j);
				del(1,search_key(shuru[j],jnum));
			}
		}
*/		act[i].ans=lisan[search(1,act[i].cixu)];
	}
	qsort(act+1,pnum,sizeof(act[1]),cmpago);
	for(i=1;i<=pnum;i++) printf("%d\n",act[i].ans);
}

int main()
{
	int i,num,pnum,v;
	scanf("%d %d",&num,&pnum);
	for(i=1;i<=num;i++)
		scanf("%d",&shuru[i]);
	for(i=1;i<=pnum;i++)
	{
		act[i].yuan=i;
		scanf("%d %d %d",&act[i].start,&act[i].end,&act[i].cixu);
	}	
	solve(num,pnum);
	return 0;
}