Advertisement
konchin_shih

very good debug

Jun 29th, 2022
638
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 6.17 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<stdbool.h>
  4. #include<string.h>
  5. #define N 10
  6. #define INF 1000000
  7. int cmp (const void* a, const void* b) {return *(int*)a - *(int*)b;}
  8. int min(const int a, const int b) {return a < b ? a : b;}
  9. void swap(int* a, int* b) {static int t; t = *a, *a = *b, *b = t;}
  10. typedef struct node {
  11.     struct node* next;
  12.     bool isrev; int sz, data[N + 1], srt[N + 1];
  13. } node;
  14. typedef node* nptr;
  15. static inline void extract(nptr cur) {
  16.     if (!cur->isrev) return;
  17.     for (int l = 0, r = cur->sz - 1; l < r; l++, r--)
  18.         swap(&cur->data[l], &cur->data[r]);
  19.     cur->isrev = false;
  20. }
  21. static inline void print1(char c[], nptr cur) {
  22.     if (!cur) return;
  23.     printf("%s", c);
  24.     extract(cur), printf("[");
  25.     for (int i = 0; i < cur->sz; i++) {
  26.         printf("%d", cur->data[i]);
  27.         if (i != cur->sz - 1) printf(" ");
  28.     } printf("]\n");
  29. }
  30. static inline void print(nptr cur) {
  31.     while (cur) {
  32.         extract(cur), printf("[");
  33.         for (int i = 0; i < cur->sz; i++) {
  34.             printf("%d", cur->data[i]);
  35.             if (i != cur->sz - 1) printf(" ");
  36.         }
  37.         cur = cur->next, printf("] ");
  38.     }
  39.     printf("\n");
  40. }
  41. static inline void update(nptr cur) {
  42.     memcpy(cur->srt, cur->data, cur->sz * sizeof(int));
  43.     qsort(cur->srt, cur->sz, sizeof(int), cmp);
  44. }
  45. static inline nptr newnode(int arr[], int ql, int qr) {
  46.     nptr ret = (nptr)malloc(sizeof(node));
  47.     ret->sz = qr - ql, ret->next = NULL, ret->isrev = false;
  48.     memcpy(ret->data, &arr[ql], ret->sz * sizeof(int));
  49.     update(ret); return ret;
  50. }
  51. static inline void merge(nptr a, nptr b) {
  52.     if (a->sz >= N / 2 || b->sz >= N / 2) {a->next = b; return;}
  53.     extract(a), extract(b);
  54.     memcpy(&a->data[a->sz], b->data, b->sz * sizeof(int));
  55.     static int tmp[N + 1];
  56.     memcpy(tmp, a->srt, a->sz * sizeof(int));
  57.     int aptr = 0, bptr = 0, ptr = 0;
  58.     while (aptr < a->sz && bptr < b->sz)
  59.         if (tmp[aptr] < b->srt[bptr])
  60.             a->srt[ptr++] = tmp[aptr++];
  61.         else
  62.             a->srt[ptr++] = b->srt[bptr++];
  63.     while (aptr < a->sz)
  64.         a->srt[ptr++] = tmp[aptr++];
  65.     while (bptr < b->sz)
  66.         a->srt[ptr++] = b->srt[bptr++];
  67.     a->next = b->next, a->sz += b->sz;
  68.     free(b);
  69. }
  70. static inline nptr split(nptr cur, int qi) {
  71.     nptr ret = (nptr)malloc(sizeof(node));
  72.     ret->next = cur->next, cur->next = ret;
  73.     ret->sz = cur->sz - qi, cur->sz = qi, ret->isrev = false;
  74.     extract(cur);
  75.     memcpy(ret->data, &cur->data[qi], ret->sz * sizeof(int));
  76.     update(cur), update(ret);
  77.     return ret;
  78. }
  79. static inline nptr build(int arr[], int n) {
  80.     nptr ret = newnode(arr, 0, min(n, N)), cur = ret;
  81.     for (int i = 1; i < (n + N - 1) / N; i++)
  82.         cur->next = newnode(arr, i * N, min(n, (i + 1) * N)), cur = cur->next;
  83.     return ret;
  84. }
  85. static inline void insert(nptr root, int qi, int qval) {
  86.     int previ = 0; nptr prevp = NULL, cur = root;
  87.     while (cur && previ + cur->sz <= qi)
  88.         previ += cur->sz, prevp = cur, cur = cur->next;
  89.     if (!cur) {
  90.         cur = (nptr)malloc(sizeof(node));
  91.         cur->next = NULL, cur->sz = 1, cur->isrev = false;
  92.         cur->data[0] = cur->srt[0] = qval;
  93.     } else {
  94.         extract(cur);
  95.         nptr nxt = split(cur, qi - previ);
  96.         if (cur->sz == N)
  97.             nxt->sz++, nxt->data[0] = nxt->srt[0] = qval;
  98.         else {
  99.             cur->data[cur->sz] = cur->srt[cur->sz] = qval;
  100.             for (int i = cur->sz; i > 0 && cur->srt[i] < cur->srt[i - 1]; i--)
  101.                 swap(&cur->srt[i], &cur->srt[i - 1]);
  102.             cur->sz++;
  103.         }
  104.         merge(cur, nxt);
  105.     }
  106.     if (prevp) merge(prevp, cur);
  107.     else *root = *cur;
  108. }
  109. static inline void erase(nptr root, int qi) {
  110.     int previ = 0; nptr cur = root, prevp = NULL;
  111.     while (cur->next && previ + cur->sz < qi)
  112.         previ += cur->sz, prevp = cur, cur = cur->next;
  113.     extract(cur);
  114.     for (int i = qi - previ; i + 1 < cur->sz; i++)
  115.         swap(&cur->data[i], &cur->data[i + 1]);
  116.     cur->sz--; int p = 0;
  117.     while (cur->srt[p] < cur->data[cur->sz]) p++;
  118.     for (int i = p; i < cur->sz; i++)
  119.         swap(&cur->srt[i], &cur->srt[i + 1]);
  120.     if (prevp) merge(prevp, cur);
  121.     else *root = *cur;
  122. }
  123. static inline void reverse(nptr root, int ql, int qr) {
  124.     int previ = 0, bufsz = 0; nptr cur = root, prevp = NULL;
  125.     static nptr buf[1000];
  126.     while (cur && previ + cur->sz < ql)
  127.         previ += cur->sz, prevp = cur, cur = cur->next;
  128.     nptr lptr = cur; cur = split(lptr, ql - previ);
  129.     previ += lptr->sz;
  130.     while (cur && previ + cur->sz <= qr)
  131.         buf[bufsz++] = cur, previ += cur->sz, cur = cur->next;
  132.     nptr rptr = split(cur, qr - previ);
  133.     buf[bufsz++] = cur;
  134.     for (int i = bufsz - 1; i > 0; i--)
  135.         buf[i]->next = buf[i - 1], buf[i]->isrev ^= 1;
  136.     buf[0]->isrev ^= 1, merge(buf[0], rptr);
  137.     merge(lptr, buf[bufsz - 1]);
  138.     if (prevp) merge(prevp, lptr);
  139.     else *root = *lptr;
  140. }
  141. static inline int bscount(nptr cur, int qval) {
  142.     int lb = 0, len = cur->sz;
  143.     while (len > 0) {
  144.         int mid = lb + (len >> 1);
  145.         if (cur->srt[mid] < qval)
  146.             lb = mid + 1, len -= (len >> 1) + 1;
  147.         else len >>= 1;
  148.     }
  149.     return lb;
  150. }
  151. static inline int count(nptr cur, int ql, int qr, int qval) {
  152.     int ret = 0, previ = 0;
  153.     while (cur && previ + cur->sz <= ql)
  154.         previ += cur->sz, cur = cur->next;
  155.     if (!cur) return ret;
  156.     extract(cur);
  157.     for (int i = ql - previ; i < min(qr - previ, cur->sz); i++)
  158.         ret += (cur->data[i] < qval);
  159.     previ += cur->sz, cur = cur->next;
  160.     if (qr <= previ) return ret;
  161.     while (cur && previ + cur->sz < qr)
  162.         ret += bscount(cur, qval), previ += cur->sz, cur = cur->next;
  163.     if (qr <= previ) return ret;
  164.     extract(cur);
  165.     for (int i = 0; i < qr - previ; i++)
  166.         ret += (cur->data[i] < qval);
  167.     return ret;
  168. }
  169. static inline int query(nptr root, int ql, int qr, int qval) {
  170.     int lb = -1e5, len = 2e5 + 5;
  171.     while (len > 0) {
  172.         int mid = lb + (len >> 1);
  173.         if (count(root, ql, qr, mid) <= qval - 1)
  174.             lb = mid + 1, len -= (len >> 1) + 1;
  175.         else len >>= 1;
  176.     }
  177.     return lb - 1;
  178. }
  179. int main() {
  180.     int n, q, arr[50005];
  181.     scanf(" %d %d", &n, &q);
  182.     for (int i = 0; i < n; i++)
  183.         scanf(" %d", &arr[i]);
  184.     nptr root = build(arr, n);
  185.     char op[10]; int x, i, l, r, k;
  186.     while (q--) {
  187.         scanf(" %s", op);
  188.         switch (op[0]) {
  189.         case '$':
  190.             print(root); break;
  191.         case 'I':
  192.             scanf(" %d %d", &i, &x);
  193.             insert(root, i - 1, x); break;
  194.         case 'D':
  195.             scanf(" %d", &i);
  196.             erase(root, i - 1); break;
  197.         case 'R':
  198.             scanf(" %d %d", &l, &r);
  199.             reverse(root, l - 1, r); break;
  200.         case 'Q':
  201.             scanf(" %d %d %d", &l, &r, &k);
  202.             printf("%d\n", query(root, l - 1, r, k));
  203.         }
  204.     }
  205.     return 0;
  206. }
  207.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement