fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. #define all(x) begin(x),end(x)
  4. template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
  5. template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
  6. #define debug(a) cerr << "(" << #a << ": " << a << ")\n";
  7. typedef long long ll;
  8. typedef vector<int> vi;
  9. typedef vector<vi> vvi;
  10. typedef pair<int,int> pi;
  11. const int mxN = 6e6+1, mxM = 1.1e5+10, oo = 1e9;
  12. // mxN is maximum number of persistent treap nodes
  13. const ll MOD = 1e9+7;
  14. struct Node;
  15. int size(Node* a);
  16.  
  17. struct Node{
  18.     // Persistent (functional) treap node, doesn't get changed after creation
  19.     array<Node*,2> kids = {};
  20.     int sz,data;
  21.     Node(int _data) {
  22.         data=_data;
  23.         sz = 1;
  24.     }
  25.     Node() {}
  26.     int kth(int k, bool reverse) {
  27.         int toleft = size(kids[reverse]);
  28.         if(toleft==k) {
  29.             return data;
  30.         } else if(toleft>k) {
  31.             return kids[reverse]->kth(k,reverse);
  32.         } else {
  33.             return kids[!reverse]->kth(k-toleft-1, reverse);
  34.         }
  35.     }
  36.     void recalc() {
  37.         sz=1+size(kids[0])+size(kids[1]);
  38.     }
  39.     void print() {
  40.         if(kids[0]) kids[0]->print();
  41.         // cout << data << ' ';
  42.         if(kids[1]) kids[1]->print();
  43.     }
  44. };
  45. int size(Node* a) {
  46.     if(!a) return 0;
  47.     return a->sz;
  48. }
  49.  
  50. Node nodes[mxN]; int p=0;
  51. Node* newnode(Node* c) {
  52.     assert(p<mxN);
  53.     auto& n = nodes[p++];
  54.     n.data = c->data;
  55.     n.sz = c->sz;
  56.     n.kids = c->kids;
  57.     return &n;
  58. }
  59. Node* newnode(int val) {
  60.     assert(p<mxN);
  61.     auto& n = nodes[p++];
  62.     n = Node(val);
  63.     return &n;
  64. }
  65.  
  66. array<Node*,2> split(Node* c, int lastinleft) {
  67.     // functional treap split
  68.     // doesn't change nodes and makes new nodes when it's needed
  69.     if(size(c->kids[0])>=lastinleft) {
  70.         if(c->kids[0]==NULL) {
  71.             return {NULL,c};
  72.         }
  73.         auto cc = newnode(c);
  74.         auto ans = split(c->kids[0],lastinleft);
  75.         cc->kids[0]=ans[1];
  76.         cc->recalc();
  77.         return {ans[0],cc};
  78.     } else {
  79.         if(c->kids[1]==NULL) {
  80.             return {c,NULL};
  81.         }
  82.         lastinleft-=size(c->kids[0])+1;
  83.         auto ans = split(c->kids[1], lastinleft);
  84.         auto cc = newnode(c);
  85.         cc->kids[1]=ans[0];
  86.         cc->recalc();
  87.         return {cc,ans[1]};
  88.     }
  89. }
  90. bool isroot(int a, int b) {
  91.     return (ll)rand() * (a + b) < (ll)a * RAND_MAX;
  92. }
  93. Node* merge(Node* a, Node* b) {
  94.     // functional treap merge, returns root of newly created tree
  95.     if(a==NULL) return b;
  96.     if(b==NULL) return a;
  97.     if(isroot(size(a), size(b))) {
  98.         auto aa = newnode(a);
  99.         aa->kids[1] = merge(a->kids[1],b);
  100.         aa->recalc();
  101.         return aa;
  102.     } else {
  103.         auto bb = newnode(b);
  104.         bb->kids[0] = merge(a,b->kids[0]);
  105.         bb->recalc();
  106.         return bb;
  107.     }
  108. }
  109.  
  110. struct listroot {
  111.     Node* left=NULL, *right=NULL;
  112.     // left and right persistent treaps that contain the head and tail part of this list
  113.     ll sum=0; // sum of current list
  114.     bool onetreap=true; 
  115.     // if list size is less than 2*mxM, the entire list is stored in one treap
  116.     listroot() {}
  117.     listroot(int val) {
  118.         left = newnode(val);
  119.         sum = val;
  120.     }
  121. };
  122. listroot roots[int(4e5+60)] = {}; int rp=0;
  123.  
  124. void head(int i) {
  125.     auto& c = roots[i];
  126.     auto tup = split(c.left,1);
  127.     int val = tup[0]->data;
  128.     roots[rp++] = listroot(val);
  129.     auto& nxt = roots[rp++] = c;
  130.     nxt.left = tup[1];
  131.     nxt.sum = (MOD+c.sum-val);
  132.     while(nxt.sum>=MOD) nxt.sum-=MOD;
  133. }
  134. void tail(int i) {
  135.     auto& c = roots[i];
  136.     auto& nxt = roots[rp++] = c;
  137.     array<Node*,2> tup;
  138.     if(c.onetreap) {
  139.         tup = split(c.left, size(c.left)-1);
  140.         nxt.left = tup[0];
  141.     } else {
  142.         tup = split(c.right, size(c.right)-1);
  143.         nxt.right = tup[0];
  144.     }
  145.  
  146.     int val = tup[1]->data;
  147.     nxt.sum = (MOD+c.sum-val);
  148.     while(nxt.sum>=MOD) nxt.sum-=MOD;
  149.  
  150.     roots[rp++] = listroot(val);
  151. }
  152. void mergelist(int i, int j) {
  153.     auto& l = roots[i], &r = roots[j];
  154.     auto& nxt = roots[rp++];
  155.     nxt.sum = l.sum+r.sum;
  156.     while(nxt.sum>=MOD) nxt.sum-=MOD;
  157.     nxt.onetreap = l.onetreap and r.onetreap;
  158.     if(!l.onetreap) nxt.left = l.left;
  159.     if(!r.onetreap) nxt.right = r.right;
  160.  
  161.     if(l.onetreap and r.onetreap) {
  162.         // l and r only store one treap each
  163.         // merge their treaps
  164.         nxt.left = merge(l.left, r.left);
  165.         if(size(nxt.left)>=2*mxM) {
  166.             // if nxt's treap can be split into two treaps of size mxM, do this
  167.             nxt.onetreap= false;
  168.             auto tup = split(nxt.left, mxM);
  169.             nxt.left = tup[0];
  170.             nxt.right = split(tup[1], size(tup[1])-mxM)[1];
  171.         }
  172.     } else if(l.onetreap) {
  173.         nxt.left = split(merge(l.left, r.left), mxM)[0];
  174.     } else if(r.onetreap) {
  175.         nxt.right = merge(l.right, r.left);
  176.         nxt.right = split(nxt.right, size(nxt.right)-mxM)[1];
  177.     }
  178. }
  179.  
  180. int main() {
  181.     ios_base::sync_with_stdio(false);
  182.     cin.tie(NULL);
  183.     int n; cin >> n;
  184.     for(int i=0;i<n;++i) {
  185.         int cur; cin >> cur;
  186.         roots[rp++] = listroot(cur);
  187.     }
  188.     int m; cin >> m;
  189.     for(int ops=0;ops<m;++ops) {
  190.         string op; cin >> op;
  191.         if(op == "merge") {
  192.             int i,j; cin >> i >> j;
  193.             --i,--j;
  194.             mergelist(i,j);
  195.         } else {
  196.             int i; cin >> i; --i;
  197.             if(op=="head") head(i);
  198.             else tail(i);
  199.             cout << roots[rp-2].sum << '\n';
  200.         }
  201.         cout << roots[rp-1].sum << '\n';
  202.     }
  203. }
Success #stdin #stdout 0.02s 156716KB
comments (?)
stdin
copy 
4
1 2 3 4
7
merge 1 2
merge 3 4
merge 6 5
head 7
tail 9
merge 2 3
merge 1 1
stdout
copy 
3
7
10
3
7
5
2
5
2
https://ideone.com/GVwY1W
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

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!