poj2104.txt

高效求一超大数组中第i个元素到第j个元素间第k小的元素.

#include<stdio.h>
#include<algorithm>
using namespace std;
struct node
{
       long val;long index;
};
node a[100024];
long m,n;
bool cmp(node a,node b)
{
	return a.val<b.val||(a.val==b.val&&a.index<b.index);
}
void input()
{
	long i;
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=n;i++){
                      scanf("%ld",&a[i].val);
                      a[i].index=i;
                      }
	sort(a+1,a+n+1,cmp);
	return;
}
int main()
{
	long i,l,t,r,j,k;
	input();
	for(i=0;i<m;i++)
	{
		scanf("%ld%ld%ld",&l,&r,&k);
		t=0;
		for(j=1;j<=n;j++)
		{
            if(a[j].index>=l&&a[j].index<=r)
            {
                                            t++;
                if(t==k){printf("%ld\n",a[j].val);break;}
                
            }
        }
	}
//	scanf("%d",&i);
	return 0;
}

#include<stdio.h>
struct node
{
       long val;long index;
};
node a[100024];
long m,n;
void quicksort(long left,long right)
{
	if(left>=right)return ;
	long i=left,j=right+1;
	long temp=a[left].val;
	long temp2=a[left].index;
	while(1)
	{
		do
		{
			i++;
		}while(a[i].val<temp);
		do
		{
			j--;
		}while(a[j].val>temp);
		if(i>=j)break;
		long s=a[i].val;
		a[i].val=a[j].val;
		a[j].val=s;
		long t=a[i].index;
		a[i].index=a[j].index;
		a[j].index=t;
	}
	a[left].val=a[j].val;
	a[j].val=temp;
	a[left].index=a[j].index;
	a[j].index=temp2;
	quicksort(left,j-1);
    quicksort(j+1,right);
    return ;
}
void input()
{
	long i;
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=n;i++){
                      scanf("%ld",&a[i].val);
                      a[i].index=i;
                      }
 //   for(i=1;i<=n;i++)printf("%ld  %ld\n",a[i].val,a[i].index);
    quicksort(1,n);
//    for(i=1;i<=n;i++)printf("%ld  %ld\n",a[i].val,a[i].index);
	return;
}
int main()
{
	long i,l,t,r,j,k;
	input();
	for(i=0;i<m;i++)
	{
		scanf("%ld%ld%ld",&l,&r,&k);
		t=0;
		for(j=1;j<=n;j++)
		{
            if(a[j].index>=l&&a[j].index<=r)
            {
                                            t++;
                if(t==k){printf("%ld\n",a[j].val);break;}
                
            }
        }
	}
//	scanf("%d",&i);
	return 0;
}