题解 P6514 【[QkOI#R1] Quark and Strings】

Ireliaღ · 2020-05-04 19:19:03 · 题解

比赛中思考过程最短的一道题。

考虑转化一下题意，每次修改相当于添加一条从l到r的线段，每次查询就是询问贯穿区间[l, r]的线段个数。

把每条线段的左端点当做第一维，右端点当做第二维，那么这条线段可以对应坐标系中的一个点，查询就可以看做询问x \in [1, l]且y \in [r, n]的矩形上的点数，剩下的就是一个kd-tree的模板了。

代码如下

#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e5 + 5;
const double A = 0.7;

struct Data{
    int x[2];

    Data(int a, int b) {
        x[0] = a;
        x[1] = b;
    }

    Data() {}
};

int operator == (const Data &a, const Data &b) {
    return a.x[0] == b.x[0] && a.x[1] == b.x[1];
}

struct Node{
    Data pos;
    Node *ch[2];
    int cnt, sum, cov;
    int mn[2], mx[2];

    Node(Data pos, int cnt) : pos(pos), cnt(cnt) {
        cov = 1;
        sum = cnt;
        for (int i = 0; i < 2; i++) mn[i] = mx[i] = pos.x[i];
        ch[0] = ch[1] = NULL;
    }

    Node() {}
}npool[MAXN];

int Comp0(Node *a, Node *b) {
    if (a->pos.x[0] != b->pos.x[0]) return a->pos.x[0] < b->pos.x[0];
    else return a->pos.x[1] < b->pos.x[1];
}

int Comp1(Node *a, Node *b) {
    if (a->pos.x[1] != b->pos.x[1]) return a->pos.x[1] < b->pos.x[1];
    else return a->pos.x[0] < b->pos.x[0];
}

int n, m;
int ncnt;
Node *rt;
Node *tree[MAXN];
int tcnt;

Node *New(Data pos, int cnt) {
    npool[ncnt] = Node(pos, cnt);
    return &npool[ncnt++];
}

void Update(Node *now) {
    now->cov = 1 + (now->ch[0] ? now->ch[0]->cov : 0) + (now->ch[1] ? now->ch[1]->cov : 0);
    now->sum = now->cnt + (now->ch[0] ? now->ch[0]->sum : 0) + (now->ch[1] ? now->ch[1]->sum : 0);
    for (int i = 0; i < 2; i++) now->mn[i] = now->mx[i] = now->pos.x[i];
    for (int i = 0; i < 2; i++) {
        if (now->ch[i]) {
            for (int j = 0; j < 2; j++) {
                now->mn[j] = min(now->mn[j], now->ch[i]->mn[j]);
                now->mx[j] = max(now->mx[j], now->ch[i]->mx[j]);
            }
        }
    }
}

int Bad(Node *now) {
    int ls = now->ch[0] ? now->ch[0]->cov : 0;
    int rs = now->ch[1] ? now->ch[1]->cov : 0;
    return 1.0 * ls > A * now->cov || 1.0 * rs > A * now->cov;
}

void DFS(Node *now) {
    if (!now) return;
    DFS(now->ch[0]);
    DFS(now->ch[1]);
    tree[++tcnt] = now;
    now->ch[0] = now->ch[1] = NULL;
    Update(now);
}

void Rebuild(Node *&now, int l, int r, int d) {
    if (l > r) return;
    int mid = l + r >> 1;
    if (d) nth_element(tree + l, tree + mid, tree + r + 1, Comp1);
    else nth_element(tree + l, tree + mid, tree + r + 1, Comp0); 
    now = tree[mid];
    Rebuild(now->ch[0], l, mid - 1, (d + 1) % 2);
    Rebuild(now->ch[1], mid + 1, r, (d + 1) % 2);
    Update(now);
}

void Maintain(Node *&now, int d) {
    if (Bad(now)) {
        tcnt = 0;
        DFS(now);
        Rebuild(now, 1, tcnt, d);
    }
}

void Insert(Node *&now, Data pos, int cnt, int d) {
    if (!now) {
        now = New(pos, cnt);
        return;
    }
    if (pos == now->pos) {
        now->cnt += cnt;
        Update(now);
        return;
    }
    if (pos.x[d] < now->pos.x[d]) Insert(now->ch[0], pos, cnt, (d + 1) % 2);
    else Insert(now->ch[1], pos, cnt, (d + 1) % 2);
    Update(now);
    Maintain(now, d);
}

int Inside(Node *now, int mn[], int mx[]) {
    for (int i = 0; i < 2; i++) {
        if (now->pos.x[i] < mn[i] || now->pos.x[i] > mx[i]) return 0;
    }
    return 1;
}

int AllIn(Node *now, int mn[], int mx[]) {
    for (int i = 0; i < 2; i++) {
        if (now->mn[i] < mn[i] || now->mx[i] > mx[i]) return 0;
    }
    return 1;
}

int AllOut(Node *now, int mn[], int mx[]) {
    for (int i = 0; i < 2; i++) {
        if (now->mn[i] > mx[i] || now->mx[i] < mn[i]) return 1;
    }
    return 0;
}

int Query(Node *now, int mn[], int mx[]) {
    if (!now) return 0;
    if (AllIn(now, mn, mx)) return now->sum;
    if (AllOut(now, mn, mx)) return 0;
    return (Inside(now, mn, mx) ? now->cnt : 0) + Query(now->ch[0], mn, mx) + Query(now->ch[1], mn, mx);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int op, x, y;
    int mn[2], mx[2];
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> op >> x >> y;
        if (op == 1) {
            Insert(rt, Data(x, y), 1, 0);
        } else {
            mn[0] = 1; mx[0] = x;
            mn[1] = y; mx[1] = n;
            cout << Query(rt, mn, mx) << '\n';
        }
    }
    return 0;
}