fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const string bases = "AGTC";
  5. const int Maxb = 4;
  6. const int Maxn = 70005;
  7.  
  8. struct item {
  9. 	int prior, myval, val[Maxb], cnt;
  10. 	int l, r;
  11. 	item(int myval = 0): prior(rand()), cnt(1), myval(myval), l(0), r(0) {
  12. 	    fill(val, val + Maxb, 0);
  13. 	    val[myval]++;
  14.     }
  15. };
  16.  
  17. char tmp[Maxn];
  18. int tlen;
  19. vector <item> T;
  20. int n;
  21. int my[Maxn];
  22. int q;
  23. int A[Maxb], B[Maxb];
  24.  
  25. void createNew(int val = 0) { T.push_back(item(val)); }
  26.  
  27. int getLst() { return int(T.size()) - 1; }
  28.  
  29. int cnt (int it) {
  30. 	return it ? T[it].cnt: 0;
  31. }
  32.  
  33. void upd_cnt (int it) {
  34. 	if (it) {
  35. 		T[it].cnt = cnt(T[it].l) + cnt(T[it].r) + 1;
  36. 		for (int i = 0; i < Maxb; i++)
  37.             T[it].val[i] = (T[it].l? T[T[it].l].val[i]: 0) +
  38.                            (T[it].r? T[T[it].r].val[i]: 0);
  39.         T[it].val[T[it].myval]++;
  40. 	}
  41. }
  42.  
  43. void merge (int &t, int l, int r) {
  44.   if (!l && !r) { t = 0; return; }
  45.   if (!l || !r) t = l? l: r;
  46.   else {
  47.     createNew(); t = getLst();
  48.     item *ptr = &T[t];
  49.     if (T[l].prior > T[r].prior) {
  50.       T[t] = T[l];
  51.       merge (T[t].r, T[l].r, r);
  52.     } else {
  53.       T[t] = T[r];
  54.       merge (T[t].l, l, T[r].l);
  55.     }
  56.     if (&T[t] != ptr)
  57.     	printf("I was %p but now am %p\n", ptr, &T[t]);
  58.   }
  59.   upd_cnt (t);
  60. }
  61.  
  62. void split (int t, int &l, int &r, int key, int add = 0) {
  63. 	if (!t)
  64. 		return void( l = r = 0 );
  65. 	int cur_key = add + cnt(T[t].l);
  66. 	createNew(); int tmp = getLst();
  67. 	T[tmp] = T[t];
  68. 	if (key <= cur_key)
  69. 		split (T[t].l, l, T[tmp].l, key, add),  r = tmp;
  70. 	else
  71. 		split (T[t].r, T[tmp].r, r, key, add + 1 + cnt(T[t].l)),  l = tmp;
  72. 	upd_cnt (tmp);
  73. }
  74.  
  75. void Modify(int &t, int old, int ind, int nval)
  76. {
  77.     createNew(); t = getLst();
  78.     T[t] = T[old];
  79.     int bef = cnt(T[old].l);
  80.     if (ind < bef) Modify(T[t].l, T[old].l, ind, nval);
  81.     else if (ind == bef) T[t].myval = nval;
  82.     else Modify(T[t].r, T[old].r, ind - bef - 1, nval);
  83.     upd_cnt(t);
  84. }
  85.  
  86. void Count(int t, int hm, int res[])
  87. {
  88.     if (!t) return;
  89.     int bef = cnt(T[t].l);
  90.     if (hm < bef) { Count(T[t].l, hm, res); return; }
  91.     if (T[t].l)
  92.         for (int i = 0; i < Maxb; i++)
  93.             res[i] += T[T[t].l].val[i];
  94.     hm -= bef;
  95.     if (hm < 1) return;
  96.     res[T[t].myval]++;
  97.     hm--;
  98.     Count(T[t].r, hm, res);
  99. }
  100.  
  101. int main()
  102. {
  103.     srand(time(0));
  104.     createNew(); // dummy
  105.     scanf("%d", &n);
  106.     for (int i = 1; i <= n; i++) {
  107.         scanf("%s", tmp); tlen = strlen(tmp);
  108.         for (int j = 0; j < tlen; j++) {
  109.             createNew(bases.find(tmp[j])); int add = getLst();
  110.             merge(my[i], my[i], add);
  111.         }
  112.     }
  113.     scanf("%d", &q);
  114.     while (q--) {
  115.         scanf("%s", tmp);
  116.         if (tmp[1] == 'R') {  // Cross
  117.             int id1, id2, k1, k2; scanf("%d %d %d %d", &id1, &id2, &k1, &k2);
  118.             int A, B; split(my[id1], A, B, k1);
  119.             int C, D; split(my[id2], C, D, k2);
  120.             merge(my[++n], A, D);
  121.             merge(my[++n], C, B);
  122.         } else if (tmp[1] == 'U') {  // Mutate
  123.             int id, k; char m; scanf("%d %d %c", &id, &k, &m);
  124.             Modify(my[id], my[id], k - 1, bases.find(m));
  125.         } else if (tmp[1] == 'O') {  // Count
  126.             int id, k1, k2; scanf("%d %d %d", &id, &k1, &k2);
  127.             fill(A, A + Maxb, 0); fill(B, B + Maxb, 0);
  128.             Count(my[id], k2, B); Count(my[id], k1 - 1, A);
  129.             for (int i = 0; i < Maxb; i++)
  130.                 printf("%d%c", B[i] - A[i], i + 1 < Maxb? ' ': '\n');
  131.         }
  132.     }
  133.     return 0;
  134. }
Success #stdin #stdout 0s 15576KB
comments (?)
stdin
copy 
2
CTCGC
TGCGG
5
MUTATE 1 2 A
COUNT 2 2 4
MUTATE 2 1 G
CROSS 2 1 1 5
COUNT 4 3 6
stdout
copy 
0 2 0 1
I was 0x55b5c222b52c but now am 0x55b5c222c9cc
I was 0x55b5c222b508 but now am 0x55b5c222c9a8
0 1 0 3
https://ideone.com/WN2kDR
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!