Advertisement
Guest User

Untitled

a guest
Dec 9th, 2019
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.21 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using ld = long double;
  5. const int N = 1e5 + 500;
  6. const int inf = INT_MAX;
  7. #define F first
  8. #define S second
  9. #define PB push_back
  10. #define sz(v) (int)v.size()
  11. #define all(v) v.begin(),v.end()
  12. #define endl '\n'
  13.  
  14. const int sz = 300;
  15.  
  16. struct block{
  17.     //int type;
  18.     int value_of_all = -1;
  19.     int add_to_all = 0;
  20.     int range_min = INT_MAX;
  21.     ll range_sum = 0;
  22. };
  23.  
  24. block ar[sz];
  25. int v[N];
  26.  
  27. int n;
  28.  
  29. void build(){
  30.     for(int i = 0;i < n;i++){
  31.         ar[i / sz].range_min = min(ar[i / sz].range_min,v[i]);
  32.         ar[i / sz].range_sum += v[i];
  33.     }
  34. }
  35.  
  36.  
  37.  
  38. int  get(int i){
  39.     return (ar[i / sz].value_of_all>-1?ar[i / sz].value_of_all:v[i] + ar[i / sz].add_to_all);
  40. }
  41.  
  42.  
  43.  
  44. void update(int l,int r,int x){ // [l,r)
  45.     int left = ((l / sz) + 1);  //next block of left element(l)
  46.     int right = (r / sz);       //block of right element(r)
  47.     ll sum = 0;
  48.     int mn = INT_MAX;
  49.  
  50.     if(left > right){ // l and r in the same block
  51.         for(int i=right * sz;i<l;i++){
  52.             v[i] = get(i);
  53.             sum += v[i];
  54.             mn = min(mn,v[i]);
  55.         }
  56.         for(;l<r;l++){
  57.             v[l] = x;
  58.             sum += v[l];
  59.             mn = min(mn,v[l]);
  60.         }
  61.         for(;r / sz<right + 1 && r<n;r++){
  62.             v[r] = get(r);
  63.             mn = min(mn,v[r]);
  64.             sum += v[r];
  65.         }
  66.         ar[right].value_of_all = -1;
  67.         ar[right].add_to_all = 0;
  68.         ar[right].range_min = mn;
  69.         ar[right].range_sum = sum;
  70.         return;
  71.     }
  72.  
  73.  
  74.     for(int i=(l / sz) * sz;i<l;i++){
  75.         v[i] = get(i);
  76.         mn = min(mn,v[i]);
  77.         sum += v[i];
  78.     }
  79.  
  80.  
  81.     for(;l / sz<left;l++){
  82.         v[l] = x;
  83.         mn = min(mn,v[l]);
  84.         sum += v[l];
  85.     }
  86.     ar[left-1].value_of_all = -1;
  87.     ar[left-1].add_to_all = 0;
  88.     ar[left-1].range_min = mn;
  89.     ar[left-1].range_sum = sum;
  90.  
  91.     sum = 0;
  92.     mn = INT_MAX;
  93.  
  94.     for(;left < right;left++){
  95.         ar[left].value_of_all = x;
  96.         ar[left].add_to_all = 0;
  97.         ar[left].range_min = x;
  98.         ar[left].range_sum = 1ll * x * sz;
  99.     }
  100.  
  101.  
  102.     for(int i = right * sz;i<r;i++){
  103.         v[i] = x;
  104.         mn = min(mn,v[i]);
  105.         sum += v[i];
  106.     }
  107.  
  108.     for(;r / sz<right + 1 && r<n;r++){
  109.         v[r] = get(r);
  110.         mn = min(mn,v[r]);
  111.         sum += v[r];
  112.     }
  113.  
  114.     ar[right].value_of_all = -1;
  115.     ar[right].add_to_all = 0;
  116.     ar[right].range_min = mn;
  117.     ar[right].range_sum = sum;
  118. }
  119.  
  120.  
  121.  
  122.  
  123. void add(int l,int r,int x){ // [l,r)
  124.     int left = ((l / sz) + 1);  //next block of left element(l)
  125.     int right = (r / sz);       //block of right element(r)
  126.     ll sum = 0;
  127.     int mn = INT_MAX;
  128.  
  129.     if(left > right){ // l and r in the same block
  130.         for(int i=right * sz;i<l;i++){
  131.             v[i] = get(i);
  132.             sum += v[i];
  133.             mn = min(mn,v[i]);
  134.         }
  135.         for(;l<r;l++){
  136.             v[l] = get(l) + x;
  137.             sum += v[l];
  138.             mn = min(mn,v[l]);
  139.         }
  140.         for(;r / sz<right + 1 && r<n;r++){
  141.             v[r] = get(r);
  142.             mn = min(mn,v[r]);
  143.             sum += v[r];
  144.         }
  145.         ar[right].value_of_all = -1;
  146.         ar[right].add_to_all = 0;
  147.         ar[right].range_min = mn;
  148.         ar[right].range_sum = sum;
  149.         return;
  150.     }
  151.  
  152.  
  153.     for(int i=(l / sz) * sz;i<l;i++){
  154.         v[i] = get(i);
  155.         mn = min(mn,v[i]);
  156.         sum += v[i];
  157.     }
  158.  
  159.  
  160.     for(;l / sz<left;l++){
  161.         v[l] = get(l) + x;
  162.         mn = min(mn,v[l]);
  163.         sum += v[l];
  164.     }
  165.     ar[left-1].value_of_all = -1;
  166.     ar[left-1].add_to_all = 0;
  167.     ar[left-1].range_min = mn;
  168.     ar[left-1].range_sum = sum;
  169.  
  170.     sum = 0;
  171.     mn = INT_MAX;
  172.  
  173.     for(;left < right;left++){
  174.         if(ar[left].value_of_all > -1){
  175.             ar[left].value_of_all += x;
  176.         }else ar[left].add_to_all += x;
  177.         ar[left].range_min += x;
  178.         ar[left].range_sum += 1ll * x * sz;
  179.     }
  180.  
  181.  
  182.     for(int i = right * sz;i<r;i++){
  183.         v[i] = get(i) + x;
  184.         mn = min(mn,v[i]);
  185.         sum += v[i];
  186.     }
  187.  
  188.     for(;r / sz<right + 1 && r<n;r++){
  189.         v[r] = get(r);
  190.         mn = min(mn,v[r]);
  191.         sum += v[r];
  192.     }
  193.  
  194.     ar[right].value_of_all = -1;
  195.     ar[right].add_to_all = 0;
  196.     ar[right].range_min = mn;
  197.     ar[right].range_sum = sum;
  198. }
  199.  
  200. ll rsq(int l,int r){
  201.     ll ans = 0;
  202.  
  203.     int left = ((l / sz) + 1);  //next block of left element(l)
  204.     int right = (r / sz);       //block of right element(r)
  205.  
  206.     if(left > right){ // l and r in the same block
  207.         for(int i=l;i<r;i++){
  208.             ans += get(i);
  209.         }
  210.         return ans;
  211.     }
  212.  
  213.     for(;l / sz<left;l++){
  214.         ans += get(l);
  215.     }
  216.  
  217.     for(;left < right;left++){
  218.         ans += ar[left].range_sum;
  219.     }
  220.  
  221.  
  222.     for(int i = right * sz;i<r;i++){
  223.         ans += get(i);
  224.     }
  225.  
  226.     return ans;
  227. }
  228.  
  229.  
  230.  
  231. int rmq(int l,int r){
  232.     int mn = INT_MAX;
  233.  
  234.     int left = ((l / sz) + 1);  //next block of left element(l)
  235.     int right = (r / sz);       //block of right element(r)
  236.  
  237.     if(left > right){ // l and r in the same block
  238.         for(int i=l;i<r;i++){
  239.             mn = min(mn,get(i));
  240.         }
  241.         return mn;
  242.     }
  243.  
  244.     for(;l / sz<left;l++){
  245.         mn = min(mn,get(l));
  246.     }
  247.  
  248.     for(;left < right;left++){
  249.         mn = min(mn,ar[left].range_min);
  250.     }
  251.  
  252.  
  253.     for(int i = right * sz;i<r;i++){
  254.         mn = min(mn,get(i));
  255.     }
  256.  
  257.     return mn;
  258. }
  259.  
  260.  
  261. int main()
  262. {
  263.     ios_base::sync_with_stdio(0); cin.tie(0);
  264.     cin>>n;
  265.     for(int i=0;i<n;i++) cin>>v[i];
  266.     build();
  267.     int m; cin>>m;
  268.     while(m--){
  269.         string type; cin>>type;
  270.         if(type == "get"){ //ready
  271.             int i; cin>>i;
  272.             cout<<get(--i)<<endl;
  273.  
  274.         }else if(type == "update"){ //ready
  275.             int l,r,x; cin>>l>>r>>x;
  276.             update(--l,r,x);
  277.         }else if(type == "add"){ //ready
  278.             int l,r,x; cin>>l>>r>>x;
  279.             add(--l,r,x);
  280.         }else if(type == "rsq"){ //ready
  281.             int l,r; cin>>l>>r;
  282.             cout<<rsq(--l,r)<<endl;
  283.         }else if(type == "rmq"){ //ready
  284.             int l,r; cin>>l>>r;
  285.             cout<<rmq(--l,r)<<endl;
  286.         }
  287.     }
  288.     return 0;
  289. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement