描述

给出 $N (N \leq 100000)$ 个点 $(x, y)$ ，有 $Q (Q \leq 100000)$ 个询问，分别是
1. 在点集里添加一个点
2. 给出一个点，查询它到点集里所有点的曼哈顿距离的最小值
3. 给出一个点，查询它到点集里所有点的曼哈顿距离的最大值

分析

终于对了！！！

对于绝对值，可以考虑拆分。

M a n h a t t a n D i s t a n c e = {\begin{array}{rcl} (x_{i} + y_{i}) - (x_{j} - y_{j}) & x_{i} \geq x_{j}, y_{i} \geq y_{j} \\ (x_{i} - y_{i}) - (x_{j} - y_{j}) & x_{i} \geq x_{j}, y_{i} \leq y_{j} \\ (y_{I} - x_{i}) + (y_{j} - x_{j}) & x_{i} \leq x_{j}, y_{i} \geq y_{j} \\ - (x_{i} + y_{i}) + (x_{j} - y_{j}) & x_{i} \leq x_{j}, y_{i} \leq y_{j} \end{array}

很显然，一个曼哈短距离可以用两个点各自横纵坐标之和或差相减表示出来。

维护线段树 $M a x s u m, M i n s u m, M a x d i f, M i n d i f$ 分别表示一个点最大/最小的横纵坐标之和，最大/最小的横纵坐标之差。

考虑没有加点操作的情况。

首先把点集和查询放在一起按照 $x$ 坐标排序，（经典套路，技巧！！！）这样就保证了 $x$ 的有序，可以说忽略了 $x$ 的顺序影响，但相反就有了时间顺序的影响。

每次遇到一个点，尝试用它来修改四棵线段树中 $y$ 位置上的值。

遇到一个询问，因为 $x$ 的有序，且每次都是放在线段树的 $y$ 位置上，很方便可以通过上述四大分类来求得答案。

如果有加点操作呢？

尝试使用 $C D Q$ 分治。

我们对时间分治，即对时间排序。原点集也可以视为加 $n$ 次点。

$l, r$ 表示我们进行操作的区间。首先先递归 $[l, m i d], [m i d + 1, r]$ ，扫一遍 $[l, m i d]$ 记录中的加点操作，视为点集。扫一遍 $[m o d + 1, r]$ 的查询操作，用上述不加点的方式来处理左边的修改对右边的影响。这也是 $C D Q$ 分治的重要思想。

到底优化了哪里呢？？？按照了时间分治，这样保证了每次分治出来的点中，（左边一半的）加点操作必定影响（右边一半的）查询操作，再按照 $x$ 排序，一个三维（时间， $x, y$ 轴）的问题，通过增加了 $l o g_{2} n$ 的时间，减少为一维。可以说绝逼巧妙！！大我 $C D Q$ 哉！

一时半会十分难解释其精髓，还是要靠刷题~~看代码~~。对 $y$ 做离散化。

时间复杂度 $O (n (l o g_{2} n)^{2})$

代码

献丑了。

{$inline on}
uses math;
const
        maxn=200000;
        maxnn=maxlongint*maxint;
var
        n,m,i:longint;
        a,s:array[0..200000,0..4] of longint;
        ans:array[0..200000] of int64;
        tree:array[0..3*maxn,1..4] of int64;
procedure lsh;
var
        i,now:longint;
        p,yuan:array[0..200000] of longint;
procedure q(l,r:longint);
var
        i,j,t,mid:longint;
begin
        i:=l;
        j:=r;
        mid:=p[(l+r) shr 1];

        while i<j do
        begin
                while p[i]<mid do inc(I);
                while p[j]>mid do dec(j);

                if i<=j then
                begin
                        t:=p[i]; p[i]:=p[j]; p[j]:=t;
                        t:=yuan[i]; yuan[i]:=yuan[j]; yuan[j]:=t;

                        inc(i); dec(j);
                end;
        end;

        if i<r then q(i,r);
        if l<j then q(l,j);
end;
begin
        for i:=1 to n+m do
        begin
                yuan[i]:=i; p[i]:=a[i,2];
        end;

        q(1,n+m);

        now:=0; p[0]:=-1;

        for i:=1 to n+m do
        begin
                if p[i]<>p[i-1] then inc(now);

                a[yuan[i],4]:=now;
        end;
end;

procedure q(l,r:longint);
var
        i,j,mid:longint;
begin
        i:=l;
        j:=r;
        mid:=s[(l+r) shr 1,1];

        while i<j do
        begin
                while s[i,1]<mid do inc(I);
                while s[j,1]>mid do dec(j);

                if i<=j then
                begin
                        s[0]:=s[i]; s[i]:=s[j]; s[j]:=s[0];

                        inc(I); dec(J);
                end;
        end;

        if i<r then q(i,r);
        if l<j then q(l,j);
end;

procedure change(root,l,r,x,y:longint);
var
        mid:longint;
begin
        if (l=r) and (r=x) then
        begin
                tree[root,1]:=max(tree[root,1],s[y,1]+s[y,2]); tree[root,2]:=min(tree[root,2],s[y,1]+s[y,2]);
                tree[root,3]:=max(tree[root,3],s[y,1]-s[y,2]); tree[root,4]:=min(tree[root,4],s[y,1]-s[y,2]);

                exit;
        end;

        mid:=(l+r) shr 1;

        if x<=mid then
                change(root*2,l,mid,x,y)
        else
                change(root*2+1,mid+1,r,x,y);

        tree[root,1]:=max(tree[root*2,1],tree[root*2+1,1]); tree[root,2]:=min(tree[root*2,2],tree[root*2+1,2]);
        tree[root,3]:=max(tree[root*2,3],tree[root*2+1,3]); tree[root,4]:=min(tree[root*2,4],tree[root*2+1,4]);
end;

function find(root,l,r,x,y,t:longint):int64;
var
        mid:longint;
begin
        if abs(tree[root,t])=maxnn then
                exit(tree[root,t]);

        if (l=x) and (r=y) then
                exit(tree[root,t]);

        mid:=(l+r) shr 1;

        if y<=mid then
                exit(find(root*2,l,mid,x,y,t))
        else
        if x>mid then
                exit(find(root*2+1,mid+1,r,x,y,t))
        else
                if (t=1) or (t=3) then
                        exit(max(find(root*2,l,mid,x,mid,t),find(root*2+1,mid+1,r,mid+1,y,t)))
                else
                        exit(min(find(root*2,l,mid,x,mid,t),find(root*2+1,mid+1,r,mid+1,y,t)));
end;

procedure clear(root,l,r,x:longint);
var
        i,mid:longint;
begin
        tree[root,1]:=-maxnn; tree[root,3]:=-maxnn;
        tree[root,2]:=maxnn; tree[root,4]:=maxnn;

        if l=r then exit;

        mid:=(l+r) shr 1;

        if x<=mid then
                clear(root*2,l,mid,x)
        else
                clear(root*2+1,mid+1,r,x);
end;

procedure cdq(l,r:longint);
var
        now:int64;
        i,y,mid,tot,sum,dif:longint;
begin
        if l=r then exit;

        mid:=(l+r) shr 1;

        cdq(l,mid); cdq(mid+1,r);

        tot:=0;

        for i:=l to mid do
                if a[i,0]=0 then
                begin
                        inc(tot); s[tot]:=a[i]; s[tot,3]:=i;
                end;

        for i:=mid+1 to r do
                if a[i,0]>0 then
                begin
                        inc(tot); s[tot]:=a[i]; s[tot,3]:=i;
                end;

        q(1,tot);

        for i:=1 to tot do
        begin
                y:=s[i,4];

                sum:=s[i,1]+s[i,2]; dif:=s[i,1]-s[i,2];

                if s[i,0]=0 then
                        change(1,1,maxn,y,i)
                else
                if s[i,0]=1 then
                begin
                        now:=sum-find(1,1,maxn,1,y,1);

                        if now>=0 then ans[s[i,3]]:=min(ans[s[i,3]],now);

                        now:=dif-find(1,1,maxn,y,maxn,3);

                        if now>=0 then ans[s[i,3]]:=min(ans[s[i,3]],now);
                end
                else
                begin
                        now:=sum-find(1,1,maxn,1,y,2);

                        if now>=0 then ans[s[i,3]]:=max(ans[s[i,3]],now);

                        now:=dif-find(1,1,maxn,y,maxn,4);

                        if now>=0 then ans[s[i,3]]:=max(ans[s[i,3]],now);
                end;
        end;

        for i:=1 to tot do
                if s[i,0]=0 then
                        clear(1,1,maxn,s[i,4]);

        for i:=tot downto 1 do
        begin
                y:=s[i,4];

                sum:=s[i,1]+s[i,2]; dif:=s[i,1]-s[i,2];

                if s[i,0]=0 then
                        change(1,1,maxn,y,i)
                else
                if s[i,0]=1 then
                begin
                        now:=-dif+find(1,1,maxn,1,y,4);

                        if now>=0 then ans[s[i,3]]:=min(ans[s[i,3]],now);

                        now:=-sum+find(1,1,maxn,y,maxn,2);

                        if now>=0 then ans[s[i,3]]:=min(ans[s[i,3]],now);
                end
                else
                begin
                        now:=-dif+find(1,1,maxn,1,y,3);

                        if now>=0 then ans[s[i,3]]:=max(ans[s[i,3]],now);

                        now:=-sum+find(1,1,maxn,y,maxn,1);

                        if now>=0 then ans[s[i,3]]:=max(ans[s[i,3]],now);
                end;
        end;

        for i:=1 to tot do
                if s[i,0]=0 then
                        clear(1,1,maxn,s[i,4]);
end;
begin
        assign(Input,'s.in');reset(input);

        readln(n);

        for i:=1 to n do
                readln(a[i,1],a[i,2]);

        readln(m);

        for i:=1 to m do
                readln(a[i+n,0],a[i+n,1],a[i+n,2]);

        lsh;

        for i:=1 to n+m do
                if a[i,0]=1 then
                        ans[i]:=maxlongint
                else
                        ans[i]:=-maxlongint;

        for i:=1 to 3*maxn do
        begin
                tree[i,1]:=-maxnn; tree[i,3]:=-maxnn;
                tree[i,2]:=maxnn; tree[i,4]:=maxnn;
        end;

        cdq(1,n+m);

        for i:=n+1 to n+m do
                if a[i,0]<>0 then
                        writeln(ans[i]);
end.

秒客网

JZOJ 3591 - 【NOI2014模拟】数据

描述

分析

代码

相关文章