COLLINEAR - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: wuhudsm
Tester: Takuki Kurokawa
Editorialist: Nishank Suresh

DIFFICULTY:

TBD

PREREQUISITES:

Segment trees with lazy propagation

PROBLEM:

Given N points (X_i, Y_i) on the plane, where X_i \lt X_{i+1}, support the following queries and updates:

  • Given L R K B, set Y_i := KX_i + B for each L \leq i \leq R
  • Given L R, report whether the points in [L, R] are collinear

EXPLANATION:

First, let’s look at the collinear query. It can be rephrased in terms of slopes as follows:

  • Define S_i to be the slope between the i-th and (i+1)-th point. That is, S_i = \frac{Y_{i+1} - Y_i}{X_{i+1} - X_i}.
  • Then, the query [L, R] really just asks if S_L = S_{L+1} = S_{L+2} = \ldots = S_{R-1}.

Computing the initial values of S_i is easy, so we just need to figure out how to maintain them across the given updates.

Let’s break down what an update L R K B looks like in terms of the S_i.

  • First, for each L \leq i \lt R, we essentially just set S_i = K.
  • The only other points that change value are S_{L-1} and S_R (if they exist).
  • Finding out what they change to can be done if we are able to query for their respective y-coordinates. So, we also need to maintain the y-coordinates of the points across queries.

Note that the y-coordinate of a point depends solely on the last (K, B) update applied to it, so we can simply maintain the (K, B) values for each point. Each update is then just a range set update, which can be done using a segment tree.

From our discussion above, we see that maintaining the S_i values needs a data structure that can:

  • Set a value of S_i to a range
  • Set a value of S_i to a point (which can just be subsumed into the first point, treating a point as a length 1 range)
  • Query for whether a range has all equal elements

The last part can be done by, for example, computing the maximum and minimum values in a range, and checking if they’re equal.
So, we need a data structure that supports range set updates, and range min/max queries. Once again, this is just a segment tree with lazy propagation.

In order to not run into precision issues, it is recommended to maintain the S_i values as pairs of (numerator, denominator) instead of directly as floating-point numbers.

TIME COMPLEXITY

\mathcal{O}(N+Q\log N).

CODE:

Setter's code (C++)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int n,q;
int x[N],y[N];

struct nod1
{
	int l,r,k,b;
	ll  y;
	nod1 *lc,*rc;
};

struct Segtree1
{
	nod1 *root;
	
	Segtree1()
	{
		build(&root,1,n);
	}
	
	void newnod(nod1 **p,int L,int R)
	{
		*p=new(nod1);
		(*p)->l=L;(*p)->r=R;(*p)->k=(*p)->b=INF;
		if(L==R) (*p)->y=y[L];
	}
	
	void build(nod1 **p,int L,int R)
	{
		newnod(p,L,R);
		if(L==R) return ;
		int M=(L+R)>>1;
		build(&(*p)->lc,L,M);
		build(&(*p)->rc,M+1,R);
	}
	
	void pushdown(nod1 *p)
	{
		if(p->k==INF) return ;
		if(p->l!=p->r)
		{
			p->lc->k=p->rc->k=p->k;
			p->lc->b=p->rc->b=p->b;
		}
		if(p->l==p->r) p->y=(ll)p->k*x[p->l]+p->b; 
		p->k=p->b=INF;
	}
	
	void modify(int L,int R,int K,int B)
	{
		_modify(root,L,R,K,B);
	}
	
	void _modify(nod1 *p,int L,int R,int K,int B)
	{
		pushdown(p);
		if(p->l==L&&p->r==R)
		{
			p->k=K;p->b=B;
			return ;
		}
		int M=(p->l+p->r)>>1;
		if(R<=M) _modify(p->lc,L,R,K,B);
		else if(L>M) _modify(p->rc,L,R,K,B);
		else
		{
			_modify(p->lc,L,M,K,B);
			_modify(p->rc,M+1,R,K,B);
		}
	}
	
	ll query(int pos)
	{
		return _query(root,pos);
	}
	
	ll _query(nod1 *p,int pos)
	{
		pushdown(p);
		if(p->l==p->r) return p->y;
		int M=(p->l+p->r)>>1;
		if(pos<=M) return _query(p->lc,pos);
		else return _query(p->rc,pos);
	}
};

struct nod2
{
	db   k,tag;
	int  l,r,equal;
	nod2 *lc,*rc;
};

struct Segtree2
{
	nod2 *root;
	
