BZOJ 4553: [Tjoi2016&Heoi2016]序列

4553: [Tjoi2016&Heoi2016]序列

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 575 Solved: 267
[Submit][Status][Discuss]

Description

佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列，数列中某些项的值

可能会变化，但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你

，能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可

。注意：每种变化最多只有一个值发生变化。在样例输入1中，所有的变化是：

1 2 3

2 2 3

1 3 3

1 1 31 2 4

选择子序列为原序列，即在任意一种变化中均为不降子序列在样例输入2中，所有的变化是:3 3 33 2 3选择子序列

为第一个元素和第三个元素，或者第二个元素和第三个元素，均可满足要求

Input

输入的第一行有两个正整数n, m，分别表示序列的长度和变化的个数。接下来一行有n个数，表示这个数列原始的

状态。接下来m行，每行有2个数x, y，表示数列的第x项可以变化成y这个值。1 <= x <= n。所有数字均为正整数

，且小于等于100,000

Output

输出一个整数，表示对应的答案

Sample Input

3 4
1 2 3
1 2
2 3
2 1
3 4

Sample Output

HINT

Source

[Submit][Status][Discuss]

分治动态规划过程，学习了

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 
  5 template <class T>
  6 inline T min(const T &a, const T &b)
  7 {
  8     return a < b ? a : b;
  9 }
 10 
 11 template <class T>
 12 inline T max(const T &a, const T &b)
 13 {
 14     return a > b ? a : b;
 15 }
 16 
 17 const int mxn = 100005;
 18 
 19 int n, m;
 20 
 21 int s[mxn];
 22 int f[mxn];
 23 
 24 int mn[mxn];
 25 int mx[mxn];
 26 
 27 inline bool cmp1(int a, int b)
 28 {
 29     return s[a] < s[b];
 30 }
 31 
 32 inline bool cmp2(int a, int b)
 33 {
 34     return mn[a] < mn[b];
 35 }
 36 
 37 int tim;
 38 int tr[mxn];
 39 int tg[mxn];
 40 
 41 inline void ins(int p, int v)
 42 {
 43     for (; p <= n; p += p & -p)
 44         if (tg[p] != tim)
 45             tr[p] = v, tg[p] = tim;
 46         else
 47             tr[p] = max(tr[p], v);
 48 }
 49 
 50 inline int qry(int p)
 51 {
 52     int r = 0;
 53     
 54     for (; p >= 1; p -= p & -p)
 55         if (tg[p] == tim)
 56             r = max(r, tr[p]);
 57     
 58     return r;
 59 }
 60 
 61 int ord[mxn];
 62 
 63 void solve(int l, int r)
 64 {
 65     int d = (l + r) >> 1;
 66         
 67     if (l != d)
 68         solve(l, d);
 69     
 70     ++tim;
 71     
 72     std::sort(ord + l,     ord + d + 1, cmp1);
 73     std::sort(ord + d + 1, ord + r + 1, cmp2);
 74     
 75     for (int i = l, j = d + 1; j <= r; ++j)
 76     {
 77         #define a ord[i]
 78         #define b ord[j]
 79         
 80         while (i <= d && s[a] <= mn[b])
 81             ins(mx[a], f[a]), ++i;
 82         
 83         f[b] = max(f[b], qry(s[b]) + 1);
 84         
 85         ord[j] = j;
 86     }
 87     
 88     if (d + 1 != r)
 89         solve(d + 1, r);
 90 }
 91 
 92 signed main(void)
 93 {
 94     scanf("%d%d", &n, &m);
 95     
 96     for (int i = 1; i <= n; ++i)
 97     {
 98         scanf("%d", s + i);
 99         
100         mn[i] = s[i];
101         mx[i] = s[i];
102     }
103     
104     for (int i = 1; i <= m; ++i)
105     {
106         int p, v; scanf("%d%d", &p, &v);
107         
108         mn[p] = min(mn[p], v);
109         mx[p] = max(mx[p], v);
110     }
111     
112     for (int i = 1; i <= n; ++i)
113         ord[i] = i, f[i] = 1;
114     
115     solve(1, n);
116     
117     int ans = 0;
118     
119     for (int i = 1; i <= n; ++i)
120         ans = max(ans, f[i]);
121     
122     printf("%d
", ans);
123 }

@Author: YouSiki