2019杭电暑假多校9：Rikka with Cake【扫描线+树状数组】

78 阅读 0 评论 52 点赞

我是靠谱客的博主小巧裙子，最近开发中收集的这篇文章主要介绍2019杭电暑假多校9：Rikka with Cake【扫描线+树状数组】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

2019 Multi-University Training Contest 9：Rikka with Cake

题意：

给定K条射线，问将N*M的矩形分成了多少块

分析：

发现每一个交点都会产生一个块，因为每条都是射线，猜测答案为交点的个数+1，知道这个就十分套路了；扫描横线，计算每条横线产生的贡献；具体做法：把横线拆成{L，R，h}，每条竖线拆成两个点，（下面的点）{x，y，h1，1}和（上面的点）{x，y，h2，-1}，代表的意思是这条竖线贡献[h1,h2)这个区间的扫描线；然后按h排序，依次扫描，如果当前扫到的是点，就把它的值加到它的X坐标上；如果扫到的是一条横线，就只需统计【L,R】的和就好了，所以用树状数组维护X数组的区间和；注意排序的时候h相同时，优先点，后横线

代码:

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 2e5+15;
int T,n,m,k,x,y,cnt,cntx;
char op;
struct point{
    int f,L,R,id,v;
}p[maxn<<1];
bool cmp(point a,point b){
    if(a.id == b.id) return a.f < b.f;
    return a.id < b.id;
}
int tr[maxn<<1],X[maxn<<1];
int getid(int x){
    return lower_bound(X+1,X+cntx,x)-X;
}
void init(){
    X[cntx++] = n; sort(X+1,X+cntx); 
    cntx = unique(X+1,X+cntx)-X;
    sort(p,p+cnt,cmp);
    for(int i = 0;i <= cntx; ++i) tr[i] = 0;
}
inline int lowbit(int x){
    return x&(-x);
}
void updata(int pos,int val){
    while(pos <= cntx){
        tr[pos] += val;
        pos += lowbit(pos);
    }
}
LL query(int pos){
    LL res = 0;
    while(pos){
        res += tr[pos];
        pos -= lowbit(pos);
    }
    return res;
}
LL solve(){
    init(); LL ans = 0;
    for(int i = 0;i < cnt; ++i){
        if(p[i].f == 0) updata(getid(p[i].L),p[i].v);
        else ans += query(getid(p[i].R))-query(getid(p[i].L));
    }
    return ans + 1;
}
int main(){
    scanf("%d",&T);
    while(T--){
        cnt = 0; cntx = 2;
        scanf("%d %d %d",&n,&m,&k);
        for(int i = 0;i < k; ++i){
            scanf("%d %d %c",&x,&y,&op);
            if(op == 'U') p[cnt++] = (point){0,x,y,y,1};
            else if(op == 'D'){
                p[cnt++] = (point){0,x,y,0,1};
                p[cnt++] = (point){0,x,y,y+1,-1};
            }
            else if(op == 'L') p[cnt++] = (point){1,0,x,y,0};
            else p[cnt++] = (point){1,x-1,n,y,0},X[cntx++] = x-1;
            X[cntx++] = x;
        }
        printf("%I64dn",solve());
    }
    return 0;
}