自动搬运

查看原文

来自洛谷，原作者为

	wrpwrp Cai

搬运于2025-08-24 22:27:46，当前版本为作者最后更新于2021-11-08 15:11:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

My Blog

题目大意

Problem Link

IOI 农场是一个种植苹果的农场，以位于一个巨大的环形湖周边而闻名。 在 IOI 农场，共有 $N$ 个员工，从 $1$ 到 $N$ 标号。共有 $M$ 棵苹果树，从 $1$ 到 $M$ 标号。湖的周长为 $L$ 米。 在初始时刻，第 $i$ ($1 \leq i \leq N$) 位员工站在离湖最北端顺时针 $A_i \,\mathrm m$ 米的位置，第 $j$ ($1 \leq j \leq M$) 棵苹果树在离湖最北端顺时针 $B_i \,\mathrm m$ 的位置。保证这 $N + M$ 个整数 $A_i, B_i$ 互不相同。 由于 IOI 农场苹果树是经过改良的特殊品种，一棵树同时只能结一个苹果。同时，如果一棵树上的苹果被摘掉了，在恰好 $C \,\mathrm s$ 后会长出一个苹果。 在初始时刻，每棵树上都有一个苹果，同时每个员工开始沿着顺时针方向移动。员工的移动速度是 $1 \,\mathrm{m/s}$。如果一个员工在某一时刻到达了一颗长有苹果的苹果树，他会摘掉这个苹果 (如果在到达时恰好长出苹果，员工也会摘掉)。这里我们忽略员工摘苹果的时间。 K 主席是 IOI 农场的股东。因为你是 IOI 农场的一名管理人员，K 主席会不断问你每个员工的工作效率。更一般的，K 主席会有 $Q$ 个问题，第 $k$ ($1 \leq k \leq Q$) 个问题的形式如下： 询问前 $T_k \,\mathrm s$ 中，第 $V_k$ 个员工一共收获了多少个苹果 (注意包含第 $T_k \,\mathrm s$ 末收获的苹果)。 请编写一个程序来回答这些询问。

题解

很震撼的题。

首先默认把 $A, B$ 排序。

问题转化

观察到这个 $C$ 是一个定值，也就是苹果的生长周期是一个定值。我们考虑一下这个定值带给了我们什么想法。

因为人的移动速度是相同的， $C$ 为定值，那么一个人摘下这个苹果以后，下一个摘这个苹果的人是固定的。不妨我们令某个人 $i$ 摘完以后下一个摘这个苹果的人的编号是 $p_i$ 。那么我们连边 $i \rightarrow p_i$ 。

那么我们这样就可以得到一棵关于人的基环内向树。

考虑 $p_i$ 如何计算。在 $A$ 中查找在 $\mod L$ 意义下 $A_i - C$ 前的第一个数的下标就是 $p_i$， 用一个 $\text{set}$ 维护即可。

然后我们考虑确定这棵树的边权， 不妨令边权 $w_i$ 表示两个人之间摘到苹果的时间差， 那么 $w_i$ 是满足如下条件的最小正整数。

• $w_i \geq C$
• $w_i \equiv A_i - A_{p_i} \pmod L$

可以直接计算得出 $w_i = \lfloor\frac{C + L - ((A_i - A_{p_i} + L) \mod L) - 1}{L}\rfloor \times L + A_i - A_{p_i}$ 。

可以发现， 一个苹果的路径只会在一棵基环树上面跑， 我们现在对每棵基环树分开考虑。

对于一个人， 我们对于其是否在基环树的环上分开讨论。

对于不在环上的人的处理

不妨对每棵苹果树处理出一个数对 $(v_0, t_0)$ 表示 $t_0$ 时刻 $v_0$ 号人第一次摘下了这个苹果。那么现在我们的问题就是求某个点 $v$ 的子树里有多少数对 $(v_0, t_0)$ 满足 $t_0 + \text{dist}(v_0, v) \leq t$ ， 也就是 $t_0 + dep_{v_0} \leq t + dep_v$ 。加上 $\text{dfs}$ 序的限制，可以在离散化以后二维数点求出。

对于在环上的人的处理

