HDU6681 二维偏序计算贡献值 树状数组 离散化

http://acm.hdu.edu.cn/showproblem.php?pid=6681

交点个数加1就是答案

使用二维偏序计算横竖射线的交点

#include <bits/stdc++.h>
using namespace std;
int T,n,m,k;
struct point {
    int x,y;
    int kind;
    point(int a,int b,int k = 0):x(a),y(b),kind(k) {};
};

vector<point>p[5];

void input() {
    int a,b;
    char s[2];
    scanf("%d%d%s",&a,&b,s);
    point pp(a,b);
    switch(s[0]) {
    case 'U':
        pp.kind = 1;
        p[1].push_back(pp);
        break;
    case 'D':
        pp.kind = 2;
        p[2].push_back(pp);
        break;
    case 'L':
        pp.kind = 3;
        p[3].push_back(pp);
        break;
    case 'R':
        pp.kind = 4;
        p[4].push_back(pp);
        break;
    }
}
void init(){
    for(int i = 1;i<=4;i++){
        p[i].clear();
    }
}
bool cmpx(point a,point b){
    return a.x<b.x;
}
bool cmpy(point a,point b){
    return a.y<b.y;
}
int c[100005] = {0};
void cinit(){
    memset(c,0,sizeof(c));
}
int ask(int x){
    int ans = 0;
    for(;x;x-=x&-x)ans+=c[x];
    return ans;
}
void add(int x,int y){
    for(;x<=100000;x+=x&-x)c[x]+=y;
}
int solve(int a,int b,bool changex,bool changey){
    ///计算每一个b类点的左下方向有几个a类点，返回对每一个b类点计算的和
    ///changex、y表示是否翻转x、y坐标
    ///比如实际计算的是左上方的点，只要翻转y轴就可以转换成计算左下方的点
    ///把a类点和b类点放在一起排序，扫描到a类点时，对树状数组做单点修改，
    ///扫描到b类点时将树状数组的前缀和加到返回值上
    vector<point> v;
    v.insert(v.end(),p[a].begin(),p[a].end());
    v.insert(v.end(),p[b].begin(),p[b].end());
    if(changex){
        for(int i = 0;i<(int)v.size();i++){
            v[i].x = 1e9 - v[i].x;
        }
    }
    if(changey){
        for(int i = 0;i<(int)v.size();i++){
            v[i].y = 1e9 - v[i].y;
        }
    }
    sort(v.begin(),v.end(),cmpy);
    for(int i = 0;i<(int)v.size();i++){
        v[i].y = i+1;///树状数组存储的是y轴坐标，因为y轴坐标范围很大，所以要先离散化
    }
    sort(v.begin(),v.end(),cmpx);
    cinit();
    int ret = 0;
    for(int i = 0;i<(int)v.size();i++){
        if(v[i].kind == a){
            add(v[i].y,1);
        }else{
            ret+=ask(v[i].y);
        }
    }
    return ret;
}

int main() {
    scanf("%d",&T);
    while(T--) {
        init();
        scanf("%d%d%d",&n,&m,&k);
        for(int i = 1; i<=k; i++) {
            input();
        }
        int ans = 0;
        ans += solve(1,3,0,0);
        ans += solve(1,4,1,0);
        ans += solve(2,3,0,1);
        ans += solve(4,2,0,0);
        printf("%d\n",ans+1);
    }
    return 0;
}