RE #34 CF诊断SegTreeRemove第一行内存错误
  • 板块CF19D Points
  • 楼主未泯
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/2 15:01
  • 上次更新2024/4/2 18:04:55
查看原帖
RE #34 CF诊断SegTreeRemove第一行内存错误
195349
未泯楼主2024/4/2 15:01
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>

using namespace std;
#define N 200010

inline int in() {
    int x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0')ch = getchar();
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}

int op[N] = {0};
int ori_x[N] = {0}, ori_y[N] = {0};
struct Point {
    int x, y;
    int index;
};
Point ori_point[N];
Point pre_point[N];
Point point[N];
Point point_order[N];


bool cmpx(Point a, Point b) {
    return b.x > a.x;
}

bool cmpy(Point a, Point b) {
    return b.y > a.y;
}

bool cmp(Point a, Point b) {
    if (a.x == b.x)return b.y > a.y;
    return b.x > a.x;
}

map<pair<int, int>, int> Index_Pre;
map<pair<int, int>, pair<int, int> > Ori;
struct SegTree {
    int l = 0, r = 0;
    int v = 0;
} tree[900010];

set<int> Top[N];

void BuildSegTree(SegTree *p, int root, int l, int r) {
    p[root].l = l, p[root].r = r;
    if (l == r)return;
    int mid = (l + r) >> 1;
    BuildSegTree(p, root << 1, l, mid);
    BuildSegTree(p, root << 1 | 1, mid + 1, r);
}

void SegTreeAdd(SegTree *p, int root, int x, int y) {
    if (p[root].l == x && p[root].r == x) {
        p[root].v = max(p[root].v, y);
        return;
    }
    int mid = (p[root].l + p[root].r) >> 1;
    if (x <= mid)SegTreeAdd(p, root << 1, x, y);
    if (x > mid)SegTreeAdd(p, root << 1 | 1, x, y);
    p[root].v = max(p[root << 1].v, p[root << 1 | 1].v);
}

void SegTreeRemove(SegTree *p, int root, int x, int y) {
    if (p[root].l == x && p[root].r == x) {
        if (p[root].v == y) {
            if (Top[x].empty())p[root].v = 0;
            else p[root].v = *Top[x].rbegin();
            return;
        }
    }
    int mid = (p[root].l + p[root].r) >> 1;
    if (x <= mid)SegTreeRemove(p, root << 1, x, y);
    if (x > mid)SegTreeRemove(p, root << 1 | 1, x, y);
    p[root].v = max(p[root << 1].v, p[root << 1 | 1].v);
}

int SegTreeQuery(SegTree *p, int root, int x, int y) {
    int result = -1;
    if (p[root].v <= y)return -1;
    if (p[root].l == p[root].r && p[root].l > x) {
        if (p[root].v > y)return p[root].l;
        else return -1;
    }
    int mid = (p[root].l + p[root].r) >> 1;
    if (x >= mid)result = SegTreeQuery(p, root << 1 | 1, x, y);
    if (x < mid) {
        result = SegTreeQuery(p, root << 1, x, y);
        if (result != -1)return result;
        else return SegTreeQuery(p, root << 1 | 1, x, y);
    }
    return result;
}

int main() {
    //freopen("D:\\Development_Software\\CLion\\CLionProjects\\Test\\in", "r", stdin);
    int n = in();
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        char s[8];
        scanf("%s", s);
        if (s[0] == 'a')op[i] = 1;
        if (s[0] == 'r')op[i] = 2;
        if (s[0] == 'f')op[i] = 3;
        ori_x[i] = in(), ori_y[i] = in();
        if (Index_Pre.find({ori_x[i], ori_y[i]}) == Index_Pre.end()) {
            pre_point[++cnt].x = ori_x[i], pre_point[cnt].y = ori_y[i];
            pre_point[cnt].index = cnt;
            ori_point[cnt] = pre_point[cnt];
            Index_Pre[{ori_x[i], ori_y[i]}] = cnt;
        }
    }
    pre_point[0] = {-1, -1, 0};//pre_point ori_point 去重后的原坐标
    //for (int i = 1; i <= cnt; i++)printf("%d %d\n", ori_point[i].x, ori_point[i].y);
    sort(pre_point + 1, pre_point + 1 + cnt, cmpx); //point 离散化后的原坐标
    int cntx = 0;
    for (int i = 1; i <= cnt; i++) {
        if (pre_point[i].x > pre_point[i - 1].x)cntx++;
        point[pre_point[i].index].x = cntx;
        point_order[pre_point[i].index].x = cntx;
    }
    sort(pre_point + 1, pre_point + 1 + cnt, cmpy);
    int cnty = 0;
    for (int i = 1; i <= cnt; i++) {
        if (pre_point[i].y > pre_point[i - 1].y)cnty++;
        point[pre_point[i].index].y = cnty;
        point_order[pre_point[i].index].y = cnty;
    }
    //for (int i = 1; i <= cnt; i++)printf("%d %d\n", point[i].x, point[i].y);
    sort(point_order + 1, point_order + 1 + cnt, cmp);//point_order 离散化后且排序后的原坐标
    //for (int i = 1; i <= cnt; i++)printf("%d %d\n", point_order[i].x, point_order[i].y);
    for (int i = 1; i <= cnt; i++) {
        Ori[{point[i].x, point[i].y}] = {ori_point[i].x, ori_point[i].y};
    }
    BuildSegTree(tree, 1, 1, cntx);
    for (int i = 1; i <= n; i++) {
        int index = Index_Pre[{ori_x[i], ori_y[i]}];
        int x = point[index].x, y = point[index].y;
        if (op[i] == 1) {
            Top[x].insert(y);
            SegTreeAdd(tree, 1, x, y);
        }
        if (op[i] == 2) {
            Top[x].erase(y);
            SegTreeRemove(tree, 1, x, y);
        }
        if (op[i] == 3) {
            int tx = SegTreeQuery(tree, 1, x, y);
            if (tx == -1) {
                printf("-1\n");
                continue;
            }
            int ty = *Top[tx].upper_bound(y);
            pair<int, int> ans = Ori[{tx, ty}];
            printf("%d %d\n", ans.first, ans.second);
        }
    }
}
2024/4/2 15:01
加载中...