daily pastebin goal
61%
SHARE
TWEET

Untitled

a guest Dec 7th, 2017 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct Seg
  2. {
  3.     int l, r;
  4.  
  5.     Seg () {}
  6.    
  7.     Seg (int _l, int _r)
  8.     {
  9.         l = _l, r = _r;
  10.     }
  11. };
  12.  
  13. struct Decomposition
  14. {
  15.     int n;
  16.     vector < Seg > b;
  17.     vector < int > a;
  18.      
  19.     Decomposition () {}
  20.  
  21.     Decomposition (int _n, const vector < int > & _a)
  22.     {  
  23.         n = _n, a = _a;
  24.         b.push_back(Seg(1, n));
  25.     }
  26.     void rebuild()
  27.     {
  28.         vector < int >_a(1);
  29.         int cnt = 0;
  30.         for (auto &it : b)
  31.         {
  32.             for (int i = it.l; i <= it.r; i++)
  33.             {
  34.                 _a.push_back(a[i]);
  35.                 cnt++;
  36.             }
  37.         }
  38.         n = cnt;
  39.         a = _a;
  40.         b.clear();
  41.         b.push_back(Seg(1, n));
  42.         _a.clear();
  43.     }
  44.     void print()
  45.     {
  46.         for (auto &it : b)
  47.             cerr << it.l << ' ' << it.r << endl;
  48.         for (int i = 0; i < (int)a.size(); i++)
  49.             cerr << a[i] << ' ';
  50.         cerr << endl;
  51.     }
  52.     int split(int l)
  53.     {
  54.         int cnt = b[0].r - b[0].l + 1, pos = 0;
  55.         while(cnt < l)
  56.         {
  57.             pos++;
  58.             cnt += b[pos].r - b[pos].l + 1;                    
  59.         }
  60.         if (l != cnt)
  61.         {
  62.             int r = b[pos].r;
  63.             int len = b[pos].r - b[pos].l + 1 - cnt + l;
  64.             b[pos].r = b[pos].l + len - 1;
  65.             b.insert(b.begin() + pos + 1, Seg(b[pos].l + len, r));
  66.         }
  67.         return pos;
  68.     }
  69.     void add(int x, int y)
  70.     {
  71.         int pos = split(x);
  72.         a.push_back(y);
  73.         n++;
  74.         b.insert(b.begin() + pos + 1, Seg(n, n));
  75.  
  76.         if ((int)b.size() > MAGIC)
  77.             rebuild();
  78.     }
  79.     void del(int x)
  80.     {
  81.         split(x);
  82.         int pos = split(x - 1);
  83.         b.erase(b.begin() + pos + 1);
  84.         if ((int)b.size() > MAGIC) 
  85.             rebuild();
  86.     }
  87. };
RAW Paste Data
Top