很妙的题。但是我今天才补/ll
发现苹果生长的间隔是定值，也就是说，第 \(i\) 个人在某个时刻摘了一棵树上的苹果，那么下一个摘到这个苹果的人确定。设其为 \(p_i\)，连边 \(i \to p_i\)，就构成了一个内向基环森林。还可以顺便给这条边赋一个边权，意义是这两个人摘到苹果的时间差。
再对于每棵苹果树求出第一个摘到它的人 \(v_0\) 和时间 \(t_0\)，于是现在就变成了，苹果树在基环树上走，走的用时是边权。
考虑对于每个询问，把基环树的在环上的点和不在环上的点分开考虑。
-
对于在环上的点：
- 对于一个询问 \((v, t)\)，答案就是有多少棵树在 \(t\) 时间内移到 \(v\) 点。
- 以环上的点为根，那么一棵苹果树会不断往父亲走。于是我们要求 \(t_0 + \operatorname{dis}(v_0, v) \le t\)，设 \(dep_u\) 为点 \(u\) 到根的距离，那么就是 \(t_0 + dep_{v_0} \le t + dep_v\)。
- 显然只有 \(v\) 子树内的苹果树可以移到 \(v\)，于是添加限制 \(dfn_{v_0} \in [L_v, R_v]\)，其中 \(dfn_u\) 为 \(u\) 的 dfn 序，\([L_u, R_u]\) 为子树的 dfn 序区间。
- 这样变成了一个裸的二维数点。对其中一维离散化后扫描线 + 树状数组即可。
-
对于不在环上的点：
- 把环拎出来，设环为 \(c_0 \gets c_1 \gets \cdots \gets c_k\)（其中 \(c_k = c_0\)），设 \(dep_i\) 为在环上不断跳出边，点 \(i\) 到 \(c_0\) 的距离。设环长为 \(len\)。
- 把 \(v_0\) 不在环上的苹果树移到环上。
- 于是对于一棵苹果树 \((c_i, t_0)\) 和一个询问 \((c_j, t)\)，苹果树对询问的贡献为：
\[\begin{cases}\max(0, \left\lfloor\dfrac{t - (t_0 + dep_i - dep_j)}{len}\right\rfloor + 1) & i \ge j \\ \max(0, \left\lfloor\dfrac{t - (t_0 + dep_i - dep_j)}{len}\right\rfloor) & i < j\end{cases} \]- 发现它们的贡献大体相同。于是我们先暂时把 \(i < j\) 的贡献合并到 \(i \ge j\) 中一起算。
- 对 \(i \ge j\) 的贡献式子变换得：
\[\max(0, \left\lfloor\dfrac{t + dep_j - (t_0 + dep_i)}{len}\right\rfloor + 1) \]- 下取整有点难搞，考虑一个分离商和余数的套路：设 \(t + dep_j = q_j \times len + r_j, t_0 + dep_i = q_i \times len + q_i\)，其中 \(r_i, r_j\) 均 \(\le len - 1\)。那么式子被化成：
\[\max(0, q_j - q_i + [r_j \ge r_i]) \]- 发现若 \(q_j \ge q_i\)，则 \(q_j - q_i + [r_j \ge r_i] \ge 0\)；若 \(q_j \le q_i\)，则 \(q_j - q_i + [r_j \ge r_i] \le 0\)。于是考虑规定偏序关系 \(q_j \ge q_i\)，对于询问求出所有满足这条关系的 \(q_j - q_i\) 之和。再加上 \(r_j \ge r_i\)，就变成二维数点了。
- 对于 \(i < j\)，发现它与 \(i \ge j\) 的贡献的区别仅仅是 \(\left\lfloor\dfrac{t + dep_j - (t_0 + dep_i)}{len}\right\rfloor\) 为非负数时减去 \(1\)。于是减去的就是 \(i < j\) 且 \(t - dep_j \ge t_0 + dep_i\) 的个数，也变成二维数点了。
至此我们终于完成了。时间复杂度是线性对数。
代码理清思路后不难写。
code
// Problem: P7217 [JOISC2020] 収穫
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7217
// Memory Limit: 500 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1000100;
const int logn = 20;
ll n, m, q, L, C, a[maxn], b[maxn], lsh[maxn], tot, p[maxn], ew[maxn], dep[maxn], ans[maxn];
int ttot, rt[maxn], bel[maxn], f[maxn / 5][logn], st[maxn], ed[maxn], times, cir[maxn], id[maxn];
bool vis[maxn];
vector<pii> G[maxn];
namespace BIT {
ll c[maxn];
inline void update(ll x, ll d) {
for (int i = x; i <= tot; i += (i & (-i))) {
c[i] += d;
}
}
inline ll query(int x) {
ll res = 0;
for (int i = x; i; i -= (i & (-i))) {
res += c[i];
}
return res;
}
inline ll query(int l, int r) {
return query(r) - query(l - 1);
}
inline void clear(int x) {
for (int i = x; i <= tot; i += (i & (-i))) {
c[i] = 0;
}
}
}
struct node {
ll v, t, id;
node(ll a = 0, ll b = 0, ll c = 0) : v(a), t(b), id(c) {}
} qq[maxn], ap[maxn];
vector<node> va[maxn / 5], vb[maxn / 5];
struct wwh {
ll q, r, id;
wwh(ll a = 0, ll b = 0, ll c = 0) : q(a), r(b), id(c) {}
};
struct pig {
ll k, x, id;
pig(ll a = 0, ll b = 0, ll c = 0) : k(a), x(b), id(c) {}
};
void dfs(int u, int fa) {
f[u][0] = fa;
for (int i = 1; i <= 18; ++i) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
bel[u] = ttot;
st[u] = ++times;
for (pii p : G[u]) {
ll v = p.fst, d = p.scd;
if (v == rt[ttot]) {
vis[u] = vis[v] = 1;
} else {
dep[v] = dep[u] + d;
dfs(v, u);
vis[u] |= vis[v];
}
}
ed[u] = times;
}
void solve() {
scanf("%lld%lld%lld%lld", &n, &m, &L, &C);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
for (int i = 1; i <= m; ++i) {
scanf("%lld", &b[i]);
}
for (int i = 1; i <= n; ++i) {
int pos = upper_bound(a + 1, a + n + 1, (a[i] - C % L + L) % L) - a - 1;
if (!pos) {
pos = n;
}
p[i] = pos;
ll w = 0, x = (a[i] - a[p[i]] + L) % L;
if (C % L <= x) {
w = C / L * L + x;
} else {
w = (C / L + 1) * L + x;
}
G[p[i]].pb(i, w);
ew[i] = w;
}
for (int i = 1; i <= n; ++i) {
if (!bel[i]) {
++ttot;
int u = i;
while (!bel[u]) {
bel[u] = ttot;
u = p[u];
}
rt[ttot] = u;
dfs(u, 0);
}
}
scanf("%lld", &q);
for (int i = 1; i <= q; ++i) {
scanf("%lld%lld", &qq[i].v, &qq[i].t);
qq[i].id = i;
}
for (int i = 1; i <= m; ++i) {
int pos = upper_bound(a + 1, a + n + 1, b[i]) - a - 1;
if (!pos) {
pos = n;
}
ap[i] = node(pos, (b[i] - a[pos] + L) % L);
}
tot = n;
sort(ap + 1, ap + m + 1, [&](const node &a, const node &b) {
return a.t + dep[a.v] < b.t + dep[b.v];
});
sort(qq + 1, qq + q + 1, [&](const node &a, const node &b) {
return a.t + dep[a.v] < b.t + dep[b.v];
});
for (int i = 1, j = 1; i <= q; ++i) {
ll val = qq[i].t + dep[qq[i].v];
while (j <= m && ap[j].t + dep[ap[j].v] <= val) {
BIT::update(st[ap[j].v], 1);
++j;
}
if (vis[qq[i].v]) {
continue;
}
ans[qq[i].id] += BIT::query(st[qq[i].v], ed[qq[i].v]);
}
for (int i = 1; i <= m; ++i) {
BIT::clear(st[ap[i].v]);
}
for (int i = 1; i <= m; ++i) {
ll v = ap[i].v, t = ap[i].t;
if (!vis[v]) {
for (int j = 18; ~j; --j) {
if (f[v][j] && !vis[f[v][j]]) {
t += dep[v] - dep[f[v][j]];
v = f[v][j];
}
}
t += ew[v];
v = f[v][0];
ap[i] = node(v, t);
}
}
mems(dep, 0);
for (int i = 1; i <= m; ++i) {
va[bel[ap[i].v]].pb(ap[i]);
}
for (int i = 1; i <= q; ++i) {
if (vis[qq[i].v]) {
vb[bel[qq[i].v]].pb(qq[i]);
}
}
mems(vis, 0);
for (int _ = 1; _ <= ttot; ++_) {
int u = rt[_], ctot = 0;
while (!vis[u]) {
cir[++ctot] = u;
vis[u] = 1;
u = p[u];
}
cir[++ctot] = cir[1];
reverse(cir + 1, cir + ctot + 1);
for (int i = 2; i <= ctot; ++i) {
dep[cir[i]] = dep[cir[i - 1]] + ew[cir[i]];
}
ll len = dep[cir[ctot]];
dep[cir[1]] = 0;
for (int i = 1; i < ctot; ++i) {
id[cir[i]] = i;
}
vector<wwh> av, qv;
tot = 0;
for (node u : va[_]) {
ll x = u.t + dep[u.v];
ll q = x / len, r = x % len;
lsh[++tot] = r;
av.pb(q, r);
}
for (node u : vb[_]) {
ll x = u.t + dep[u.v], id = u.id;
ll q = x / len, r = x % len;
lsh[++tot] = r;
qv.pb(q, r, id);
}
sort(av.begin(), av.end(), [&](const wwh &a, const wwh &b) {
return a.q < b.q;
});
sort(qv.begin(), qv.end(), [&](const wwh &a, const wwh &b) {
return a.q < b.q;
});
sort(lsh + 1, lsh + tot + 1);
tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
for (wwh &u : av) {
u.r = lower_bound(lsh + 1, lsh + tot + 1, u.r) - lsh;
}
for (wwh &u : qv) {
u.r = lower_bound(lsh + 1, lsh + tot + 1, u.r) - lsh;
}
lll s = 0;
for (int i = 0, j = 0; i < (int)qv.size(); ++i) {
while (j < (int)av.size() && av[j].q <= qv[i].q) {
s += av[j].q;
BIT::update(av[j].r, 1);
++j;
}
ans[qv[i].id] += (lll)qv[i].q * j - s + BIT::query(qv[i].r);
}
for (wwh u : av) {
BIT::clear(u.r);
}
tot = 0;
vector<pig> vp, vq;
for (node u : va[_]) {
ll k = id[u.v], x = u.t + dep[u.v];
vp.pb(k, x);
lsh[++tot] = x;
}
for (node u : vb[_]) {
ll k = id[u.v], x = u.t + dep[u.v], id = u.id;
vq.pb(k, x, id);
lsh[++tot] = x;
}
sort(vp.begin(), vp.end(), [&](const pig &a, const pig &b) {
return a.k < b.k;
});
sort(vq.begin(), vq.end(), [&](const pig &a, const pig &b) {
return a.k < b.k;
});
sort(lsh + 1, lsh + tot + 1);
tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
for (pig &u : vp) {
u.x = lower_bound(lsh + 1, lsh + tot + 1, u.x) - lsh;
}
for (pig &u : vq) {
u.x = lower_bound(lsh + 1, lsh + tot + 1, u.x) - lsh;
}
for (int i = 0, j = 0; i < (int)vq.size(); ++i) {
while (j < (int)vp.size() && vp[j].k < vq[i].k) {
BIT::update(vp[j].x, 1);
++j;
}
ans[vq[i].id] -= BIT::query(vq[i].x);
}
for (pig u : vp) {
BIT::clear(u.x);
}
}
for (int i = 1; i <= q; ++i) {
printf("%lld\n", ans[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}