数据结构之——线段树(2)

??? 学习了上一节线段树的基本操作之后，再用例题详细讨论线段树的Lazy操作的精髓。

1. 矩形面积并。POJ1389 / HDU1542

??? 题意：矩形面积并是给出n个矩形(边都平行于x轴或y轴)，这些矩形可能会相互重合，求出总的覆盖面积。

??? 分析： 通过画图并观察，在x轴方向扫描这些矩形，发现只需要记录前面边的重合（有效）长度，比如有两条边，分别为[2,4], [3,8]，那么他们的有效长度为6。矩形的左边(入边)为1，右边(出边)为-1。现在就需要如何维护这些线段的有效长度了。可以想到用线段树来维护，因为它的插入和删除都是logn级别的。

??? 解：a. 将点y坐标升序排序，离散化并去重，构建线段树，注意叶子节点区间长度为1。

????????? b. 将扫描线(矩形的左右边)按x升序排序，依次插入线段树中，维护有效距离。

????????? c. 面积 += 整个区间的有效长度 * (下一条扫描线的x坐标-本条线的x坐标)。

??? 可见，如何维护有效距离是本问题的关键。

??? 一种简单的方法是每次更新到叶子节点，但这样发挥不出线段树的优势，没有用到lazy思想。

??? 可以设置两个变量len和cover，len表示该区间的有效长度，cover代表该区间是否被完全覆盖(0表示未被完全覆盖，>=1表示被完全覆盖)。当cover>=1时，len=y[r]-y[l]；否则，如果是叶子节点，则len=0；否则，len=len[l]+len[r]。

??? 实质：区间累加+统计区间有效长度

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define LL(x) ((x)<<1)#define RR(x) ((x)<<1|1)const int N = 1005;int yy[N*2],range;    //离散ystruct Line{    int x;    int y_up;    int y_down;    int cover;  //入边为1，出边为-1}line[N*2];struct Seg_Tree{    int left;    int right;    int cover;  //完全覆盖为>=1，未被完全覆盖为0    int len;    //该段被覆盖的有效长度    int calmid()    {        return (left+right)>>1;    }}tree[N*8];bool cmp(Line a, Line b){    return a.x < b.x;}void build(int left, int right, int idx){    tree[idx].left = left;    tree[idx].right = right;    tree[idx].cover = 0;    tree[idx].len = 0;    if(left+1==right)        return;    int mid = (left+right)>>1;    build(left,mid,LL(idx));    build(mid,right,RR(idx));}int BiSearch(int v){    int low = 0;    int high = range;    while(low<=high)    {        int mid = (low+high)>>1;        if(yy[mid]==v)            return mid;        if(yy[mid] < v)            low = mid + 1;        else            high = mid - 1;    }    return low;}void updateLen(int i){    if(tree[i].cover)        tree[i].len = yy[tree[i].right] - yy[tree[i].left];    else if(tree[i].left + 1 == tree[i].right)        tree[i].len =  0;    else        tree[i].len = tree[LL(i)].len + tree[RR(i)].len;}//更新段[a,b]void update(int a, int b, int c, int idx){    if(tree[idx].left==a && tree[idx].right == b)    {        tree[idx].cover += c;        updateLen(idx);        return ;    }    int mid = tree[idx].calmid();    if(b <= mid)        update(a,b,c,LL(idx));    else if(a >= mid)        update(a,b,c,RR(idx));    else    {        update(a,mid,c,LL(idx));        update(mid,b,c,RR(idx));    }    updateLen(idx);}int main(){    int i,j;    int x1,y1,x2,y2;    while(scanf("%d %d %d %d",&x1,&y1,&x2,&y2)!=EOF&&x1!=-1&&y1!=-1&&x2!=-1&&y2!=-1)    {        i = 0;        do        {            line[i].x = x1;            line[i].y_down = y1;            line[i].y_up = y2;            line[i].cover = 1;            yy[i] = y1;            i++;            line[i].x = x2;            line[i].y_down = y1;            line[i].y_up = y2;            line[i].cover = -1;            yy[i] = y2;            i++;        }while(scanf("%d %d %d %d",&x1,&y1,&x2,&y2)&&x1!=-1&&y1!=-1&&x2!=-1&&y2!=-1);        sort(line,line+i,cmp);        sort(yy,yy+i);        range = 0;        for(j = 0; j < i; j++)        {            if(j==0||yy[j]!=yy[j-1])                yy[range++] = yy[j];        }        range--;        build(0,range,1);        int result = 0;        for(j = 0; j < i-1; j++)        {            int a = BiSearch(line[j].y_down);            int b = BiSearch(line[j].y_up);            update(a,b,line[j].cover,1);            result += tree[1].len*(line[j+1].x - line[j].x);        }        printf("%d\n",result);    }    return 0;}/*0 1 3 42 0 4 31 2 5 5-1 -1 -1 -1*/

?

?

?

2. 矩形面积交。HDU1255

??? 类似于矩形面积并，用扫描线+线段树求解。这里需要设置两个变量one_len和more_len，分别用来表示覆盖次数>=1次的长度和>=2次的长度。

??? 如果cover>=2，one_len=more_len=y[r]-y[l]；

??? 如果cover==1，one_len=y[r]-y[l]，more_len=one_len[l] + one_len[r]；

