哪个网站做欧洲旅游攻略好,wordpress视频模块,上饶建设培训中心网站,上海百度网络推广L. Continuous Intervals
给定一个长度为nnn的数组#xff0c;问里面有多少个区间[l,r][l, r][l,r]#xff0c;满足#xff0c;对这个区间排序后#xff0c;两两差值$ \leq 1$#xff0c;输出区间个数。
如果说区间[l,r][l, r][l,r]是符合要求的#xff0c;则满足max(a…L. Continuous Intervals
给定一个长度为nnn的数组问里面有多少个区间[l,r][l, r][l,r]满足对这个区间排序后两两差值$ \leq 1$输出区间个数。
如果说区间[l,r][l, r][l,r]是符合要求的则满足max(al,…,ar)−min(al,…,ar)1cntmax(a_l, \dots, a_r) - min(a_l, \dots, a_r) 1 cntmax(al,…,ar)−min(al,…,ar)1cntcntcntcnt为区间[l,r][l, r][l,r]中不同的数的个数。
则我们要统计的就是对于每个rrr有多少个点iii满足max−min−cnt−1max - min - cnt -1max−min−cnt−1然后累加个数即可。
区间不满足条件则一定有max−min−cnt−1max - min - cnt -1max−min−cnt−1所以我们可以对每个点都存放max−min−cutmax - min - cutmax−min−cut的值然后维护最小值个数即可。
当点[1,i−1][1, i -1][1,i−1]区间都已经统计好了这个时候iii加入数组所以我们要更新的就是最大值为aia_iai的最小值为aia_iai的以及cntcntcnt的贡献。
对于maxmaxmaxminminmin的更新可以用单调栈维护一下然后区间更新即可cntcntcnt可以离散化找到上一个点出现的最后位置或者直接用mapmapmap。
#include bits/stdc.h
#define mid (l r 1)
#define ls rt 1
#define lson rt 1, l, mid
#define rson rt 1 | 1, mid 1, r
#define ls rt 1
#define rs rt 1 | 1using namespace std;const int N 1e5 10;int value[N 2], sum[N 2], lazy[N 2];int a[N], stk1[N], stk2[N], top1, top2, n;void build(int rt, int l, int r) {lazy[rt] sum[rt] value[rt] 0;if (l r) {return ;}build(lson);build(rson);
}void push_down(int rt) {if (lazy[rt]) {value[ls] lazy[rt], value[rs] lazy[rt];lazy[ls] lazy[rt], lazy[rs] lazy[rt];lazy[rt] 0;}
}void push_up(int rt) {value[rt] min(value[ls], value[rs]), sum[rt] 0;if (value[ls] value[rt]) {sum[rt] sum[ls];}if (value[rs] value[rt]) {sum[rt] sum[rs];}
}void update(int rt, int l, int r, int x) {if (l r) {value[rt] -1;sum[rt] 1;return ;}push_down(rt);if (x mid) {update(lson, x);}else {update(rson, x);}push_up(rt);
}void update(int rt, int l, int r, int L, int R, int v) {if (L R) {return ;}if (l L r R) {value[rt] v, lazy[rt] v;return ;}push_down(rt);if (L mid) {update(lson, L, R, v);}if (R mid) {update(rson, L, R, v);}push_up(rt);
}mapint, int mp;int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);int T;scanf(%d, T);for (int cas 1; cas T; cas) {scanf(%d, n);for (int i 1; i n; i) {scanf(%d, a[i]);}build(1, 1, n);top1 top2 0, mp.clear();long long ans 0;for (int i 1; i n; i) {update(1, 1, n, i);while (top1 a[stk1[top1]] a[i]) {int v a[i] - a[stk1[top1]];int l stk1[top1 - 1] 1, r stk1[top1];update(1, 1, n, l, r, v);top1--;}stk1[top1] i;while (top2 a[stk2[top2]] a[i]) {int v a[stk2[top2]] - a[i];int l stk2[top2 - 1] 1, r stk2[top2];update(1, 1, n, l, r, v);top2--;}stk2[top2] i;int l mp.count(a[i]) ? mp[a[i]] 1 : 1;mp[a[i]] i;update(1, 1, n, l, i - 1, -1);ans sum[1];}printf(Case #%d: %lld\n, cas, ans);}return 0;
}
