泉州市建设局网站,网页视频怎么下载到u盘,wordpress nginx安装,百度推广客户端手机版JZOJ 3854
题意
有 n n n 个人#xff0c;每个人有地位 r i r_i ri 和年龄 a i a_i ai#xff0c;对于一个若干人组成的小组#xff0c;定义其队长为地位最高的成员#xff08;若相等则取二者均可#xff09;#xff0c;其他成员的年龄与队长的差不能超过 k k …JZOJ 3854
题意
有 n n n 个人每个人有地位 r i r_i ri 和年龄 a i a_i ai对于一个若干人组成的小组定义其队长为地位最高的成员若相等则取二者均可其他成员的年龄与队长的差不能超过 k k k。 q q q 次询问若将 x , y x,y x,y 安排在同一个小组那么这个小组最多多少人。
题解
先预处理每个人当队长时小组最多有多少人。设这个值为 c n t i cnt_i cnti。
具体来说按 r r r 排序对于 i i i 需要求前面 i i i 个人有多少个人的年龄在 [ a i − k , a i k ] [a_i-k,a_ik] [ai−k,aik] 的区间内。用一个动态开点权值线段树即可。下标是年龄。
考虑对询问离线。不妨假设 r x ≤ r y r_x\le r_y rx≤ry那么对于一个询问 i i i能够包含 x i , y i x_i,y_i xi,yi 的队长的范围是 r ≥ r y i , max ( a x i , a y i ) − k ≤ a ≤ min ( a x i , a y i ) k r\ge r_{y_i},\max (a_{x_i},a_{y_i}) - k\le a\le \min(a_{x_i},a_{y_i})k r≥ryi,max(axi,ayi)−k≤a≤min(axi,ayi)k。因为与 x , y x,y x,y 的年龄差要同时小于 k k k所以选范围小的区间。
按 r y r_y ry 为关键值将询问从大到小排序。然后一个动态开点权值线段树下标是年龄叶子节点存储 c n t i cnt_i cnti。这样对于一个询问只需要查找在 [ max ( a x i , a y i ) − k , min ( a x i , a y i ) k ] [\max (a_{x_i},a_{y_i}) - k,\min(a_{x_i},a_{y_i})k] [max(axi,ayi)−k,min(axi,ayi)k] 区间内的最大值即可。
时间复杂度 O ( n log w ) O(n\log w) O(nlogw)。
实现
记得判 -1。注意输入的标号是排序前的标号要处理一下。
#include bits/stdc.h
using namespace std;
const int N 100005, W 1e9;
int n, K, Q, ans[N], vp[N], cnt[N];
int tr[N 4], mx[N 4], rt1 0, rt2 0, tot1 0, tot2 0, ls1[N 4], rs1[N 4], ls2[N 4], rs2[N 4];
struct mem {int r, ag, id;bool operator (const mem T) const { return r T.r; }
} a[N];
struct Query {int x, y, id;bool operator (const Query T) const { return a[y].r a[T.y].r; }
} q[N];
void upd1(int rt, int x, int y, int pos, int val) {if (!rt) rt tot1;if (x y) { tr[rt] val; return; }int mid x y 1;if (pos mid) upd1(ls1[rt], x, mid, pos, val);else upd1(rs1[rt], mid 1, y, pos, val);tr[rt] tr[ls1[rt]] tr[rs1[rt]];
}
int qry1(int rt, int x, int y, int l, int r) {if (l y || r x || !rt) return 0;if (l x y r) return tr[rt];int mid x y 1;return qry1(ls1[rt], x, mid, l, r) qry1(rs1[rt], mid 1, y, l, r);
}
void upd2(int rt, int x, int y, int pos, int val) {if (!rt) rt tot2;if (x y) { mx[rt] max(mx[rt], val); return; }int mid x y 1;if (pos mid) upd2(ls2[rt], x, mid, pos, val);else upd2(rs2[rt], mid 1, y, pos, val);mx[rt] max(mx[ls2[rt]], mx[rs2[rt]]);
}
int qry2(int rt, int x, int y, int l, int r) {if (l y || r x || !rt) return 0;if (l x y r) return mx[rt];int mid x y 1;return max(qry2(ls2[rt], x, mid, l, r), qry2(rs2[rt], mid 1, y, l, r));
}
int main() {scanf(%d%d, n, K);for (int i 1; i n; i) scanf(%d, a[i].r), a[i].id i;for (int i 1; i n; i) scanf(%d, a[i].ag);sort(a 1, a n 1);for (int i 1; i n; i) vp[a[i].id] i;for (int i 1; i n; ) {int j i;while (a[j].r a[j 1].r) upd1(rt1, 1, W, a[j].ag, 1), j;upd1(rt1, 1, W, a[j].ag, 1);for (; i j; i) cnt[i] qry1(rt1, 1, W, a[i].ag - K, a[i].ag K);}scanf(%d, Q);for (int i 1; i Q; i) {scanf(%d%d, q[i].x, q[i].y), q[i].x vp[q[i].x], q[i].y vp[q[i].y], q[i].id i;if (q[i].x q[i].y) swap(q[i].x, q[i].y);}sort(q 1, q Q 1);int k n;for (int i 1; i Q; i) {while (q[i].y k) upd2(rt2, 1, W, a[k].ag, cnt[k]), k--;ans[q[i].id] qry2(rt2, 1, W, max(a[q[i].x].ag, a[q[i].y].ag) - K, min(a[q[i].x].ag, a[q[i].y].ag) K);if (ans[q[i].id] 2) ans[q[i].id] -1;}for (int i 1; i Q; i) printf(%d\n, ans[i]);return 0;
}
