整体二分+扫描线树状数组

具体做法看这里a
CODE

#include <cctype>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

template<class T>inline void read(T &res) {

    char ch; int flg = 1; for(;!isdigit(ch=getchar());)if(ch=='-')flg=-flg;

    for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0'); res*=flg;

}

const int MAXN = 40005;

struct matrix {

	int x[2], y[2], val;

	matrix(){}

	matrix(int minx, int maxx, int miny, int maxy, int v) {

		x[0] = minx, x[1] = maxx;

		y[0] = miny, y[1] = maxy; val = v;

	}

}a[MAXN<<1], b[MAXN<<2];

struct Query { int x, y, k, id; }q[MAXN], tmp[MAXN];

int n, m, tot, Q, ans[MAXN], fir[MAXN], to[MAXN<<1], nxt[MAXN<<1], cnt;

int mylg2[MAXN], dep[MAXN], f[MAXN][16], in[MAXN], out[MAXN], val[MAXN], tmr;

inline void add(int u, int v) {

	to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt;

	to[++cnt] = u; nxt[cnt] = fir[v]; fir[v] = cnt;

}

void dfs(int u) {

	in[u] = ++tmr;

	dep[u] = dep[f[u][0]] + 1;

	for(int i = fir[u]; i; i = nxt[i])

		if(to[i] != f[u][0])

			f[to[i]][0] = u, dfs(to[i]);

	out[u] = tmr;

}

inline void pre() {

	mylg2[1] = 0;

	for(int j = 1; j < 16; ++j) {

		mylg2[1<<j] = j;

		for(int i = 1; i <= n; ++i)

			f[i][j] = f[f[i][j-1]][j-1];

	}

}

inline int find(int u, int v) {

	int tmp = dep[v] - dep[u] - 1;

	while(tmp)

		v = f[v][mylg2[tmp&-tmp]], tmp -= tmp&-tmp;

	return v;

}

inline bool cmp(const matrix &A, const matrix &B) { return A.y[0] < B.y[0]; }

inline bool cmpv(const matrix &A, const matrix &B) { return A.val < B.val; }

inline bool cmpQ(const Query &A, const Query &B) { return A.y < B.y; }

int T[MAXN];

inline void upd(int x, int val) {

	while(x <= n) T[x] += val, x += x&-x;

}

inline int qsum(int x) {

	int res = 0;

	while(x) res += T[x], x -= x&-x;

	return res;

}

inline void calc(int ql, int qr, int L, int R) {

	for(int i = ql; i <= qr; ++i) val[i] = 0;

	int l = 1, r = tot+1, mid;

	while(l < r) {

		mid = (l + r) >> 1;

		if(a[mid].val < L) l = mid+1;

		else r = mid;

	}

	if(l > tot) return;

	int cur = 0;

	for(int i = l; i <= tot && a[i].val <= R; ++i) {

		b[++cur] = matrix(a[i].x[0], a[i].x[1], a[i].y[0], 0, 1);

		b[++cur] = matrix(a[i].x[0], a[i].x[1], a[i].y[1]+1, 0, -1);

	}

	if(!cur) return;

	sort(b + 1, b + cur + 1, cmp);

	sort(q + ql, q + qr + 1, cmpQ);

	int j = 1;

	for(int i = ql; i <= qr; ++i) {

		while(j <= cur && b[j].y[0] <= q[i].y) {

			upd(b[j].x[0], b[j].val), upd(b[j].x[1]+1, -b[j].val);

			++j;

		}

		val[i] = qsum(q[i].x);

	}

	while(j <= cur) upd(b[j].x[0], b[j].val), upd(b[j].x[1]+1, -b[j].val), ++j;

}

void solve(int ql, int qr, int vl, int vr) {

	if(ql > qr) return;

	if(vl == vr) { for(int i = ql; i <= qr; ++i) ans[q[i].id] = vl; return; }

	int vmid = (vl + vr) >> 1;

	calc(ql, qr, vl, vmid);

	int st = ql, ed = qr;

	for(int i = ql; i <= qr; ++i)

		if(val[i] >= q[i].k) tmp[st++] = q[i];

		else q[i].k -= val[i], tmp[ed--] = q[i];

	for(int i = ql; i <= qr; ++i) q[i] = tmp[i];

	solve(ql, st-1, vl, vmid);

	solve(ed+1, qr, vmid+1, vr);

}

int main () {

	read(n), read(m), read(Q);

	for(int i = 1, x, y; i < n; ++i)

		read(x), read(y), add(x, y);

	dfs(1); pre();

	int u, v, w, c;

	while(m--) {

		read(u), read(v), read(c);

		if(in[u] > in[v]) swap(u, v);

		if(in[u] <= in[v] && out[v] <= out[u]) { //u is anc of v

			w = find(u, v);

			a[++tot] = matrix(1, in[w]-1, in[v], out[v], c);

			if(out[w] < n) a[++tot] = matrix(in[v], out[v], out[w]+1, n, c);

		}

		else a[++tot] = matrix(in[u], out[u], in[v], out[v], c);

	}

	sort(a + 1, a + tot + 1, cmpv);

	for(int i = 1; i <= Q; ++i) {

		read(q[i].x), read(q[i].y), read(q[i].k), q[i].id = i;

		q[i].x = in[q[i].x], q[i].y = in[q[i].y];

		if(q[i].x > q[i].y) swap(q[i].x, q[i].y);

	}

	solve(1, Q, 0, 1e9);

	for(int i = 1; i <= Q; ++i) printf("%d\n", ans[i]);

}
巴特西

BZOJ 4009: [HNOI2015]接水果 (整体二分+扫描线树状数组)

CODE

最新文章

热门文章

巴特西

BZOJ 4009: [HNOI2015]接水果 (整体二分+扫描线 树状数组)

CODE

最新文章

热门文章

BZOJ 4009: [HNOI2015]接水果 (整体二分+扫描线树状数组)
