题解 P6349 [PA2011]Kangaroos

此题除了能用kd树，还能用莫队做

这篇题解分析的是kd树做法qwq

分析

考虑某询问\([A, B]\)与某元素\([l, r]\)有交的条件：\(l \leq B 且 r \geq A\)

可以发现是二维偏序，于是我们用kd树就能快速查询与某询问有交的元素集合

考虑直接回答每个询问，发现因为所得元素集合在序列\(a\)上是无序的，难以快速合并答案

怎么办？不会了QAQ

想一想，我们能快速查询与某询问有交的元素集合，反过来，我们也能快速查询与某元素有交的询问集合

这样，对原问题就有另一种解决思路：先将询问离线，然后把各个元素的贡献加给其对应的询问集合，最后回答每一个询问

同样的问题，无序的贡献难以合并，在这种思路中可以轻松解决：按照\(a\)的顺序加贡献即可

具体的贡献合并略

代码坑是下传标记后标记忘清零（没用到的标记也可能要清零啊！awa）

代码

#include 

#define lep(x, l, r) for(int x = (l), _ = (r); x <= _; ++x)
#define rep(x, r, l) for(int x = (r), _ = (l); x >= _; --x)

using namespace std;

template void read(T &x) {
    x = 0;
    char f = 0, c = getchar();
    while(!isdigit(c)) f = (c == '-'), c = getchar();
    if(f) while(isdigit(c)) x = x * 10 - c + 48, c = getchar();
    else while(isdigit(c)) x = x * 10 + c - 48, c = getchar();
}
template void bemin(T &x, T y) { if(x > y) x = y; }
template void bemax(T &x, T y) { if(x < y) x = y; }

const int N = 5e4 + 5, M = 2e5 + 5;

int n, m;

int ans[M];

struct range {
    int l, r, id;
} a[N], q[M];

bool cmpx(range X, range Y) {
    return X.l < Y.l;
}
bool cmpy(range X, range Y) {
    return X.r < Y.r;
}

struct KD_Tree {
    struct node {
	int xl, xr, yl, yr;
	int qtag, htag, mtag;
	bool tag0;
	node(int xl = 0, int xr = 0, int yl = 0, int yr = 0) {
	    this->xl = xl, this->xr = xr, this->yl = yl, this->yr = yr;
	    qtag = htag = mtag = 0, tag0 = false;
	}
    } T[M << 2];
    inline int ls(int now) { return now << 1; }
    inline int rs(int now) { return now << 1 | 1; }
    inline void push_down(int now) {
	node &x = T[now], &L = T[ls(now)], &R = T[rs(now)];
	if(!L.tag0) L.qtag += x.qtag;
	L.htag += x.qtag;
	if(!R.tag0) R.qtag += x.qtag;
	R.htag += x.qtag;
	if(x.tag0) {
	    L.mtag = max(L.mtag, max(L.htag, x.mtag));
	    L.htag = x.htag, L.tag0 = true;
	    R.mtag = max(R.mtag, max(R.htag, x.mtag));
	    R.htag = x.htag, R.tag0 = true;
	}
	x.qtag = x.htag = 0, x.tag0 = false;
    }
    inline void update(int now) {
	node &x = T[now], &L = T[ls(now)], &R = T[rs(now)];
	x.xl = min(L.xl, R.xl), x.xr = max(L.xr, R.xr);
	x.yl = min(L.yl, R.yl), x.yr = max(L.yr, R.yr);
    }
    void build(int l, int r, bool k = true, int now = 1) {
	if(l == r) {
	    T[now] = node(q[l].l, q[l].l, q[l].r, q[l].r);
	    return;
	}
	int mid = (l + r) >> 1;
	nth_element(q + l, q + mid, q + r + 1, k? cmpx : cmpy);
	build(l, mid, !k, ls(now)), build(mid + 1, r, !k, rs(now));
	update(now);
    }
    void add1(int xl, int xr, int yl, int yr, int now = 1) {
	node &x = T[now];
	if(x.xr < xl || x.xl > xr || x.yr < yl || x.yl > yr) return;
	if(xl <= x.xl && x.xr <= xr && yl <= x.yl && x.yr <= yr) {
	    if(!x.tag0) ++x.qtag;
	    ++x.htag;
	    return;
	}
	push_down(now);
	add1(xl, xr, yl, yr, ls(now)), add1(xl, xr, yl, yr, rs(now));
    }
    void change0(int xl, int xr, int yl, int yr, int now = 1) {
	node &x = T[now];
	if(x.xr < xl || x.xl > xr || x.yr < yl || x.yl > yr) return;
	if(xl <= x.xl && x.xr <= xr && yl <= x.yl && x.yr <= yr) {
	    x.mtag = max(x.mtag, x.htag);
	    x.htag = 0, x.tag0 = true;
	    return;
	}
	push_down(now);
	change0(xl, xr, yl, yr, ls(now)), change0(xl, xr, yl, yr, rs(now));
    }
    void get_ans(int l, int r, int now = 1) {
	if(l == r) {
	    ans[q[l].id] = max(T[now].htag, T[now].mtag);
	    return;
	}
	push_down(now);
	int mid = (l + r) >> 1;
	get_ans(l, mid, ls(now)), get_ans(mid + 1, r, rs(now));
    }
} kdt;



int main() {
    read(n), read(m);
    lep(i, 1, n) {
	read(a[i].l), read(a[i].r);
    }
    lep(i, 1, m) {
	read(q[i].l), read(q[i].r);
	q[i].id = i;
    }
    kdt.build(1, m);
    lep(i, 1, n) {
	int l = a[i].l, r = a[i].r;
	kdt.add1(1, r, l, 1e9);
	kdt.change0(1, 1e9, 1, l - 1);
	kdt.change0(r + 1, 1e9, 1, 1e9);
    }
    kdt.get_ans(1, m);
    lep(i, 1, m) {
	cout << ans[i] << "\n";
    }
    return 0;
}