Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- const int N = 1e5 + 500;
- const int inf = INT_MAX;
- #define F first
- #define S second
- #define PB push_back
- #define sz(v) (int)v.size()
- #define all(v) v.begin(),v.end()
- #define endl '\n'
- const int sz = 300;
- struct block{
- //int type;
- int value_of_all = -1;
- int add_to_all = 0;
- int range_min = INT_MAX;
- ll range_sum = 0;
- };
- block ar[sz];
- int v[N];
- int n;
- void build(){
- for(int i = 0;i < n;i++){
- ar[i / sz].range_min = min(ar[i / sz].range_min,v[i]);
- ar[i / sz].range_sum += v[i];
- }
- }
- int get(int i){
- return (ar[i / sz].value_of_all>-1?ar[i / sz].value_of_all:v[i] + ar[i / sz].add_to_all);
- }
- void update(int l,int r,int x){ // [l,r)
- int left = ((l / sz) + 1); //next block of left element(l)
- int right = (r / sz); //block of right element(r)
- ll sum = 0;
- int mn = INT_MAX;
- if(left > right){ // l and r in the same block
- for(int i=right * sz;i<l;i++){
- v[i] = get(i);
- sum += v[i];
- mn = min(mn,v[i]);
- }
- for(;l<r;l++){
- v[l] = x;
- sum += v[l];
- mn = min(mn,v[l]);
- }
- for(;r / sz<right + 1 && r<n;r++){
- v[r] = get(r);
- mn = min(mn,v[r]);
- sum += v[r];
- }
- ar[right].value_of_all = -1;
- ar[right].add_to_all = 0;
- ar[right].range_min = mn;
- ar[right].range_sum = sum;
- return;
- }
- for(int i=(l / sz) * sz;i<l;i++){
- v[i] = get(i);
- mn = min(mn,v[i]);
- sum += v[i];
- }
- for(;l / sz<left;l++){
- v[l] = x;
- mn = min(mn,v[l]);
- sum += v[l];
- }
- ar[left-1].value_of_all = -1;
- ar[left-1].add_to_all = 0;
- ar[left-1].range_min = mn;
- ar[left-1].range_sum = sum;
- sum = 0;
- mn = INT_MAX;
- for(;left < right;left++){
- ar[left].value_of_all = x;
- ar[left].add_to_all = 0;
- ar[left].range_min = x;
- ar[left].range_sum = 1ll * x * sz;
- }
- for(int i = right * sz;i<r;i++){
- v[i] = x;
- mn = min(mn,v[i]);
- sum += v[i];
- }
- for(;r / sz<right + 1 && r<n;r++){
- v[r] = get(r);
- mn = min(mn,v[r]);
- sum += v[r];
- }
- ar[right].value_of_all = -1;
- ar[right].add_to_all = 0;
- ar[right].range_min = mn;
- ar[right].range_sum = sum;
- }
- void add(int l,int r,int x){ // [l,r)
- int left = ((l / sz) + 1); //next block of left element(l)
- int right = (r / sz); //block of right element(r)
- ll sum = 0;
- int mn = INT_MAX;
- if(left > right){ // l and r in the same block
- for(int i=right * sz;i<l;i++){
- v[i] = get(i);
- sum += v[i];
- mn = min(mn,v[i]);
- }
- for(;l<r;l++){
- v[l] = get(l) + x;
- sum += v[l];
- mn = min(mn,v[l]);
- }
- for(;r / sz<right + 1 && r<n;r++){
- v[r] = get(r);
- mn = min(mn,v[r]);
- sum += v[r];
- }
- ar[right].value_of_all = -1;
- ar[right].add_to_all = 0;
- ar[right].range_min = mn;
- ar[right].range_sum = sum;
- return;
- }
- for(int i=(l / sz) * sz;i<l;i++){
- v[i] = get(i);
- mn = min(mn,v[i]);
- sum += v[i];
- }
- for(;l / sz<left;l++){
- v[l] = get(l) + x;
- mn = min(mn,v[l]);
- sum += v[l];
- }
- ar[left-1].value_of_all = -1;
- ar[left-1].add_to_all = 0;
- ar[left-1].range_min = mn;
- ar[left-1].range_sum = sum;
- sum = 0;
- mn = INT_MAX;
- for(;left < right;left++){
- if(ar[left].value_of_all > -1){
- ar[left].value_of_all += x;
- }else ar[left].add_to_all += x;
- ar[left].range_min += x;
- ar[left].range_sum += 1ll * x * sz;
- }
- for(int i = right * sz;i<r;i++){
- v[i] = get(i) + x;
- mn = min(mn,v[i]);
- sum += v[i];
- }
- for(;r / sz<right + 1 && r<n;r++){
- v[r] = get(r);
- mn = min(mn,v[r]);
- sum += v[r];
- }
- ar[right].value_of_all = -1;
- ar[right].add_to_all = 0;
- ar[right].range_min = mn;
- ar[right].range_sum = sum;
- }
- ll rsq(int l,int r){
- ll ans = 0;
- int left = ((l / sz) + 1); //next block of left element(l)
- int right = (r / sz); //block of right element(r)
- if(left > right){ // l and r in the same block
- for(int i=l;i<r;i++){
- ans += get(i);
- }
- return ans;
- }
- for(;l / sz<left;l++){
- ans += get(l);
- }
- for(;left < right;left++){
- ans += ar[left].range_sum;
- }
- for(int i = right * sz;i<r;i++){
- ans += get(i);
- }
- return ans;
- }
- int rmq(int l,int r){
- int mn = INT_MAX;
- int left = ((l / sz) + 1); //next block of left element(l)
- int right = (r / sz); //block of right element(r)
- if(left > right){ // l and r in the same block
- for(int i=l;i<r;i++){
- mn = min(mn,get(i));
- }
- return mn;
- }
- for(;l / sz<left;l++){
- mn = min(mn,get(l));
- }
- for(;left < right;left++){
- mn = min(mn,ar[left].range_min);
- }
- for(int i = right * sz;i<r;i++){
- mn = min(mn,get(i));
- }
- return mn;
- }
- int main()
- {
- ios_base::sync_with_stdio(0); cin.tie(0);
- cin>>n;
- for(int i=0;i<n;i++) cin>>v[i];
- build();
- int m; cin>>m;
- while(m--){
- string type; cin>>type;
- if(type == "get"){ //ready
- int i; cin>>i;
- cout<<get(--i)<<endl;
- }else if(type == "update"){ //ready
- int l,r,x; cin>>l>>r>>x;
- update(--l,r,x);
- }else if(type == "add"){ //ready
- int l,r,x; cin>>l>>r>>x;
- add(--l,r,x);
- }else if(type == "rsq"){ //ready
- int l,r; cin>>l>>r;
- cout<<rsq(--l,r)<<endl;
- }else if(type == "rmq"){ //ready
- int l,r; cin>>l>>r;
- cout<<rmq(--l,r)<<endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement