2019杭电多校十 1011 Make Rounddog Happy（rmq + 分治）

博观而约取，厚积而薄发。这篇文章主要讲述2019杭电多校十 1011 Make Rounddog Happy（rmq + 分治）相关的知识，希望能为你提供帮助。
题意有一个大小为 \(n ,(n \leq 3e5)\) 的序列，序列中的每一个数 \(a_i\) 满足\(1 \leq a_i \leq n\)，
现定义 good subarray：对于一段区间\(a_l, a_{l+1}, \dots, a_r\)，满足区间内无重复元素并且 \(\max\{a_l, a_{l+1}, \dots, a_r\} - (r-l+1) \leq k\)。
求序列a中的 good subarray的数量。
思路rmq + 分治的套路题。
针对最大值，可通过rmq预处理，待需要时可通过\(O(log)\)的复杂度查询区间最大值的位置。
对于每个位置，可通过dp (瞎搞)，求出与其无重复元素的左右两端。
接下来就可以通过对最大值分治。
【2019杭电多校十 1011 Make Rounddog Happy（rmq + 分治）】分治过程中对于区间 \([l, r]\) 可通过rmq查询快速得到最大值的位置 \(p\) ，在\(p-l、 r-p\) 两段中选择一个较小的暴力枚举合法区间数量。
通过分治，每个点的期望遍历次数为\(log\) 次，整体代码期望复杂度为\(O(nlog)\) 。
Code

#include < bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 3e5+10; ll ans; int a[maxn], st[maxn][30]; int vis[maxn], _l[maxn], _r[maxn]; int T, n, k; int query(int l, int r) { int len = r-l+1, d=0; while((1< < d+1)< =len) ++d; int p=1< < d; if(a[st[l][d]]> a[st[r-p+1][d]]) return st[l][d]; return st[r-p+1][d]; }void solve(int l, int r) { if(l > r) return; int p = query(l, r); solve(l, p-1); solve(p+1,r); int len = a[p]-k; if(p-l < r-p) { for (int i=p; i> =l; --i) { int L = max(p, i+len-1); int R = min(r, _r[i]); if(R> =L) ans += R-L+1; } } else { for (int i=p; i< =r; ++i) { int L = max(_l[i], l); int R = min(i-len+1, p); if(R> =L) ans += R-L+1; } } }int main() { scanf(" %d" , & T); while(T--) { scanf(" %d%d" , & n, & k); for (int i=1; i< =n; ++i) scanf(" %d" , a+i), st[i][0]=i; for (int j=1; j< =20; ++j) { int p = 1< < j-1, l=1< < j; for (int i=1; i+l-1< =n; ++i) { if(a[st[i][j-1]] > a[st[i+p][j-1]]) st[i][j] = st[i][j-1]; else st[i][j] = st[i+p][j-1]; } }for (int i=1; i< =n; ++i) vis[i]=n+1; for (int i=n; i> =1; --i) { _r[i]=vis[a[i]]-1; vis[a[i]]=i; } for (int i=n-1; i> =1; --i) _r[i] = min(_r[i], _r[i+1]); for (int i=1; i< =n; ++i) vis[i]=0; for (int i=1; i< =n; ++i) { _l[i]=vis[a[i]]+1; vis[a[i]]=i; } for (int i=2; i< =n; ++i) _l[i] = max(_l[i-1], _l[i]); ans = 0; solve(1, n); printf(" %lld\n" , ans); } return 0; }/* 2 5 3 2 3 2 2 5 10 4 1 5 4 3 6 2 10 8 4 5 */

总结刚开始忽略掉了区间中无重复值这个条件，满脑子都是单调栈+瞎搞，等看到这个条件时已经神志不清了，再做题时，需要读好题目中的要求，头脑清醒的分析抽象题目、理清思路与其时间空间以及手敲的复杂度之后再上机，避免既浪费时间，又影响心态。