#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int INF = 1e18;
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;
if(idx.tot.first == idx.sz){
if(idx1.mxl.second == idx.tot.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 = idx.mxr;
pair<int,int> tempright = idx.mxr;
if(idx1.tot.first == idx1.sz){
if(idx.mxr.second == idx.tot.second) tempright = {idx1.sz + idx.mxr.first, idx.mxr.second};// join both lefts
else tempright = idx.mxl;
}
ans.mxr = max(ans.mxr, tempright); // take max
// TAKE TOTAL
ans.tot = max(ans.mxl, ans.mxr);
// 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;
seg.assign(2*n, tmpn); lazy.resize(2*n);
for(int i = 0; i<n1; 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];
}
for(int i = n-1; i>=1; i--) 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)/2;
seg[idx].mxr.second = v;
seg[idx].mxr.first = (r-l+1)/2;
seg[idx].tot.second = v;
seg[idx].tot.first = (r-l+1)/2;
}
void PushDown(int k, int l, int r){
if(lazy[k].first == 0){
//add
if(lazy[2*k].first == 1) lazy[2*k] = {0,0};
add(2*k, lazy[k].second, l,r);
if(lazy[2*k+1].first == 1) lazy[2*k+1] = {0,0};
add(2*k+1,lazy[k].second, l, r);
}
else{
//set
set(2*k, lazy[k].second, l, 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){
return query(ql,qr,1,0,n-1).tot.first;
}
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
add(k,v,l,r);
if(lazy[k].first == 1) lazy[k] = {0,0};
lazy[k].second += v;
return;
}
else{
set(k,v,l,r);
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];
while(q--){
int tp; cin>>tp;
if(tp == 1){
//add
int l,r; cin>>l>>r; l--; r--;
int s,c; cin>>s>>c;
if(l == 0) v[0] += s;
seg.update(l,r-1,0,c);
seg.update(r,r,0,s);
if(l) seg.update(l-1,l-1,0,-s);
}
else if(tp == 2){
int l,r; cin>>l>>r; int s,c; cin>>s>>c;
// seg.update(l,r-1,1,c); // set differences
int sum = v[0];
if(l) sum+=seg.sum(0,l-1);
int val = s + (r-l)*s;
int sum1 = v[0];
if(r) sum1+=seg.sum(0,r-1);
if(l == 0) v[0] = s;
if(l) seg.update(l-1, l-1, 0, s-sum);
seg.update(r,r,0, val-sum1);
seg.update(l,r-1,1,c);
}
else{
int l,r; cin>>l>>r; l--; r--;
if(l == r){
cout<<1<<endl; continue;
}
cout<<seg.query(l,r-1)+1<<endl;
}
}
}
Compilation message
Progression.cpp: In function 'int main()':
Progression.cpp:152:6: warning: unused variable 'val' [-Wunused-variable]
152 | int val = v[0];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
239 ms |
89700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
366 ms |
90572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
400 ms |
89544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
366 ms |
90572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
239 ms |
89700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
