我们考虑从左往右扫右端点和从右往左扫左端点的两遍扫描线。（以下选取从左往右的扫描线来说明）考虑每个点向它左边第一个比它大的点连边形成的树。设i左边第一个比它大的点的坐标是 lasti last_i（如果没有则 lasti=0 last_i=0），i右边第一个比它大的点的坐标是 nexti

为什么当时我认定这是一道字符串题，写了半个AC自动机，删掉，改成枚举+哈希？写完之后感觉很奇怪，怎么没用上p是素数这个假设？ 考试的前天晚上还和学长讨论莫队算法来着……嗯，还讨论了主席树…… 莫队算法是解决一类离线区间查询问题的算法。设序列长度为n，有m个查询。为了达到理想的时间复杂度，需要保证[l, r]能在 O(1) O(1)的时间转移到[l, r+1]，[l, r-1]，[r-1, l]

4540: [Hnoi2016]序列 Time Limit: 20 Sec Memory Limit: 512 MB Description 　　给定长度为n的序列：a1,a2,…,an，记为a[1:n]。类似地，a[l:r]（1≤l≤r≤N）是指序列：al,al+1,…,ar-1,ar。若1≤l≤s≤t≤r≤n，则称a[s:t]是a[l:r]的子序列。现在有q个询问，每个询问给定两个数l