L. Continuous Intervals

給定一個長度為$n$的數組，問里面有多少個區間$[l,r]$，滿足，對這個區間排序后，兩兩差值$ \leq 1$，輸出區間個數。

如果說區間$[l,r]$是符合要求的，則滿足$max(a_l,\dots ,a_r)?min(a_l,\dots ,a_r)+1=cnt$，$cnt$為區間$[l,r]$中不同的數的個數。

則我們要統計的就是，對于每個$r$，有多少個點$i$滿足$max?min?cnt=?1$，然后累加個數即可。

區間不滿足條件則一定有$max?min?cnt>?1$，所以我們可以對每個點都存放$max?min?cut$的值，然后維護最小值個數即可。

當點$[1,i?1]$區間都已經統計好了，這個時候$i$加入數組，所以我們要更新的就是最大值為$a_i$的，最小值為$a_i$的，以及$cnt$的貢獻。

對于$max$，$min$的更新，可以用單調棧維護一下，然后區間更新即可，$cnt$可以離散化找到上一個點出現的最后位置，或者直接用$map$。

#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); }map<int, 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; }

總結

以上是生活随笔為你收集整理的L. Continuous Intervals（单调栈 + 线段树 + 思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。