#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;
const int maxN = int(3e5)+7;
int n , q; ll a[maxN];
#define lef(id) id * 2
#define rig(id) id * 2 + 1
struct segtree_point{
struct node{
ll a , b , val;
bool isAdd;
node(){
a = b = val = 0ll;
isAdd = true;
}
void reset(){
a = b = 0ll;
isAdd = true;
}
} st[4 * maxN];
void build(int id , int l , int r){
if (l == r){
st[id].val = a[l];
return;
}
int mid = (l + r) / 2;
build(lef(id) , l , mid);
build(rig(id) , mid + 1 , r);
}
void modify(int id , ll a , ll b , bool isAdd){
if (isAdd == false){
st[id].a = a;
st[id].b = b;
st[id].isAdd = false;
}
else{
st[id].a += a;
st[id].b += b;
}
}
void down(int id){
ll a = st[id].a;
ll b = st[id].b;
bool isAdd = st[id].isAdd;
modify(lef(id) , a , b , isAdd);
modify(rig(id) , a , b , isAdd);
st[id].reset();
}
void update(int id , int l , int r , int u , int v , ll a , ll b , bool isAdd){
if (v < l || r < u) return;
if (u <= l && r <= v){
return modify(id , a , b , isAdd);
}
if (l != r) down(id);
int mid = (l + r) / 2;
update(lef(id) , l , mid , u , v , a , b , isAdd);
update(rig(id) , mid + 1 , r , u , v , a , b , isAdd);
}
ll get(int id , int l , int r , int p){
if (l == r){
ll x = 1ll * st[id].a * p + st[id].b;
if (st[id].isAdd == false){
st[id].val = x;
}
else{
st[id].val += x;
}
st[id].reset();
return st[id].val;
}
if (l != r) down(id);
int mid = (l + r) / 2;
if (p <= mid){
return get(lef(id) , l , mid , p);
}
else{
return get(rig(id) , mid + 1 , r , p);
}
}
} A;
struct segtree_range{
struct node{
int val;
ll st; int cnt_st;
ll en; int cnt_en;
bool same;
ll lazy;
bool isAdd;
node(){
val = 0;
st = 0; cnt_st = 0;
en = 0; cnt_en = 0;
same = false;
lazy = 0;
isAdd = true;
}
} st[4 * maxN];
node calc(node X , node Y){
if (X.val == 0) return Y;
if (Y.val == 0) return X;
node ans;
//
ans.val = max(X.val , Y.val);
if (X.en == Y.st){
ans.val = max(ans.val , X.cnt_en + Y.cnt_st);
}
//
ans.st = X.st;
ans.cnt_st = X.cnt_st;
if (X.same == true){
if (X.en == Y.st) ans.cnt_st += Y.cnt_st;
}
//
ans.en = Y.en;
ans.cnt_en = Y.cnt_en;
if (Y.same == true){
if (X.en == Y.st) ans.cnt_en += X.cnt_en;
}
//
if (X.same == true && Y.same == true && X.en == Y.st){
ans.same = true;
}
else{
ans.same = false;
}
//
return ans;
}
void build(int id , int l , int r){
if (l == r){
st[id].val = 1;
st[id].st = a[l + 1] - a[l]; st[id].cnt_st = 1;
st[id].en = a[l + 1] - a[l]; st[id].cnt_en = 1;
st[id].same = true;
return;
}
int mid = (l + r) / 2;
build(lef(id) , l , mid);
build(rig(id) , mid + 1 , r);
st[id] = calc(st[lef(id)] , st[rig(id)]);
}
void modify(int id , int l , int r , ll x , bool isAdd){
if (isAdd == false){
st[id].val = r - l + 1;
st[id].st = x; st[id].cnt_st = r - l + 1;
st[id].en = x; st[id].cnt_en = r - l + 1;
st[id].same = true;
st[id].lazy = x;
st[id].isAdd = false;
}
else{
st[id].st += x;
st[id].en += x;
st[id].lazy += x;
}
}
void down(int id , int l , int r){
ll &x = st[id].lazy;
bool &isAdd = st[id].isAdd;
int mid = (l + r) / 2;
modify(lef(id) , l , mid , x , isAdd);
modify(rig(id) , mid + 1 , r , x , isAdd);
x = 0; isAdd = true;
}
void update(int id , int l , int r , int u , int v , ll x , bool isAdd){
if (v < l || r < u) return;
if (u <= l && r <= v){
return modify(id , l , r , x , isAdd);
}
if (l != r) down(id , l , r);
int mid = (l + r) / 2;
update(lef(id) , l , mid , u , v , x , isAdd);
update(rig(id) , mid + 1 , r , u , v , x , isAdd);
st[id] = calc(st[lef(id)] , st[rig(id)]);
}
node get(int id , int l , int r , int u , int v){
if (v < l || r < u) return node();
if (u <= l && r <= v) return st[id];
if (l != r) down(id , l , r);
int mid = (l + r) / 2;
return calc(get(lef(id) , l , mid , u , v) , get(rig(id) , mid + 1 , r , u , v));
}
} B;
void solve(){
cin >> n >> q;
for (int i = 1 ; i <= n ; i++) cin >> a[i];
A.build(1 , 1 , n);
B.build(1 , 1 , n - 1);
for (int i = 1 ; i <= q ; i++){
int t; cin >> t;
if (t == 1){
int l , r; ll s , c;
cin >> l >> r >> s >> c;
A.update(1 , 1 , n , l , r , 1ll * c , 1ll * s - 1ll * c * l, true);
B.update(1 , 1 , n - 1 , l , r - 1 , 1ll * c , true);
if (l - 1 >= 1){
ll x = A.get(1 , 1 , n , l) - A.get(1 , 1 , n , l - 1);
B.update(1 , 1 , n - 1 , l - 1 , l - 1 , x , false);
}
if (r + 1 <= n){
ll x = A.get(1 , 1 , n , r + 1) - A.get(1 , 1 , n , r);
B.update(1 , 1 , n - 1 , r , r , x , false);
}
}
if (t == 2){
int l , r; ll s , c;
cin >> l >> r >> s >> c;
A.update(1 , 1 , n , l , r , 1ll * c , 1ll * s - 1ll * c * l , false);
B.update(1 , 1 , n - 1 , l , r - 1 , 1ll * c , false);
if (l - 1 >= 1){
ll x = A.get(1 , 1 , n , l) - A.get(1 , 1 , n , l - 1);
B.update(1 , 1 , n - 1 , l - 1 , l - 1 , x , false);
}
if (r + 1 <= n){
ll x = A.get(1 , 1 , n , r + 1) - A.get(1 , 1 , n , r);
B.update(1 , 1 , n - 1 , r , r , x , false);
}
}
if (t == 3){
int l , r;
cin >> l >> r;
cout << B.get(1 , 1 , n - 1 , l , r - 1).val + 1 << "\n";
}
}
}
#define name "A"
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(name".INP" , "r")){
freopen(name".INP" , "r" , stdin);
freopen(name".OUT" , "w" , stdout);
}
int t = 1; //cin >> t;
while (t--) solve();
return 0;
}
Compilation message
Progression.cpp:7:13: error: expected primary-expression before 'long'
7 | #define int long long
| ^~~~
Progression.cpp:14:18: note: in expansion of macro 'int'
14 | const int maxN = int(3e5)+7;
| ^~~
Progression.cpp:16:17: error: size of array 'a' is not an integral constant-expression
16 | int n , q; ll a[maxN];
| ^~~~
Progression.cpp:35:12: error: size of array 'st' is not an integral constant-expression
35 | } st[4 * maxN];
| ~~^~~~~~
Progression.cpp:119:12: error: size of array 'st' is not an integral constant-expression
119 | } st[4 * maxN];
| ~~^~~~~~
Progression.cpp: In function 'int main()':
Progression.cpp:261:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
261 | freopen(name".INP" , "r" , stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:262:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
262 | freopen(name".OUT" , "w" , stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
