http://acm.hdu.edu.cn/showproblem.php?pid=4747

題意：

我們定義mex(l,r)表示一個序列a[l]....a[r]中沒有出現過得最小的非負整數， 然后我們給出一個長度為n的序列，求他所有的連續的子序列的mex(l,r)的和。

思路：

首先因為n的最大值就是2*10^5 所有我們字需要考慮200000之內的數就好了，然后O(2*n)可以求出（1,1）,(1,2), (1,3),(1,4) ... (1,n)來 mex是不減的。

然后我們考慮將第一個數拿走我們就能夠得到（2,2）,(2,3) ......（2，n） , 如何求他們？下邊給出圖解：

下邊是粘貼別人的，感覺有個例子很好理解。

例： ? ? ? ??? 1， 6，0，2，3，1，4，3

初始mex 0，?0，2，3，4，4，5，5 ? ? ???mex[1,r]

刪除1后 ? 0， ?0，1，1，1，4，5，5 ? ? ??? mex[2,r]

……

當刪除第一個1后，紅色的mex不變！，紫色的mex值變為1，橙色的mex值不變，刪除點的mex置0

因此，用線段樹維護一個單調不遞增隊列，每次求和。查找位置時用二分。線段樹延時標記即可。

?

ps：我這里二筆了一下，題意一下大家，lazy一定要出事化為-1，因為這里面有置0的操作。我因此wa好多次。。

#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <cstring> #include <algorithm> #include <string> #include <set> #include <functional> #include <numeric> #include <sstream> #include <stack> #include <map> #include <queue>#define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define ll __int64 #define L(x) (x) << 1 #define R(x) (x) << 1 | 1 #define MID(l, r) (l + r) >> 1 #define Min(x, y) (x) < (y) ? (x) : (y) #define Max(x, y) (x) < (y) ? (y) : (x) #define E(x) (1 << (x)) #define iabs(x) (x) < 0 ? -(x) : (x) #define OUT(x) printf("%I64d\n", x) #define keyTree (chd[chd[root][1]][0]) #define Read() freopen("din.txt", "r", stdin) #define Write() freopen("dout.txt", "w", stdout);#define M 100007 #define N 200017using namespace std;int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1};const int inf = 0x7f7f7f7f; const int mod = 1000000007;const double eps = 1e-8;int mex[N],a[N],next[N]; int vis[N]; ll val[4*N], lz[4*N]; int n;void pushup(int rt) {val[rt] = val[rt<<1] + val[rt<<1|1]; } void pushdown(int rt,int m) {if (lz[rt] != -1){lz[rt<<1] = lz[rt<<1|1] = lz[rt];val[rt<<1] = lz[rt] * (m - (m>>1));val[rt<<1|1] = lz[rt] * (m>>1);lz[rt] = -1;} } void build(int l, int r, int rt) {lz[rt] = -1;val[rt] = 0;if (l == r){val[rt] = mex[l];return ;}int m = (l + r) >> 1;build(lc); build(rc);pushup(rt); } void update(int L, int R, ll sc, int l, int r, int rt) {if (l >= L && r <= R){lz[rt] = sc;val[rt] = sc*(r - l + 1);return ;}pushdown(rt,r - l + 1);int m = (l + r) >> 1;if (L <= m) update(L,R,sc,lc);if (R > m) update(L,R,sc,rc);pushup(rt); } ll query(int pos, int l,int r, int rt) {if (l == r) return val[rt];int m = (l + r) >> 1;pushdown(rt, r - l + 1);if (pos <= m) return query(pos,lc);else return query(pos,rc); } int BSR(int l, int r, int v) {int ans = -1;while (l <= r){int mid = (l + r) >> 1;if (query(mid,1,n,1) > v){ans = mid;r = mid - 1;} else l = mid + 1;}return ans; } int main() {while (~scanf("%d",&n)){if (!n) break;CL(vis,0); CL(next,0);for (int i = 1; i <= n; ++i){scanf("%d",&a[i]);a[i] = min(a[i],200001);if (vis[a[i]]) next[vis[a[i]]] = i;vis[a[i]] = i;}for (int i = 1; i <= n; ++i) if (!next[i]) next[i] = n + 1;CL(vis,0); int last = 0;for (int i = 1; i <= n; ++i){vis[a[i]] = 1;while (true){if (!vis[last]){mex[i] = last;break;}last++;}}build(1,n,1); ll ans = 0;for (int i = 1; i <= n; ++i){ans += val[1];if (i == n) continue;int l = i + 1;int r = next[i] - 1;int pos = BSR(l,r,a[i]);if (pos != -1) update(pos, r, a[i], 1, n, 1);update(i, i, 0, 1, n, 1);}printf("%I64d\n",ans);}return 0; }

　　

?

?

轉載于:https://www.cnblogs.com/E-star/p/3348552.html

總結

以上是生活随笔為你收集整理的hdu 4747 mex 线段树+思维的全部內容，希望文章能夠幫你解決所遇到的問題。

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