	Segtree2()
	{
		build(&root,1,n-1);
	}
	
	void newnod(nod2 **p,int L,int R)
	{
		*p=new(nod2);
		(*p)->l=L;(*p)->r=R;(*p)->tag=INF;
		if(L==R) 
		{
			(*p)->equal=1;
			(*p)->k=(db)(y[L+1]-y[L])/(db)(x[L+1]-x[L]);
		}
	}
	
	void build(nod2 **p,int L,int R)
	{
		newnod(p,L,R);
		if(L==R) return ;
		int M=(L+R)>>1;
		build(&(*p)->lc,L,M);
		build(&(*p)->rc,M+1,R);
		(*p)->equal=((*p)->lc->equal&&(*p)->rc->equal&&(*p)->lc->k==(*p)->rc->k);
		(*p)->k=(*p)->lc->k;
	}
	
	void pushdown(nod2 *p)
	{
		if(p->tag==INF) return ;
		if(p->l!=p->r) p->lc->tag=p->rc->tag=p->tag;
		p->equal=1; 
		p->k=p->tag;
		p->tag=INF;
	}
	
	void modify(int L,int R,db K)
	{
		_modify(root,L,R,K);
	}
	
	void _modify(nod2 *p,int L,int R,db K)
	{
		pushdown(p);
		if(p->l==L&&p->r==R)
		{
			p->tag=K;
			return ;
		}
		int M=(p->l+p->r)>>1;
		if(R<=M) _modify(p->lc,L,R,K);
		else if(L>M) _modify(p->rc,L,R,K);
		else
		{
			_modify(p->lc,L,M,K);
			_modify(p->rc,M+1,R,K);
		}
		pushdown(p->lc);
		pushdown(p->rc);
		p->equal=(p->lc->equal&&p->rc->equal&&p->lc->k==p->rc->k);
		p->k=p->lc->k;
	}
	
	int query(int L,int R)
	{
		return _query(root,L,R)!=((db)INF*INF);
	}
	
	db _query(nod2 *p,int L,int R)
	{
		pushdown(p);
		if(p->l==L&&p->r==R) return p->equal?p->k:(db)INF*INF;
		int M=(p->l+p->r)>>1;
		if(R<=M) return _query(p->lc,L,R);
		else if(L>M) return _query(p->rc,L,R);
		else
		{
			db lk=_query(p->lc,L,M),rk=_query(p->rc,M+1,R);
			return lk==rk?lk:(db)INF*INF;
		}
	}
};

int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
	Segtree1 TY;
	Segtree2 TK;
	for(int i=1;i<=q;i++)
	{
		int t,L,R,K,B;
		scanf("%d%d%d",&t,&L,&R);
		if(t==2)
		{
			if(R-L<=1) printf("YES\n");
			else printf("%s\n",TK.query(L,R-1)?"YES":"NO");
		}
		else
		{
			scanf("%d%d",&K,&B);
			TY.modify(L,R,K,B);
			if(L!=R) TK.modify(L,R-1,K);
			if(L!=1) TK.modify(L-1,L-1,(db)(TY.query(L)-TY.query(L-1))/(db)(x[L]-x[L-1]));
			if(R!=n) TK.modify(R,R,(db)(TY.query(R+1)-TY.query(R))/(db)(x[R+1]-x[R]));
		}
	}

	return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct input_checker {
    string buffer;
    int pos;

    const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    const string number = "0123456789";
    const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const string lower = "abcdefghijklmnopqrstuvwxyz";

    input_checker() {
        pos = 0;
        while (true) {
            int c = cin.get();
            if (c == -1) {
                break;
            }
            buffer.push_back((char) c);
        }
    }

    int nextDelimiter() {
        int now = pos;
        while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
            now++;
        }
        return now;
    }

    string readOne() {
        assert(pos < (int) buffer.size());
        int nxt = nextDelimiter();
        string res;
        while (pos < nxt) {
            res += buffer[pos];
            pos++;
        }
        // cerr << res << endl;
        return res;
    }

    string readString(int minl, int maxl, const string& pattern = "") {
        assert(minl <= maxl);
        string res = readOne();
        assert(minl <= (int) res.size());
        assert((int) res.size() <= maxl);
        for (int i = 0; i < (int) res.size(); i++) {
            assert(pattern.empty() || pattern.find(res[i]) != string::npos);
        }
        return res;
    }

    int readInt(int minv, int maxv) {
        assert(minv <= maxv);
        int res = stoi(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

    long long readLong(long long minv, long long maxv) {
        assert(minv <= maxv);
        long long res = stoll(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

    void readSpace() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == ' ');
        pos++;
    }

    void readEoln() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == '\n');
        pos++;
    }

    void readEof() {
        assert((int) buffer.size() == pos);
    }
};

