题目大意：n个数，每个数的权值会传给它左右严格大于它的第一个数，求每个数被传到的权值总和。

题解：

　　方法一：如果对于某个数，它左右的最大值都≤它自己，那么它左边就不用传；否则就要传给最接近它的大于它的数。由于需要询问最大值，可用RMQ预处理一波，然后二分地查找：若区间内最大值≤那个“它”，该区间就没有满足要求的数。注意一下左右即可。时间O（nlog（n））。

　　方法二：考虑每个数收到的权从哪儿来并到哪儿去。为了简化，先考虑往右传，例如前面有5 3 2三个数，遇到一个4，那么3，2就传给4，并且他们的权与后面的答案毫无关系。根据这个特点建一个单调栈，一旦遇到一个大于栈顶元素的数，就传权并把栈顶元素弹出，接着这个数入栈。左传右传各搞一遍即可。时间O（n）。

代码

　　方法一：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 //#include
           
             7 using namespace std; 8 9 int n;10 #define maxn 5001111 int rmq[maxn][18],H[maxn],V[maxn];12 int qread()13 {14 char c;int s=0;while (!isdigit(c=getchar()));15 do {s=s*10+c-'0';} while (isdigit(c=getchar()));16 return s;17 }18 void make_rmq()19 {20 for (int i=1;i<=n;i++) rmq[i][0]=H[i];21 for (int j=1;(1<
            
             <=n;j++)22 for (int i=1,lar=(1<
             
              <=n;i++)23 rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);24 }25 int voi[maxn];26 int ask_rmq(int l,int r)27 {28 int k=0;29 while (l+(1<
              
               <=r) k++;k--;30 return max(rmq[l][k],rmq[r-(1<
               
                1) play(1,i-1,0,H[i],V[i]);65 if (i
               
              
             
            
           
          
         
        
       
      

　　方法二：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 //#include
          
            6 using namespace std; 7  8 int qread() 9 {10     char c;int s=0;while (!isdigit(c=getchar()));11     do {s=s*10+c-'0';} while (isdigit(c=getchar()));12     return s;13 }14 int n;15 #define maxn 5001116 int H[maxn],V[maxn],sta[maxn],top=0,voi[maxn];17 int main()18 {19     n=qread();20     for (int i=1;i<=n;i++) H[i]=qread(),V[i]=qread();21     memset(voi,0,sizeof(voi));22     for (int i=1;i<=n;i++)23     {24         while (top && H[sta[top]]
           
            =1;i--)28 {29 while (top && H[sta[top]]