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