picture.cpp

线段树的C代码实现 可以实现高效的区间求和等算法

/*
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
*/

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

struct node 
{
    int l, r;//左右端点
    int il, ir;
    node * pl, * pr;//左右子树
    int len;//测度
    int cover;//完全覆盖线段数
    int lines;//独立线段数
    int lbd, rbd;//左右端点覆盖
}mem[40000];
int mem_pos;

struct line 
{
    int x,y1,y2;
    int flag;
    bool operator < (const line & tt ) const 
	{
        if(x != tt.x) 
		{
            return x < tt.x;
        }
        return flag > tt.flag;
    }
}list[11000];

int yaxis[11000] , temp[11000];

node *new_node()
{
    node *pt = &mem[mem_pos ++];
    memset(pt,0,sizeof(node));
    return pt;
}

void cal_len(node * root)
{
    root ->len = 0;
    if(root ->cover > 0) 
	{
        root ->len = root ->r - root ->l;
    }
    else 
	{
        if(root ->pl && root ->pr) 
		{
            root ->len = root ->pl ->len + root ->pr ->len;
        }
    }
}

void cal_line(node * root)
{
    root ->lbd = root ->rbd = root ->lines = 0;
    if(root ->cover > 0) 
	{
        root ->lbd = root ->rbd = root ->lines = 1;
    }
    else 
	{
        if(root ->pl && root ->pr) 
		{
            root ->lbd = root ->pl ->lbd;
            root ->rbd = root ->pr ->rbd;
            root ->lines = root ->pl ->lines + root ->pr ->lines
                        - (root ->pl ->rbd * root ->pr ->lbd); 
        }
    }
}

node *make_tree(int axis[], int il, int ir)
{
    node *root = new_node();
    root ->l = axis[il];
    root ->r = axis[ir];
    root ->il = il;
    root ->ir = ir;
    if(ir - il > 1)
	{
        int mid = (il+ir)/2;
        root ->pl = make_tree(axis, il, mid);
        root ->pr = make_tree(axis, mid, ir);
    }
    return root;
}

void update(node * root, line e)
{
    if(e.y1 <= root ->l && root ->r <= e.y2) 
	{
        root ->cover += e.flag;
    }
    if(root ->ir - root ->il > 1) 
	{
        int mid = (root ->il + root ->ir)/2;
        if(e.y1 < yaxis[mid]) 
		{
            update(root ->pl, e);
        }
        if(yaxis[mid] < e.y2) 
		{
            update(root ->pr, e);
        }
    }
    cal_len(root);
    cal_line(root);
}

int main()
{
    int t,n,i;
    int ls , top;
    int x1,x2,y1,y2;
    int sum;
    while(scanf("%d", &n) != EOF) 
	{
        ls = 0;
        mem_pos = 0;
        sum = 0;
        for(i=0;i<n;i++) 
		{
            scanf("%d %d %d %d", &x1,&y1,&x2,&y2);
            list[ls].x = x1;
            list[ls].y1 = y1;    list[ls].y2 = y2;
            list[ls].flag = 1;
            list[ls+1].x = x2;
            list[ls+1].y1 = y1;    list[ls+1].y2 = y2;
            list[ls+1].flag = -1;
            temp[ls] = y1;
            temp[ls+1] = y2;

            ls += 2;
        }
        sort(temp, temp+ls);
        sort(list, list+ls);

        top=0;
		yaxis[top++]=temp[0];
		for(i=1;i<ls;i++)
			if(temp[i]!=temp[i-1])
				yaxis[top++]=temp[i];

        int preLen = 0, preLines = 0 , nowLen = 0, nowLines = 0;
        node *root = make_tree(yaxis, 0, top-1);
        for(i=0;i<ls;i++) 
		{
            update(root, list[i]);
			nowLen = root ->len;
            nowLines = root ->lines;
            sum += abs(root ->len - preLen);
            sum += 2 * preLines * (list[i].x - list[i-1].x);
            //printf("(%d,%d) %d (%d,%d) ", root->len, root->lines, sum, preLen,preLines);
            preLen = nowLen;
            preLines = nowLines;
        }
        printf("%d\n", sum);
    }
}