同样考虑处理一个数对 $(v_0, t_0)$ 表示 $t_0$ 时刻 $v_0$ 号人第一次在环上摘下了这个苹果。我们可以倍增处理这个东西。然后我们开始讨论这棵基环树的环。不妨设这个环的形态是 $c_0 \leftarrow c_1 \leftarrow c_2 \leftarrow \cdots \leftarrow c_{s - 1} \leftarrow c_s(c_0)$ 。记 $dep_i$ 表示环上边长的前缀和， $P$ 表示环长。

设这个数对为 $(c_i, t0)$ ， 人的位置为 $c_j$， 不妨设 $i \geq j$ 。那么这个苹果对这个人的贡献如下

$$\max\{0, \lfloor \frac{t - (t_0 + dep_i - dep_j}{P} \rfloor + 1\} $$

考虑对贡献右边进行变化

$$\lfloor \frac{t + dep_j - (t_0 + dep_i)}{P} \rfloor + 1 $$

这样一棵苹果树对应一个参数 $\delta_t = t_0 + dep_i$ ， 一个人对应一个参数 $\delta_y = t + dep_j$ 。由于有对 $P$ 做除法的操作， 不妨按照套路，设 $\delta_t = P \times q_t + r_t, \delta_y = P \times q_y + r_y$ 。带进原式得

$$\lfloor\frac{\delta_y - \delta_t}{P}\rfloor = \lfloor \frac{P\times(q_y - q_t) + (r_y - r_t)}{P}\rfloor + 1 = q_y - q_t + [r_y \geq r_t] $$

那么可以先对于 $q_y \geq q_t$ 的点， 求出$q_y - q_t$之和， 然后每次求有多少点满足 $r_y \geq r_t$ 。同样是一个二维数点。

然后再考虑 $i < j$ 的情况，发现把式子化简以后就是所有答案为正数的情况下答案减少了$1$。 那么我们把 $i < j$ 的情况和前面同等考虑， 然后减去满足 $i < j, t_0 + dep_i \leq t + dep_j$ 的点对个数即可。

所有询问全部离线树状数组处理， 时间复杂度 $O(N \log N)$ 。

#include <bits/stdc++.h>

using namespace std;

#define lep(i, l, r) for(int i = (l); i <= (r); i ++)
#define rep(i, l, r) for(int i = (l); i >= (r); i --)
#define Lep(i, l, r) for(int i = (l); i <  (r); i ++)
#define Rep(i, l, r) for(int i = (l - 1); i >= (r); i --)
#define pb push_back
#define fi first
#define se second

using i64 = long long;
using uint = unsigned int;
using ui64 = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;

namespace io {
	struct io {
		io() {
            ios :: sync_with_stdio(false); 
            cin.tie(0); cout.tie(0);
        }
	} unname;
    struct read {
        operator int () { int x; cin >> x; return x; }
        operator i64 () { i64 x; cin >> x; return x; }
        operator char () { char x; cin >> x; return x; }
        operator double () { double x; cin >> x; return x; }
        operator string () { string x; cin >> x; return x; }
    } rd;
} ;

using io :: rd;

const int N = 4e5 + 10;

namespace Unique {
    vector<i64> unique(vector<i64> &vec) {
        sort(vec.begin(), vec.end());
        auto end = unique(vec.begin(), vec.end());
        vector<i64> res;
        for (auto it = vec.begin(); it != end; ++ it) res.push_back(* it);
        return res;
    }
} ;

#define lowbit(x) (x & -x)

struct Bit {
    i64 c[N];
    vector<int> bck;
    void upd(int x, i64 y) {
        bck.push_back(x);
        for (; x < N; x += lowbit(x)) c[x] += y;
    }
    i64 qry(int x) {
        i64 ans = 0;
        for (; x; x -= lowbit(x)) ans += c[x];
        return ans;
    }
    i64 qry(int l, int r) { return qry(r) - qry(l - 1); }
    void clr(int x) {
        for (; x < N; x += lowbit(x)) c[x] = 0;
    }
    void clr() {
        for (auto x : bck) clr(x); bck.clear(); //n = 0;
    }
} bt;

#undef lowbit

int n, m, L, C;

inline int reduce(int x, int mod) { return (x % mod + mod) % mod; }

int A[N], B[N];
int p[N];
vector<pair<int, int> > e[N];

int bel[N], tree_number, root[N], sz[N], number, dfn[N], oncir[N], fa[N][20], lg[N];
i64 dep[N], ew[N];

void dfs(int x, int fx) {
    dfn[x] = ++ number; sz[x] = 1; bel[x] = tree_number; fa[x][0] = fx;
    Lep (i, 1, 20) fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for(auto p : e[x]) {
        int y = p.first, w = p.second;
        if(y == root[tree_number]) oncir[y] = 1, oncir[x] = 1;
        else dep[y] = dep[x] + w, dfs(y, x), oncir[x] |= oncir[y], sz[x] += sz[y];
    }
}

i64 Ans[N];
struct Three { i64 a, b, c; } ;
struct Qry {
    int v; i64 t; int id;
} ;
vector<Qry> qrys1, qrys2;

struct Point { i64 x, y; } ;
struct Line { i64 l1, r1, h, id, type; } ;
struct Mat { i64 l1, r1, l2, r2; } ;

/* Two-side count nodes */

namespace Count {
    vector<i64> twoside_count(vector<Mat> &mt, vector<Point> &pt) {
        vector<Line> lns;
        vector<i64> ans(mt.size());
        lep (i, 0, (int) mt.size() - 1) {
            lns.push_back( {mt[i].l1, mt[i].r1, mt[i].l2 - 1, i, -1} );
            lns.push_back( {mt[i].l1, mt[i].r1, mt[i].r2, i, 1} );
        }
        sort(lns.begin(), lns.end(), [] (Line a, Line b) { return a.h == b.h ? a.type < b.type : a.h < b.h; } );
        sort(pt.begin(), pt.end(), [] (Point a, Point b) { return a.y < b.y; } );
        int j = 0;
        bt.clr();
        for (auto p : lns) {
            while (j < pt.size() && pt[j].y <= p.h) {
                bt.upd(pt[j].x, 1); j ++;
            }
            ans[p.id] += p.type * bt.qry(p.l1, p.r1);
        }
        return ans;
    }
} 

signed main() {
#ifdef FILEIN
    freopen("1.in", "r", stdin);
#endif
    n = rd; m = rd; L = rd; C = rd;
    lep (i, 1, n) A[i] = rd;
    lep (i, 1, m) B[i] = rd;
    /* Build Tree */
    lep (i, 1, n) {
        auto it = upper_bound(A + 1, A + 1 + n, reduce(A[i] - C, L)) - A - 1;
        if(! it) it = n;
        p[i] = it;
        int w = (C + L - reduce(A[i] - A[p[i]], L) - 1) / L * L + reduce(A[i] - A[p[i]], L);
        e[p[i]].push_back( {i, w} );
        ew[i] = w;
    }
    lep (i, 2, n) lg[i] = lg[i >> 1] + 1;
    lep (i, 1, n) if (! bel[i]) {
        ++ tree_number;
        int j = i;
        while(! bel[j]) { bel[j] = tree_number; j = p[j]; }
        root[tree_number] = j;
        dfs(j, 0);
    } 
    int q = rd;
    lep (i, 1, q) {
        int v = rd; i64 t = rd;
        if(! oncir[v]) qrys1.push_back( {v, t, i} );
        else qrys2.push_back( {v, t, i} );
    }
    /* Not on circle */
    vector<pair<int, i64> > pairs;
    lep (i, 1, m) {
        auto it = upper_bound(A + 1, A + 1 + n, B[i]) - A;
        if (it == 1) it = n; else it --;
        int v0 = it, t0 = reduce(B[i] - A[it], L);
        pairs.push_back( {v0, t0} );
    }
    vector<Mat> mat;
    vector<Point> pnt;
    vector<i64> values, record;
    for (auto p : pairs) pnt.push_back( {dfn[p.first], p.second + dep[p.first]} ), values.push_back(p.second + dep[p.first]);
    for (auto p : qrys1) {
        mat.push_back( {dfn[p.v], dfn[p.v] + sz[p.v] - 1, 1, dep[p.v] + p.t} ), values.push_back(dep[p.v] + p.t);
    }
    values.push_back(1);
    values = Unique :: unique(values);
    for (auto &p : pnt) p.y = lower_bound(values.begin(), values.end(), p.y) - values.begin() + 1;
    for (auto &p : mat) 
        p.l2 = lower_bound(values.begin(), values.end(), p.l2) - values.begin() + 1, 
        p.r2 = lower_bound(values.begin(), values.end(), p.r2) - values.begin() + 1;
    record = Count :: twoside_count(mat, pnt); 
    int cnt = 0;
    for (auto &p : qrys1) Ans[p.id] = record[cnt], cnt ++;

    /* Is on circle */
    for (auto &p : pairs) {
        int &v0 = p.first;
        i64 &t0 = p.second;
        if (! oncir[v0]) {
            rep (i, 19, 0) if (fa[v0][i] && ! oncir[fa[v0][i]]) {
                t0 += dep[v0] - dep[fa[v0][i]];
                v0 = fa[v0][i];
            }
            t0 += ew[v0];
            v0 = fa[v0][0];
        }
    }
    static int vis[N], loc[N];
    memset(dep, 0, sizeof(dep));
    static vector<Qry> link_qry[N];
    static vector<pair<i64, i64> > link_pair[N];
    for (auto p : qrys2) link_qry[bel[p.v]].push_back(p);
    for (auto p : pairs) link_pair[bel[p.first]].push_back(p);
    lep (now, 1, tree_number) {
        int rt = root[now];
        int i = rt;
        vector<int> cir;
        while (! vis[i]) {
            cir.push_back(i);
            vis[i] = 1;
            i = p[i];
        }    
        cir.push_back(cir[0]);
        reverse(cir.begin(), cir.end());
        dep[cir[0]] = 0;
        lep (i, 1, (int) cir.size() - 1) dep[cir[i]] = dep[cir[i - 1]] + ew[cir[i]];
        lep (i, 0, (int) cir.size() - 2) loc[cir[i]] = i;
        i64 P = dep[cir[0]];dep[cir[0]] = 0;
        vector<pair<i64, i64> > tree_node;
        vector<Three> people_node;
        for (auto p : link_pair[now]) tree_node.push_back( {(p.second + dep[p.first]) / P, (p.second + dep[p.first]) % P} );
        for (auto p : link_qry[now]) {
            i64 delta = p.t + dep[p.v];
            people_node.push_back( {delta / P, delta % P, p.id} );
        }
        sort(tree_node.begin(), tree_node.end(), [] (pair<i64, i64> a, pair<i64, i64> b) { return a.first < b.first; } );
        sort(people_node.begin(), people_node.end(), [] (Three a, Three b) { return a.a < b.a; } );
        values.clear();
        for (auto p : tree_node) values.push_back(p.second);
        for (auto p : people_node) values.push_back(p.b);
        values = Unique :: unique(values);
        for (auto &p : tree_node) p.second = lower_bound(values.begin(), values.end(), p.second) - values.begin() + 1;
        for (auto &p : people_node) p.b = lower_bound(values.begin(), values.end(), p.b) - values.begin() + 1;
        bt.clr();
        i64 sum = 0; i = 0;
        for (auto p : people_node) {
            i64 qy = p.a, ry = p.b, id = p.c;
            while (i < tree_node.size() && tree_node[i].first <= qy) {
                sum += tree_node[i].first; 
                bt.upd(tree_node[i].second, 1);
                i ++;
            }
            Ans[id] += 1ll * i * qy - sum + bt.qry(ry);
        }
        tree_node.clear();
        people_node.clear();
        for (auto p : link_pair[now]) tree_node.push_back( {loc[p.first], p.second + dep[p.first]} );
        for (auto p : link_qry[now]) {
            i64 delta = p.t + dep[p.v];
            people_node.push_back( {loc[p.v], p.t + dep[p.v], p.id} );
        }
        values.clear();
        for (auto p : tree_node) values.push_back(p.second);
        for (auto p : people_node) values.push_back(p.b);
        values = Unique :: unique(values);
        for (auto &p : tree_node) p.second = lower_bound(values.begin(), values.end(), p.second) - values.begin() + 1;
        for (auto &p : people_node) p.b = lower_bound(values.begin(), values.end(), p.b) - values.begin() + 1;
        sort(tree_node.begin(), tree_node.end(), [] (pair<i64, i64> a, pair<i64, i64> b) { return a.first < b.first; } );
        sort(people_node.begin(), people_node.end(), [] (Three a, Three b) { return a.a < b.a; } );
        bt.clr(); i = 0;
        for (auto p : people_node) {
            i64 cj = p.a, vj = p.b, id = p.c;
            while (i < tree_node.size() && tree_node[i].first < cj) {
                bt.upd(tree_node[i].second, 1);
                i ++;
            }
            Ans[id] -= bt.qry(vj);
        }
    }

    lep (i, 1, q) printf("%lld\n", Ans[i]);
	return 0;
}