LAZER - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Vivek Chauhan
Tester: Suchan Park
Editorialist: William Lin

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Sweep Line, Binary Indexed Tree, Segment Tree

PROBLEM:

There are N points, the i-th point is at (i, A_i). For all 0\le i \le N-2, segment i connects points i and i+1. You are given Q queries (l, r, y), meaning that you need to calculate the number of segments in [l, r) that intersect with the horizontal line with height y.

QUICK EXPLANATION:

Segment i will intersect with the line if \min(A_i, A_{i+1})\le y \le \max(A_i, A_{i+1}). We will sweep over y while maintaining the segments that could be intersected in a data structure while answer queries.

EXPLANATION:

Segment i will be active if it intersects with the horizontal line at y for some query (even if the segment is not within [l, r)). Let the value of a segment be 1 if it is active and 0 if it is inactive. The values of the segments are represented by the array v shown below:

The answer for a query is the number of active segments in [l, r), or the sum of the values of the segments in [l, r). In order to answer the queries efficiently, we will use a sweepline algorithm. The idea of this sweepline algorithm is to imagine a horizontal line sweeping from y=-\infty to y=\infty. At any point in time, the values of the segments should be updated for the current horizontal line. Whenever the horizontal line reaches y_i for some query i, we will answer query i.

There are three types of events:

  1. For each segment i, when the line reaches y=\min(A_i, A_{i+1}), the value of the segment i will become 1.
  2. For each query i, when the line reaches y_i, we will answer query i by adding up the values of the segments in [l, r).
  3. For each segment i, when the line goes over y=\max(A_i, A_{i+1}), the value of the segment i will become 0.

Since the sweepline starts from y=-\infty and moves to y=\infty, we should process the events in increasing order of y. The only thing which remains is to calculate the sum of the values of the segments in [l, r) efficiently for each query. This can be done with any data structure which supports 1. update x_i=v, given i and v 2. find the sum of x_i in a given range. A binary indexed tree or a segment tree will work.

The total time complexity is O(N \log N).

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const ll N = 100005;
char en = '\n';
ll inf = 1e16;
ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
  ll res = 1;
  x %= mod;
  while (n) {
    if (n & 1)
      res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
}
 
struct Event
{
  ll type;
  ll val;
  ll indx;
  Event(ll type, ll val, ll indx):type(type), val(val), indx(indx){}
};
 
 
bool compMin(const Event &a, const Event &b)
{
  if(a.val!=b.val)
    return a.val>b.val;
  else
    return a.type>b.type;
}
 
bool compMax(const Event &a, const Event &b)
{
  if(a.val!=b.val)
    return a.val<b.val;
  else
    return a.type>b.type;
}
 
// initialise bit to 0
// memset(bit,0,sizeof(bit));
// N>=n
// 1 based indexing
// query - prefix sum
ll bit[N];
void update(ll indx, ll val, ll n) {
  while (indx <= n) {
    bit[indx] += val;
    indx += (indx) & (-indx);
  }
}
 
