№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

I finally figured out a nice way to implement dynamic convex hull that has a reasonable constant factor! I wouldn't be surprised if this is "well known in China" though.

Consider the problem of finding nested convex hulls in $$$O(n\log^2{n})$$$. The simplest way I know of is to make a convex hull data structure that supports point deletions, which is what I do here. It should in theory be possible to extend this implementation handle insertions as well.

This implementation is based on this paper by Overmars and van Leeuwen that describes a data structure for online fully dynamic convex hull in $$$O(\log^2{n})$$$ per operation. Directly implementing that is complicated and has a bad constant factor, so we'll do it a bit differently using ideas from FizzyDavid's solution to 1270H.

The data structure

We need a data structure for points in the plane that can support

deleting a point in $$$O(\log^2{n})$$$
returning the convex hull of k points in $$$O(k\log^2{n})$$$ time

The left and right hulls are handled separately. From now on, we'll only consider the left hull.

We can build the left hull using a divide and conquer strategy:

Split the points in half by y-coordinate.
Recursively build the hull for both halves
Find a "bridge" that connects the two hulls. This can be done in $$$O(\log{n})$$$ with a binary search.
Merge the two hulls with the bridge. Edges covered by the bridge are discarded.

To make this dynamic, we can turn this divide and conquer into a segment tree.

The paper explicitly stores the convex hull in a balanced binary search tree that supports split and concatenate in $$$O(\log^2{n})$$$. We'll instead implicitly represent the convex hull of each node in a segment tree.

Each node of the segment tree must store

Pointers to its left and right children
The bridge between the convex hulls of its children
The bottommost point of its leaves

In a leaf node, we just pretend the bridge is between the point and itself.

Interestingly, computing the bridge can be done by querying its children in $$$O(\log{n})$$$.

Finding the bridge efficiently

A node of the segment tree must be able to compute the bridge of its children's convex hulls efficiently.

The paper has $$$10$$$ cases, but I think we only need $$$6$$$.

We have two segment tree nodes $$$p$$$ and $$$q$$$ that we want to find the bridge between. Let $$$a$$$ and $$$b$$$ be the points of the bridge of the first node and $$$c$$$ and $$$d$$$ be the points of the bridge of the second node.

Repeat the following until both $$$p$$$ and $$$q$$$ are leaves.

If $$$a\ne b$$$ ($$$p$$$ is not a leaf) and $$$a,b,c$$$ is in counterclockwise order, we can discard $$$b$$$ and all points above it. Set $$$p$$$ to $$$p$$$'s first child.
If $$$c\ne d$$$ and $$$b,c,d$$$ is in counterclockwise order, we can discard $$$c$$$ and all points below it. Set $$$q$$$ to $$$q$$$'s second child.
Otherwise, if $$$a=b$$$, we can discard $$$d$$$ and all points above it. Set $$$q$$$ to $$$q$$$'s first child.
Otherwise, if $$$c=d$$$, we can discard $$$a$$$ and all points below it. Set $$$p$$$ to $$$p$$$'s second child.
If we get here, $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ are clockwise. Consider any horizontal line through the first point of $$$q$$$ separates the two hulls. Depending on which side of the line the intersection of lines $$$ab$$$ and $$$cd$$$ are, we can either discard $$$a$$$ and all points below it, or $$$d$$$ and all points above it. We either set $$$p$$$ to $$$p$$$'s second child or set $$$q$$$ to $$$q$$$'s first child.

After every iteration, we move either $$$p$$$ or $$$q$$$ to its children, so this process must terminate in $$$O(\log{n})$$$ iterations.

Extracting the convex hull

To compute the convex hull, we define a recursive function that does the following:

Given a node and two points $$$l$$$ and $$$r$$$ on the convex hull of the node, output the points on the convex hull between them, inclusive.

We just need to handle a few cases.

If the bridge is contained between $$$l$$$ and $$$r$$$, we recurse on both children
If the bridge is fully covered, we recurse on the child that isn't covered.

It is impossible for the bridge to be partially covered.

Implementation

Code

//"segment tree"-style implementation of online decremental dynamic convex hull
//Based on paper "Maintenance of configurations in the plane" by Overmars and van Leeuwen, with some modifications
//This implementation only supports efficient (O(log^2n)) deletion of points, which is enough to compute nested convex hulls in O(nlog^2n).
//It should be possible to modify this to support insertions as well.

//Assumes all points are distinct
//Assumes coordinates are at most 10^6
//Can handle 200000 points in a few seconds.

#include <cstdio>
#include <vector>
#include <map>
#include <stdint.h>
#include <algorithm>
#include <cassert>
#include <set>

struct Point{
  int64_t x,y;
  Point operator-(Point p)const{
    return {x-p.x,y-p.y};
  }
  int64_t cross(Point p)const{
    return x*p.y-y*p.x;
  }
  int64_t dot(Point p)const{
    return x*p.x+y*p.y;
  }
  bool operator<(Point p)const{
    if(y!=p.y) return y<p.y;
    return x<p.x;
  }
  bool operator==(Point p)const{
    return x==p.x&&y==p.y;
  }
  Point operator-()const{
    return {-x,-y};
  }
};

