hdu 4908 BestCoder Sequence

이 문제는 매우 시험적인 사고이다. 처음에 이렇게 하려고 생각했다. 왼쪽이 크고 작으며 중위수의 개수를 기록하고 오른쪽이 크고 작음을 중위수의 개수를 기록한 다음에 배열 조합을 배열한다. 그러나 이렇게 하면 광계산이 초과된다.
올바른 방법: dp가 중위수의 위치에서 양쪽 dp로 우리는 이렇게 생각할 수 있다. 만약에 이 수가 중위수보다 크면 dp[i]=dp[i-1]+1, 그렇지 않으면 dp[i]=dp[i-1]-1을 얻을 수 있다. 그러면 우리는 중위수 양측의 dp값을 얻을 수 있다. 생각해 보면 첫 번째 분해: Lmax[i]  R_min[i] 좌우 dp에서 0보다 작고 0보다 큰 개수를 기록한 다음에 같은 아래 표시된 곱하기 즉 Lmax[i]*R_min[i], 두 번째 부분의 해: 왼쪽에서 미드필더, 미드필더가 오른쪽, 양쪽을 함께 변수 l로 계산하고 r는 왼쪽과 오른쪽 dp가 0과 같은 개수를 기록하며 l+r+l*r+1;
dp[i]를 자세히 분석하면 i위치까지 중위수보다 크거나 중위수보다 작으면 대응하는 열의 개수를 나타낸다.

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#define B(x) (1<<(x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned ui;
const int oo = 0x3f3f3f3f;
//const ll OO = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define lson rt<<1
#define rson rt<<1|1
void cmax(int& a, int b){ if (b > a)a = b; }
void cmin(int& a, int b){ if (b < a)a = b; }
void cmax(ll& a, ll b){ if (b > a)a = b; }
void cmin(ll& a, ll b){ if (b < a)a = b; }
void cmax(double& a, double b){ if (a - b < eps) a = b; }
void cmin(double& a, double b){ if (b - a < eps) a = b; }
void add(int& a, int b, int mod){ a = (a + b) % mod; }
void add(ll& a, ll b, ll mod){ a = (a + b) % mod; }
const ll MOD = 1000000007;
const int maxn = 110000;
int a[maxn];
int dp[maxn];
int L_min[maxn], L_max[maxn];
int R_min[maxn], R_max[maxn];

int main()
{
	int n, mid, pos, l, r;
	while (scanf("%d%d", &n, &mid) != EOF)
	{
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			if (a[i] == mid)
				pos = i;
		}
		memset(L_min, 0, sizeof L_min);
		memset(L_max, 0, sizeof L_max);
		memset(R_min, 0, sizeof R_min);
		memset(R_max, 0, sizeof R_max);
		l = r = 0;
		dp[pos] = 0;
		for (int i = pos - 1; i >= 1; i--)
		{
			if (a[i] > mid)
				dp[i] = dp[i + 1] + 1;
			else
				dp[i] = dp[i + 1] - 1;
			if (dp[i] > 0)
				L_max[dp[i]]++;
			else if (dp[i] == 0)
				l++;
			else
				L_min[-dp[i]]++;
		}
		for (int i = pos + 1; i <= n; i++)
		{
			if (a[i] > mid)
				dp[i] = dp[i - 1] + 1;
			else
				dp[i] = dp[i - 1] - 1;
			if (dp[i] > 0)
				R_max[dp[i]]++;
			else if (dp[i] == 0)
				r++;
			else
				R_min[-dp[i]]++;
		}
		ll ans = l + r + l*r + 1;
		for (int i = 1; i <= 40000; i++)
		{
			ans += (ll)L_min[i] * (ll)R_max[i];
			ans += (ll)L_max[i] * (ll)R_min[i];
		}
		printf("%lld
", ans);
	}
	return 0;
}