ll query(ll indx) {
  if (indx == 0)
    return 0;
  ll res = 0;
  while (indx >= 1) {
    res += bit[indx];
    indx -= (indx) & (-indx);
  }
  return res;
}
ll query(ll a, ll b) { return query(b) - query(a - 1); }
 
 
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 
 
  ll t;
  cin>>t;
  while(t--)
  {
    ll n,q;
    cin>>n>>q;
    ll arr[n+5];
    for(ll i=1;i<=n;i++)
    {
      cin>>arr[i];
    }
    ll minPt[n+5],maxPt[n+5];
    vector<Event> eventMin;
    vector<Event> eventMax;
 
    for(ll i=1;i<n;i++)
    {
      minPt[i] = min(arr[i], arr[i+1]);
      maxPt[i] = max(arr[i], arr[i+1]);
      eventMin.emplace_back(1,minPt[i],i);
      eventMax.emplace_back(1,maxPt[i],i);
    }
 
    ll queries[q+5][3];
 
    for(ll i=1;i<=q;i++) {
      ll x1, x2, y;
      cin >> x1 >> x2 >> y;
      queries[i][0] = x1,queries[i][1]=x2, queries[i][2]= y;
      eventMin.emplace_back(2, y, i);
      eventMax.emplace_back(2, y, i);
    }
 
    sort(eventMin.begin(), eventMin.end(), compMin);
 
    sort(eventMax.begin(), eventMax.end(), compMax);
    ll ans[q+5];
    memset(ans,0,sizeof(ans));
    memset(bit, 0, sizeof(bit));
 
    for(Event& event: eventMin)
    {
      if(event.type==1)
      {
        update(event.indx, 1, n-1);
      } else
      {
        ll indx = event.indx;
        ans[indx]+=query(queries[indx][0], queries[indx][1]-1);
      }
    }
 
    memset(bit, 0, sizeof(bit));
 
    for(Event& event: eventMax)
    {
      if(event.type==1)
      {
        update(event.indx, 1, n-1);
      } else
      {
        ll indx = event.indx;
        ans[indx]+=query(queries[indx][0], queries[indx][1]-1);
      }
    }
 
    for(ll i=1;i<=q;i++)
    {
      cout<<(queries[i][1]-queries[i][0])-ans[i]<<en;
    }
 
  }
 
  return 0;
}
Tester's Solution
#include <bits/stdc++.h>
 
const int BUFFER_SIZE = int(1.1e5);
 
char _buf[BUFFER_SIZE + 10];
int _buf_pos, _buf_len;
 
char seekChar() {
    if(_buf_pos >= _buf_len) {
        _buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
        _buf_pos = 0;
    }
    assert(_buf_pos < _buf_len);
    return _buf[_buf_pos];
}
 
bool seekEof() {
    if(_buf_pos >= _buf_len) {
        _buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
        _buf_pos = 0;
    }
    return _buf_pos >= _buf_len;
}
 
char readChar() {
    char ret = seekChar();
    _buf_pos++;
    return ret;
}
 
int readInt(int lb, int rb) {
    char c = readChar();
    int mul = 1;
    if(c == '-') {
        c = readChar();
        mul = -1;
    }
    assert(isdigit(c));
 
    long long ret = c - '0';
    char first_digit = c;
    int len = 0;
    while(!seekEof() && isdigit(seekChar()) && ++len <= 19) {
        ret = ret * 10 + readChar() - '0';
    }
    ret *= mul;
 
    if(len >= 2) assert(first_digit != '0');
    assert(len <= 18);
    assert(lb <= ret && ret <= rb);
    return (int)ret;
}
 
void readEoln() {
    char c = readChar();
    //assert(c == '\n');
    assert(c == '\n' || (c == '\r' && readChar() == '\n'));
}
 
void readSpace() {
    assert(readChar() == ' ');
}
 
struct Event {
    int y, x, t;
};
 
int A[int(1.1e5)];
 
int ans[int(1.1e5)];
int X1[int(1.1e5)], X2[int(1.1e5)];
 
int tree[int(1.1e5)];
void add(int x, int v) {
    for(; x <= int(1e5); x += x & -x) tree[x] += v;
}
int get(int x) {
    int ret = 0;
    while(x > 0) {
        ret += tree[x];
        x &= x-1;
    }
    return ret;
}
int get(int x, int y) {
    return get(y) - get(x-1);
}
 
void run() {
    int N = readInt(2, 100000);
    readSpace();
    int Q = readInt(1, 100000);
    readEoln();
 
    for(int i = 1; i <= N; i++) {
        A[i] = readInt(1, int(1e9));
        if(i + 1 <= N) readSpace(); else readEoln();
    }
 
    std::vector<Event> events;
    for(int i = 1; i+1 <= N; i++) {
        int y1 = std::min(A[i], A[i+1]);
        events.push_back({y1, i, +1});
    }
 
    std::fill(ans+1, ans+Q+1, 0);
    for(int q = 1; q <= Q; q++) {
        int x1, x2, y;
        x1 = readInt(1, N);
        readSpace();
        x2 = readInt(1, N);
        readSpace();
        assert(x1 < x2);
        y = readInt(1, int(1e9));
        readEoln();
 
        X1[q] = x1;
        X2[q] = x2;
        events.push_back({y, -1, q});
    }
 
    for(int i = 1; i+1 <= N; i++) {
        int y2 = std::max(A[i], A[i+1]);
        events.push_back({y2, i, -1});
    }
 
    std::stable_sort(events.begin(), events.end(), [&](const Event &e1, const Event &e2) { return e1.y < e2.y; });
 
    memset(tree, 0, sizeof tree);
    for(const Event &event : events) {
        if(event.x > 0) {
            add(event.x, event.t);
        }else {
            ans[event.t] += get(X1[event.t], X2[event.t] - 1);
        }
    }
 
    for(int q = 1; q <= Q; q++) {
        printf("%d\n", ans[q]);
    }
}
 
