\u3002\u3002\u3002\u7ed9\u5b9a\u4e00\u4e2a\u957f\u5ea6\u4e3a n \u7684\u975e\u8d1f\u6570\u5217\u3002\u3002\u5b9a\u4e49 mex(l, r) \u4e3a l\uff0cr \u533a\u95f4\u91cc\u6700\u5c0f\u7684\u6ca1\u6709\u51fa\u73b0\u7684\u6570\u5b57\u3002
\n\u3002\u3002\u6c42\u6240\u6709 mex(l, r) \u7684\u548c\u3002\u3002\u3002
\n<\/p>\n
..\u3002\u76f4\u63a5\u5408\u5e76\u533a\u95f4\u96be\u4ee5\u8fdb\u884c\u65f6\u3002\u3002\u5229\u7528\u79bb\u7ebf\u5148\u56fa\u5b9a\u4e00\u4e2a\u7aef\u70b9\u3002\u3002\u6cbf\u7740\u53e6\u4e00\u4e2a\u7aef\u70b9\u626b\u5e94\u8be5\u662f\u63a5\u4e0b\u6765\u7b2c\u4e00\u4e2a\u8981\u60f3\u7684\u65b9\u6cd5\u4e86\u3002\u3002\u3002
\n\u3002\u8279\u3002\u3002\u6211\u662f\u50bb\u903c\u4e48\u3002\u3002<\/p>\n
\u3002\u3002\u5148 O(n) \u641e\u51fa mex1[i] \u8868\u793a\u521d\u59cb\u7684 mex(1, i)\u3002\u3002\u8fd9\u4e2a\u662f\u5355\u8c03\u9012\u589e\u7684\u3002\u3002\u3002
\n\u3002\u3002\u3002\u518d O(n) \u641e\u51fa\u6bcf\u4e2a nxt[i] \u3002\u3002\u8868\u793a\u53f3\u8fb9\u7b2c\u4e00\u4e2a\u548c i \u76f8\u540c\u7684\u4f4d\u7f6e\u3002\u3002\uff08\u5982\u679c\u6ca1\u6709\u5219\u7b49\u4e8e n+1\u3002\u3002\u3002\u3002
\n\u3002\u3002\u3002\u63a5\u7740\u6cbf\u7740\u5de6\u4fa7\u5f00\u59cb\u5220\u9664\u3002\u3002\u5220\u9664\u524d\u8981\u7edf\u8ba1\u51fa\u4ee5\u8fd9\u4e2a\u70b9\u4e3a\u5de6\u7aef\u70b9\u7684\u6240\u6709 mex\u3002 \u3002\u3002
\n\u3002\u3002\u3002\u8003\u8651\u5220\u9664 a[i]\u3002\u3002\u90a3\u4e48\u5c06 i+1 \u5230 nxt[i]-1 \u4e4b\u95f4\u3002\u3002mex \u5927\u4e8e a[i] \u7684\u5168\u8bbe\u7f6e\u6210 a[i]\u3002\u5373\u53ef\u3002\u3002\u3002<\/p>\n
\u3002\u3002\u3002\u4e8e\u662f\u6211\u4eec\u9700\u8981\u7ef4\u62a4\u3002\u3002\u3002\u533a\u95f4\u6c42\u548c\u3002\u3002\u3002\u4ee5\u53ca\u533a\u95f4\u8d4b\u503c\u6210\u81f3\u591a a[i]\u3002\u3002\u3002\u8fd9\u662f\u4e00\u4e2a\u7ebf\u6bb5\u6811\u7684 Open Problem \u3002\u3002\u3002\uff08\u81f3\u5c11\u5bf9\u6211\u800c\u8a00\u3002\uff1f\u3002\u3002
\n\u3002\u3002\u3002\u8fdb\u4e00\u6b65\u5206\u6790\u53d1\u73b0 mex \u59cb\u7ec8\u662f\u5355\u8c03\u9012\u589e\u7684\u3002\u3002
\n\u3002\u3002\u3002\u56e0\u6b64\u5c06 i+1 \u5230 nxt[i]-1 \u8d4b\u503c\u5230\u81f3\u591a a[i]\u3002\u3002\u5c31\u662f\u5c06\u7b2c\u4e00\u4e2a\u5927\u4e8e a[i] \u7684\u4f4d\u7f6e \u5230 nxt[i] -1 \u8d4b\u503c\u5230 a[i] \u5373\u53ef\u3002\u3002\u800c\u8fd9\u662f\u4e00\u4e2a\u7ebf\u6bb5\u6811\u5165\u95e8\u7ea7\u522b\u7684\u64cd\u4f5c\u3002\u3002\u3002<\/p>\n
\r\nconst int N = 200009, NN = 4*N;\r\nint A[N], C[N], nxt[N], mex1[N];\r\nint n;\r\n\r\nLL ss[NN]; int mx[NN]; bool dd[NN]; int a, b, c;\r\n\r\n#define root 1, 1, n\r\n#define lx (x << 1)\r\n#define rx (lx | 1)\r\n#define ml (l + r >> 1)\r\n#define mr (ml + 1)\r\n#define len (r - l + 1)\r\n#define xc x, l, r\r\n#define lc lx, l, ml\r\n#define rc rx, mr, r\r\n\r\ninline void Apply_Cov(int x, int l, int r, int val){\r\n mx[x] = val, ss[x] = (LL) len * val, dd[x] = 1;\r\n}\r\n\r\nvoid Release(int x, int l, int r){\r\n if (dd[x]){\r\n Apply_Cov(lc, mx[x]), Apply_Cov(rc, mx[x]);\r\n dd[x] = 0;\r\n }\r\n}\r\n\r\nvoid Update(int x){\r\n mx[x] = max(mx[lx], mx[rx]);\r\n ss[x] = ss[lx] + ss[rx];\r\n}\r\n\r\nvoid Insert(int x, int l, int r){\r\n if (b < l || r < a) return;\r\n if (a <= l && r <= b){\r\n Apply_Cov(xc, c);\r\n }\r\n else{\r\n Release(xc);\r\n Insert(lc), Insert(rc);\r\n Update(x);\r\n }\r\n}\r\n\r\nint Upper_Bound(int x, int l, int r){\r\n if (l == r) return l;\r\n else{\r\n Release(xc);\r\n return mx[lx] > c ? Upper_Bound(lc) : Upper_Bound(rc);\r\n }\r\n}\r\n\r\nvoid Build(int x, int l, int r){\r\n dd[x] = 0; if (l == r) mx[x] = ss[x] = mex1[l];\r\n else Build(lc), Build(rc), Update(x);\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n while (RD(n)){\r\n\r\n REP_1_C(i, n) checkMin(RD(A[i]), 200001);\r\n\r\n int mex = 0; RST(C); REP_1(i, n){\r\n ++C[A[i]]; while (C[mex]) ++mex;\r\n mex1[i] = mex;\r\n }\r\n\r\n fill(C, C+N, n+1); DWN_1(i, n, 1){\r\n nxt[i] = C[A[i]];\r\n C[A[i]] = i;\r\n }\r\n\r\n LL res = 0; Build(root); REP_1(i, n){\r\n res += ss[1]; if (mx[1] > A[i]){\r\n c = A[i], a = Upper_Bound(root), b = nxt[i]-1; if (a <= b) Insert(root);\r\n }\r\n a = i, b = i, c = 0, Insert(root);\r\n if (!mx[1]) break;\r\n }\r\n\r\n OT(res);\r\n }\r\n}\r\n<\/pre>\nExternal link:<\/h3>\n