Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const long long N = 2 * 1e5 + 1;
  7. const long long MAXX = 1e18 + 1;
  8.  
  9. long long a[N];
  10.  
  11. long long x = 1;
  12. long long n;
  13.  
  14. struct node
  15. {
  16.     bool c = false;
  17.     long long data;
  18.     long long l, r;
  19.     long long add;
  20.     long long sett;
  21.     node()
  22.     {
  23.         add = l = r = 0;
  24.         data = MAXX;
  25.         sett = MAXX;
  26.         c = false;
  27.     }
  28. };
  29.  
  30. vector <node> t;
  31.  
  32. void print()
  33. {
  34.     for (long long i = 0; i < t.size(); ++i)
  35.     {
  36.         cout << t[i].c << " " << t[i].data << " " << t[i].l << " " << t[i].r << '\n';
  37.     }
  38. }
  39.  
  40. void push(long long v)
  41. {
  42.     if ((t[v].l != t[v].r) && t[2 * v + 2].c)
  43.     {
  44.         if (t[v].sett != MAXX)
  45.         {
  46.             t[2 * v + 2].sett = t[v].sett;
  47.             t[2 * v + 2].data = t[v].sett;
  48.             t[2 * v + 2].add = 0;
  49.         }
  50.         if (t[v].add != 0)
  51.         {
  52.             if (t[2 * v + 2].sett != MAXX)
  53.             {
  54.                 t[2 * v + 2].sett += t[v].add;
  55.             }
  56.             else
  57.             {
  58.                 t[2 * v + 2].add += t[v].add;
  59.             }
  60.             t[2 * v + 2].data += t[v].add;
  61.         }
  62.     }
  63.     if ((t[v].l != t[v].r) && t[2 * v + 1].c)
  64.     {
  65.         if (t[v].sett != MAXX)
  66.         {
  67.             t[2 * v + 1].sett = t[v].sett;
  68.             t[2 * v + 1].data = t[v].sett;
  69.             t[2 * v + 1].add = 0;
  70.         }
  71.         if (t[v].add != 0)
  72.         {
  73.             if (t[2 * v + 1].sett < MAXX)
  74.             {
  75.                 t[2 * v + 1].sett += t[v].add;
  76.             }
  77.             else
  78.             {
  79.                 t[2 * v + 1].add += t[v].add;
  80.             }
  81.             t[2 * v + 1].data += t[v].add;
  82.         }
  83.     }
  84.     t[v].sett = MAXX;
  85.     t[v].add = 0;
  86. }
  87.  
  88. long long query(long long v, long long a, long long b)
  89. {
  90.     push(v);
  91.     if ((t[v].r < a) || (t[v].l > b))
  92.     {
  93.         return MAXX;
  94.     }
  95.     if ((t[v].l >= a) && (t[v].r <= b))
  96.     {
  97.         return t[v].data;
  98.     }
  99.     long long ans = min(query(2 * v + 1, a, b), query(2 * v + 2, a, b));
  100.     t[v].data = min(t[2 * v + 1].data, t[2 * v + 2].data);
  101.     return ans;
  102. }
  103.  
  104. void update_add(long long v, long long a, long long b, long long val)
  105. {
  106.     push(v);
  107.     if ((t[v].r < a) || (t[v].l > b))
  108.     {
  109.         return;
  110.     }
  111.     if ((t[v].l >= a) && (t[v].r <= b))
  112.     {
  113.         if (t[v].sett != MAXX)
  114.         {
  115.             t[v].sett += val;
  116.         }
  117.         else
  118.         {
  119.             t[v].add += val;
  120.         }
  121.         t[v].data += val;
  122.         push(v);
  123.         return;
  124.     }
  125.     //push(v);
  126.     update_add(2 * v + 1, a, b, val);
  127.     update_add(2 * v + 2, a, b, val);
  128.     t[v].data = min(t[2 * v + 1].data, t[2 * v + 2].data);
  129. }
  130.  
  131. void update_sett(long long v, long long a, long long b, long long val)
  132. {
  133.     push(v);
  134.     if ((t[v].r < a) || (t[v].l > b))
  135.     {
  136.         return;
  137.     }
  138.     push(v);
  139.     if ((t[v].l >= a) && (t[v].r <= b))
  140.     {
  141.         t[v].sett = val;
  142.         t[v].data = t[v].sett;
  143.         t[v].add = 0;
  144.         push(v);
  145.         return;
  146.     }
  147.     //push(v);
  148.     update_sett(2 * v + 1, a, b, val);
  149.     update_sett(2 * v + 2, a, b, val);
  150.     t[v].data = min(t[2 * v + 1].data, t[2 * v + 2].data);
  151. }
  152.  
  153. void build(long long v, long long l, long long r)
  154. {
  155.     t[v].add = 0;
  156.     t[v].sett = MAXX;
  157.     t[v].l = l;
  158.     t[v].r = r;
  159.     t[v].c = true;
  160.     if (l == r)
  161.     {
  162.         t[v].data = a[l];
  163.     }
  164.     else
  165.     {
  166.         long long m = (l + r) / 2;
  167.         build(2 * v + 1, l, m);
  168.         build(2 * v + 2, m + 1, r);
  169.         t[v].data = min(t[2 * v + 1].data, t[2 * v + 2].data);
  170.     }
  171. }
  172.  
  173. int main()
  174. {
  175.     freopen("rmq2.in", "r", stdin);
  176.     freopen("rmq2.out", "w", stdout);
  177.     ios_base::sync_with_stdio(false);
  178.     cin.tie(nullptr);
  179.     cin >> n;
  180.     for (int i = 0; i < n; ++i) {
  181.         cin >> a[i];
  182.     }
  183.     t.resize(static_cast<unsigned long>(4 * n));
  184.     build(0, 0, n - 1);
  185.     string s;
  186.     //print();
  187.     //cout << '\n';
  188.     while (cin >> s)
  189.     {
  190.         if (s == "min")
  191.         {
  192.             long long tl, tr;
  193.             cin >> tl >> tr;
  194.             --tl;
  195.             --tr;
  196.             cout << query(0, tl, tr) << '\n';
  197.         }
  198.         else if (s == "add")
  199.         {
  200.             long long tl, tr, val;
  201.             cin >> tl >> tr >> val;
  202.             --tl;
  203.             --tr;
  204.             update_add(0, tl, tr, val);
  205.         }
  206.         else if (s == "set")
  207.         {
  208.             long long tl, tr, val;
  209.             cin >> tl >> tr >> val;
  210.             --tl;
  211.             --tr;
  212.             update_sett(0, tl, tr, val);
  213.         }
  214.     }
  215.     return 0;
  216. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement