bzoj 2739 最远点——分治处理决策单调性

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2739

分治处理决策单调性的思想就是先找到一个询问，枚举所有可能的转移找到它的决策点，那么这个询问之前的询问的决策点就是在该决策点之前（含）的，这个询问之后的询问的决策点就是在该决策点之后（含）的。

但是有那个“（含）”，所以复杂度可能被卡？

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

ll Sqr(int a){return (ll)a*a;}

const int N=5e5+;

int n,x[N<<],y[N<<],ans[N];

bool cz(int bh,int u,int v)

{

  if(u<bh||u>bh+n)return false;//u<bh!!! u>.. not u>=...

  if(v<bh||v>bh+n)return true;

  ll a=Sqr(x[u]-x[bh])+Sqr(y[u]-y[bh]);

  ll b=Sqr(x[v]-x[bh])+Sqr(y[v]-y[bh]);

  return a>b;

}

void solve(int l,int r,int L,int R)

{

  if(l>r)return; int mid=l+r>>,ret=L;

  for(int i=L+;i<=R;i++)if(cz(mid,i,ret))ret=i;

  ans[mid]=ret;

  solve(l,mid-,L,ret); solve(mid+,r,ret,R);

}

int main()

{

  int T=rdn();

  while(T--)

    {

      n=rdn();

      for(int i=;i<=n;i++)

    x[i]=x[i+n]=rdn(), y[i]=y[i+n]=rdn();

      solve(,n,,n<<);

      for(int i=;i<=n;i++)printf("%d\n",ans[i]>n?ans[i]-n:ans[i]);

    }

  return ;

}