题解 P1502 【窗口的星星】

Lysus · 2019-10-27 20:36:28 · 题解

这是一道离散化加线段树

我们把每个星星都看成属于它那个矩形的左下角

再按照x轴和y轴离散化

把y轴用线段树处理，x轴扫过去

扫到一个矩形就加相应的light值，相反扫出矩形就减去相应的light值（线段树操作）

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

typedef long long ll;
const int MAX = 100010;

int n, w, h, t;
struct Node {
    int light, x_1, x_2, y_1, y_2;
}s[MAX];
struct node {
    int xx, yy, id;
}L[MAX << 2];
int tot;
struct nOde {
    int lazy, sum;
}tree[MAX << 2];
int f[MAX][101], g[MAX][101];

inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * w;
}

bool cmp_x(node a, node b) {return a.xx < b.xx;}
bool cmp_y(node a, node b) {return a.yy < b.yy;}
bool cmp_X(Node a, Node b) {return a.x_1 == b.x_1 ? a.x_2 < b.x_2 : a.x_1 < b.x_1;}
void push_down(int u) {
    if(tree[u].lazy) {
        tree[u << 1].lazy += tree[u].lazy;
        tree[u << 1 | 1].lazy += tree[u].lazy;
        tree[u << 1].sum += tree[u].lazy;
        tree[u << 1 | 1].sum += tree[u].lazy;
        tree[u].lazy = 0;
    }
}
void change_1(int u, int x, int y, int a, int b, int k) {
    if(a <= x && b >= y) {
        tree[u].lazy += k;
        tree[u].sum += k;
        push_down(u);
        return ;
    }
    int mid = (x + y) >> 1;
    push_down(u);
    if(a <= mid) change_1(u << 1, x, mid, a, b, k);
    if(b > mid) change_1(u << 1 | 1, mid + 1, y, a, b, k);
    tree[u].sum = max(tree[u << 1].sum, tree[u << 1 | 1].sum);
}
int ask(int u, int x, int y) {
    if(x == y) return tree[u].sum;
    int mid = (x + y) >> 1;
    push_down(u);
    return max(ask(u << 1, x, mid), ask(u << 1 | 1, mid + 1, y));
    return 0;
}
int main()
{
    t = read();
    while(t--) {
        tot = 0;
        n = read(), w = read(), h = read();
        for(int i = 1; i <= n; i++) {
            int x = read(), y = read();
            s[i].x_1 = s[i].x_2 = s[i].y_1 = s[i].y_2 = 0;
            s[i].light = read();

            L[++tot].xx = x;
            L[tot].yy = y;
            L[tot].id = i;

            L[++tot].xx = x + w - 1;
            L[tot].yy = y - h + 1;
            L[tot].id = i;
        }
        sort(L + 1, L + 1 + tot, cmp_y);//离散化x，y轴
        int ty = 0;
        for(int i = 1; i <= tot; i++) {
            if(L[i].yy != L[i - 1].yy) ty++;
            if(!s[L[i].id].y_1) s[L[i].id].y_1 = ty;
            else s[L[i].id].y_2 = ty; 
        }
        sort(L + 1, L + 1 + tot, cmp_x);
        int tx = 0;
        for(int i = 1; i <= tot; i++) {
            if(L[i].xx != L[i - 1].xx) tx++;
            if(!s[L[i].id].x_2) s[L[i].id].x_2 = tx, f[tx][++f[tx][0]] = L[i].id;
            else s[L[i].id].x_1 = tx, g[tx][++g[tx][0]] = L[i].id;
        }
        //for(int i = 1; i <= n; i++) {printf("\nx_1: %d  x_2: %d  y_1: %d  y_2: %d  light: %d\n",  s[i].x_1, s[i].x_2, s[i].y_1, s[i].y_2, s[i].light);}
        //sort(s + 1, s + n + 1, cmp_X);
        int ans = 0;
        for(int i = 1; i <= tx; i++) {
            for(int j = 1; j <= f[i][0]; j++) {
                int v = f[i][j];
                change_1(1, 1, ty, s[v].y_1, s[v].y_2, s[v].light);
            }
            ans = max(ans, /*ask(1, 1, ty)*/tree[1].sum);
            for(int j = 1; j <= g[i][0]; j++) {
                int v = g[i][j];
                change_1(1, 1, ty, s[v].y_1, s[v].y_2, -s[v].light);
            }
        }
        printf("%d\n", ans);
        for(int i = 1; i <= tx; i++) f[i][0] = g[i][0] = 0;
    }
    return 0;
}