题意：
给定一个长度为 n 的非负数列，定义 mex(l, r) 为 l，r 区间里最小的没有出现的数字。
求所有 mex(l, r) 的和
分析参见
我的代码：
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <vector> 5 typedef long long ll; 6 #define lson l, mid, rt << 1 7 #define rson mid + 1, r, rt << 1 |1 8 9 struct node { 10 int mx, mi, setv; 11 ll sum; 12 }; 13 14 const int N = 200000 + 10; 15 int ar[N]; 16 node seg[N << 2]; 17 18 bool vis[N]; 19 int idx; 20 21 void Up(node& fa, node& ls, node& rs) { 22 fa.mx = std::max(ls.mx , rs.mx); 23 fa.sum = ls.sum + rs.sum; 24 fa.mi = std::min(ls.mi, rs.mi); 25 } 26 void build( int l, int r, int rt) { 27 seg[rt].setv = - 1; 28 if (l == r) { 29 vis[ar[l]] = true; 30 while (vis[idx]) 31 ++idx; 32 seg[rt].mx = seg[rt].mi = seg[rt].sum = idx; 33 } else { 34 int mid = (l + r) >> 1; 35 build(lson); 36 build(rson); 37 Up(seg[rt], seg[rt << 1], seg[rt << 1 | 1]); 38 } 39 } 40 void Down(node& fa, node& ls, node& rs, int len) { 41 if (~fa.setv) { 42 ls.setv = rs.setv = ls.mx = rs.mx = ls.mi = rs.mi = fa.setv; 43 ls.sum = (ll)(len - (len >> 1)) * fa.setv; 44 rs.sum = (ll)(len >> 1) * fa.setv; 45 fa.setv = - 1; 46 } 47 } 48 ll query( int L, int R, int l, int r, int rt) { 49 if (L == l && R == r) 50 return seg[rt].sum; 51 Down(seg[rt], seg[rt << 1], seg[rt << 1 | 1], r - l + 1); 52 int mid = (l + r) >> 1; 53 if (R <= mid) return query(L, R, lson); 54 else if (L > mid) return query(L, R, rson); 55 else return query(L, mid, lson) + query(mid + 1, R, rson); 56 } 57 void update( int L, int R, int v, int l, int r, int rt) { 58 if (seg[rt].mx <= v) return ; 59 int mid = (l + r) >> 1; 60 if (L == l && R == r) { 61 if (seg[rt].mi >= v) { 62 seg[rt].mi = seg[rt].mx = seg[rt].setv = v; 63 seg[rt].sum = (ll)(r - l + 1) * v; 64 return ; 65 } 66 if (l == r) { 67 if (seg[rt].mx > v) { 68 seg[rt].mi = seg[rt].mx = seg[rt].sum = v; 69 seg[rt].setv = - 1; 70 } 71 return ; 72 } 73 // 74 Down(seg[rt], seg[rt << 1], seg[rt << 1 | 1], r - l + 1); 75 if (R <= mid) update(L, R, v, lson); 76 else if (L > mid) update(L, R, v, rson); 77 else { 78 update(L, mid, v, lson); 79 update(mid + 1, R, v, rson); 80 } 81 Up(seg[rt], seg[rt << 1], seg[rt << 1 | 1]); 82 // 83 } else { 84 Down(seg[rt], seg[rt << 1], seg[rt << 1 | 1], r - l + 1); 85 if (R <= mid) update(L, R, v, lson); 86 else if (L > mid) update(L, R, v, rson); 87 else { 88 update(L, mid, v, lson); 89 update(mid + 1, R, v, rson); 90 } 91 Up(seg[rt], seg[rt << 1], seg[rt << 1 | 1]); 92 } 93 } 94 int n; 95 96 int nex[N], hap[N]; 97 98 void work() { 99 for ( int i = 1; i <= n; ++i) { 100 scanf( " %d ", &ar[i]); 101 if (ar[i] > n) 102 ar[i] = n + 1; 103 } 104 memset(vis, 0, sizeof(vis)); 105 idx = 0; 106 build( 1, n, 1); 107 ll ans = query( 1, n, 1, n, 1); 108 109 memset(hap, - 1, sizeof(hap)); 110 memset(nex, - 1, sizeof(nex)); 111 112 for ( int i = 1; i <= n; ++i) { 113 if (hap[ar[i]] == - 1) 114 hap[ar[i]] = i; 115 else { 116 nex[hap[ar[i]]] = i; 117 hap[ar[i]] = i; 118 } 119 } 120 121 int to; 122 for ( int i = 1; i <= n - 1; ++i) { 123 if (nex[i] == - 1) 124 to = n; 125 else 126 to = nex[i] - 1; 127 update(i, to, ar[i], 1, n, 1); 128 ans = ans + query(i, n, 1, n, 1); 129 } 130 printf( " %I64d\n ", ans); 131 } 132 int main() { 133 while ( 1 == scanf( " %d ", &n)) { 134 if ( 0 == n) break; 135 work(); 136 } 137 return 0; 138 }
CLJ有一个很诡异的map解法
1 #include <vector> 2 #include < string> 3 #include <iostream> 4 #include <algorithm> 5 #include <queue> 6 #include < set> 7 #include <map> 8 #include <sstream> 9 #include <iomanip> 10 #include <cstdio> 11 #include <cstdlib> 12 #include <cstring> 13 #include <cmath> 14 using namespace std; 15 typedef long long ll; 16 typedef double du; 17 #define pb push_back 18 #define mp make_pair 19 #define fi first 20 #define se second 21 #define FOR(i, s, t) for(i = (s); i < (t); i++) 22 #define RFOR(i, s, t) for(i = (s)-1; i >= (t); i--) 23 const int MAXN = 200004; 24 25 int a[MAXN]; 26 int nextSame[MAXN], next[MAXN]; 27 bool vis[MAXN]; 28 map< int, int> s; 29 30 int main() 31 { 32 #ifdef __FIO 33 freopen( " in.txt ", " r ", stdin); 34 // freopen("out.txt", "w", stdout); 35 #endif 36 int T; 37 // scanf("%d", &T); 38 while( 1){ 39 int n; 40 int i, j, k; 41 int si; 42 ll sum, tsum; 43 sum = tsum = 0; 44 scanf( " %d ", &n); 45 if(n == 0) 46 break; 47 for(i = 0; i < n; i++){ 48 scanf( " %d ", &a[i]); 49 if(a[i] > n) 50 a[i] = n+ 1; 51 } 52 for(i = 0; i <= n+ 1; i++) 53 next[i] = n; 54 for(i = n- 1; i >= 0; i--){ 55 nextSame[i] = next[a[i]]; 56 next[a[i]] = i; 57 } 58 memset(vis, 0, sizeof vis); 59 j = 0; 60 s.clear(); 61 for(i = 0; i < n; i++){ 62 vis[a[i]] = true; 63 while(vis[j]) 64 j++; 65 tsum += j; 66 s[i] = j; 67 } 68 s[n] = n; 69 sum += tsum; 70 for(i = 0; i < n- 1; i++){ 71 tsum -= s.begin()->se; 72 s[i] = - 1; 73 map< int, int>::iterator it = s.lower_bound(nextSame[i]- 1); 74 if(it->se > a[i]){ 75 if(it->fi >= nextSame[i]){ 76 int temp = it->se-a[i]; 77 tsum -= (ll)temp*(nextSame[i]- 1); 78 it--; 79 tsum += (ll)temp*it->fi; 80 } 81 while(it->se >= a[i]){ 82 int temp = it->se-a[i]; 83 tsum -= (ll)temp*it->fi; 84 s.erase(it--); 85 tsum += (ll)temp*it->fi; 86 } 87 s[nextSame[i]- 1] = a[i]; 88 } 89 s.erase(i); 90 sum += tsum; 91 } 92 printf( " %I64d\n ", sum); 93 } 94 return 0; 95 }