1use std::cmp::Reverse;
2
3pub trait LisMapProj<T: Ord + Clone> {
4 type Mapped: Ord + Clone;
5 fn map(&self, index: usize, elt: &T) -> Self::Mapped;
6 fn proj(&self, elt: &Self::Mapped) -> usize;
7}
8
9pub struct Smallest;
10pub struct Largest;
11pub struct Leftmost;
12pub struct Rightmost;
13
14impl<T: Ord + Clone> LisMapProj<T> for Smallest {
15 type Mapped = (Reverse<T>, usize);
16 fn map(&self, index: usize, elt: &T) -> (Reverse<T>, usize) {
17 (Reverse(elt.clone()), index)
18 }
19 fn proj(&self, &(_, index): &(Reverse<T>, usize)) -> usize { index }
20}
21impl<T: Ord + Clone> LisMapProj<T> for Largest {
22 type Mapped = (T, usize);
23 fn map(&self, index: usize, elt: &T) -> (T, usize) { (elt.clone(), index) }
24 fn proj(&self, &(_, index): &(T, usize)) -> usize { index }
25}
26impl<T: Ord + Clone> LisMapProj<T> for Leftmost {
27 type Mapped = Reverse<usize>;
28 fn map(&self, index: usize, _: &T) -> Reverse<usize> { Reverse(index) }
29 fn proj(&self, &Reverse(index): &Reverse<usize>) -> usize { index }
30}
31impl<T: Ord + Clone> LisMapProj<T> for Rightmost {
32 type Mapped = usize;
33 fn map(&self, index: usize, _: &T) -> usize { index }
34 fn proj(&self, &index: &usize) -> usize { index }
35}
36
37pub trait Lis {
38 type Item: Ord + Clone;
39 fn lis(
40 &self,
41 strict: bool,
42 mp: impl LisMapProj<Self::Item>,
43 ) -> Vec<Self::Item>;
44 fn lis_len(&self, strict: bool) -> usize {
45 self.lis(strict, Rightmost).len()
46 }
47}
48
49impl<T: Ord + Clone> Lis for [T] {
50 type Item = T;
51 fn lis(&self, strict: bool, mp: impl LisMapProj<T>) -> Vec<Self::Item> {
52 if self.is_empty() {
53 return vec![];
54 }
55
56 let n = self.len();
57 let ord = {
58 let mut ord: Vec<_> = (0..n).collect();
59 if strict {
60 ord.reverse();
61 }
62 ord.sort_by_key(|&i| &self[i]);
63 ord
64 };
65 let mut dp = FenwickTree::from(vec![None; n]);
66 let mut prev = vec![None; n];
67 for &i in &ord {
68 let max = dp.max(..i).unwrap_or(None);
69 let max_len = max.as_ref().map(|x: &(usize, _)| x.0).unwrap_or(0);
70 dp.update(i, Some((max_len + 1, mp.map(i, &self[i]))));
71 prev[i] = max.map(|(_, x)| mp.proj(&x));
72 }
73 let mut last =
74 dp.max(..n).unwrap_or(None).map(|(_, x): (usize, _)| mp.proj(&x));
75 let mut res = vec![];
76 while let Some(i) = last {
77 res.push(self[i].clone());
78 last = prev[i];
79 }
80 res.reverse();
81 res
82 }
83 fn lis_len(&self, strict: bool) -> usize {
84 if self.is_empty() {
85 return 0;
86 }
87
88 let n = self.len();
89 let ord = {
90 let mut ord: Vec<_> = (0..n).collect();
91 if strict {
92 ord.reverse();
93 }
94 ord.sort_by_key(|&i| &self[i]);
95 ord
96 };
97 let mut dp = FenwickTree::from(vec![0; n]);
98 for &i in &ord {
99 let max_len = dp.max(..i).unwrap_or(0);
100 dp.update(i, max_len + 1);
101 }
102 dp.max(..n).unwrap_or(0)
103 }
104}
105
106use std::ops::RangeTo;
107
108struct FenwickTree<T: Ord + Clone>(Vec<T>);
109
110impl<T: Ord + Clone> From<Vec<T>> for FenwickTree<T> {
111 fn from(buf: Vec<T>) -> Self { Self(buf) }
112}
113
114impl<T: Ord + Clone> FenwickTree<T> {
115 fn max(&self, RangeTo { end: i }: RangeTo<usize>) -> Option<T> {
116 std::iter::successors(Some(i), |&i| Some(i - (i & i.wrapping_neg())))
117 .take_while(|&i| i > 0)
118 .map(|i| &self.0[i - 1])
119 .max()
120 .cloned()
121 }
122 fn update(&mut self, i: usize, x: T) {
123 let n = self.0.len();
124 std::iter::successors(Some(i + 1), |&i| {
125 Some(i + (i & i.wrapping_neg()))
126 })
127 .take_while(|&i| i <= n)
128 .for_each(|i| {
129 if self.0[i - 1] < x {
130 self.0[i - 1] = x.clone();
131 }
132 });
133 }
134}
135
136#[test]
137fn sanity_check() {
138 assert_eq!([1, 1, 1].lis(true, Smallest), [1]);
139 assert_eq!([1, 1, 1].lis(false, Smallest), [1, 1, 1]);
140
141 assert_eq!([1, 2, 3, 4].lis(true, Smallest), [1, 2, 3, 4]);
142 assert_eq!([1, 2, 4, 3].lis(true, Smallest), [1, 2, 3]);
143 assert_eq!([1, 3, 2, 4].lis(true, Smallest), [1, 2, 4]);
144 assert_eq!([1, 3, 4, 2].lis(true, Smallest), [1, 3, 4]);
145 assert_eq!([1, 4, 2, 3].lis(true, Smallest), [1, 2, 3]);
146 assert_eq!([1, 4, 3, 2].lis(true, Smallest), [1, 2]);
147
148 assert_eq!([2, 1, 3, 4].lis(true, Smallest), [1, 3, 4]);
149 assert_eq!([2, 1, 4, 3].lis(true, Smallest), [1, 3]);
150 assert_eq!([2, 3, 1, 4].lis(true, Smallest), [2, 3, 4]);
151 assert_eq!([2, 3, 4, 1].lis(true, Smallest), [2, 3, 4]);
152 assert_eq!([2, 4, 1, 3].lis(true, Smallest), [1, 3]);
153 assert_eq!([2, 4, 3, 1].lis(true, Smallest), [2, 3]);
154
155 assert_eq!([3, 1, 2, 4].lis(true, Smallest), [1, 2, 4]);
156 assert_eq!([3, 1, 4, 2].lis(true, Smallest), [1, 2]);
157 assert_eq!([3, 2, 1, 4].lis(true, Smallest), [1, 4]);
158 assert_eq!([3, 2, 4, 1].lis(true, Smallest), [2, 4]);
159 assert_eq!([3, 4, 1, 2].lis(true, Smallest), [1, 2]);
160 assert_eq!([3, 4, 2, 1].lis(true, Smallest), [3, 4]);
161
162 assert_eq!([4, 1, 2, 3].lis(true, Smallest), [1, 2, 3]);
163 assert_eq!([4, 1, 3, 2].lis(true, Smallest), [1, 2]);
164 assert_eq!([4, 2, 1, 3].lis(true, Smallest), [1, 3]);
165 assert_eq!([4, 2, 3, 1].lis(true, Smallest), [2, 3]);
166 assert_eq!([4, 3, 1, 2].lis(true, Smallest), [1, 2]);
167 assert_eq!([4, 3, 2, 1].lis(true, Smallest), [1]);
168
169 assert_eq!([1, 2, 3, 4].lis(true, Largest), [1, 2, 3, 4]);
170 assert_eq!([1, 2, 4, 3].lis(true, Largest), [1, 2, 4]);
171 assert_eq!([1, 3, 2, 4].lis(true, Largest), [1, 3, 4]);
172 assert_eq!([1, 3, 4, 2].lis(true, Largest), [1, 3, 4]);
173 assert_eq!([1, 4, 2, 3].lis(true, Largest), [1, 2, 3]);
174 assert_eq!([1, 4, 3, 2].lis(true, Largest), [1, 4]);
175
176 assert_eq!([2, 1, 3, 4].lis(true, Largest), [2, 3, 4]);
177 assert_eq!([2, 1, 4, 3].lis(true, Largest), [2, 4]);
178 assert_eq!([2, 3, 1, 4].lis(true, Largest), [2, 3, 4]);
179 assert_eq!([2, 3, 4, 1].lis(true, Largest), [2, 3, 4]);
180 assert_eq!([2, 4, 1, 3].lis(true, Largest), [2, 4]);
181 assert_eq!([2, 4, 3, 1].lis(true, Largest), [2, 4]);
182
183 assert_eq!([3, 1, 2, 4].lis(true, Largest), [1, 2, 4]);
184 assert_eq!([3, 1, 4, 2].lis(true, Largest), [3, 4]);
185 assert_eq!([3, 2, 1, 4].lis(true, Largest), [3, 4]);
186 assert_eq!([3, 2, 4, 1].lis(true, Largest), [3, 4]);
187 assert_eq!([3, 4, 1, 2].lis(true, Largest), [3, 4]);
188 assert_eq!([3, 4, 2, 1].lis(true, Largest), [3, 4]);
189
190 assert_eq!([4, 1, 2, 3].lis(true, Largest), [1, 2, 3]);
191 assert_eq!([4, 1, 3, 2].lis(true, Largest), [1, 3]);
192 assert_eq!([4, 2, 1, 3].lis(true, Largest), [2, 3]);
193 assert_eq!([4, 2, 3, 1].lis(true, Largest), [2, 3]);
194 assert_eq!([4, 3, 1, 2].lis(true, Largest), [1, 2]);
195 assert_eq!([4, 3, 2, 1].lis(true, Largest), [4]);
196
197 assert_eq!([1, 2, 3, 4].lis(true, Leftmost), [1, 2, 3, 4]);
198 assert_eq!([1, 2, 4, 3].lis(true, Leftmost), [1, 2, 4]);
199 assert_eq!([1, 3, 2, 4].lis(true, Leftmost), [1, 3, 4]);
200 assert_eq!([1, 3, 4, 2].lis(true, Leftmost), [1, 3, 4]);
201 assert_eq!([1, 4, 2, 3].lis(true, Leftmost), [1, 2, 3]);
202 assert_eq!([1, 4, 3, 2].lis(true, Leftmost), [1, 4]);
203
204 assert_eq!([2, 1, 3, 4].lis(true, Leftmost), [2, 3, 4]);
205 assert_eq!([2, 1, 4, 3].lis(true, Leftmost), [2, 4]);
206 assert_eq!([2, 3, 1, 4].lis(true, Leftmost), [2, 3, 4]);
207 assert_eq!([2, 3, 4, 1].lis(true, Leftmost), [2, 3, 4]);
208 assert_eq!([2, 4, 1, 3].lis(true, Leftmost), [2, 4]);
209 assert_eq!([2, 4, 3, 1].lis(true, Leftmost), [2, 4]);
210
211 assert_eq!([3, 1, 2, 4].lis(true, Leftmost), [1, 2, 4]);
212 assert_eq!([3, 1, 4, 2].lis(true, Leftmost), [3, 4]);
213 assert_eq!([3, 2, 1, 4].lis(true, Leftmost), [3, 4]);
214 assert_eq!([3, 2, 4, 1].lis(true, Leftmost), [3, 4]);
215 assert_eq!([3, 4, 1, 2].lis(true, Leftmost), [3, 4]);
216 assert_eq!([3, 4, 2, 1].lis(true, Leftmost), [3, 4]);
217
218 assert_eq!([4, 1, 2, 3].lis(true, Leftmost), [1, 2, 3]);
219 assert_eq!([4, 1, 3, 2].lis(true, Leftmost), [1, 3]);
220 assert_eq!([4, 2, 1, 3].lis(true, Leftmost), [2, 3]);
221 assert_eq!([4, 2, 3, 1].lis(true, Leftmost), [2, 3]);
222 assert_eq!([4, 3, 1, 2].lis(true, Leftmost), [1, 2]);
223 assert_eq!([4, 3, 2, 1].lis(true, Leftmost), [4]);
224
225 assert_eq!([1, 2, 3, 4].lis(true, Rightmost), [1, 2, 3, 4]);
226 assert_eq!([1, 2, 4, 3].lis(true, Rightmost), [1, 2, 3]);
227 assert_eq!([1, 3, 2, 4].lis(true, Rightmost), [1, 2, 4]);
228 assert_eq!([1, 3, 4, 2].lis(true, Rightmost), [1, 3, 4]);
229 assert_eq!([1, 4, 2, 3].lis(true, Rightmost), [1, 2, 3]);
230 assert_eq!([1, 4, 3, 2].lis(true, Rightmost), [1, 2]);
231
232 assert_eq!([2, 1, 3, 4].lis(true, Rightmost), [1, 3, 4]);
233 assert_eq!([2, 1, 4, 3].lis(true, Rightmost), [1, 3]);
234 assert_eq!([2, 3, 1, 4].lis(true, Rightmost), [2, 3, 4]);
235 assert_eq!([2, 3, 4, 1].lis(true, Rightmost), [2, 3, 4]);
236 assert_eq!([2, 4, 1, 3].lis(true, Rightmost), [1, 3]);
237 assert_eq!([2, 4, 3, 1].lis(true, Rightmost), [2, 3]);
238
239 assert_eq!([3, 1, 2, 4].lis(true, Rightmost), [1, 2, 4]);
240 assert_eq!([3, 1, 4, 2].lis(true, Rightmost), [1, 2]);
241 assert_eq!([3, 2, 1, 4].lis(true, Rightmost), [1, 4]);
242 assert_eq!([3, 2, 4, 1].lis(true, Rightmost), [2, 4]);
243 assert_eq!([3, 4, 1, 2].lis(true, Rightmost), [1, 2]);
244 assert_eq!([3, 4, 2, 1].lis(true, Rightmost), [3, 4]);
245
246 assert_eq!([4, 1, 2, 3].lis(true, Rightmost), [1, 2, 3]);
247 assert_eq!([4, 1, 3, 2].lis(true, Rightmost), [1, 2]);
248 assert_eq!([4, 2, 1, 3].lis(true, Rightmost), [1, 3]);
249 assert_eq!([4, 2, 3, 1].lis(true, Rightmost), [2, 3]);
250 assert_eq!([4, 3, 1, 2].lis(true, Rightmost), [1, 2]);
251 assert_eq!([4, 3, 2, 1].lis(true, Rightmost), [1]);
252}
253
254#[test]
255fn check() {
256 for ai in (0..7_u32.pow(7)).map(|x| {
257 std::iter::successors(Some(x), |x| Some(x / 7))
258 .map(|x| x % 7)
259 .take(7)
260 .collect::<Vec<_>>()
261 }) {
262 assert_eq!(ai.lis(true, Rightmost).len(), ai.lis_len(true));
263 assert_eq!(ai.lis(true, Smallest), ai.lis(true, Rightmost));
264 assert_eq!(ai.lis(true, Largest), ai.lis(true, Leftmost));
265 assert_eq!(ai.lis(false, Rightmost).len(), ai.lis_len(false));
266 assert_eq!(ai.lis(false, Smallest), ai.lis(false, Rightmost));
267 assert_eq!(ai.lis(false, Largest), ai.lis(false, Leftmost));
268 }
269}