#ifndef ATCODER_LAZYSEGTREE_HPP
#define ATCODER_LAZYSEGTREE_HPP 1

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP 1

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int) (n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
constexpr int bsf_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder

#endif  // ATCODER_INTERNAL_BITOP_HPP

namespace atcoder {

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {
   public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)>
    int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G>
    int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)>
    int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G>
    int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

   private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

}  // namespace atcoder

#endif  // ATCODER_LAZYSEGTREE_HPP

struct S {
    long long x;
    long long k;
    long long b;
    int f;
    int s;
};

S op(S a, S b) {
    a.f += b.f;
    a.s += b.s;
    return a;
}

S e() {
    return S{0, 0, 0, 0, 0};
}

struct F {
    long long k;
    long long b;
    int f;
};

S mapping(F f, S x) {
    if (f.k > 1000000) {
        return x;
    }
    x.k = f.k;
    x.b = f.b;
    x.f = f.f * x.s;
    return x;
}

F composition(F f, F g) {
    if (f.k > 1000000) {
        return g;
    } else {
        return f;
    }
}

F id() {
    return F{10000000, 0, 0};
}

using segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;

int main() {
    input_checker in;
    int n = in.readInt(1, 300000);
    in.readSpace();
    int q = in.readInt(1, 300000);
    in.readEoln();
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) {
        x[i] = in.readInt(-1000000, 1000000);
        in.readSpace();
        y[i] = in.readInt(-1000000, 1000000);
        in.readEoln();
    }
    vector<S> sdef(n);
    for (int i = 0; i < n; i++) {
        sdef[i].x = x[i];
        sdef[i].k = 0;
        sdef[i].b = y[i];
        sdef[i].f = 0;
        sdef[i].s = 1;
    }
    segtree seg(sdef);
    auto Check = [&](int i) {
        if (i <= 0 || i >= n - 1) {
            return false;
        }
        vector<long long> x0, y0;
        for (int j = i - 1; j <= i + 1; j++) {
            auto p = seg.get(j);
            x0.emplace_back(p.x);
            y0.emplace_back(p.x * 1LL * p.k + p.b);
        }
        vector<long long> dx, dy;
        for (int j = 0; j < 2; j++) {
            dx.emplace_back(x0[j + 1] - x0[j]);
            dy.emplace_back(y0[j + 1] - y0[j]);
        }
        return dx[0] * dy[1] == dx[1] * dy[0];
    };
    for (int i = 1; i < n - 1; i++) {
        if (Check(i)) {
            sdef[i].f = 1;
        }
    }
    seg = segtree(sdef);
    while (q--) {
        int op = in.readInt(1, 2);
        in.readSpace();
        int l = in.readInt(1, n);
        in.readSpace();
        int r = in.readInt(l, n);
        l--;
        r--;
        if (op == 1) {
            in.readSpace();
            int k = in.readInt(-1000000, 1000000);
            in.readSpace();
            int b = in.readInt(-1000000, 1000000);
            in.readEoln();
            seg.apply(l, r + 1, F{k, b, 1});
            for (int i : {l, l - 1, r, r + 1}) {
                if (Check(i)) {
                    auto p = seg.get(i);
                    p.f = 1;
                    seg.set(i, p);
                } else if (0 <= i && i < n) {
                    auto p = seg.get(i);
                    p.f = 0;
                    seg.set(i, p);
                }
            }
        } else {
            in.readEoln();
            if (r - l <= 1) {
                cout << "YES" << '\n';
            } else {
                auto p = seg.prod(l + 1, r);
                cout << (p.f == p.s ? "YES" : "NO") << '\n';
            }
        }
    }
    in.readEof();
    return 0;
}
Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const array<ll, 2> inf = {LLONG_MAX, LLONG_MAX};
const array<ll, 2> minf = {LLONG_MIN, LLONG_MIN};

struct Data {
	array<ll, 2> mn = inf, mx = minf;
};
Data unit;

struct Node {
	using T = Data;
	T f(T a, T b) { 
		a.mn = min(a.mn, b.mn);
		a.mx = max(a.mx, b.mx);
		return a;
	}
 
