太神辣 treap的随机键值竟然能派上用场。。
要用不旋转的treap来进行维护区间信息
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<iostream> 6 7 using namespace std; 8 9 template<typename Q> Q &read(Q &x) { 10 static char c, f; 11 for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1; 12 for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0'; 13 if(f) x = -x; return x; 14 } 15 template<typename Q> Q read() { 16 static Q x; read(x); return x; 17 } 18 19 typedef long long LL; 20 const int N = 40000 + 10; 21 22 LL S(LL x) { 23 return x * (x + 1) >> 1; 24 } 25 26 struct Node *null, *pis; 27 struct Node { 28 int sz, h, tag; 29 LL ans; 30 Node *ch[2]; 31 32 Node() {} 33 Node(int h) : h(h) { 34 sz = 1, ans = tag = 0; 35 ch[0] = ch[1] = null; 36 } 37 38 void add(int d) { 39 if(this == null) return; 40 h += d, tag += d; 41 } 42 43 void maintain() { 44 sz = ch[0]->sz + ch[1]->sz + 1; 45 ans = 0; 46 for(int c = 0; c < 2; c++) { 47 ans += ch[c]->ans + S(ch[c]->sz) * (ch[c]->h - h); 48 } 49 } 50 51 void down() { 52 ch[0]->add(tag); 53 ch[1]->add(tag); 54 tag = 0; 55 } 56 57 void *operator new(size_t) { 58 return pis++; 59 } 60 }pool[N]; 61 62 Node *merge(Node *l, Node *r) { 63 if(l == null) return r; 64 if(r == null) return l; 65 if(l->h < r->h) { 66 l->down(); 67 l->ch[1] = merge(l->ch[1], r); 68 return l->maintain(), l; 69 }else { 70 r->down(); 71 r->ch[0] = merge(l, r->ch[0]); 72 return r->maintain(), r; 73 } 74 } 75 76 typedef pair<Node *, Node *> pnn; 77 pnn split(Node *o, int k) { 78 if(o == null) return pnn(null, null); 79 pnn res; o->down(); 80 if(o->ch[0]->sz >= k) { 81 res = split(o->ch[0], k); 82 o->ch[0] = res.second; 83 res.second = o; 84 }else { 85 res = split(o->ch[1], k - o->ch[0]->sz - 1); 86 o->ch[1] = res.first; 87 res.first = o; 88 } 89 return o->maintain(), res; 90 } 91 92 pair<int, int> p[100000 + 10]; 93 94 int main() { 95 #ifdef DEBUG 96 freopen("in.txt", "r", stdin); 97 freopen("out.txt", "w", stdout); 98 #endif 99 100 int r, c, n; 101 scanf("%d%d%d", &r, &c, &n); 102 for(int i = 0; i < n; i++) { 103 scanf("%d%d", &p[i].first, &p[i].second); 104 } 105 sort(p, p + n); 106 107 pis = pool, null = new Node(0); 108 null->sz = 0; 109 Node *root = null; 110 for(int i = 1; i <= c; i++) { 111 root = merge(root, new Node(0)); 112 } 113 114 LL ans = S(r) * S(c); 115 for(int i = 1, j = 0; i <= r; i++) { 116 root->add(1); 117 while(j < n && p[j].first == i) { 118 int x = p[j++].second; 119 pnn r1 = split(root, x - 1); 120 pnn r2 = split(r1.second, 1); 121 r2.first->h = 0; 122 root = merge(merge(r1.first, r2.first), r2.second); 123 } 124 ans -= root->ans + S(root->sz) * root->h; 125 } 126 cout << ans << endl; 127 128 return 0; 129 }
谁说一定要用fhq treap？
用普通的treap就好了 而且常数小！
注意建树最好$O(n)$建一下，每次insert有可能退化成$O(n^2)$的。
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<iostream> 6 7 using namespace std; 8 9 template<typename Q> Q &read(Q &x) { 10 static char c, f; 11 for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1; 12 for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0'; 13 if(f) x = -x; return x; 14 } 15 template<typename Q> Q read() { 16 static Q x; read(x); return x; 17 } 18 19 typedef long long LL; 20 const int N = 40000 + 10; 21 22 LL S(LL x) { 23 return x * (x + 1) >> 1; 24 } 25 26 struct Node *null, *pis, *bin[N]; 27 int top; 28 struct Node { 29 int sz, v, h, tag; 30 LL ans; 31 Node *ch[2]; 32 33 Node() {} 34 Node(int v, int h) : v(v), h(h) { 35 sz = 1, ans = tag = 0; 36 ch[0] = ch[1] = null; 37 } 38 39 void add(int d) { 40 if(this == null) return; 41 h += d, tag += d; 42 } 43 44 void maintain() { 45 sz = ch[0]->sz + ch[1]->sz + 1; 46 ans = 0; 47 for(int c = 0; c < 2; c++) { 48 ans += ch[c]->ans + S(ch[c]->sz) * (ch[c]->h - h); 49 } 50 } 51 52 void down() { 53 ch[0]->add(tag); 54 ch[1]->add(tag); 55 tag = 0; 56 } 57 58 void *operator new(size_t) { 59 return top ? bin[--top] : pis++; 60 } 61 62 void operator delete(void *p) { 63 bin[top++] = (Node *) p; 64 } 65 66 int cmp(int x) const { 67 if(x == v) return -1; 68 return x < v ? 0 : 1; 69 } 70 }pool[N]; 71 72 void rotate(Node *&o, int d) { 73 Node *t = o->ch[d]; 74 o->ch[d] = t->ch[d ^ 1]; 75 t->ch[d ^ 1] = o; 76 o->maintain(); 77 (o = t)->maintain(); 78 } 79 80 void modify(Node *&o, int x, int w) { 81 o->down(); 82 int d = o->cmp(x); 83 if(d == -1) return o->h = w, o->maintain(), void(); 84 modify(o->ch[d], x, w); 85 if(o->ch[d]->h < o->h) rotate(o, d); 86 else o->maintain(); 87 } 88 89 pair<int, int> p[100000 + 10]; 90 91 void build(Node *&o, int l, int r) { 92 if(l > r) return; 93 int mid = (l + r) >> 1; 94 o = new Node(mid, 0); 95 build(o->ch[0], l, mid - 1); 96 build(o->ch[1], mid + 1, r); 97 o->maintain(); 98 } 99 100 int main() { 101 #ifdef DEBUG 102 freopen("in.txt", "r", stdin); 103 freopen("out.txt", "w", stdout); 104 #endif 105 106 int r, c, n; 107 scanf("%d%d%d", &r, &c, &n); 108 for(int i = 0; i < n; i++) { 109 read(p[i].first), read(p[i].second); 110 } 111 sort(p, p + n); 112 113 pis = pool, null = new Node(0, 0); 114 null->sz = 0; 115 Node *root; 116 build(root, 1, c); 117 118 LL ans = S(r) * S(c); 119 for(int i = 1, j = 0; i <= r; i++) { 120 root->add(1); 121 while(j < n && p[j].first == i) { 122 modify(root, p[j++].second, 0); 123 } 124 ans -= root->ans + S(root->sz) * root->h; 125 } 126 cout << ans << endl; 127 128 return 0; 129 }