2019杭电多校第⑨场B Rikka with Cake (主席树，离散化)

题意：

给定一块n*m的矩形区域，在区域内有若干点，每个顶点发出一条射线，有上下左右四个方向，问矩形被分成了几个区域？

思路：

稍加观察和枚举可以发现，区域数量=射线交点数+1(可以用欧拉定理验证，但是我不会)，问题就转变为统计射线交点数量

可以将四个方向的射线分开，用左右的射线去查询与多少个上下的射线相交，先考虑向左的射线A与几条向上的射线相交，设A(x,y)，即求(1,x)区间内\(\le y\)的向上的射线条数，显然可以利用主席树进行维护(也可以用树状数组并且更快，但是我不会)。其他情况同理，注意离散化时向上靠近还是向下靠近

由于y是在(1,1e9)范围内的，因此y需要离散化，因为主席树的性质，x必须排序离散化

//memory= 1.3e8 int

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

const int maxn=1e5+5;

const int N=1e5+2;

int xu[maxn],xd[maxn],val[maxn];

int x1[maxn],y1[maxn];

char c1[maxn];

const int Log=50;

int root[2][maxn],num[2][maxn*Log],lson[2][maxn*Log],rson[2][maxn*Log];

int tot[2];

double Sum,Num;

int build(int id,int l,int r){

    int root=++tot[id];

    num[id][root]=0;

    if(l<r){

        int mid=(l+r)>>1;

        lson[id][root]=build(id,l,mid);

        rson[id][root]=build(id,mid+1,r);

    }

    return root;

}

int update(int id,int pre,int l,int r,int x){

    int root=++tot[id];

    num[id][root]=num[id][pre]+1;

    lson[id][root]=lson[id][pre];

    rson[id][root]=rson[id][pre];

    if(l<r){

        int mid=(l+r)>>1;

        if(x<=mid) lson[id][root]=update(id,lson[id][pre],l,mid,x);

        else rson[id][root]=update(id,rson[id][pre],mid+1,r,x);

    }

    return root;

}

int query(int id,int Old,int New,int l,int r,int k){//Old和New对应旧版本的根和新版本的根

    if(id==0){//向上，查区间内<=k的数的个数

        if(r<=k){

            return num[id][New]-num[id][Old];

        }

        int mid=(l+r)>>1;

        int res=0;

        if(l<=k) res+=query(id,lson[id][Old],lson[id][New],l,mid,k);

        if(mid+1<=k) res+=query(id,rson[id][Old],rson[id][New],mid+1,r,k);

        return res;

    }

    else{//向下，查区间内>=k的数的个数

        if(l>=k){

            return num[id][New]-num[id][Old];

        }

        int mid=(l+r)>>1;

        int res=0;

        if(mid>=k) res+=query(id,lson[id][Old],lson[id][New],l,mid,k);

        if(r>=k) res+=query(id,rson[id][Old],rson[id][New],mid+1,r,k);

        return res;

    }

}

struct node{

    node(int a,int b):x(a),y(b){}

    int x,y;

};

bool cmp(node a,node b){

    return a.x<b.x;

}

int main(){

    int t;

    cin>>t;

    while(t--){

        tot[0]=tot[1]=0;

        int n,m,k;

        vector<node> U,D,R,L;

        scanf("%d%d%d",&n,&m,&k);

        int x,y;

        char c;

        int sizexu=0,sizexd=0,sizey=0;

        for(int i=1;i<=k;i++){

            scanf("%d%d %c",&x,&y,&c);

            x1[i]=x;y1[i]=y;c1[i]=c;

            if(c=='U') xu[++sizexu]=x;

            if(c=='D') xd[++sizexd]=x;

            val[++sizey]=y;

        }

        sort(xu+1,xu+1+sizexu);

        sort(xd+1,xd+1+sizexd);

        sort(val+1,val+1+sizey);

        sizexu=unique(xu+1,xu+1+sizexu)-(xu+1);

        sizexd=unique(xd+1,xd+1+sizexd)-(xd+1);

        sizey=unique(val+1,val+1+sizey)-(val+1);

        for(int i=1;i<=k;i++){//U,D中存离散化的坐标值。L,R存原值，之后再在对应数组中二分找离散值

            if(c1[i]=='U'){

                x1[i]=lower_bound(xu+1,xu+1+sizexu,x1[i])-xu;

                y1[i]=lower_bound(val+1,val+1+sizey,y1[i])-val;

                U.push_back(node(x1[i],y1[i]) );

            }

            if(c1[i]=='D'){

                x1[i]=lower_bound(xd+1,xd+1+sizexd,x1[i])-xd;

                y1[i]=lower_bound(val+1,val+1+sizey,y1[i])-val;

                D.push_back(node(x1[i],y1[i]) );

            }

            if(c1[i]=='L') L.push_back(node(x1[i],y1[i]) );

            if(c1[i]=='R') R.push_back(node(x1[i],y1[i]) );

        }

        //建2棵主席树，分别存U，D，再用L和R取查找

        root[0][0]=build(0,1,N);

        root[1][0]=build(1,1,N);

        sort(U.begin(),U.end(),cmp);

        for(int i=0;i<U.size();i++)

            root[0][i+1]=update(0,root[0][i],1,N,U[i].y);

        sort(D.begin(),D.end(),cmp);

        for(int i=0;i<D.size();i++)

            root[1][i+1]=update(1,root[1][i],1,N,D[i].y);

        int ans=0;

        for(int i=0;i<L.size();i++){

            int r0=upper_bound(xu+1,xu+1+sizexu,L[i].x)-xu-1;//找<=，向左靠近

            int r1=upper_bound(xd+1,xd+1+sizexd,L[i].x)-xd-1;//找<=，向左靠近

            int h=lower_bound(val+1,val+1+sizey,L[i].y)-val;

            ans+=query(0,root[0][0],root[0][r0],1,N,h);

            ans+=query(1,root[1][0],root[1][r1],1,N,h);

        }

        for(int i=0;i<R.size();i++){

            int l0=lower_bound(xu+1,xu+1+sizexu,R[i].x)-xu;//找>=，向右靠近

            int l1=lower_bound(xd+1,xd+1+sizexd,R[i].x)-xd;//找>=，向右靠近

            int h=lower_bound(val+1,val+1+sizey,R[i].y)-val;

            ans+=query(0,root[0][l0-1],root[0][U.size()],1,N,h);

            ans+=query(1,root[1][l1-1],root[1][D.size()],1,N,h);

        }

        printf("%d\n",ans+1);

    }

}

巴特西

2019杭电多校第⑨场B Rikka with Cake (主席树，离散化)

题意：

思路：

最新文章

热门文章