	Node *l = 0, *r = 0;
	int lo, hi;
	T mset = unit;
	T val = unit;
	Node(int _lo,int _hi):lo(_lo),hi(_hi){}
	T query(int L, int R) {
		if (R <= lo || hi <= L) return unit;
		if (L <= lo && hi <= R) return val;
		push();
		return f(l->query(L, R), r->query(L, R));
	}
	void set(int L, int R, T x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) {
			mset = x;
			val = x;
		}
		else {
			push(), l->set(L, R, x), r->set(L, R, x);
			val = f(l->val, r->val);
		}
	}
	void push() {
		if (!l) {
			int mid = lo + (hi - lo)/2;
			l = new Node(lo, mid); r = new Node(mid, hi);
		}
		if (mset.mn != inf or mset.mx != minf)
			l->set(lo,hi,mset), r->set(lo,hi,mset), mset = unit;
	}
};

const array<int, 2> unit2 = {INT_MIN, INT_MIN};
struct Node2 {
	using T = array<int, 2>;
	T f(T a, T b) {
		if (a == unit2) return b;
		return a;
	}
 
	Node2 *l = 0, *r = 0;
	int lo, hi;
	T mset = unit2;
	T val = unit2;
	Node2(int _lo,int _hi):lo(_lo),hi(_hi){}
	T query(int L, int R) {
		if (R <= lo || hi <= L) return unit2;
		if (L <= lo && hi <= R) return val;
		push();
		return f(l->query(L, R), r->query(L, R));
	}
	void set(int L, int R, T x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) {
			mset = x;
			val = x;
		}
		else {
			push(), l->set(L, R, x), r->set(L, R, x);
			val = f(l->val, r->val);
		}
	}
	void push() {
		if (!l) {
			int mid = lo + (hi - lo)/2;
			l = new Node2(lo, mid); r = new Node2(mid, hi);
		}
		if (mset != unit2)
			l->set(lo,hi,mset), r->set(lo,hi,mset), mset = unit2;
	}
};

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	int n, q; cin >> n >> q;
	vector<array<int, 2>> pt(n);
	for (auto &[x, y] : pt) cin >> x >> y;
	Node *slopes = new Node(0, n);
	Node2 *vals = new Node2(0, n);
	for (int i = 0; i+1 < n; ++i) {
		int num = pt[i+1][1] - pt[i][1];
		int den = pt[i+1][0] - pt[i][0];
		int g = gcd(num, den);
		num /= g, den /= g;
		if (den < 0) num *= -1, den *= -1;
		Data cur; cur.mn = cur.mx = array<ll, 2>{num, den};
		slopes -> set(i, i+1, cur);
	}

	while (q--) {
		int type; cin >> type;
		if (type == 1) {
			int l, r, k, b; cin >> l >> r >> k >> b;
			Data cur; cur.mn = cur.mx = {k, 1};
			--l, --r;
			slopes -> set(l, r, cur);
			vals -> set(l, r+1, array{k, b});

			auto upd = [&] (int ind) {
				auto m1 = vals -> query(ind-1, ind);
				auto m2 = vals -> query(ind, ind+1);
				ll y1, y2;
				if (m1 == unit2) y1 = pt[ind-1][1];
				else y1 = 1LL*m1[0]*pt[ind-1][0] + m1[1];
				if (m2 == unit2) y2 = pt[ind][1];
				else y2 = 1LL*m2[0]*pt[ind][0] + m2[1];

				ll num = y2 - y1, den = pt[ind][0] - pt[ind-1][0];
				ll g = gcd(num, den);
				num /= g, den /= g;
				if (den < 0) num *= -1, den *= -1;
				Data cur; cur.mn = cur.mx = array<ll, 2>{num, den};
				slopes -> set(ind-1, ind, cur);
			};
			if (l > 0) upd(l);
			if (r < n-1) upd(r+1);
		}
		else {
			int l, r; cin >> l >> r;
			if (l == r) {
				cout << "Yes\n";
				continue;
			}
			auto res = slopes -> query(l-1, r-1);
			if (res.mn == res.mx) cout << "Yes\n";
			else cout << "No\n";
		}
	}
}

// Let s[i] = slope(i, i+1) = y[i+1] - y[i] /  x[i+1] - x[i]
// Query [L, R] = is s[L] = s[L+1] = ... = s[R-1]
// upd(L, R, K, B) = ?
// s[L] = s[L+1] = ... = s[R-1] = K
// update s[L-1] and s[R] separetely using y values

I think using Chtholly Tree is a more intuitive solution to this problem.