别人程序就不贴了...我按她的意思写了一个:
#include<iostream>
#include<algorithm>
using namespace std;
struct MM
{
	int v,id;
}a[50002];
int b[50002];
bool com(MM p,MM q)
{
	return p.v<q.v;
}
int main()
{
	int n,m,i,j,k,st,end;
	while(scanf("%d %d",&n,&m)==2)
	{
		for(i=0;i<n;i++)
		{
			scanf("%d",&b[i+1]);
			a[i].v=b[i+1];
			a[i].id=i+1;
		}
		sort(&a[0],&a[n],com);
		
		for(i=0;i<m;i++)
		{
			scanf("%d %d",&st,&end);
			if(end-st<50)
			{
				int maxm=b[st];
				int minm=b[st];
				for(j=st;j<=end;j++)
				{
					if(maxm<b[j]) maxm=b[j];
					if(minm>b[j]) minm=b[j];
				}
				printf("%d\n",maxm-minm);
				continue;
			}
			for(j=0;j<n;j++)
				if(a[j].id>=st&&a[j].id<=end) break;
				
			for(k=n-1;k>=0;k--)
				if(a[k].id>=st&&a[k].id<=end) break;
			printf("%d\n",a[k].v-a[j].v);
		}
	}
	return 0;
}

• Re:RMQ (18) cookie 2007-07-13 21:20:20
  • 没想到这样也可以过！！！汗，我的RMQ也很慢。。。。。。 (20) dongshanluo 2007-07-13 23:30:26
• Re:RMQ (21) cpp0600648238 2007-07-14 10:40:10
  • Re:RMQ (25) drownever 2007-07-14 11:41:16
• 没有天理了，这种算法怎么能过呢？ (0) hbu_jaysoon 2007-07-15 10:14:29
• 对这个程序那是佩服的五体投地啊 ， 太强悍了！！！！！！！！！！ (0) zengkui 2007-08-08 00:48:26
  • admire弱的算法有什么用…… (0) frkstyc 2007-08-08 01:45:18
    • 为什么不出数据把这种方法rej掉? (93) huacm01 2007-08-31 22:16:40
      • 这个题不是很容易的题目吧 怎么过这么多人? (0) huacm01 2007-08-31 22:17:22
      • 为什么要出数据把这种方法rej掉？ (58) johnzhao 2009-07-29 14:15:50
  • USACO (0) zhougelin 2007-08-08 11:38:34
    • USACO的数据结构题数据本来就弱 (0) zhougelin 2007-08-08 11:38:57
• Re:RMQ (110) windyrobin 2008-09-10 12:31:33
• Re:RMQ (957) ScutFoX 2009-08-26 16:41:38
• 好猥琐的方法...学习了 (0) Acaini 2010-03-27 01:41:13