hdu 4533 威威猫系列故事——晒被子（线段树 成端更新）

具体参考 

点击打开链接

其实是建立一个T的线段树，然而不同矩形对于不同的T会有三种形态。

讲这些面积用t的表达式算出来  会发现最后的面积是一个关于t的一元二次方程

最后维护这个方程的三个系数，从而达到求解。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 200005
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define eps 1e-12
typedef long long LL;
using namespace std;
int n=maxn-5;
LL A[maxn<<2],B[maxn<<2],C[maxn<<2];

void pushdown(int num)
{
    A[num<<1]+=A[num];A[num<<1|1]+=A[num];
    B[num<<1]+=B[num];B[num<<1|1]+=B[num];
    C[num<<1]+=C[num];C[num<<1|1]+=C[num];
    A[num]=B[num]=C[num]=0;
}
LL query(int num,int s,int e,LL pos)
{
    if(s==e)
    {
        return pos*pos*A[num]+B[num]*pos+C[num];
    }
    int mid=(s+e)>>1;
    pushdown(num);
    if(pos<=mid)return query(lson,pos);
    else return query(rson,pos);
}
void update(int num,int s,int e,int l,int r,LL a,LL b,LL c)
{
    if(l<=s && r>=e)
    {
        A[num]+=a;
        B[num]+=b;
        C[num]+=c;
        return;
    }
    int mid=(s+e)>>1;
    if(l<=mid)update(lson,l,r,a,b,c);
    if(r>mid)update(rson,l,r,a,b,c);
}
void work(LL x1,LL y1,LL x2,LL y2)
{
    LL a=0,b=0,c=0;

    update(1,1,n,max(x2,y2)+1,n,0,0,(x2-x1)*(y2-y1));//如果T==5的时候  s=10  那么 T==10的时候   s也应该等于10  这个就是更新后面的区域

    if(x2<y2)
    {
        update(1,1,n,max(x2,y1)+1,y2,0,-x1+x2,y1*(x1-x2));
    }
    else
    {
        update(1,1,n,max(y2,x1)+1,x2,0,-y1+y2,x1*(y1-y2));
    }

    if(max(x1,y1)<min(x2,y2))//这个是第一种情况
    update(1,1,n,max(x1,y1),min(x2,y2),1,-(x1+y1),x1*y1);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int m;
        scanf("%d",&m);
        memset(A,0,sizeof A);
        memset(B,0,sizeof B);
        memset(C,0,sizeof C);

        while(m--)
        {
            LL x1,y1,x2,y2;
            scanf("%I64d%I64d%I64d%I64d",&x1,&y1,&x2,&y2);
            work(x1,y1,x2,y2);
        }
        scanf("%d",&m);
        while(m--)
        {
            LL pos;//这里一定要定义为ll  不然会越界。
            scanf("%I64d",&pos);
            printf("%I64d\n",query(1,1,n,pos));
        }
    }
    return 0;
}

hdu 4533 威威猫系列故事——晒被子（线段树 成端更新）,布布扣,bubuko.com

hdu 4533 威威猫系列故事——晒被子（线段树 成端更新）

原文：http://blog.csdn.net/u010709592/article/details/20959473