#include <iostream>
#include <list>
using namespace std;

const int MIN = 50000;
const int MID = 20002;
int A[MID];
int C[2 * MID];
int R[MIN];

int main()
{
	int i, j, p, N, M;
	int st, ed, K;
	scanf("%d%d", &N, &M);
	for(i=1; i<=N; i++) {
		scanf("%d", A+i);
	}
	for(i=1; i<=M; i++) {
		list <int> L[2*MID];
		int lt=MID, rt=MID;	//left , right
		int k;
		memset(C, 0, 2*MID*sizeof(int));
		
		scanf("%d%d%d",&st, &ed, &K);
		for(j=st; j<=ed; j++)
		{
			p=A[j]/MIN + MID;
			if(A[j]<0) p--;
			C[p]++;
			if(p<lt) lt=p;
			if(p>rt) rt=p;
		    L[p].push_back(A[j] - (p-MID)*MIN);
		}
		for(j=lt;K-C[j] > 0 && j<=rt; j++)
		{
			    K-=C[j];
		}
		//radixSort(j);
		memset(R, 0, MIN*sizeof(int));
		list <int> ::iterator lit;
//		printf("list element: ");
		for(lit=L[j].begin(); lit!=L[j].end(); ++lit)
		{
			R[*lit]++; 
//			printf("%d ", *lit);
		}
//		puts("");
		for(k=0; k<MIN; k++)
		{
//          printf("R[%d]: %d \n",k, R[k]);
			if(K-R[k] > 0)
				K-=R[k];
			else break;
		}
		printf("%d\n", k + MIN*(j-MID));
	}

	return 0;
}

• 这个题本来就没打算让这么样的算法过的 (1222) frkstyc 2007-05-11 12:07:31