E - 秋实大哥与家

Time Limit: 1 Sec  Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/contest/show/59

Description

Input

Output

Sample Input

Sample Output

HINT

题意

题解：

对于每一个矩形，我们都向左边延展m-1厘米，包括边界，然后这道题就可以转化为求剩下的面积是多少啦

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <map>

using namespace std;

#define LL(x) (x<<1)

#define RR(x) (x<<1|1)

typedef long long LL;

const int N=;

struct Line

{

    int x,y1,y2,valu;

    Line(){}

    Line(int a,int b,int c,int d){x=a;y1=b;y2=c;valu=d;}

    bool operator<(const Line &b)const

    {

        return x<b.x;

    }

};

struct node

{

    int lft,rht,sum,valu;

    int mid(){return lft+(rht-lft)/;}

};

map<int,int> imap;

vector<int> y;

vector<Line> line;

int data[N][];

struct Segtree

{

    node tree[N*];

    void relax(int ind)

    {

        if(tree[ind].valu>)

            tree[ind].sum=y[tree[ind].rht]-y[tree[ind].lft];

        else

        {

            if(tree[ind].lft+==tree[ind].rht) tree[ind].sum=;

            else tree[ind].sum=tree[LL(ind)].sum+tree[RR(ind)].sum;

        }

    }

    void build(int lft,int rht,int ind)

    {

        tree[ind].lft=lft;  tree[ind].rht=rht;

        tree[ind].sum=;    tree[ind].valu=;

        if(lft+!=rht)

        {

            int mid=tree[ind].mid();

            build(lft,mid,LL(ind));

            build(mid,rht,RR(ind));

        }

    }

    void updata(int be,int end,int ind,int valu)

    {

        int lft=tree[ind].lft,rht=tree[ind].rht;

        if(be<=lft&&rht<=end)

        {

            tree[ind].valu+=valu;

            relax(ind);

        }

        else

        {

            int mid=tree[ind].mid();

            if(be<mid) updata(be,end,LL(ind),valu);

            if(end>mid) updata(be,end,RR(ind),valu);

            relax(ind);

        }

    }

}seg;

LL solve(int n,int w,int h,int m)

{

    y.clear();  line.clear(); imap.clear();

    y.push_back(); y.push_back(h);

    line.push_back(Line(max(,w-m),,h,));

    line.push_back(Line(w,,h,-));

    for(int i=;i<n;i++)

    {

        int x1=max(,data[i][]-m),y1=data[i][];

        int x2=data[i][],y2=data[i][];

        line.push_back(Line(x1,y1,y2,));

        line.push_back(Line(x2,y1,y2,-));

        y.push_back(y1);y.push_back(y2);

    }

    sort(y.begin(),y.end());

    y.erase(unique(y.begin(),y.end()),y.end());

    for(int i=;i<(int)y.size();i++)

        imap.insert(make_pair(y[i],i));

    sort(line.begin(),line.end());

    LL res=;

    seg.build(,(int)y.size(),);

    for(int i=;i<(int)line.size();i++)

    {

        if(i!=) res+=(LL)seg.tree[].sum*(line[i].x-line[i-].x);

        seg.updata(imap[line[i].y1],imap[line[i].y2],,line[i].valu);

    }

    return res;

}

int main()

{

    //线段树 矩形面积

    int w,h,n,m;

    while(scanf("%d%d%d%d",&w,&h,&n,&m)!=EOF)

    {

        for(int i=;i<n;i++)

            for(int j=;j<;j++)

            {

                scanf("%d",&data[i][j]);

                if(j==||j==) data[i][j]++;

            }

        LL res1=(LL)w*h-solve(n,w+,h+,m-);

        for(int i=;i<n;i++)

        {

            swap(data[i][],data[i][]);

            swap(data[i][],data[i][]);

        }

        LL res2=(LL)w*h-solve(n,h+,w+,m-);

        if(m!=) printf("%lld\n",res1+res2);

        else printf("%lld\n",res1);

    }

    return ;

}