本文共 5264 字，大约阅读时间需要 17 分钟。
离散化+伸展树。
1 /* 3436 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set 25 #define stpii set > 26 #define mpii map 27 #define vi vector 28 #define pii pair 29 #define vpii vector > 30 #define rep(i, a, n) for (int i=a;i =a;--i) 32 #define clr clear 33 #define pb push_back 34 #define mp make_pair 35 #define fir first 36 #define sec second 37 #define all(x) (x).begin(),(x).end() 38 #define SZ(x) ((int)(x).size()) 39 #define lson l, mid, rt<<1 40 #define rson mid+1, r, rt<<1|1 41 #define grandlson ch[ch[root][1]][0] 42 43 typedef struct { 44 char c; 45 int x; 46 } Cmd; 47 48 const int maxq = 1e5+5; 49 const int maxn = 3e5+5; 50 int pre[maxn], ch[maxn][2], s[maxn], key[maxn], pos[maxn]; 51 int arr[maxn], cnt[maxn]; 52 int b[maxn], e[maxn]; 53 int tot, root, n, m; 54 Cmd cmd[maxq]; 55 56 int search(int x) { 57 int l = 0, r = m - 1, mid; 58 int ret = -1; 59 60 while (l <= r) { 61 mid = (l + r) >> 1; 62 if (b[mid]<=x && x<=e[mid]) 63 return mid; 64 if (e[mid] < x) { 65 l = mid + 1; 66 } else { 67 r = mid - 1; 68 } 69 } 70 71 return ret; 72 } 73 74 void newNode(int& r, int k, int fa) { 75 r = tot++; 76 pre[r] = fa; 77 ch[r][0] = ch[r][1] = 0; 78 key[r] = k; 79 pos[k] = r; 80 s[r] = cnt[r] = e[k] - b[k] + 1; 81 } 82 83 void PushUp(int r) { 84 s[r] = s[ch[r][0]] + s[ch[r][1]] + cnt[r]; 85 } 86 87 void Build(int& rt, int l, int r, int fa) { 88 if (l > r) return; 89 90 int mid = (l + r) >>1; 91 92 newNode(rt, mid, fa); 93 Build(ch[rt][0], l, mid-1, rt); 94 Build(ch[rt][1], mid+1, r, rt); 95 PushUp(rt); 96 } 97 98 void Rotate(int x, int d) { 99 int y = pre[x];100 ch[y][d^1] = ch[x][d];101 pre[ch[x][d]] = y;102 if (pre[y])103 ch[pre[y]][ch[pre[y]][1]==y] = x;104 pre[x] = pre[y];105 ch[x][d] = y;106 pre[y] = x;107 PushUp(y);108 }109 110 void Splay(int r, int goal) {111 while (pre[r] != goal) {112 if (pre[pre[r]] == goal) {113 Rotate(r, ch[pre[r]][0]==r);114 } else {115 int y = pre[r];116 int d = (ch[pre[y]][0] == y);117 if (ch[y][d] == r) {118 Rotate(r, d^1);119 Rotate(r, d);120 } else {121 Rotate(y, d);122 Rotate(r, d);123 }124 }125 }126 PushUp(r);127 if (goal == 0)128 root = r;129 }130 131 void Insert(int& r, int k, int fa) {132 if (r == 0) {133 newNode(r, k, fa);134 return ;135 }136 Insert(ch[r][0], k, r);137 PushUp(r);138 }139 140 int getMin(int r) {141 while (ch[r][0]) {142 r = ch[r][0];143 }144 return r;145 }146 147 int kth(int r, int k) {148 int sz = s[ch[r][0]];149 150 if (k <= sz)151 return kth(ch[r][0], k);152 else if (k <= sz+cnt[r])153 return b[key[r]] + k - sz - 1;154 else155 return kth(ch[r][1], k-sz-cnt[r]);156 }157 158 int Rank(int x) {159 return kth(root, x);160 }161 162 int Query(int x) {163 int k = search(x);164 int p = pos[k];165 166 Splay(p, 0);167 return s[ch[root][0]] + 1;168 }169 170 void Delete() {171 int k = getMin(ch[root][1]);172 173 Splay(k, root);174 ch[ch[root][1]][0] = ch[root][0];175 root = ch[root][1];176 pre[ch[root][0]] = root;177 pre[root] = 0;178 PushUp(root);179 }180 181 void top(int x) {182 int k = search(x);183 int p = pos[k];184 185 Splay(p, 0);186 if (ch[root][0]==0 || ch[root][1]==0) {187 root = ch[root][0] + ch[root][1];188 pre[root] = 0;189 } else {190 Delete();191 }192 Insert(root, k, 0);193 Splay(pos[k], 0);194 }195 196 void inorder(int rt) {197 if (rt == 0) return ;198 199 inorder(ch[rt][0]);200 printf("rt = %2d: lson = %2d, rson = %2d, fa = %2d, size = %2d, key = %2d, num = %2d \n",201 rt, ch[rt][0], ch[rt][1], pre[rt], s[rt], key[rt], cnt[rt]);202 inorder(ch[rt][1]);203 }204 205 void init() {206 root = tot = 0;207 ch[root][0] = ch[root][1] = s[root] = pre[root] = cnt[root] = key[root] = 0;208 tot = 1;209 Build(root, 0, m-1, 0);210 #ifndef ONLINE_JUDGE211 // inorder(root);212 #endif213 }214 215 int main() {216 ios::sync_with_stdio(false);217 #ifndef ONLINE_JUDGE218 freopen("data.in", "r", stdin);219 freopen("data.out", "w", stdout);220 #endif221 222 int t, q;223 int l, x;224 int ans;225 char event[10];226 227 scanf("%d", &t);228 rep(tt, 1, t+1) {229 printf("Case %d:\n", tt);230 scanf("%d %d", &n, &q);231 l = 0;232 arr[l++] = 0;233 rep(i, 0, q) {234 scanf("%s %d", event, &cmd[i].x);235 if (event[0] != 'R')236 arr[l++] = cmd[i].x;237 cmd[i].c = event[0];238 }239 arr[l++] = n;240 sort(arr, arr+l);241 242 m = 0;243 rep(i, 1, l) {244 if (arr[i] != arr[i-1]) {245 if (arr[i]-arr[i-1] > 1) {246 b[m] = arr[i-1] + 1;247 e[m] = arr[i] - 1;248 ++m;249 }250 b[m] = e[m] = arr[i];251 ++m;252 }253 }254 255 init();256 rep(i, 0, q) {257 if (cmd[i].c == 'T') {258 top(cmd[i].x);259 } else if (cmd[i].c == 'Q') {260 ans = Query(cmd[i].x);261 printf("%d\n", ans);262 } else {263 ans = Rank(cmd[i].x);264 printf("%d\n", ans);265 }266 #ifndef ONLINE_JUDGE267 printf("iteration [%d]:\n", i);268 inorder(root);269 #endif270 }271 }272 273 #ifndef ONLINE_JUDGE274 printf("time = %d.\n", (int)clock());275 #endif276 277 return 0;278 }
转载于:https://www.cnblogs.com/bombe1013/p/4908635.html