You've successfully subscribed to ムえのBLOG
Welcome back! You've successfully signed in.

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


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