#include<iostream>
using namespace std;

int n,m;

int num[100001];
int id[100001];

int from[5001];
int to[5001];
int k[5001];

int L[50001];
int Li[50001];
int R[50001];
int Ri[50001];

void merge(int start,int h,int end)
{
	int nl=h-start+1;
	int nr=end-h;
	int i,j;
	for(i=1;i<=nl;++i){ L[i]=num[start+i-1]; Li[i]=id[start+i-1]; }
	for(j=1;j<=nr;++j){ R[j]=num[h+j]; Ri[j]=id[h+j]; }
	L[nl+1]=1e9+1;
	R[nr+1]=1e9+1;
	//cout<<"L[i]"<<L[nl+1]<<endl;
	int kk;
	i=1;j=1;
	for(kk=start;kk<=end;++kk)
	{
		if(L[i]<=R[j]){ id[kk]=Li[i]; num[kk]=L[i++]; }
		else { id[kk]=Ri[j]; num[kk]=R[j++]; }
	}
}
void mergesort(int start,int end)
{
	if(start<end)
	{
		int h=(start+end)/2;
		mergesort(start,h);
		mergesort(h+1,end);
		merge(start,h,end);
	}
}

int main()
{
	scanf("%d %d",&n,&m);
	int i,j;
	
　　　　　for(i=1;i<=n;++i)scanf("%d",&num[i]);
	for(i=1;i<=n;++i)id[i]=i;
	　
　　　　　mergesort(1,n);
	//for(i=1;i<=n;++i)printf("%d ",num[i]);printf("\n");
	//for(i=1;i<=n;++i)printf("%d ",id[i]);printf("\n");
	

　　　　　for(i=1;i<=m;++i)
	{
		scanf("%d %d %d",&from[i],&to[i],&k[i]);
		
		int t=0;
		for(j=1;j<=n;++j)
		{
			if(from[i]<=id[j] && id[j]<=to[i])++t;
			if(t==k[i])break;
		}
		printf("%d\n",j);
	}
	
	return 0;
}

• "n different integer numbers"中的different有保障么？？有的话应该没错的 (0) wcfairytale 2007-12-16 21:34:16
  • 搞错了。。。改 (0) wcfairytale 2007-12-16 22:59:04
  • 问题已解决！虽然耗了8000多ms！ (0) wcfairytale 2007-12-16 22:59:37