2019HDU多校 Round9

Solved:3

 

02 Rikka with Cake (树状数组)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, K;
int cntx, cnty, cntl, cntr, cntu, cntd;
struct node {
    int x, y, tx, ty;
    char dir;
}E[100005];
node L[100005], R[100005], U[100005], D[100005];
int idx[100005];
int idy[100005];
char s[5];

bool cmp1(node A, node B) {
    return A.x < B.x;
}
bool cmp2(node A, node B) {
    return A.y < B.y;
}
bool cmp3(node A, node B) {
    return A.y > B.y;
}

int sum[100005];
void add(int k) {
    for(int i = k; i <= 100000; i += (i & -i)) sum[i]++;
}
int query(int k) {
    int res = 0;
    for(int i = k; i >= 1; i -= (i & -i)) res += sum[i];
    return res;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        cntx = cnty = cntl = cntr = cntu = cntd = 0;
        scanf("%d%d%d", &n, &m, &K);
        for(int i = 1; i <= K; i++) {
            scanf("%d%d", &E[i].x, &E[i].y);
            scanf("%s", s + 1); E[i].dir = s[1];
        }
        sort(E + 1, E + 1 + K, cmp1);
        for(int i = 1; i <= K; i++) {
            if(E[i].x != E[i - 1].x) E[i].tx = ++cntx;
            else E[i].tx = cntx;
        }
        sort(E + 1, E + 1 + K, cmp2);
        for(int i = 1; i <= K; i++) {
            if(E[i].y != E[i - 1].y) E[i].ty = ++cnty;
            else E[i].ty = cnty;
        }
        for(int i = 1; i <= K; i++) {
            if(E[i].dir == 'U') U[++cntu] = E[i];
            else if(E[i].dir == 'D') D[++cntd] = E[i];
            else if(E[i].dir == 'L') L[++cntl] = E[i];
            else if(E[i].dir == 'R') R[++cntr] = E[i];
        }
        sort(L + 1, L + 1 + cntl, cmp3);
        sort(R + 1, R + 1 + cntr, cmp3);
        sort(U + 1, U + 1 + cntu, cmp3);
        memset(sum, 0, sizeof(sum));

        ll ans = 0;
        int tt = 1;
        for(int i = 1; i <= cntu; i++) {
            while(L[tt].ty >= U[i].ty && tt <= cntl) {
                add(L[tt].tx);
                tt++;
            }
            ans += 1LL * (query(100000) - query(U[i].tx - 1));
        }

        tt = 1;
        memset(sum, 0, sizeof(sum));
        for(int i = 1; i <= cntu; i++) {
            while(R[tt].ty >= U[i].ty && tt <= cntr) {
                add(R[tt].tx);
                tt++;
            }
            ans += 1LL * query(U[i].tx);
        }

        sort(D + 1, D + 1 + cntd, cmp2);
        sort(L + 1, L + 1 + cntl, cmp2);
        sort(R + 1, R + 1 + cntr, cmp2);
        tt = 1;
        memset(sum, 0, sizeof(sum));
        for(int i = 1; i <= cntd; i++) {
            while(L[tt].ty <= D[i].ty && tt <= cntl) {
                add(L[tt].tx);
                tt++;
            }
            ans += 1LL * (query(100000) - query(D[i].tx - 1));
        }

        tt = 1;
        memset(sum, 0, sizeof(sum));
        for(int i = 1; i <= cntd; i++) {
            while(R[tt].ty <= D[i].ty && tt <= cntr) {
                add(R[tt].tx);
                tt++;
            }
            ans += 1LL * query(D[i].tx);
        }
        printf("%lld\n", ans + 1LL);
    }
    return 0;
}