HDU6681 Rikka with Cake

题意

给一个n*m的矩形，n,m 1e9。给k(1e5)个点坐标(x,y)，每个点可向上下左右发出射线，问将矩形分成几份。
题目连接

思路

观察发现分成的块数等于交点数加一。离散化上下分别考虑，对于下垂下来的线按照下垂点从下向上插入树状数组，同时从下向上查询水平射线，对于向左的射线，查询小于等于其发出点x坐标的下垂线有几个，对于向右的射线，查询大于等于其发出点x坐标的下垂线有几个。对于向上的线同理。

代码

#include
using namespace std;
typedef long long LL;
const int maxn = 100000+10;

struct line
{
    int x,y,o;
};

struct node
{
    int p,v;
};

int n,m,k,nn,mm;
char s[10];
line a[maxn];
int b[maxn],c[maxn],u[maxn],d[maxn],l[maxn],r[maxn];
node tmp[maxn];
int t[maxn];

int lowbit(int x)
{
    return x&(-x);
}

void add(int x)
{
    while (x<=nn)
    {
        t[x]++;
        x+=lowbit(x);
    }
}

int ask(int x)
{
    int ans=0;
    while (x>0)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}

bool cmp(node a,node b)
{
    return a.v=r[i]) l[i]=nn,r[i]=nn;
        }

        LL ans=1;

        for (int i=1;i<=nn;i++) tmp[i].p=i,tmp[i].v=u[i];
        sort(tmp+1,tmp+nn+1,cmp);
        int cur=1;
        memset(t,0,sizeof(t));
        for (int i=1;i1;i--)
        {
            while (cur>=1&&tmp[cur].v>=i)
            {
                add(tmp[cur].p);
                cur--;
            }
            ans+=ask(l[i]);
            ans+=ask(nn)-ask(r[i]-1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}