CF997E. Good Subsegments

Description

給定一個序列，多次詢問一個區間內的連續段個數。
$n,q\le 2\times 10^5$

Solution

算得上是經典題了吧。

Part one

先考慮求全部的連續段個數。

相當于求區間內$mx?mn+1?len=0$的子區間個數，且顯然有$mx?mn+1?len\ge 0$，因此相當于維護最小值及其個數。于是我們考慮從前往后枚舉區間右端點$r$，維護所有右端點為$r$的區間的信息。

不難觀察到前綴$mx$和前綴$mn$的單調性，每次我們加入一個$p_r$時，會讓一段后綴的$mx$和一段后綴的$mn$改變，且改變的這一段后綴$mx$會變成$p_r$，$mn$同理。于是我們用單調棧分別維護前綴$mx,mn$的連續段，每次彈棧的時候做區間加就可以維護我們需要的信息了。

這樣的時間復雜度是$O(mlgn)$的。

Part two

再考慮區間詢問，上述枚舉右端點的做法啟示我們離線詢問。考慮每個右端點的詢問，限制$[l,r]$相當于是只能統計左端點在$l$后面的連續段。

然后我們考慮維護$c_l$表示當前右端點為$r$（枚舉的右端點），左端點為$l$的連續段個數，然后詢問就是一段區間和。這個直接在線段樹上打$tag$，表示這個區間的最小值為$0$的點都有多少次新增的貢獻即可維護。

實現時注意下傳$tag$的標記即可。
時間復雜度$O(mlgn)$。

Code

#include <bits/stdc++.h>using namespace std;template<typename T> inline bool upmin(T &x, T y) { return y < x ? x = y, 1 : 0; } template<typename T> inline bool upmax(T &x, T y) { return x < y ? x = y, 1 : 0; }#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondtypedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int, int> PR; typedef vector<int> VI; const lod eps = 1e-9; const lod pi = acos(-1); const int oo = 1 << 30; const ll loo = 1ll << 62; const int mods = 1e9 + 7; const int MAXN = 300005; const int INF = 0x3f3f3f3f; //1061109567 /*--------------------------------------------------------------------*/namespace FastIO{constexpr int SIZE = (1 << 21) + 1;int num = 0, f;char ibuf[SIZE], obuf[SIZE], que[65], *iS, *iT, *oS = obuf, *oT = obuf + SIZE - 1, c;#define gc() (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)), (iS == iT ? EOF : *iS ++)) : *iS ++)inline void flush() {fwrite(obuf, 1, oS - obuf, stdout);oS = obuf;}inline void putc(char c) {*oS ++ = c;if (oS == oT) flush();}inline void getc(char &c) {for (c = gc(); c < 'A' || c > 'Z' ; c = gc());}template<class I>inline void read(I &x) {for (f = 1, c = gc(); c < '0' || c > '9' ; c = gc()) if (c == '-') f = -1;for (x = 0; c >= '0' && c <= '9' ; c = gc()) x = (x << 3) + (x << 1) + (c & 15);x *= f;}template<class I>inline void print(I x) {if (x < 0) putc('-'), x = -x;if (!x) putc('0');while (x) que[++ num] = x % 10 + 48, x /= 10;while (num) putc(que[num --]);}struct Flusher_{~Flusher_(){flush();}} io_Flusher_; } using FastIO :: read; using FastIO :: print; using FastIO :: putc;ll Ans[MAXN], c[MAXN << 2], tagc[MAXN << 2]; int MX = 0, tag[MAXN << 2], mn[MAXN << 2], s[MAXN << 2], stkmx[MAXN], stkmn[MAXN], p[MAXN]; void up(int x) {mn[x] = min(mn[x << 1], mn[x << 1 | 1]);s[x] = (mn[x << 1] == mn[x]) * s[x << 1] + (mn[x << 1 | 1] == mn[x]) * s[x << 1 | 1]; } void down(int x) {if (tag[x] != 0) {mn[x << 1] += tag[x], mn[x << 1 | 1] += tag[x]; tag[x << 1] += tag[x], tag[x << 1 | 1] += tag[x];tag[x] = 0;}if (tagc[x] != 0) {if (mn[x << 1] == mn[x]) c[x << 1] += tagc[x] * s[x << 1], tagc[x << 1] += tagc[x];if (mn[x << 1 | 1] == mn[x]) c[x << 1 | 1] += tagc[x] * s[x << 1 | 1], tagc[x << 1 | 1] += tagc[x];tagc[x] = 0;} } void build(int x, int l, int r) {if (l == r) { mn[x] = r - l + 1, s[x] = 1; return; }int mid = (l + r) >> 1;build(x << 1, l, mid);build(x << 1 | 1, mid + 1, r);up(x); } void update(int x, int l, int r, int L, int R, int y) {if (l >= L && r <= R) { mn[x] += y, tag[x] += y; return; }down(x);int mid = (l + r) >> 1;if (R <= mid) update(x << 1, l, mid, L, R, y);else if (L > mid) update(x << 1 | 1, mid + 1, r, L, R, y);else update(x << 1, l, mid, L, mid, y), update(x << 1 | 1, mid + 1, r, mid + 1, R, y);up(x); } ll query(int x, int l, int r, int L, int R) {if (l >= L && r <= R) return c[x];down(x);int mid = (l + r) >> 1;if (R <= mid) return query(x << 1, l, mid, L, R);else if (L > mid) return query(x << 1 | 1, mid + 1, r, L, R);else return query(x << 1, l, mid, L, mid) + query(x << 1 | 1, mid + 1, r, mid + 1, R); } struct Qnode{ int l, r, id; } Q[MAXN]; signed main() { #ifndef ONLINE_JUDGEfreopen("a.in", "r", stdin); #endifint n, m; read(n);for (int i = 1; i <= n ; ++ i) read(p[i]);read(m);for (int i = 1; i <= m ; ++ i) read(Q[i].l), read(Q[i].r), Q[i].id = i;sort(Q + 1, Q + m + 1, [&](Qnode x, Qnode y){ return x.r < y.r; });build(1, 1, n); for (int i = 1, topmx = 0, topmn = 0, nw = 1; i <= n ; ++ i) {while (topmx && p[stkmx[topmx]] < p[i]) update(1, 1, n, stkmx[topmx - 1] + 1, stkmx[topmx], -p[stkmx[topmx]]), -- topmx;while (topmn && p[stkmn[topmn]] > p[i]) update(1, 1, n, stkmn[topmn - 1] + 1, stkmn[topmn], p[stkmn[topmn]]), -- topmn;update(1, 1, n, 1, i, -1);update(1, 1, n, stkmx[topmx] + 1, i, p[i]);update(1, 1, n, stkmn[topmn] + 1, i, -p[i]);stkmx[++ topmx] = i;stkmn[++ topmn] = i;down(1), ++ tagc[1], c[1] += s[1];while (nw <= m && Q[nw].r == i) Ans[Q[nw].id] = query(1, 1, n, Q[nw].l, i), ++ nw;}for (int i = 1; i <= m ; ++ i) print(Ans[i]), putc('\n');return 0; }

總結

以上是生活随笔為你收集整理的CF997E. Good Subsegments(线段树，单调栈)的全部內容，希望文章能夠幫你解決所遇到的問題。

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