Codeforces 678F - Lena and Queries

Problem Statement:
http://codeforces.com/contest/678/problem/F

Summary:
There are n <= 300000 queries of the form: add lines ax+b, remove line ax+b, and the maximum intersection between vertical line x = q and all lines.



Solution:
This problem can be solved by partitioning the queries into sqrt(n) blocks. Proceed from first block of queries to the last. We will answer each of query of the third type in O(sqrt(N) + log(N)).

Suppose we are currently processing block i. In current block, find all the queries of second type where we delete a line from previous blocks. The idea is to move these deleted lines into current block, as if we have created it in this current block i.

Next we iterate through all lines created in the previous blocks 1, 2, .., i-1, which has not been deleted in block i, and build a "convex-hull" like structure where we keep track of the top lines and the intersection points of those top lines. (What I mean by top lines are, if you draw several linear lines and trace the highest intersection with every vertical lines x = q, you will get segments of top lines).

This can be done by going through the lines in sorted order (in increasing gradient a, and followed by increasing b to break ties). Keep a stack of lines S. For each line L, we pop the stack until we find the case where the intersection between S.top() and L is in front of the intersection between the two lines on the top of S. S will in the end define the convex-hull structure, where all lines in S are top lines for various values of x. This construction takes O(N).

To answer the queries of the third type in current block i, we first collect and sort those queries. Since there are at most sqrt(N) of them in current block, sorting will take O(sqrt(N) log (N)). Then we go through the convex-hull structure from left to right, iterating through the top lines one by one and if current query is on the line, we can compute aq+b for that query and move on. Iterating two sorted lists in this fashion takes O(N).

However for each query we also need to compare the result from the convex-hull with all the lines in the current block. Since there are at most sqrt(N) lines in current block, we can iterate through them one by one and compute the max aq+b among the lines in the current block in O(sqrt(N)). Deletion can also be handled in O(1) by using a flag array. Hence overall in the current block we will perform O(N + sqrt(N) log (N)) operations. Overall, since there are O(sqrt(N)) blocks, the run time complexity is O(N sqrt(N) + N log N).

Implementation:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
#include <cmath>
#include <cstring>
using namespace std;
constexpr int N = 300010;
constexpr int64_t MIN_INF = -1234567891234567891LL;
struct Request {
  int type;
  int key;
};
int n, num_lines, num_reqs, sz;
pair<int,int> lines[N];
Request requests[N];
vector<int> sstable;
vector<int> sstable_index;
void SortLines() {
  for(int i=0;i<num_lines;++i){
    sstable.push_back(i);
  }
  sort(sstable.begin(), sstable.end(),
      [](int i, int j) {
        if (lines[i].first == lines[j].first) {
          return lines[i].second < lines[j].second;
        }
        return lines[i].first < lines[j].first;
      });
  sstable_index.resize(num_lines,0);
  for(int i=0;i<num_lines;++i){
    sstable_index[sstable[i]]=i;
  }
}
vector<int> cur_block;
int in_block[N];
int in_hull[N];
vector<pair<int,int>> queries;
vector<int> convex_hull;
vector<int64_t> final_ans;
int num_query=0;
int block_cnt=0;
void ProcessQueries(int beg, int end) {
  ++block_cnt;
  cur_block.clear();
  queries.clear();
  for (int i=beg;i<=end;++i){
    if (requests[i].type == 2) {
      if (requests[i].key >= beg) continue;
      int key = requests[i].key;
      in_block[requests[key].key] = block_cnt;
      in_hull[sstable_index[requests[key].key]] = 0;
      cur_block.push_back(requests[key].key);
    } else if (requests[i].type == 3) {
      queries.push_back({requests[i].key, final_ans.size()});
      final_ans.push_back(MIN_INF);
    }
  }
  for (int i=beg-sz;i<beg;++i){
    if (requests[i].type == 1) {
      if (in_block[requests[i].key] == block_cnt) continue;
      in_hull[sstable_index[requests[i].key]] = 1;
    } else if (requests[i].type == 2) {
      int key = requests[i].key;
      in_hull[sstable_index[requests[key].key]] = 0;
    }
  }
  convex_hull.clear();
  int a,b,a1,a2,b1,b2;
  for (int i=0;i<num_lines; ++i) {
    if (!in_hull[i]) continue;
    a = lines[sstable[i]].first;
    b = lines[sstable[i]].second;
    while (!convex_hull.empty()) {
      a1 = lines[convex_hull.back()].first;
      b1 = lines[convex_hull.back()].second;
      if (a == a1) {
        convex_hull.pop_back();
        continue;
      }
      if (convex_hull.size() == 1) {
        break;
      }
      a2 = lines[convex_hull[convex_hull.size()-2]].first;
      b2 = lines[convex_hull[convex_hull.size()-2]].second;
      if ((1LL*b1-b2)*(1LL*a1-a) < (1LL*a2-a1)*(1LL*b-b1)) break;
      convex_hull.pop_back();
    }
    convex_hull.push_back(sstable[i]);
  }
  sort(queries.begin(), queries.end());
  int j=0;
  for (int i=0;i<queries.size() && !convex_hull.empty();++i){
    while (1) {
      a = lines[convex_hull[j]].first;
      b = lines[convex_hull[j]].second;
      if (j+1 < convex_hull.size()) {
        int a1 = lines[convex_hull[j+1]].first;
        int b1 = lines[convex_hull[j+1]].second;
        if ((1LL*b-b1)>=(1LL*a1-a)*queries[i].first) {
          break;
        }
        ++j;
      } else break;
    }
    final_ans[queries[i].second] = 1LL*a*queries[i].first+b;
  }
  int num_deleted = 0;
  for (int i=beg;i<=end;++i){
    if (requests[i].type==1) {
      cur_block.push_back(requests[i].key);
      in_block[requests[i].key]=block_cnt;
    } else if (requests[i].type==2) {
      int key = requests[i].key;
      in_block[requests[key].key]=0;
      ++num_deleted;
    } else {
      if (cur_block.size() == num_deleted) {
        ++num_query;
        continue;
      }
      for (int j=0;j<cur_block.size();++j){
        if (in_block[cur_block[j]] != block_cnt) continue;
        final_ans[num_query] = max(final_ans[num_query], 1LL*requests[i].key*lines[cur_block[j]].first+lines[cur_block[j]].second);
      }
      ++num_query;
    }
  }
}
void Solve() {
  sz = sqrt(n);
  for(int i=0;i<n;i+=sz){
    ProcessQueries(i, min(i+sz-1,n-1));
  }
}
int main(){
  scanf("%d",&n);
  int t,a,b;
  for (int i=0;i<n;++i){
    scanf("%d",&t);
    if (t == 1) {
      scanf("%d%d",&a,&b);
      lines[num_lines++] = {a,b};
      requests[num_reqs++] = {t, num_lines-1};
    } else {
      scanf("%d",&a);
      if (t==2) {
        requests[num_reqs++] = {t, a-1};
      } else {
        requests[num_reqs++] = {t, a};
      }
    }
  }
  SortLines();
  Solve();
  for(int i=0;i<final_ans.size();++i){
    if (final_ans[i] == MIN_INF) printf("EMPTY SET\n");
    else printf("%I64d\n", final_ans[i]);
  }
  return 0;
}

Observation: Sometimes the act of partitioning queries/data into chunks (of sqrt(N) in size for example) can result in an interesting solution with cool time complexity.

Note: Apparently it is possible to solve this problem using a segment tree, which is way shorter and way faster than the above approach.