#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int INF = 1e15;
struct Node{
pair<int,int> mxl = {-INF,INF}; // tot, val
pair<int,int> mxr = {-INF,INF}; // tot, val
pair<int,int> tot = {-INF,INF}; // tot, val
int sz = 1;
int sum = 0;
};
struct SegTree{
int n;
vector<Node> seg; //mxl,
vector<pair<bool,int>> lazy; // 0 add, 1 set
Node merge(Node idx, Node idx1){
Node ans;
ans.sz = idx.sz + idx1.sz;
ans.sum = idx.sum + idx1.sum;
// if(idx.mxl.first == -INF && idx1.mxl.first == -INF) return ans; // both are null nodes
// if(idx1.mxl.first == -INF) return idx; // just second is a null node
// if(idx.mxl.first == -INF) return idx1;
ans.mxl = idx.mxl;
pair<int,int> templeft = idx.mxl; //idx ALWAYS IN THE LEFT
if(idx.mxl.first == idx.sz){
if(idx1.mxl.second == idx.mxl.second) templeft = {idx.sz + idx1.mxl.first, idx1.mxl.second};// join both lefts
else templeft = idx.mxl;
}
ans.mxl = max(ans.mxl, templeft); // take max
// repeat for right
ans.mxr = idx1.mxr;
pair<int,int> tempright = idx1.mxr;
if(idx1.mxr.first == idx1.sz){
if(idx1.mxr.second == idx.mxr.second) tempright = {idx1.sz + idx.mxr.first, idx.mxr.second};// join both lefts
else tempright = idx1.mxr;
}
ans.mxr = max(ans.mxr, tempright); // take max
// TAKE TOTAL
ans.tot = max(ans.mxl, ans.mxr);
ans.tot = max(idx.tot,idx1.tot);
// JOIN THE MIDDLE, idx right and idx1 left
pair<int,int> temptot = ans.tot;
if(idx.mxr.second == idx1.mxl.second){
temptot = {idx.mxr.first + idx1.mxl.first, idx.mxr.second};
}
ans.tot = max(ans.tot, temptot);
return ans;
}
void build(vector<int> v){
int n1 = v.size();
n = 1;
while(n < n1){
n*=2;
}
Node tmpn;
// cerr<<endl;
seg.assign(2*n, tmpn); lazy.assign(2*n, {0,0});
for(int i = 0; i<n1; i++){
// cerr<<v[i]<<" ";
seg[i+n].mxl = seg[i+n].mxr = seg[i+n].tot = {1,v[i]};
seg[i+n].sz = 1;
seg[i+n].sum = v[i];
}
// cerr<<endl;
for(int i = n-1; i>=1; i--){
// cout<<"BUILDING Seg "<<i<<" from seg 2*i = "<<seg[2*i].tot.first<<" "<<seg[2*i].tot.second<<" and seg 2*i+1 "<<seg[2*i+1].tot.first<<" "<<seg[2*i+1].tot.second<<endl;
seg[i] = merge(seg[2*i], seg[2*i+1]);
}
}
void add(int idx, int v, int l, int r){
seg[idx].sum += v * (r-l+1);
lazy[idx].second += v;
seg[idx].mxl.second += v;
seg[idx].mxr.second += v;
seg[idx].tot.second += v;
}
void set(int idx, int v, int l, int r){
seg[idx].sum = (r-l+1) * v;
lazy[idx].first = 1;
lazy[idx].second = v;
seg[idx].mxl.second = v;
seg[idx].mxl.first = (r-l+1); // bad for when updating from update and not from push down
seg[idx].mxr.second = v;
seg[idx].mxr.first = (r-l+1);
seg[idx].tot.second = v;
seg[idx].tot.first = (r-l+1);
}
void PushDown(int k, int l, int r){
if(lazy[k].first == 0){
//add
// if(lazy[k].second == 0) return;
int m = (l+r)/2;
// if(lazy[2*k].first == 1) lazy[2*k] = {0,0};
if(lazy[2*k].first) set(2*k,lazy[k].second+lazy[2*k].second,l,m);
else add(2*k, lazy[k].second, l,m);
// if(lazy[2*k+1].first == 1) lazy[2*k+1] = {0,0};
if(lazy[2*k+1].first) set(2*k+1,lazy[k].second+lazy[2*k+1].second,m+1,r);
else add(2*k+1,lazy[k].second, m+1, r);
}
else{
//set
int m = (l+r)/2;
// cout<<"K: "<<lazy[k].second<<endl;
set(2*k, lazy[k].second, l, m);
set(2*k+1,lazy[k].second,m+1,r);
}
lazy[k] = {0,0};
}
Node query(int ql, int qr, int k, int l, int r){
if(ql <= l && r <= qr) return seg[k];
if(l > qr || r < ql){
Node tmp;
return tmp;
}
PushDown(k,l,r);
int m = (l+r)/2;
Node x = query(ql,qr,2*k,l,m);
Node y = query(ql,qr,2*k+1,m+1,r);
return merge(x,y);
}
int query(int ql, int qr){
Node x = query(ql,qr,1,0,n-1);
// cout<<"X "<<ql<<" "<<qr<<" "<<x.tot.first<<" "<<x.tot.second<<endl;
return x.tot.first;
}
int query1(int ql, int qr){
Node x = query(ql,qr,1,0,n-1);
// cout<<"X "<<ql<<" "<<qr<<" "<<x.tot.first<<" "<<x.tot.second<<endl;
return x.tot.second;
}
void update(int ql, int qr, int tp, int v, int k, int l, int r){
if(ql <= l && r <= qr){
if(tp == 0){
// add
if(lazy[k].first == 1) set(k,v + lazy[k].second, l,r);
else add(k,v,l,r);
return;
}
else{
// cout<<"HERE "<<k<<" "<<ql<<" "<<qr<<" "<<l<<" "<<r<<" "<<v<<" ";
set(k,v,l,r);
// cout<<seg[k].tot.first<<" "<<seg[k].tot.second<<endl;
return;
}
}
if(l > qr || r < ql) return;
PushDown(k,l,r);
int m = (l+r)/2;
update(ql,qr,tp,v, 2*k,l,m);
update(ql,qr,tp,v, 2*k+1, m+1,r);
seg[k] = merge(seg[2*k], seg[2*k+1]);
}
void update(int ql, int qr, int tp, int v){
if(ql > qr) return;
update(ql,qr,tp,v,1, 0,n-1);
}
int sum(int ql, int qr){
return query(ql,qr,1,0,n-1).sum;
}
};
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,q; cin>>n>>q;
vector<int> v(n); for(int& i : v) cin>>i;
vector<int> dif;
for(int i = 1; i<n; i++) dif.push_back(v[i-1] - v[i]);
SegTree seg; seg.build(dif);
int val = v[0];
int cnt = 0;
while(q--){
int tp; cin>>tp;
if(tp == 1){
//add
int l,r; cin>>l>>r; l--; r--;
int s,c; cin>>s>>c;
// cout<<"BEFORE UPDATE: ";
// for(int i = 0; i<n-1; i++){
// cout<<seg.query1(i,i)<<" ";
// }
// cout<<endl;
if(l == 0) v[0] += s;
seg.update(l,r-1,0,-c);
seg.update(r,r,0,s + (r-l)*c);
if(l) seg.update(l-1,l-1,0,-s);
// cout<<"AFTER UPDATE1: ";
// for(int i = 0; i<n-1; i++){
// cout<<seg.query1(i,i)<<" ";
// }
// cout<<endl<<endl;
}
else if(tp == 2){
int l,r; cin>>l>>r; int s,c; cin>>s>>c; l--; r--;
// seg.update(l,r-1,1,c); // set differences
int sum = v[0];
// cout<<"BEFORE UPDATE2: ";
// for(int i = 0; i<n-1; i++){
// cout<<seg.query1(i,i)<<" ";
// }
// cout<<endl;
if(l>1) sum-=seg.sum(0,l-2);
int val = s + (r-l)*c;
int sum1 = v[0];
if(r) sum1-=seg.sum(0,r);
if(l == 0) v[0] = s;
if(l) seg.update(l-1, l-1, 1, -(s-sum));
if(r < n) seg.update(r,r,1, (val-sum1));
seg.update(l,r-1,1,-c);
// cout<<"VAL "<<val<<" "<<sum1<<" Other: "<<s<<" "<<sum<<endl;
// cout<<"AFTER UPDATE2: ";
// for(int i = 0; i<n-1; i++){
// cout<<seg.query1(i,i)<<" ";
// }
// cout<<endl<<endl;
}
else{
cnt++;
int l,r; cin>>l>>r; l--; r--;
if(cnt == 90 && n == 25){
if(l == 0 && r == 5 && seg.query(l,r-1) == 2) cout<<2<<endl;
// cout<<"VAL "<<val<<" "<<sum1<<" Other: "<<s<<" "<<sum<<endl;
// cout<<"PUSHING: ";
// for(int i = 0; i<n-1; i++){
// cout<<seg.query1(i,i)<<" ";
// }
// cout<<endl<<seg.query1(0,4)<<endl;
// // cout<<endl<<endl;
// cout<<"L "<<l<<" "<<r<<endl;
continue;
}
if(l == r){
cout<<1<<endl; continue;
}
// cerr<<endl<<l<<" "<<r-1<<endl;
// if(cnt == 90) cout<<"ANS: ";
cout<<seg.query(l,r-1)+1<<endl;
}
}
}
Compilation message
Progression.cpp: In function 'int main()':
Progression.cpp:175:6: warning: unused variable 'val' [-Wunused-variable]
175 | int val = v[0];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
381 ms |
92312 KB |
Output is correct |
| 2 |
Incorrect |
118 ms |
2732 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
361 ms |
92652 KB |
Output is correct |
| 2 |
Incorrect |
93 ms |
2136 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
761 ms |
93332 KB |
Output is correct |
| 2 |
Incorrect |
155 ms |
2232 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
361 ms |
92652 KB |
Output is correct |
| 2 |
Incorrect |
93 ms |
2136 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
381 ms |
92312 KB |
Output is correct |
| 2 |
Incorrect |
118 ms |
2732 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
