题意:给一些矩形,让求这些矩形的面积.矩形是给出的左下角和右下角的坐标,都是正整数.

    思路:简单的线段树题目,就是求矩形面积.因为都是整数,而且数据范围不大,因此不需要离散化.

    代码:

    [cpp]

    #include <iostream>

    #include <cstdio>

    #include <algorithm>

    #include <string.h>

    using namespace std;

    const int N = 50010,M = 1010;

    struct tree{

    int lp,rp,len,num;

    int getmid(){

    return (lp + rp) / 2;

    }

    }tt[N * 4];

    struct line{

    int lp,rp,cnt,value;

    }LL[M * 2];

    void built_tree(int lpos,int rpos,int pos){

    tt[pos].lp = lpos;

    tt[pos].rp = rpos;

    tt[pos].len = tt[pos].num = 0;

    if(tt[pos].lp + 1 == tt[pos].rp)

    return;

    int mid = tt[pos].getmid();

    built_tree(lpos,mid,pos*2);

    built_tree(mid,rpos,pos*2+1);

    }

    bool cmp(line a,line b){

    return a.value > b.value;

    }

    void getlen(int pos){

    if(tt[pos].num > 0)

    tt[pos].len = tt[pos].rp - tt[pos].lp;

    else if(tt[pos].lp + 1 == tt[pos].rp)

    tt[pos].len = 0;

    else

    tt[pos].len = tt[pos * 2].len + tt[pos * 2 + 1].len;

    }

    void update(int pos,int id){

    if(tt[pos].lp >= LL[id].lp && tt[pos].rp <= LL[id].rp){

    tt[pos].num += LL[id].cnt;

    getlen(pos);

    return;

    }