PROBLEM LINK:
Author: Evgeny Karpovich
Tester: Aryanc Choudhary
Editorialist: Srikkanth R
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Segment Tree, Lazy Propagation, Euclid’s GCD, Two-Pointers
PROBLEM:
You are given an array A of size N and Q queries each of which is of following type:
-
l r x yReplace theA[l+i]withx + i * yfor each 0 \leq i \leq r-l
The beauty of an array is given by the maximum of \gcd(A_l, A_{l+1}, \dots, A_r). (r-l+1) for all 0 \leq l \leq r \le n, i.e. compute for each sub-array the product of its gcd and length and then take the maximum over all values computed for every sub-array.
Print the beauty of the given array and then the beauty of the array after performing the first i queries for each i = 1, 2, \dots Q.
QUICK EXPLANATION:
Given any two numbers A, B, either \gcd(A, B) = \min(A, B), otherwise \gcd(A, B) \leq \frac{\min(A, B)}{2}.
Therefore consider all the sub-arrays starting from some index i, there will be only O(\log C) where C = 10^9 distinct \gcd values among all the sub-arrays beginning at index i.
To calculate the maximum over all sub-arrays, we can use the divide and conquer approach.
To merge the left and right halves, we need to iterate through the suffix of the left half and the prefix of the right half.
By compressing those prefixes and suffixes with the same \gcd, we need to only iterate through O(\log C) different sub-arrays in the left and right halves and so merging can be done by considering each pair, finding the cost of the combined arrays and updating the answer. The time complexity per merge is O(\log^2 C).
To accommodate the queries, we can build a segment tree with lazy updates over this D&C solution which immediately leads to an O(N \log N \log^2 C) solution, which can be a bit difficult to fit into the time limit.
The clever observation to optimize the above is that while merging two adjacent sub-arrays into one, if the \gcd changes, i.e. the \gcd is lesser than the \gcd of both the sub-arrays then the cost of the combined sub-array is not greater than the cost of both the sub-arrays considered individually. Thus we need only find those (suffix, prefix) pairs that have the same \gcd value. Since the prefix and suffixes have \gcd's in sorted order we can use a two-pointer approach to find them all and implement the merge procedure in O(\log C) time. This gives us an O(n \log n \log C) algorithm which can comfortably fit into the time limit.
EXPLANATION:
Let’s first consider the problem without queries, which is much easier.
On the GCD operation
The first observation is that when applying the \gcd operation on two numbers, the result is either equal to the minimum or is at most half of the minimum.
This is because \gcd(A, B) is a factor of both A, B. If it is not equal to B, then it must be a proper factor of B. A proper factor of B will be lesser by at least one prime factor, and the smallest of all primes is 2.
Remember that the \gcd(A, B) operation takes up to O(\log{B}), actually we can even write it as O(\log{\frac{B}{g}}) where g is the result of the \gcd operation. This will come in handy when analyzing the runtime of the algorithms that we develop.
Divide and Conquer strategy
In many cases when we want to minimize a function over all sub-arrays, it might be useful to think about a Divide and Conquer style algorithm. If the merge part can be done efficiently, then we get a nice runtime complexity and another hint that such an algorithm is applicable is the presence of range queries in the question. Such Divide and Conquer solutions can (in most cases) be adapted to construct a segment tree with efficient point/range updates and point/range queries.
Following the Divide and Conquer strategy, we split the array into two halves, compute the answer for each and then merge them. We will discuss here how to merge efficiently.
To combine, we need to only consider those sub-arrays that cross the midpoint of the array, which can be represented as a union of a suffix of the left half and a prefix of the right half.
In each half, the prefixes and suffixes have only O(\log C) distinct \gcd values, and we only need the sub-arrays with maximum length among those distinct values. So we can compress them.
To merge, if we naively consider every possible prefix and suffix, we will have O(\log^2 C) distinct pairs of sub-arrays to consider. Also note that if we fix the prefix of the right half and iterate through the suffixes of the left half, the total cost of performing the \gcd operation is O(\log C) total for each prefix.
This is because if the \gcd values are g_1, g_2, \dots g_k then the total number of operations is O(\log \frac{C}{g_1} + \log \frac{g_1}{g_2} + \dots \frac{g_k}{1}) = O(\log C).
Another way to see this is by tracking the modulo operations done while applying the \gcd algorithm. The modulo operation can only be applied \log(C) times until the value reduces to 0 and so the total cost of performing all the \gcd's for a fixed prefix is O(\log C).
So in total, the complexity of the merge operation is O(\log^2 C).
Segment Tree Implementation Details
If we store the answers computed for each divide and conquer iteration, along with the compressed prefixes and suffixes, we get a segment tree and we can perform the range updates by using lazy propagation.
More formally for each node in the segment tree, we maintain the following
- The set of distinct prefix \gcd's and their maximum lengths (stored and (\gcd, \texttt{length}) pairs)
- The set of distinct suffix \gcd's and their maximum lengths (stored and (\gcd, \texttt{length}) pairs)
- The maximum beauty of all sub-arrays which are completely within the interval of the node of the segment tree
And then to merge the left node L and the right node R and obtain the resultant node S, we do the following:
- Set prefix of S as the prefix of L and extend it by visiting the prefixes of R
- Set suffix of S as the suffix of R and extend it by visiting the suffixes of L
- Set maximum beauty as the maximum of beauties of L and R
- For each suffix of L and prefix of R, compute the result of combining them and update the maximum beauty
Range Updates
The range update is change a sub-array of the array to an arithmetic progression. Notice that for an arithmetic progression, A, A+D, A+2D, \dots A+xD, the \gcd of any sub-array of size 2 will be \gcd(A+iD, A+(i+1)*D) = \gcd(A + iD, D) = \gcd(A, D), therefore, the \gcd of any sub-array of size at least 2 is also \gcd(A, D).
So the distinct prefixes are \{(A, 1), (\gcd(A, D), sz-1)\}. Be careful of the case when sz=1.
Similarly, distinct suffixes can also be obtained.
In the usual style of performing segment tree with lazy updates, we will find the O(\log n) disjoint intervals that make up the given update range [l, r] and we can simply forget about the values stored previously and update them with the new values calculated above. We can mark the children as lazy and store the arithmetic progressions that have to be added there. Refer to the code below for more details.
Complexity analysis
Let’s analyze the time complexity of each merge operation.
For extending the prefix and suffix of the left and right nodes, suppose we ended up with k different \gcd values, namely g_1, g_2, \dots g_k, then we performed in total k called to \gcd function (i.e. Euclid’s algorithm), however they are all factors of each other. Therefore the total cost of performing \gcd for all of them is O(\log \frac{C}{g_1} + \log \frac{g_1}{g_2} + \dots \frac{g_k}{1}) = O(\log C).
Similarly, if we fix the suffix in the left node L and iterate through the prefixes of R, we will take only O(\log C) operations for each suffix, this gives a total of O(\log ^2 C) complexity for each merge operation.
Combined with the segment tree updates the total complexity of this approach is O(N \log N \log^2 C) which can be difficult to fit into the constraints. But the bottleneck is the merge operation above, which we will now optimize.
Optimizing the merge operation
Suppose we have two adjacent sub-arrays with (\gcd, \texttt{size}) pairs as (g_1, L_1) and (g_2, L_2) respectively, then the combined sub-array has (\gcd(g_1, g_2), L_1 + L_2). Suppose \gcd(g_1, g_2) < \min(g_1, g_2), i.e. we get a new distinct \gcd by combining the two, then the beauty of the resulting array is \gcd(g_1, g_2) * (L_1 + L_2).
Suppose L_1 \leq L_2, then \gcd(g_1, g_2) * (L_1 + L_2) \leq \frac{g_2}{2}{2 * L_2} = g_2 L_2. So merging two sub-arrays with different \gcd's can be avoided and since the \gcd is decreasing across each suffix and prefix, we can find all pairs whose \gcd's are equal by using a two-pointer approach in O(\log C).
With this idea, our solution is O(N \log N \log C) which can comfortably fit into the time limit.
TIME COMPLEXITY:
TIME: \mathcal{O}(N \log N \log C)
SPACE: \mathcal{O}(N)
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int const maxn = 1e5 + 5;
int a[maxn];
ll ans[(1 << 18)];
vector < pair < int, int > > pref[(1 << 18)], suff[(1 << 18)];
int psh_x[(1 << 18)], psh_y[(1 << 18)];
inline void merge(int i) {
ans[i] = max(ans[2 * i + 1], ans[2 * i + 2]);
pref[i] = pref[2 * i + 1];
for (auto key : pref[2 * i + 2]) {
int nxt_gcd = __gcd(pref[i].back().first, key.first);
if (nxt_gcd == pref[i].back().first) {
pref[i].back().second += key.second;
}
else {
pref[i].push_back({nxt_gcd, key.second});
}
}
suff[i] = suff[2 * i + 2];
for (auto key : suff[2 * i + 1]) {
int nxt_gcd = __gcd(suff[i].back().first, key.first);
if (nxt_gcd == suff[i].back().first) {
suff[i].back().second += key.second;
}
else {
suff[i].push_back({nxt_gcd, key.second});
}
}
int len_suff = 0, len_pref = 0, ptr = 0;
for (auto key : suff[2 * i + 1]) {
len_suff += key.second;
while (ptr < (int)pref[2 * i + 2].size() && pref[2 * i + 2][ptr].first % key.first == 0) {
len_pref += pref[2 * i + 2][ptr].second;
ptr++;
}
ans[i] = max(ans[i], (ll)(len_pref + len_suff) * (ll)key.first);
}
len_pref = 0, len_suff = 0, ptr = 0;
for (auto key : pref[2 * i + 2]) {
len_pref += key.second;
while (ptr < (int)suff[2 * i + 1].size() && suff[2 * i + 1][ptr].first % key.first == 0) {
len_suff += suff[2 * i + 1][ptr].second;
ptr++;
}
ans[i] = max(ans[i], (ll)(len_pref + len_suff) * (ll)key.first);
}
}
void build(int i, int l, int r) {
pref[i] = {}, suff[i] = {}, psh_x[i] = 0;
if (r - l == 1) {
pref[i] = {{a[l], 1}};
suff[i] = {{a[l], 1}};
ans[i] = a[l];
return;
}
int m = (r + l) / 2;
build(2 * i + 1, l, m);
build(2 * i + 2, m, r);
merge(i);
}
inline void push(int i, int l, int r) {
if (psh_x[i] == 0) return;
ans[i] = psh_x[i] + (r - l - 1) * psh_y[i];
int val = __gcd(psh_x[i], psh_y[i]);
ans[i] = max(ans[i], (ll)(r - l) * (ll)val);
pref[i] = {{psh_x[i], 1}};
suff[i] = {{psh_x[i] + (r - l - 1) * psh_y[i], 1}};
if (r - l > 1) {
pref[i].push_back({val, r - l - 1});
suff[i].push_back({val, r - l - 1});
int m = (r + l) / 2;
psh_x[2 * i + 1] = psh_x[i];
psh_y[2 * i + 1] = psh_y[i];
psh_x[2 * i + 2] = psh_x[i] + (m - l) * psh_y[i];
psh_y[2 * i + 2] = psh_y[i];
}
psh_x[i] = 0;
}
void update(int i, int l, int r, int lq, int rq, int x, int y) {
push(i, l, r);
if (lq >= r || l >= rq) return;
if (lq <= l && r <= rq) {
psh_x[i] = x + (l - lq) * y, psh_y[i] = y;
push(i, l, r);
return;
}
int m = (r + l) / 2;
update(2 * i + 1, l, m, lq, rq, x, y);
update(2 * i + 2, m, r, lq, rq, x, y);
merge(i);
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, q, l, r, x, y;
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> a[i];
build(0, 1, n + 1);
cout << ans[0] << '\n';
for (int i = 1; i <= q; ++i) {
cin >> l >> r >> x >> y;
update(0, 1, n + 1, l, r + 1, x, y);
cout << ans[0] << '\n';
}
}
return 0;
}
Tester's Solution
/* in the name of Anton */
/*
Compete against Yourself.
Author - Aryan (@aryanc403)
Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/
#ifdef ARYANC403
#include <header.h>
#else
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize ("-ffloat-store")
#include<bits/stdc++.h>
#define dbg(args...) 42;
#endif
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
Fun fun_;
public:
template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
using namespace std;
#define fo(i,n) for(i=0;i<(n);++i)
#define repA(i,j,n) for(i=(j);i<=(n);++i)
#define repD(i,j,n) for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
vi readVectorInt(int n,lli l,lli r){
vi a(n);
for(int i=0;i<n-1;++i)
a[i]=readIntSp(l,r);
a[n-1]=readIntLn(l,r);
return a;
}
const lli INF = 0xFFFFFFFFFFFFFFFL;
lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{ return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};
void add( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt==m.end()) m.insert({x,cnt});
else jt->Y+=cnt;
}
void del( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt->Y<=cnt) m.erase(jt);
else jt->Y-=cnt;
}
bool cmp(const ii &a,const ii &b)
{
return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
const lli mod = 1000000007L;
// const lli maxN = 1000000007L;
const lli N9=1e9;
int gcd(int a,int b){
if(a==0||b==0)
return a+b;
return __gcd(a,b);
}
struct Node{
lli ans;
vector<pair<int,int>> prefix,suffix;
};
#define leftChild(x) (x<<1)
#define rightChild(x) ((x<<1)|1)
void solve(const int n,const int q){
const auto a=readVectorInt(n,1,N9);
dbg(a);
vector<Node> seg(4*n+15);
vector<pair<int,int>> lazy(4*n+15,{-1,-1});
auto findAnswer=[&](const vector<pair<int,int>> &a,const vector<pair<int,int>> &b){
const int n=sz(a),m=sz(b);
int i=0,j=0,len=0;
lli ans=0;
while(i<n){
const int g=a[i].X;
len+=a[i].Y;
while(j<m&&b[j].X%g==0){
len+=b[j].Y;
j++;
}
ans=max(ans,g*1LL*len);
i++;
}
return ans;
};
auto merge=[&](const int id){
const auto &lCld=seg[leftChild(id)],&rCld=seg[rightChild(id)];
auto &cur=seg[id];
cur.ans=max(lCld.ans,rCld.ans);
cur.prefix=lCld.prefix;
for(auto x:rCld.prefix){
if(cur.prefix.empty())
cur.prefix.pb(x);
else{
x.X=gcd(x.X,cur.prefix.back().X);
if(cur.prefix.back().X==x.X)
cur.prefix.back().Y+=x.Y;
else
cur.prefix.pb(x);
}
}
cur.suffix=rCld.suffix;
for(auto x:lCld.suffix){
if(cur.suffix.empty())
cur.suffix.pb(x);
else{
x.X=gcd(x.X,cur.suffix.back().X);
if(cur.suffix.back().X==x.X)
cur.suffix.back().Y+=x.Y;
else
cur.suffix.pb(x);
}
}
cur.ans=max(cur.ans,findAnswer(lCld.suffix,rCld.prefix));
cur.ans=max(cur.ans,findAnswer(rCld.prefix,lCld.suffix));
dbg(id,cur.ans);
};
auto updateNode=[&](const int id,const int l,const int r,const int A,const int D){
auto &cur=seg[id];
cur.prefix.clear();
cur.suffix.clear();
if(l==r){
cur.prefix=cur.suffix={{A,1}};
cur.ans=A;
dbg(id,l,r,cur.ans);
return;
}
const lli g=gcd(A,A+D);
if(A==g){
cur.prefix={{g,r-l+1}};
} else {
cur.prefix={{A,1},{g,r-l}};
}
if(A+(r-l)*D==g){
cur.suffix={{g,r-l+1}};
} else {
cur.suffix={{A+(r-l)*D,1},{g,r-l}};
}
cur.ans=max(1LL*A+(r-l)*D,g*(r-l+1));
lazy[id]={A,D};
dbg(id,l,r,cur.ans);
};
auto push=[&](const int id,const int l,const int r)->void{
if(lazy[id].X==-1)
return;
const int A=lazy[id].X,D=lazy[id].Y;
dbg(A,D,l,r,"Hello");
lazy[id]={-1,-1};
const int mid=(l+r)>>1;
updateNode(leftChild(id),l,mid,A,D);
// if(mid+1<=r)
updateNode(rightChild(id),mid+1,r,A+D*(mid+1-l),D);
};
auto build=y_combinator([&](const auto &self,int id,int l,int r)->void{
if(l==r){
updateNode(id,l,r,a[l],0);
return;
}
const int mid=(l+r)>>1;
self(leftChild(id),l,mid);
self(rightChild(id),mid+1,r);
merge(id);
});
auto updateSegment=y_combinator([&](const auto &self,int id,int l,int r,int L,int R,int A,int D)->void{
if(r<L||R<l)
return;
push(id,l,r);
if(L<=l&&r<=R){
updateNode(id,l,r,A+D*(l-L),D);
return;
}
const int mid=(l+r)>>1;
self(leftChild(id),l,mid,L,R,A,D);
self(rightChild(id),mid+1,r,L,R,A,D);
merge(id);
});
auto update=[&](int l,int r,int A,int D){
updateSegment(1,0,n-1,l,r,A,D);
};
build(1,0,n-1);
cout<<seg[1].ans<<endl;
for(int iq=0;iq<q;++iq){
const lli l=readIntSp(1,n)-1;
const lli r=readIntSp(l,n)-1;
const lli A=readIntSp(1,N9);
const lli D=readIntLn(0,N9);
assert(A+(r-l)*D<=N9);
update(l,r,A,D);
cout<<seg[1].ans<<endl;
}
}
int main(void) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
// freopen("txt.in", "r", stdin);
// freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
lli sumN=1e5,sumQ=1e5;
lli T=readIntLn(1,sumN);
while(T--)
{
const lli n=readIntSp(1,sumN),q=readIntLn(1,sumQ);
sumN-=n;sumQ-=q;
solve(n,q);
} aryanc403();
readEOF();
return 0;
}
Editorialist's Implementation
#include <bits/stdc++.h>
#define LL long long
using namespace std;
clock_t start = clock();
const int N = (int)1e5 + 5;
// Each segment tree node
struct SegNode {
// All the distinct prefix and suffix gcd's of the sub-array represented by the node in the segment tree
// stored as (gcd, size) pairs where size is the number of prefixes/suffixes with the same gcd
// The size of these is always $O(\log C)$
vector<pair<int, int>> pref, suf;
// Answer for the sub-array represented by the node in the segment tree
LL ans;
SegNode() {
ans = 0;
}
// Initialize a segment tree node with single value equal to x
SegNode(int x) {
pref.push_back({x, 1});
suf.push_back({x, 1});
ans = x;
}
// Initialize a segment tree node with an arithmetic progression with:
// size: `sz`
// first element: `A`
// common difference: `D`
SegNode(int A, int D, int sz) {
if (sz == 1) {
pref.clear(); suf.clear();
pref.push_back({A, 1});
suf.push_back({A, 1});
ans = A;
return;
}
pref = vector<pair<int, int>>({{A, 1}, {__gcd(A, D), sz-1}});
suf = vector<pair<int, int>>({{A + (sz - 1) * D, 1}, {__gcd(A, D), sz-1}});
ans = max({(LL)A, (LL)A + (sz - 1) * D, __gcd(A, D) * 1LL * sz});
}
}tree[4 * N];
// Merging two nodes in the segment tree, works in $O(\log C)$!
SegNode Merge(SegNode &A, SegNode &B) {
if (A.pref.empty()) return B;
if (B.pref.empty()) return A;
// Extend the prefix/suffix of one node with the prefix/suffix of the other node
auto myAppend = [](vector<pair<int, int>> &v, vector<pair<int, int>> &w) {
for (auto &p : w) {
int g = __gcd(v.back().first, p.first);
if (g == v.back().first) {
v.back().second += p.second;
} else {
v.push_back({g, p.second});
}
}
};
SegNode ret;
ret.pref = A.pref;
myAppend(ret.pref, B.pref);
ret.suf = B.suf;
myAppend(ret.suf, A.suf);
ret.ans = max(A.ans, B.ans);
// Merge operation, for each suffix of the left node, iterate through the suffix of the right
// We only need to consider those pairs with same gcd's!
int ptr = 0, cntL = 0, cntR = 0;
for (auto &p : B.pref) {
cntR += p.second;
while (ptr < (int)A.suf.size() && A.suf[ptr].first % p.first == 0) {
cntL += A.suf[ptr].second;
ptr++;
}
ret.ans = max(ret.ans, (cntL + cntR) * 1LL * p.first);
}
// Merge operation, for each prefix of the right node, iterate through the suffix of the left
// We only need to consider those pairs with same gcd's!
ptr = 0; cntL = 0, cntR = 0;
for (auto &p : A.suf) {
cntL += p.second;
while (ptr < (int)B.pref.size() && B.pref[ptr].first % p.first == 0) {
cntR += B.pref[ptr].second;
ptr++;
}
ret.ans = max(ret.ans, (cntL + cntR) * 1LL * p.first);
}
return ret;
}
// v[1], v[2], ... v[n] is the input array
// lzA[node] and lzD[node] is the lazy tag saying convert the segment tree `node` to an AP with first term A and common difference D
int v[N], lzA[4 * N], lzD[4 * N];
// Building the segment tree, (! don't forget to initialize the lazy tags for multiple testcases)
void build(int node, int st, int en) {
lzA[node] = lzD[node] = -1;
if (st == en) {
tree[node] = SegNode(v[st]);
return;
}
int m = (st + en) >> 1;
build(node * 2 + 1, st, m);
build(node * 2 + 2, m+1, en);
tree[node] = Merge(tree[node * 2 + 1], tree[node * 2 + 2]);
}
// Lazy propagate operation
void push(int node, int st, int en) {
if (lzA[node] != -1) {
tree[node] = SegNode(lzA[node], lzD[node], en - st + 1);
if (st < en) {
int m = (st + en) >> 1;
lzA[node * 2 + 1] = lzA[node];
lzA[node * 2 + 2] = lzA[node] + (m - st + 1) * lzD[node];
lzD[node * 2 + 1] = lzD[node * 2 + 2] = lzD[node];
}
lzA[node] = -1; lzD[node] = -1;
}
}
// Range updates
void update(int l, int r, int x, int y, int node, int st, int en) {
// cerr << node << " " << st << " " << en << " " << l << " " << r << " here\n";
// assert(l <= r);
push(node, st, en);
if (en < l || st > r) return;
if (st >= l && en <= r) {
tree[node] = SegNode(x + y * (st - l), y, en - st + 1);
if (st < en) {
int m = (st + en) >> 1;
push(2 * node + 1, st, m);
push(2 * node + 2, m+1, en);
lzA[2 * node + 1] = x + y * (st - l);
lzA[2 * node + 2] = x + y * (m + 1 - l);
lzD[2 * node + 1] = lzD[2 * node + 2] = y;
}
return;
}
int m = (st + en) >> 1;
update(l, r, x, y, 2*node+1, st, m);
update(l, r, x, y, 2*node+2, m+1, en);
tree[node] = Merge(tree[node * 2 + 1], tree[node * 2 + 2]);
}
// Debug function to display segment trees
void display(int node, int st, int en) {
cerr << node << " (" << st << "," << en << "): " << lzA[node] << ", " << lzD[node] << '\n';
cerr << "Pref : ";
for (auto it : tree[node].pref) {
cerr << it.first << "," << it.second << " ";
} cerr << '\n';
cerr << "Suf : ";
for (auto it : tree[node].suf) {
cerr << it.first << "," << it.second << " ";
} cerr << '\n';
cerr << "Ans : " << tree[node].ans << '\n';
if (st == en) {
return;
}
int m = (st + en) >> 1;
display(node * 2 + 1, st, m);
display(node * 2 + 2, m+1, en);
}
void solve() {
// Read Input
int n, q;
cin >> n >> q;
for (int i=1;i<=n;++i) {
cin >> v[i];
}
// Build the segment tree
build(0, 1, n);
// display(0, 1, n);
// Desired answer stored in the root
cout << tree[0].ans << '\n';
while (q--) {
int l, r, x, y;
cin >> l >> r >> x >> y;
// update with lazy propagation
update(l, r, x, y, 0, 1, n);
// display(0, 1, n);
// Desired answer stored in the root
cout << tree[0].ans << '\n';
}
}
int main() {
// FASTIO
ios_base::sync_with_stdio(false); cin.tie(NULL);
// Solve multiple testcases
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}