连号区间数+CF526F[CF]

CF题目链接

题意

  • 【CF题意】：在N*N的二维矩阵上有N个点，一定是一行或者一列，有且仅有一个数，总有多少个子矩阵，也满足一行或一列，有且仅有一个数,N为30万.
  • 【蓝桥杯题意】：给出N个数的某个排列，求出有多少个子序列，把它排序后是连续递增的.N为5万.

题外话

这是一个两年前就折磨了我的题目..本来我已经忘了这事儿，没想到前几天在某群里看见有人问这个问题了，一下子勾起了我的回忆.在13年的蓝桥杯省赛中，最后一道压轴题就是连号区间数，当时写了个$O(n^2)$的算法水了一下，后来在蓝桥杯官网中也发现数据比较水，N方随便过,我只知道这个算法是不科学的，但想了好久，也没搞定这题，后来渐渐的就忘了..
前两天看见有人问起这题，说是线段树是一个科学的解法，还给了一个题解链接,于是我突然又兴奋了，决定解决掉这题…

正题

  • 主要算法：dp & 线段树

思路

  • 对于A[1...N]的一个子序列A[j...i](i >= j)，令区间内最大值maxValue = max(A[j...i]),最小值minValue = min(A[j...i])可以得到一个公式maxValue - minValue >= i - j,当maxValue - minValue == i - j的时候，我们的答案+1,把j移到左边转换一下就成了maxValue - minValue + j == i;
    所以我们维护一下等式左边的值dp[p]，当我们从左到右枚举A[i],看有多少个位置p的结果等于k就可以得出答案了(p<=i)，
    怎么维护呢？
  • 我们设函数f(j) = maxValue - minValue + j(注意maxValue和minValue一直在变).
    我们可以用一棵线段树来维护，每个节点seg[k]范围为l到r，表示的是枚举到i时，l到r范围内有多少个最小值fMinLR,fMinLR = min(f(j)),(l <= j <= r)
    我们初始时所有叶子节点都为对应的位置p
  • 对于第i个数A[i],我们可以找到一个j满足:j要尽量小，而且A[j - 1] < A[i],找到一个k满足:k要尽量小而且A[k - 1] > A[i], 这时候区间[j,i]的最大值maxValue等于A[i],区间[k, i]的最小值minValue是A[i],所以这时候区间更新(区间+maxValue,区间-minValue)就可以得出区间内所有的f(x)值了
    枚举完A[i]该枚举下一个了A[i + 1],会有新的区间[j1,i + 1],[k1, i + 1],更新新区间的时候会和这次的更新重叠，所以要把这次更新的恢复回去(重叠部分)，然后才能进行下次更新。
    差不多就这样了…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#pragma comment(linker,"/STACK:102400000,102400000")
#include <bits/stdc++.h>
namespace Defination {
typedef long long LLONG;
static const int sciArraySize = 3e5 + 10;
#define debug(x) std::cout << #x << " = " << x << std::endl;
};
using namespace Defination;
struct SegmentTree {
#define LSON    (v << 1)
#define RSON    (v << 1 | 1)
  void build(int l, int r, int v) {
    minValue[v] = l;
    if (l >= r) {
      countOfMinValue[v] = 1;
      return;
    }
    int mid = l + r >> 1;
    build(l, mid, LSON);
    build(mid + 1, r, RSON);
  }
  int getCountWithValue(int v, int mv) {
    return minValue[v] + lazy[v] == mv ? countOfMinValue[v] : 0;
  }
  void pushUp(int v) {
    int mv = std::min(minValue[LSON] + lazy[LSON], minValue[RSON] + lazy[RSON]);
    minValue[v] = mv;
    countOfMinValue[v] = getCountWithValue(LSON, mv) + getCountWithValue(RSON, mv);
  }
  void pushDown(int v) {
    if (lazy[v]) {
      lazy[LSON] += lazy[v];
      lazy[RSON] += lazy[v];
      lazy[v] = 0;
    }
  }
  void update(int l, int r, int x, int y, int addValue, int v) {
    if (l >= x && r <= y) {
      lazy[v] += addValue;
      if (x >= y) countOfMinValue[v] = 1;
      return;
    }
    pushDown(v);
    int mid = l + r >> 1;
    if (mid >= x) update(l, mid, x, y, addValue, LSON);
    if (mid < y) update(mid + 1, r, x, y, addValue, RSON);
    pushUp(v);
  }
private:
  int minValue[sciArraySize << 2];  //区间内最小值
  int lazy[sciArraySize << 2];
  int countOfMinValue[sciArraySize << 2]; //f(x)最小值计数
} tree;
int A[sciArraySize];
int dpLager[sciArraySize];  //dp[i] = j 表示区间[j,i]的最小值是A[i],[1, j - 1]的最小值大于A[i]
int dpLower[sciArraySize];  //dp[i] = k 表示区间[k,i]的最大值是A[i],[1, k - 1]的最大值小于A[i]
int main() {
  int n;
  LLONG answer = 0;
  std::cin >> n;
  for (int i = 1; i <= n; ++i) {
    int r, c;
    std::cin >> r >> c;
    A[r] = c;
  }
  tree.build(1, n, 1);
  for (int i = 1; i <= n; ++i) {
    for (dpLower[i] = i - 1; dpLower[i] > 0 && A[dpLower[i]] <= A[i]; dpLower[i] = dpLower[dpLower[i]])
      tree.update(1, n, dpLower[dpLower[i]] + 1, dpLower[i], -A[dpLower[i]], 1);
    for (dpLager[i] = i - 1; dpLager[i] > 0 && A[dpLager[i]] >= A[i]; dpLager[i] = dpLager[dpLager[i]])
      tree.update(1, n, dpLager[dpLager[i]] + 1, dpLager[i], A[dpLager[i]], 1);
    tree.update(1, n, dpLower[i] + 1, i, A[i], 1);
    tree.update(1, n, dpLager[i] + 1, i, -A[i], 1);
    answer += tree.getCountWithValue(1, i);
  }
  std::cout << answer << std::endl;
  return 0;
}

留言

2016-01-02
▲