HDU6681-Rikka with Cake（转化为线段树模型）

题目链接

Problem Description

Rikka's birthday is on June 12th. The story of this problem happens on that day.
Today is Rikka's birthday. Yuta prepares a big cake for her: the shape of this cake is a rectangular of ncentimeters times mcentimeters. With the guidance of a grimoire, Rikka is going to cut the cake.
For simplicity, Rikka firstly builds a Cartesian coordinate system on the cake: the coordinate of the left bottom corner is (0,0)while that of the right top corner is (n,m). There are Kinstructions on the grimoire: The ith cut is a ray starting from (xi,yi)while the direction is Di. There are four possible directions: L, passes (xi−1,yi); R, passes (xi+1,yi); U, passes (xi,yi+1); D, passes (xi,yi−1).
Take advantage of the infinite power of Tyrant's Eye, Rikka finishes all the instructions quickly. Now she wants to count the number of pieces of the cake. However, since a huge number of cuts have been done, the number of pieces can be very large. Therefore, Rikka wants you to finish this task.

Input

The first line of the input contains a single integer T(1≤T≤100), the number of the test cases.
For each test case, the first line contains three positive integers n,m,K(1≤n,m≤109,1≤K≤105), which represents the shape of the cake and the number of instructions on the grimoire.
Then Klines follow, the ith line contains two integers xi,yi(1≤xi<n,1≤yi<m)'L','R','U','D'}, which describes the ith cut.
The input guarantees that there are no more than 5test cases with K>1000, and no two cuts share the same xcoordinate or ycoordinate, i.e., ∀1≤i<j≤K, xi≠xjand yi≠yj.

Output

For each test case, output a single line with a single integer, the number of pieces of the cake.

Hint
The left image and the right image show the results of the first and the second test case in the sample input respectively. Clearly, the answer to the first test case is 3while the second one is 5.

Sample Input

2

4 4 3

1 1 U

2 2 L

3 3 L

5 5 4

1 2 R

3 1 U

4 3 L

2 4 D

Sample Output

3

5

题意

给一个m*n的矩阵，有几条从上下左右的射线将矩阵分割，问最后分成了几块？

思路

将问题转化为线段树模型：每有一条射线相交，就多出一个块。因此数有多少交点。

每一个射线按其x点从小到大排序，U和D操作是update，L和R是query：

这样就转化为了线段树模型，区间修改，单点查询。 区间修改的是每个数组的值，因此需要lazy操作；单点查询的是数组中存的值，因为是单点，所以只需要叶子节点保存就行了。

w在非叶子结点表示的是lazy标记，在叶子结点表示的是数组的单值。 

想到转化为数组就好做了，tnl。

大体思路是：求块的个数 => 求射线交点个数 => 排序后上下是update操作，修改区间值；左右是query操作，访问数组的单点值

还有离散化的操作，三步： sort ， unique ， lower_bound .

参考

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 1e5;

struct nodep
{
    int x,y;char ch;
};
bool cmp(nodep a,nodep b)
{
    return a.x<b.x;
}

struct node
{
    int l,r,w;
}tr[N*4+10];

void build(int k,int l,int r)
{
    tr[k].l = l; tr[k].r = r; tr[k].w = 0;
    if(l==r) return;
    int mid = (l+r)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
}

void pushdown(int k)
{
    tr[k*2].w += tr[k].w;
    tr[k*2+1].w += tr[k].w;
    tr[k].w = 0;
}

int query(int k,int p)
{
    if(tr[k].l==p&&tr[k].r==p) return tr[k].w;
    int mid = (tr[k].l+tr[k].r)/2;
    if(tr[k].w) pushdown(k);
    if(p<=mid) return query(k*2,p);
    else if(p>mid) return query(k*2+1,p);
}

void update(int k,int l,int r,int v)
{
    if(tr[k].r<l||tr[k].l>r) return;
    if(tr[k].l>=l&&tr[k].r<=r) {tr[k].w += v;return;}
    pushdown(k);
    update(k*2,l,r,v);
    update(k*2+1,l,r,v);
}

int main(){
    int T; scanf("%d",&T);
    while(T--)
    {
        nodep p[N];
        int m,n,k;
        scanf("%d%d%d",&m,&n,&k);
        for(int i=0;i<k;i++){
            scanf("%d%d %c",&p[i].x,&p[i].y,&p[i].ch);
        }
        int a[N],b[N];
        for(int i=0;i<k;i++){
            a[i] = p[i].x;
            b[i] = p[i].y;
        }
        sort(a,a+k); sort(b,b+k);
        int am = unique(a,a+k)-a;
        int bm = unique(b,b+k)-b;
        for(int i=0;i<k;i++){
            p[i].x = lower_bound(a,a+am,p[i].x)-a+1;
            p[i].y = lower_bound(b,b+bm,p[i].y)-b+1;
        }

        sort(p,p+k,cmp);

        build(1,1,N);
        ll ans = 1;
        for(int i=0;i<k;i++){
            //printf("%c  :%dn",p[i].ch,p[i].y);
            if(p[i].ch=='D') update(1,1,p[i].y,1);
            else if(p[i].ch=='U') update(1,p[i].y,N,1);
            else if(p[i].ch=='L') ans += query(1,p[i].y);
        }
        //printf(":%lldn",ans);
        build(1,1,N);
        for(int i=k-1;i>=0;i--){
            //printf("%c :%dn",p[i].ch,p[i].y);
            if(p[i].ch=='D') update(1,1,p[i].y,1);
            else if(p[i].ch=='U') update(1,p[i].y,N,1);
            else if(p[i].ch=='R') ans += query(1,p[i].y);
        }
        printf("%lldn",ans);
    }
    return 0;
}

最后

以上就是大意小懒猪最近收集整理的关于HDU6681-Rikka with Cake（转化为线段树模型）的全部内容，更多相关HDU6681-Rikka内容请搜索靠谱客的其他文章。