# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
I can`t understend why answer is "1 2 3".
1 because {1}={2}, 2 because {3,1}={10,1}, and what is 3?
UPD. understood
3 because {1,2} = {4,5}
Maybe in KMP:
a[0]...a[i]...a[j]...a[k]
a[0]...a[i]==a[j]...a[k]
ifa[0]...a[i-1]==a[j]...a[k-1]
anda[i]==a[k]
.a[i]==a[k]
if and only if count of numbers which greather thena[i]
ina[0]..a[i-1]
is equal to count of numbers which greather thena[k]
ina[j]..a[k-1]
.We can use the struct like segment tree, which help us get this count in
O(log(400000))
(just +1 toa[i]
when we add numbera[i]
ans -1 else). If we getsuffix(a[j]..a[k-1])
we don't forget to decrease all values which don't include to this suffix (it'sa[j]..a[h]
, ifa[j]..a[k-1]=a[j]..a[h]a[h+1]..a[k-1]
). And first we should decrease all numbers as it possibly in any sequence because numbers are in the range1..2^32
(then we can use a segment tree).I don't know is it correct solution, but maybe.
Yes, I did something like that for POJ 3167, using a BIT. But in that problem we only need to match one pattern. In SPOJ UNTITLED you need to match many patterns.
read the solution to ceoi 2011 Matching