记录编号	414728	评测结果	AAAAAAAAAA
题目名称	忠诚	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.156 s
提交时间	2017-06-14 21:00:08	内存使用	13.93 MiB

#include <cstdio>
#include <cmath>
#include <vector>
#include <iostream>

using namespace std;
 
void read(int &x) {
    char c;bool flag = 0;
    while((c=getchar())<'0'||c>'9') flag |= (c=='-');
    x=c-'0';while((c=getchar())>='0'&&c<='9') x = (x<<3)+(x<<1)+c-'0';
    flag?x=-x:x;
}

#define N 210000

struct RMQ {
    struct Node { 
	   int val,key,l,r;
	   void out() {cout<<val<<" "<<key<<"\n";}
       Node(int val = 0,int key = 0):val(val),key(key),l(-1),r(-1){} 
	}t[N<<1]; 
	
    int S[N],top,pos[N],sz;
    
    void build(int a[],int n) {
	   t[0] = Node(-1,n+1);
	   S[top = 1] = 0; sz = 0;
	   for (int i = 1; i <= n; i++) {
	      t[++sz] = Node(a[i],i);
	      int p = -1;
	      while(t[S[top]].val >= t[sz].val) p = S[top--];
	      t[sz].l = p;	t[S[top]].r = sz;
	      S[++top] = sz;
	   }
   }
   
   struct Que {int y,id;};
   int f[N],v[N],Lca[N];
   vector<Que> q[N];
   
   int fd(int x) {
   	 return x==f[x] ? x : f[x]=fd(f[x]);
   }
   
   void Tarjan(int x) {
   	//cout<<x<<"\n";
   	   v[x] = 1; f[x] = x;
   	   for (int i = 0; i < 2; i++) {
   	   	 int to = i?t[x].l:t[x].r;
   	   	 if(to != -1 && !v[to]) {
            Tarjan(to);
			f[to] = x; 	   	 	
		 }
       }
	   for (int i = 0; i < q[x].size(); i++) 
	    if(v[q[x][i].y] && !Lca[q[x][i].id])
	     Lca[q[x][i].id] = fd(q[x][i].y);
   }
   
   void slove (int m) {
   	   for (int i = 1,l,r; i <= m; i++) {
   	   	   read(l); read(r); 
		   l = pos[l]; r = pos[r];
		   //cout<<t[l].key<<" "<<t[r].key<<"\n";
   	   	   q[l].push_back((Que){r,i});
   	   	   q[r].push_back((Que){l,i});
	   }
	   Tarjan(0);
   	   for (int i = 1; i <= m; i++) printf("%d ",t[Lca[i]].val);
   }
   
   inline void dfs(int o) {
   	 if(o == -1) return;
   	// cout<<o<<" "<<t[o].l<<" "<<t[o].r<<"\n";
   	 dfs(t[o].l);
	 //t[o].out();	 
	 pos[t[o].key] = o;
   	 dfs(t[o].r);
   }
   
}t;

int main() {
	freopen("faithful.in","r",stdin);freopen("faithful.out","w",stdout);
	static int n,q,a[N];
	read(n); read(q);
	for (int i = 1; i <= n; i++) read(a[i]);
	t.build(a,n);
	t.dfs(0);
	t.slove(q);
	return 0;
}