int main() {
#ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    freopen("input.txt", "r", stdin);
#endif
 
    int T = readInt(1, 100);
    readEoln();
 
    while(T--) {
        run();
    }
    return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

const int mxN=1e5;
int n, q, a[mxN], ans[mxN], ql[mxN], qr[mxN], qy[mxN], ft[mxN];

void upd(int i, int x) {
	for(++i; i<n; i+=i&-i)
		ft[i]+=x;
}

int qry(int i) {
	int r=0;
	for(; i; i-=i&-i)
		r+=ft[i];
	return r;
}

struct event {
	int y, t, i;
	bool operator<(const event &o) const {
		return make_pair(y, t)<make_pair(o.y, o.t);
	}
};

void solve() {
	//input
	cin >> n >> q;
	for(int i=0; i<n; ++i)
		cin >> a[i];
	for(int i=0; i<q; ++i)
		cin >> ql[i] >> qr[i] >> qy[i], --ql[i], --qr[i];

	vector<event> ve;
	//create events for the segments
	for(int i=0; i+1<n; ++i) {
		//add segment
		ve.push_back({min(a[i], a[i+1]), 1, i});
		//remove segment
		ve.push_back({max(a[i], a[i+1]), 3, i});
	}
	//create events for the queries
	for(int i=0; i<q; ++i)
		ve.push_back({qy[i], 2, i});

	//process events
	sort(ve.begin(), ve.end());
	for(event e : ve) {
		if(e.t==1) {
			//add segment
			upd(e.i, 1);
		} else if(e.t==2) {
			//answer query
			ans[e.i]=qry(qr[e.i])-qry(ql[e.i]);
		} else {
			//remove segment
			upd(e.i, -1);
		}
	}

	//output
	for(int i=0; i<q; ++i)
		cout << ans[i] << "\n";
}

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

	int t;
	cin >> t;
	while(t--)
		solve();
}

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

15 Likes

Could anyone explain how this statement works?

Thanks

1 Like

Thats overloading “<” operator to make std::sort() works.

2 Likes

Can anyone explain, how this works ??
Thanks in advance to the one who will help me…

Hello William

According my understanding, you use segment tree to compute range sum of v. But i don’t understand your implementation. Especially the implementation trick “i+= i & -i” in upd() function. Similar with “i -= i & -i” in qry() function.

I found 2 links of segment tree implementation:
https://cp-algorithms.com/data_structures/segment_tree.html

Do you have a link that reuse your implementation trick ?

Regard

Jean

struct event {
	int y, t, i;
	bool operator<(const event &o) const {
		return make_pair(y, t)<make_pair(o.y, o.t);
	}
};

can someone provide python implementation of the above code or python implementation of whole code as I do not know c++.Most of the python submissions are not 100pts.
thanks in advance

Can anybody suggest a good blog or video wherefrom I can learn about SweepLine Algorithm?

BIT is used

Hello Kumar

this link explain the BIT.

Thank you :slight_smile:

best explanation for BIT

1 Like

can someone explain me how is this sorting working and why there is a need to sort and what is the approach to solve it

1 Like

This particular portion has to do with Operator overloading.

Provided possible links for understanding it.

Followed by comparision of structures.

Also thanks for the awesome editorial!

My submission with segment tree. (Its about the same as William’s code I just switched BIT for segment tree)

https://www.codechef.com/viewsolution/30887786

https://www.codechef.com/viewsolution/31267102

Can any plz find whats wrong with code or logic?

Please do also made a tutorial on line sweep algorithm. I am not finding any proper resources for it.