CSU 1807 最長上升子序列~

[

​​Submit​​​][

​​​Status​​​][

​​​Web Board​​]

Description

1,p

2,…,p

n.

1,p

2,…,p

n 互不相同（即 p

1,p

2,…,p

n

現在 Bobo 想知道，替換後最長上升子序列的長度恰好為 (n-1) 數列的數量。

Input

輸入包含不超過 300 組資料，其中不超過 20 組的 n 超過 100.

5).

1,p

2,…,p

n  (0≤p

i≤n).

1,p

2,…,p

n中非 0 的元素互不相同。

Output

Sample Input

3
0 0 0
4
0 0 0 0
5
1 0 0 4 5      

Sample Output

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,int>
#define in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-8;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int n, a[N];
LL dp[N];

void init()
{
  dp[0] = dp[1] = 0; rep(i, 2, N - 1) dp[i] = dp[i - 1] + 2 * i - 3;
}

int check(int x)
{
  int now = 1;
  rep(i, 1, n)
  {
    if (now == a[x]) ++now;
    if (i == x) continue;
    if (a[i] && a[i] != now) return 0;
    ++now;
  }
  return 1;
}

int check(int x, int y)
{
  if (x != y - 1) return 0;
  rep(i, 1, n)
  {
    if (i == x || i == y) continue;
    if (a[i] && a[i] != i) return 0;
  }
  return 1;
}

LL get(int x, int y)
{
  int l = n + 1, r = 0;
  rep(i, 1, n) if (a[i] && a[i] != i) l = min(l, i), r = max(r, i);
  rep(i, l, r) if (a[i] && a[i] == i) return 0;
  int L = l, R = n - r + 1;
  per(i, l, 1) if (a[i] == i) { L = l - i; break; }
  rep(i, r, n) if (a[i] == i) { R = i - r; break; }
  return 1LL * (L - x) * (R - y);
}

LL get()
{
  LL res = 0, now = 0;
  rep(i, 1, n) if (a[i]) res += dp[a[i] - now - 1], now = a[i];
  return res + dp[n - now];
}

int main()
{
  init();
  while (scanf("%d", &n) != EOF)
  {
    int flag = 0, l = 0, r = 0;
    rep(i, 1, n)
    {
      scanf("%d", &a[i]);
      if (!a[i]) continue;
      if (abs(a[i] - i) > 1) flag = i;
      if (a[i] - i == 1) l = i;
      if (i - a[i] == 1) r = i;
    }
    if (flag) { printf("%d\n", check(flag)); continue; }
    if (l&&r) { printf("%d\n", check(l, r)); continue; }
    if (l || r) { printf("%lld\n", get(!l, !r)); continue; }
    printf("%lld\n", get());
  }
  return 0;
}