题解 P4333【单调栈】[COI2007] Patrik

官方题解居然压行了（

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <stack>

using namespace std;

typedef long long llint;
typedef pair<int,int> par;

stack<par> S;

int main( void ) {
   int n;
   scanf( "%d", &n );

   llint ret = 0;
   for( int i = 0; i < n; ++i ) {
      int h;
      scanf( "%d", &h );
      
      par p( h, 1 );
      for( ; !S.empty() && S.top().first <= h; S.pop() ) {
         ret += S.top().second;
         if( S.top().first == h ) p.second += S.top().second;
      }

      if( !S.empty() ) ++ret;
      S.push( p );
   }
   
   cout << ret << endl;

   return 0;
}

非stack版，用了一个二分查找加速

#include<iostream>

using namespace std;
long long stack[10000000], n, top = 1, ans, m;
int main() {
    cin>>n;
    int a;
    cin>>stack[1];
    for (int i = 2; i <= n; i++) {
        cin>>a;
        if (stack[top] > a) {
            stack[++top] = a;
            ++ans;
        } else {
            int l = 1, r = top;
            while (l < r) {
                m = (l + r) >> 1;
                if (r == l + 1) m = r;
                if (a >= stack[m]) r = m - 1;
                else l = m;
            }
            ans += top - l + 1;
            while (top && stack[top] < a) top--;
            stack[++top] = a;
        }
    }
    cout<<ans;
}