其实8.4是在昨天，只不过昨天我电脑出了点问题，输入法死活调不出来。
主要做了2件事，一是刷KD—tree的板子题，二是自己YY一个替罪羊树的板子
KD-tree：由于只刷了板子题，还没什么想法
替罪羊：其实还是有点子思维量的，思想很简单，但实现要仔细斟酌，替罪羊树最核心的
就是它的重构函数，选择适当的时间及适当的范围进行重构，从而使得子树保持平衡，便于操作
其实感觉数组版应该比较好打，然而旁边几个人一直劝我打指针，我又不会什么骚操作，
然后就莫名奇妙加了好多行判空;
1 #include <bits/stdc++.h> 2 #define N 1000006 3 #define A 0.75 4 #define puts puts 5 using namespace std; 6 struct sheep { 7 int val, fsz, tsz, cnt; 8 sheep *ch[2], *fa; 9 } * rt; 10 int tot, alr; 11 sheep *re[N]; 12 bool pingheng(sheep *g) { 13 return (g->ch[0] ? g->ch[0]->fsz : 0) <= g->fsz * A || (g->ch[1] ? g->ch[1]->fsz : 0) <= g->fsz * A; 14 } 15 void update(sheep *p) { 16 p->fsz = p->tsz = p->cnt; 17 if (p->ch[0] != NULL) 18 p->fsz += p->ch[0]->fsz, p->tsz += p->ch[0]->tsz; 19 if (p->ch[1] != NULL) 20 p->fsz += p->ch[1]->fsz, p->tsz += p->ch[1]->tsz; 21 } 22 void getup(sheep *g) { 23 if (g->ch[0] != NULL) 24 getup(g->ch[0]); 25 if (g->cnt) 26 re[++alr] = g; 27 if (g->ch[1] != NULL) 28 getup(g->ch[1]); 29 } 30 sheep *build(int l, int r, sheep *f) { 31 const int mid = l + r >> 1; 32 if (l != mid) 33 re[mid]->ch[0] = build(l, mid - 1, re[mid]); 34 else 35 re[mid]->ch[0] = NULL; 36 if (r != mid) 37 re[mid]->ch[1] = build(mid + 1, r, re[mid]); 38 else 39 re[mid]->ch[1] = NULL; 40 update(re[mid]); 41 re[mid]->fa = f; 42 return re[mid]; 43 } 44 sheep *rebuild(sheep *g, sheep *f) { 45 alr = 0; 46 getup(g); 47 return build(1, alr, f); 48 } 49 void insert2(int x, sheep *g) { 50 // puts("boom at insert2"); 51 ++g->fsz; 52 ++g->tsz; 53 if (g->val < x) { 54 if (g->ch[1] == NULL) { 55 g->ch[1] = new sheep(); 56 g->ch[1]->fa = g; 57 g->ch[1]->val = x, g->ch[1]->fsz = g->ch[1]->tsz = g->ch[1]->cnt = 1; 58 return; 59 } 60 insert2(x, g->ch[1]); 61 } else if (g->val == x) { 62 ++g->cnt; 63 } else { 64 if (g->ch[0] == NULL) { 65 g->ch[0] = new sheep(); 66 g->ch[0]->fa = g; 67 g->ch[0]->val = x, g->ch[0]->fsz = g->ch[0]->tsz = g->ch[0]->cnt = 1; 68 return; 69 } 70 insert2(x, g->ch[0]); 71 } 72 73 if (g == rt) { 74 if (!pingheng(g)) { 75 sheep *f = new sheep(); 76 rt = rebuild(g, f); 77 rt->fa = NULL; 78 } 79 return; 80 } 81 if (!pingheng(g) && pingheng(g->fa)) { 82 sheep *f = g->fa; 83 if (f->ch[0] == g) 84 f->ch[0] = rebuild(g, f); 85 else 86 f->ch[1] = rebuild(g, f); 87 } 88 update(g); 89 } 90 void insert(int p) { 91 if (rt == NULL) { 92 rt = new sheep(), rt->val = p, rt->fsz = rt->tsz = rt->cnt = 1; 93 return; 94 } 95 insert2(p, rt); 96 } 97 sheep *getval(int rk) { 98 int ans = 0; 99 sheep *g = rt; 100 while (1) { 101 if (g->cnt && rk >= (g->ch[0] == NULL ? 0 : g->ch[0]->tsz) + 1 && 102 rk <= (g->ch[0] == NULL ? 0 : g->ch[0]->tsz) + g->cnt) 103 return g; 104 if (rk > (g->ch[0] ? g->ch[0]->tsz : 0) + g->cnt) { 105 rk -= (g->ch[0] ? g->ch[0]->tsz : 0) + g->cnt; 106 g = g->ch[1]; 107 } else 108 g = g->ch[0]; 109 } 110 } 111 int getrank(int x) { 112 int ans = 0; 113 sheep *g = rt; 114 while (1) { 115 if (g->cnt && x == g->val) 116 return ans + (g->ch[0] ? g->ch[0]->tsz : 0) + 1; 117 if (x > g->val) { 118 ans += (g->ch[0] ? g->ch[0]->tsz : 0) + g->cnt; 119 g = g->ch[1]; 120 } else 121 g = g->ch[0]; 122 } 123 } 124 sheep *getzz(int x) { 125 int ans = 0; 126 sheep *g = rt; 127 while (1) { 128 if (g->cnt && x == g->val) 129 return g; 130 if (x > g->val) 131 g = g->ch[1]; 132 else 133 g = g->ch[0]; 134 } 135 } 136 void del(sheep *p) { 137 --p->tsz; 138 --p->cnt; 139 while (p != rt) { 140 p = p->fa; 141 update(p); 142 } 143 } 144 int main() { 145 int n, x, p; 146 scanf("%d", &n); 147 while (n--) { 148 scanf("%d%d", &p, &x); 149 switch (p) { 150 case 1: { 151 insert(x); 152 break; 153 } 154 case 2: { 155 del(getzz(x)); 156 break; 157 } 158 case 3: { 159 insert(x); 160 printf("%d ", getrank(x)); 161 del(getzz(x)); 162 break; 163 } 164 case 4: { 165 printf("%d ", getval(x)->val); 166 break; 167 } 168 case 5: { 169 insert(x); 170 printf("%d ", getval(getrank(x) - 1)->val); 171 del(getzz(x)); 172 break; 173 } 174 case 6: { 175 insert(x); 176 printf("%d ", getval(getrank(x) + getzz(x)->cnt)->val); 177 del(getzz(x)); 178 break; 179 } 180 } 181 } 182 }
自己的板子，有错误还请各位dalao指正;
现在距NOIP还有94天，今天上午模拟赛后就要分机房了，我刚好在一机房和二机房的分界线出
现在慌的一批，成败在此一举，我更应调整心态，积极面对，留在第一机房是我的实力，不能留
也是一种经历。