BZOJ 1717: [Usaco2006 Dec]Milk Patterns 产奶的模式

1717: [Usaco2006 Dec]Milk Patterns 产奶的模式

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1066 Solved: 582
[Submit][Status][Discuss]

Description

农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时，这个长度为4。

Input

* Line 1: 两个整数 N,K。

* Lines 2..N+1: 每行一个整数表示当天的质量值。

Output

* Line 1: 一个整数：N天中最长的出现了至少K次的模式的长度

Sample Input

8 2
1
2
3
2
3
2
3
1

Sample Output

HINT

Source

Gold

[Submit][Status][Discuss]

求出后缀数组,二分答案,在height数组里找出最大的出现次数进行判断

  1 #include <bits/stdc++.h>
  2 
  3 inline char Char(void)
  4 {
  5     static const int siz = 1 << 20;
  6     
  7     static char buf[siz];
  8     static char *hd = buf + siz;
  9     static char *tl = buf + siz;
 10     
 11     if (hd == tl)
 12         fread(hd = buf, 1, siz, stdin);
 13     
 14     return *hd++;
 15 }
 16 
 17 inline int Int(void)
 18 {
 19     int ret = 0, neg = 0, c = Char();
 20     
 21     for (; c < 48; c = Char())
 22         if (c == '-')neg ^= true;
 23     
 24     for (; c > 47; c = Char())
 25         ret = ret * 10 + c - '0';
 26     
 27     return neg ? -ret : ret;
 28 }
 29 
 30 const int siz = 20005;
 31 
 32 int n, m, s[siz];
 33 
 34 int map[siz], tot;
 35 
 36 int sa[siz], rk[siz], ht[siz];
 37 
 38 inline void prework_sa(void)
 39 {
 40     static int ta[siz];
 41     static int wa[siz], wb[siz];
 42     static int ca[siz], cb[siz];
 43     
 44     for (int i = 1; i <= n; ++i)
 45         ++ca[s[i]];
 46     
 47     for (int i = 1; i <= n; ++i)
 48         ca[i] += ca[i - 1];
 49     
 50     for (int i = n; i >= 1; --i)
 51         sa[ca[s[i]]--] = i;
 52     
 53     rk[sa[1]] = 1;
 54     
 55     for (int i = 2; i <= n; ++i)
 56     {
 57         rk[sa[i]] = rk[sa[i - 1]];
 58         if (s[sa[i]] != s[sa[i - 1]])
 59             ++rk[sa[i]];
 60     }
 61     
 62     for (int l = 1; rk[sa[n]] < n; l <<= 1)
 63     {
 64         for (int i = 1; i <= n; ++i)
 65             ca[i] = cb[i] = 0;
 66         
 67         for (int i = 1; i <= n; ++i)
 68         {
 69             ++ca[wa[i] = rk[i]];
 70             ++cb[wb[i] = i + l <= n ? rk[i + l] : 0];
 71         }
 72         
 73         for (int i = 1; i <= n; ++i)
 74         {
 75             ca[i] += ca[i - 1];
 76             cb[i] += cb[i - 1];
 77         }
 78         
 79         for (int i = n; i >= 1; --i)
 80             ta[cb[wb[i]]--] = i;
 81         
 82         for (int i = n; i >= 1; --i)
 83             sa[ca[wa[ta[i]]]--] = ta[i];
 84         
 85         rk[sa[1]] = 1;
 86         
 87         for (int i = 2; i <= n; ++i)
 88         {
 89             rk[sa[i]] = rk[sa[i - 1]];
 90             if (wa[sa[i]] != wa[sa[i - 1]]
 91             ||  wb[sa[i]] != wb[sa[i - 1]])
 92                 ++rk[sa[i]];
 93         }
 94     }
 95     
 96     for (int i = 1, j = 0; i <= n; ++i)
 97     {
 98         if (--j < 0)j = 0;
 99         while (s[i + j] == s[sa[rk[i] - 1] + j])++j;
100         ht[rk[i]] = j;
101     }
102 }
103 
104 inline int count(int len)
105 {
106     int ret = 0, cnt = 1;
107     
108     for (int i = 2; i <= n; ++i)
109         if (ht[i] >= len)
110             ++cnt;
111         else
112         {
113             if (ret < cnt)
114                 ret = cnt;
115             cnt = 1;
116         }
117     
118     if (ret < cnt)
119         ret = cnt;
120     
121     return ret;
122 }
123 
124 signed main(void)
125 {
126     n = Int();
127     m = Int();
128     
129     for (int i = 1; i <= n; ++i)
130         s[i] = map[++tot] = Int();
131     
132     std::sort(map + 1, map + tot + 1);
133     
134     tot = std::unique(map + 1, map + tot + 1) - map;
135     
136     for (int i = 1; i <= n; ++i)
137         s[i] = std::lower_bound(map + 1, map + tot, s[i]) - map;
138         
139     prework_sa();
140     
141     int lt = 0, rt = n, mid, ans = 0;
142     
143     while (lt <= rt)
144     {
145         mid = (lt + rt) >> 1;
146         
147         if (count(mid) >= m)
148             lt = mid + 1, ans = mid;
149         else
150             rt = mid - 1;
151     }
152     
153     printf("%d
", ans);
154 }

@Author: YouSiki