博观而约取,厚积而薄发。这篇文章主要讲述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
*/
总结刚开始忽略掉了区间中无重复值这个条件,满脑子都是单调栈+瞎搞,等看到这个条件时已经神志不清了,再做题时,需要读好题目中的要求,头脑清醒的分析抽象题目、理清思路与其时间空间以及手敲的复杂度之后再上机,避免既浪费时间,又影响心态。
推荐阅读
- appium 切换native/ webview,findby,还有页面元素定位一直小于0的问题的解决
- Android插件化原理Activity插件化
- eclipse中搭建Android开发环境
- Appium-处理系统弹窗
- Spring整合MyBatis (使用扫描包配置mapper代理)
- Android之使用传感器获取相应数据
- android虚拟机的垃圾收集
- 浅谈@RequestMapping @ResponseBody 和 @RequestBody 注解的用法与区别
- cannot access android.support.v4.app.BaseFragmentActivityJB的解决