??? 如果cover==0，one_len=one_len[l]+one_len[r]，more_len=more_len[l]+more_len[r]。

void setLen(int idx){    int r = tree[idx].right;    int l = tree[idx].left;    if(tree[idx].cover > 1)        tree[idx].one_len = tree[idx].more_len = yy[r] - yy[l];    else if(tree[idx].cover == 1)    {        tree[idx].one_len = yy[r] - yy[l];        if(l+1 == r)            tree[idx].more_len = 0;        else            tree[idx].more_len = tree[LL(idx)].one_len + tree[RR(idx)].one_len;    }    else    {        if(l+1 == r)            tree[idx].one_len = tree[idx].one_len = 0;        else        {            tree[idx].one_len = tree[LL(idx)].one_len + tree[RR(idx)].one_len;            tree[idx].more_len = tree[LL(idx)].more_len + tree[RR(idx)].more_len;        }    }}

?

?

?

3. 一个矩形最多能够框多少个点（边界点不算）。POJ2482 / HDU4007

??? 题意：二维平面上有n个点，给出一个宽为w高为h的矩形，矩形可以任意平移，问这个矩形最多能够框住多少个点。

??? 分析：这个问题看似没有思路，不妨将点看做一个以它为左下顶点的w*h的矩形。矩形左边为1，右边为-1。是不是有点像上面的形式了？其实这里是将一颗点分为两点(x,y,1)和(x+w,y,-1)，这样，当我们不断插入点时，就相当于有一个矩形在从左向右移动，因为碰到第一点总数+1，相当于框住了该点；碰到第二点是1+(-1)=0，相当于没有框住点。每次插入时，由于x固定，而y不固定，该点在y轴上影响到的范围为[y,y+h)，注意这里是开区间，因为边界的点不算在内。同时记录最大值。

?? 关键问题：如何实现区间累加和最值的维护。用两个变量add和max：add代表当前加的数的和，max记录该区间的最值。每次进行更新时，若当前节点add!=0，就将该节点的add值传递到左右孩子节点上，自己的add重新赋为0。整个区间的最值为左右孩子区间的较大者。

??? 实质：区间累加+区间最值

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;#define LL(x) ((x)<<1)#define RR(x) ((x)<<1|1)typedef __int64 int64;const int N = 10005;int n,w,h;struct Point{    int64 x,y;    int64 v;    bool operator <(const Point &p) const    {        if(x != p.x)            return x < p.x;        return v < p.v;    }}point[N*2];int64 y[N*2];struct Seg_Tree{    int left;    int right;    int64 max;  //当前区间的max    int64 add;  //记录当前加的数和    int calmid()    {        return (left+right)>>1;    }}tt[N*8];bool cmp(const int64& a, const int64& b){    return a < b;}int64 max(int64 a, int64 b){    return a > b ? a : b;}void build(int left, int right, int idx){    tt[idx].left = left;    tt[idx].right = right;    tt[idx].add = tt[idx].max = 0;    if(left == right)        return;    int mid = (left+right)>>1;    build(left,mid,LL(idx));    build(mid+1,right,RR(idx));}int BinSearch(int aim, int low, int high){    while(low <= high)    {        int mid = (low+high)>>1;        if(y[mid] == aim)            return mid;        if(y[mid] < aim)            low = mid + 1;        else            high = mid - 1;    }    return -1;}void update(int left, int right, int value, int idx){    if(tt[idx].left>=left&&tt[idx].right<=right)    {        tt[idx].add += value;        tt[idx].max += value;        return;    }    if(tt[idx].add != 0)    {        tt[LL(idx)].add += tt[idx].add;        tt[RR(idx)].add += tt[idx].add;        tt[LL(idx)].max += tt[idx].add;        tt[RR(idx)].max += tt[idx].add;        tt[idx].add = 0;    }    int mid = tt[idx].calmid();    if(left <= mid)        update(left,right,value,LL(idx));    if(right > mid)        update(left,right,value,RR(idx));    tt[idx].max = max(tt[LL(idx)].max, tt[RR(idx)].max);}int main(){    int i;    while(scanf("%d %d %d",&n,&w,&h)!=EOF)    {        for(i = 0; i < n; i++)        {            scanf("%I64d %I64d %I64d",&point[i].x,&point[i].y,&point[i].v);            y[i] = point[i].y;            y[n+i] = point[i].y+h;            point[n+i].x = point[i].x+w;            point[n+i].y = point[i].y;            point[n+i].v = -point[i].v;        }        n = n<<1;        sort(y,y+n,cmp);        sort(point,point+n);        int k = 0;        //unique如何使用        for(i = 0; i < n; i++)        {            if(i==0 || y[i] != y[i-1])                y[k++] = y[i];        }        k--;        build(0,k,1);        int64 result = -1;        for(i = 0; i < n; i++)        {            int left = BinSearch(point[i].y, 0, k);            int right = BinSearch(point[i].y+h, 0, k) - 1; //更新区间[y,y+h)            if(left>right)                swap(left,right);            update(left,right,point[i].v,1);            if(result < tt[1].max)                result = tt[1].max;        }        printf("%I64d\n",result);    }    return 0;}/*3 5 32 2 33 1 54 -2 48*/

?

?