int64_t cross(Point a,Point b,Point c){
  return (b-a).cross(c-a);
}


class LeftHull{
  std::vector<Point> ps;
  struct Node{
    int bl,br;
    int L,R;
    int lchd,rchd;
  };
  std::vector<Node> nodes;
  int root;
  bool isleaf(int w){
    return nodes[w].lchd==-1&&nodes[w].rchd==-1;
  }
  void pull(int w){
    assert(!isleaf(w));
    int l=nodes[w].lchd,r=nodes[w].rchd;
    int64_t split_y=ps[nodes[r].L].y;
    while(!isleaf(l)||!isleaf(r)){
      int a=nodes[l].bl,b=nodes[l].br,
	c=nodes[r].bl,d=nodes[r].br;
      if(a!=b && cross(ps[a],ps[b],ps[c])>0){
	l=nodes[l].lchd;
      }else if(c!=d && cross(ps[b],ps[c],ps[d])>0){
	r=nodes[r].rchd;
      }else if(a==b){
	r=nodes[r].lchd;
      }else if(c==d){
	l=nodes[l].rchd;
      }else{
	int64_t s1=cross(ps[a],ps[b],ps[c]);
	int64_t s2=cross(ps[b],ps[a],ps[d]);
	assert(s1+s2>=0);
	if(s1+s2==0||s1*ps[d].y+s2*ps[c].y<split_y*(s1+s2)){
	  l=nodes[l].rchd;
	}else{
	  r=nodes[r].lchd;
	}
      }
    }
    nodes[w].bl=nodes[l].L;
    nodes[w].br=nodes[r].L;
  }
  void build(int w,int L,int R){
    nodes[w].L=L;
    nodes[w].R=R;
    if(R-L==1){
      nodes[w].lchd=nodes[w].rchd=-1;
      nodes[w].bl=nodes[w].br=L;
    }else{
      int M=(L+R)/2;
      nodes[w].lchd=w+1;
      nodes[w].rchd=w+2*(M-L);
      build(nodes[w].lchd,L,M);
      build(nodes[w].rchd,M,R);
      pull(w);
    }
  }
  int erase(int w,int L,int R){
    if(R<=nodes[w].L||L>=nodes[w].R) return w;
    if(L<=nodes[w].L&&R>=nodes[w].R) return -1;
    nodes[w].lchd=erase(nodes[w].lchd,L,R);
    nodes[w].rchd=erase(nodes[w].rchd,L,R);
    if(nodes[w].lchd==-1) return nodes[w].rchd;
    if(nodes[w].rchd==-1) return nodes[w].lchd;
    pull(w);
    return w;
  }
  //only works for whole hull
  void get_hull(int w,int l,int r,std::vector<int>& res){
    if(isleaf(w)){
      res.push_back(nodes[w].L);
    }else if(r<=nodes[w].bl){
      get_hull(nodes[w].lchd,l,r,res);
    }else if(l>=nodes[w].br){
      get_hull(nodes[w].rchd,l,r,res);
    }else{
      assert(l<=nodes[w].bl&&nodes[w].br<=r);
      get_hull(nodes[w].lchd,l,nodes[w].bl,res);
      get_hull(nodes[w].rchd,nodes[w].br,r,res);
    }
  }
public:
  LeftHull(const std::vector<Point>& ps):ps(ps),nodes(ps.size()*2),root(0){
    build(0,0,ps.size());
  }
  std::vector<int> get_hull(){
    if(root==-1) return {};
    std::vector<int> res;
    get_hull(root,0,ps.size()-1,res);
    return res;
  }
  void erase(int L){
    root=erase(root,L,L+1);
  }
};

std::vector<Point> ps;
std::map<Point,int> id;
int layer[1000005];
int ans[1000005];

int main(){
  int N;
  scanf("%d",&N);
  for(int i=0;i<N;i++){
    int X,Y;
    scanf("%d %d",&X,&Y);
    ps.push_back({X,Y});
    id[{X,Y}]=i;
  }
  
  std::sort(ps.begin(),ps.end());
  struct LeftHull left(ps);
  std::reverse(ps.begin(),ps.end());
  for(auto& p:ps){
    p=-p;
  }
  struct LeftHull right(ps);
  for(auto& p:ps){
    p=-p;
  }
  std::reverse(ps.begin(),ps.end());
  for(int l=1,cnt=0;cnt<N;l++){
    std::set<int> hull;
    for(int i:left.get_hull()){
      hull.insert(i);
    }
    for(int i:right.get_hull()){
      hull.insert(N-1-i);
    }
    for(int i:hull){
      assert(!layer[i]);
      cnt++;
      layer[i]=l;
      left.erase(i);
      right.erase(N-1-i);
    }
  }
  for(int i=0;i<N;i++){
    ans[id[ps[i]]]=layer[i];
  }
  for(int i=0;i<N;i++){
    printf("%d\n",ans[i]);
  }
}

Questions

Can all problems solvable by Overmars and van Leeuwen's technique be solved by this type of segment tree?