You've successfully subscribed to ムえのBLOG
Great! Next, complete checkout for full access to ムえのBLOG
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.

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

. 1 min read

官方题解居然压行了(

#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;
}


本站总访问量 正在加载今日诗词....