讲课讲得非常清楚啊，我绝赞膜拜。节奏可以，思路清晰，解法自然，为讲师点赞。

第一个题是 loj3282 / joisc2020 - Treatment Project。原问题由 $\left(S, t, w\right)$ 三个维度构成，分别表示村民被治疗的状态，时间，花费。比较自然的思路是针对 $t$ 做规划，但是这样有一个问题——$t$ 和 $S$ 是息息相关的，若从 $t$ 入手则几乎不得不记录 $S$，这是不被接受的。考虑直接 $S$ 入手。如果我可以考虑一段连续的区间而不是子序列，是不是复杂度一定会降？那么考察前缀，具体，设 $f_i$ 表示将 $[1, i]$ 的村民治好的最小花费。进一步地，不妨将 $f_i$ 重新描述为将 $[1, r_i]$ 的村民治好的最小花费。

为什么这样设计状态就不需要考虑时间的影响了（不是说整体，仅仅是在设计状态的时候）？我个人的理解是这样做将村民，或者说 $S$，作为第一个研究的对象，而时间则作为后续求解中对 $f$ 的限制，所以放到后面考虑即可。

转移方程即为 $\displaystyle f_i\gets\min_{1\leqslant j<i,r_j-l_i+1\geqslant|t_i-t_j|}\{f_j\}+w_i$。将绝对值拆开，这里以 $t_i\geqslant t_j$ 为例。那么转移的条件就成了 $r_j+t_j+1\geqslant t_i+l_i$。那么现在转移有二维偏序的关系，即 $t_i\geqslant t_j,r_j+t_j+1\geqslant t_i+l_i$。在优化之前，首先注意到这是一个最短路模型，转移条件即连边的条件，考虑用最优的 $f_j$ 去松弛 $f_i$，那么每个 $f_i$ 就只会被松弛一次（几乎是自明的），于是按 $t$ 排序后用线段树维护即可。

#include <bits/stdc++.h>
using namespace std;
// implementation: time-ordered
using ll = long long;
using pli = pair<ll, int>;
const ll inf = 1e18;
int n, m;
ll dp[100100];
struct node {
    int l, r, t;
    ll w;
} a[100100];
priority_queue<pli, vector<pli>, greater<pli>> q; // slacked
struct segment_tree {
    ll mix[400100], miy[400100];
    void pull(int now) {
        mix[now] = min(mix[now*2], mix[now*2+1]);
        miy[now] = min(miy[now*2], miy[now*2+1]);
    }
    void ins(int pos, ll x, ll y, int now=1, int l=1, int r=n) {
        if (l == r) {
            mix[now] = x, miy[now] = y;
            return;
        }
        int mid = (l+r)/2;
        if (mid >= pos) ins(pos, x, y, now*2, l, mid);
        else ins(pos, x, y, now*2+1, mid+1, r);
        pull(now);
    }
    void slackx(int lq, int rq, ll lim, ll dlt, int now=1, int l=1, int r=n) {
        if (lq > rq || l > rq || r < lq || mix[now] > lim) return;
        if (l == r) {
            dp[l] = dlt+a[l].w;
            q.emplace(dp[l], l);
            mix[now] = miy[now] = inf;
            return;
        }
        int mid = (l+r)/2;
        slackx(lq, rq, lim, dlt, now*2, l, mid);
        slackx(lq, rq, lim, dlt, now*2+1, mid+1, r);
        pull(now);
    }
    void slacky(int lq, int rq, ll lim, ll dlt, int now=1, int l=1, int r=n) {
        if (lq > rq || l > rq || r < lq || miy[now] > lim) return;
        if (l == r) {
            dp[l] = dlt+a[l].w;
            q.emplace(dp[l], l);
            mix[now] = miy[now] = inf;
            return;
        }
        int mid = (l+r)/2;
        slacky(lq, rq, lim, dlt, now*2, l, mid);
        slacky(lq, rq, lim, dlt, now*2+1, mid+1, r);
        pull(now);
    }
} sgt;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n;
    for (int i=1;i<=n;++i) {
        dp[i] = inf;
        cin >> a[i].t >> a[i].l >> a[i].r >> a[i].w;
    }
    sort(a+1, a+n+1, [&](node a, node b) {
        return a.t < b.t;
    });
    for (int i=1;i<=n;++i) {
        if (a[i].l == 1) {
            dp[i] = a[i].w;
            q.emplace(dp[i], i);
            sgt.ins(i, inf, inf);
        }
        else {
            sgt.ins(i, a[i].l-a[i].t, a[i].l+a[i].t);
        }
    }
    while (!q.empty()) {
        // use nodes slacked to slack other nodes
        int x = q.top().second;
        q.pop();
        sgt.slackx(1, x-1, a[x].r-a[x].t+1, dp[x]);
        sgt.slacky(x+1, n, a[x].r+a[x].t+1, dp[x]);
    }
    ll ans = inf;
    for (int i=1;i<=n;++i) {
        if (a[i].r == m) {
            ans = min(ans, dp[i]);
        }
    }
    if (ans == inf) cout << "-1\n";
    else cout << ans << "\n";
    return 0;
}

第二个题是 codeforces - 1476F，整个课上唯一一个自己想出来的题，还错了个细节。直接 dp 有着自明的后效性，说两种消除之的方法。第一个是「将 $i$ 点亮灯的能力挂到 $i$ 能够点亮的最右边的灯上」，这样一次操作只会影响前面的，这消除了后效性。第二个直接在 dp 状态上下手，也是正解的思路，即设 $f_i$ 表示以 $[1, i]$ 的灯能够点亮的最长前缀（完全可能超过 / 不足 $i$），这样相当于将「点灯的灯」和「被点的灯」隔离开了，影响就被消除了。

因为我写的第二个，所以说一下第二个（其实是差不多的）。先考虑 $i$ 向右照的情况，转移非常简单 $f_i\gets\max\{f_i, i+p_i\}$（当然 $f_i$ 要先继承 $f_{i-1}$，这也昭示了其单调性）。$i$ 向左照的情况比较复杂。考虑有这样一个 $j$，满足 $f_j\geqslant i-p_i-1$（保证维护的是前缀），那么让 $\forall t,s.t.j<t<i$ 向右照是最优的，贪心地想，我们就需要使得 $j$ 最小，由于 $f$ 有单调性，直接二分即可，然后 RMQ 找 $(j, i)$ 区间中最大的 $t+p_t$ 即可。

#include <bits/stdc++.h>
using namespace std;
int n, p[300100], dp[300100], dp2[20][300100], lgs[300100], pre[300100], isl[300100];
int get(int l, int r) {
    if (l > r) return 0;
    int k = lgs[r-l+1];
    return max(dp2[k][l], dp2[k][r-(1<<k)+1]);
}
void print(int now) {
    if (now == 0) return;
    print(pre[now]);
    if (isl[now]) {
        cout << "R";
        return;
    }
    for (int i=pre[now]+1; i<now; ++i) cout << "R";
    cout << "L";
}
void solve() {
    cin >> n;
    for (int i=1;i<=n;++i) {
        cin >> p[i];
        dp2[0][i] = i+p[i];
    }
    for (int i=1;(1<<i)<=n;++i) {
        for (int j=1;j+(1<<i)-1<=n;++j) {
            dp2[i][j] = max(dp2[i-1][j], dp2[i-1][j+(1<<(i-1))]);
        }
    }
    pre[1] = 0, isl[1] = 1;
    for (int i=2;i<=n;++i) {
        dp[i] = dp[i-1], pre[i] = i-1, isl[i] = 1;
        if (dp[i-1] >= i) {
            dp[i] = max(dp[i], i+p[i]);
        }
        int l = 0, r = i-1, j = -1, mid;
        while (l <= r) {
            mid = (l+r)/2;
            if (dp[mid] >= i-p[i]-1) r = mid-1, j = mid;
            else l = mid+1;
        }
        if (j == -1) continue;
        if (max(i-1, get(j+1, i-1)) >= dp[i]) {
            isl[i] = 0, pre[i] = j;
        }
        dp[i] = max({dp[i], i-1, get(j+1, i-1)});
    }
    if (dp[n] >= n) {
        cout << "YES\n";
        print(n);
        cout << "\n";
        return;
    }
    cout << "NO\n";
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt;
    for (int i=2; i<300100; ++i) {
        lgs[i] = lgs[i>>1]+1;
    }
    for (cin>>tt;tt--;) {
        solve();
    }
}

第三个题是 codeforces - 1523F。再次考虑这个题的维度 $(S, t, i, w)$，分别表示点亮传送塔的集合，时间，所处位置（传送塔或任务点），完成任务数量。据此可以写出一个朴素的 dp，$f_{S, i, w}$ 表示点亮传送塔的集合为 $S$，当前在位置 $i$，完成了 $w$ 个任务，所花费的最小时间。这里把题目中的「答案」完成任务数量作为状态并非不自然，是单纯因为时间太大忍不下。这里有两个重要的观察：

• 处在传送塔时，不关心自己的位置；
• 处在任务点时，不关心当前的时间。

正确性不必多言，关键在于观察到之的洞察力。于是我们可以优化状态（这里的根据是，传送塔 $\cup$ 任务点 $=$ 所有地址），分别定义 $f_{S, i}$，$g_{S, i}$ 表示点亮传送塔的集合为 $S$，完成了 $i$ 个任务，并且现在处于传送塔的最小时间，和点亮传送塔的集合为 $S$，在 $i$ 个地址，最大完成任务总数。转移分 传送塔 $\rightarrow$ 任务点、传送塔 $\rightarrow$ 传送塔、任务点 $\rightarrow$ 任务点、任务点 $\rightarrow$ 传送塔 讨论即可。同时还有转移顺序的问题，具体见代码。

#include <bits/stdc++.h>
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, ans = -inf;
int w[16484][120], up, f[16484][120], g[16484][120];
struct pnt {
    int x, y, t;
} a[120];
int dst(int i, int j) {
    return abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    up = 1<<n;
    for (int i=0; i<n; ++i) {
        cin >> a[i].x >> a[i].y;
    }
    for (int i=n; i<n+m; ++i) {
        cin >> a[i].x >> a[i].y >> a[i].t;
    }
    sort(a+n, a+n+m, [&](pnt x, pnt y) {
        return x.t < y.t;
    });
    for (int s=0; s<up; ++s) {
        for (int i=0; i<n+m; ++i) {
            w[s][i] = inf;
            for (int j=0; j<n; ++j) {
                if (s&(1<<j)) cmin(w[s][i], dst(i, j));
            }
        }
    }
    for (int s=0; s<up; ++s) {
        for (int i=0; i<m; ++i) f[s][i] = inf, g[s][i] = -inf;
        f[s][m] = inf;
    }
    for (int i=0; i<n; ++i) f[1<<i][0] = 0;
    for (int i=0; i<m; ++i) g[0][i] = 1;
    for (int s=0; s<up; ++s) {
        for (int i=0; i<=m; ++i) {
            if (f[s][i] != inf) {
                for (int j=0; j<n; ++j) {
                    if ((s&(1<<j)) == 0) {
                        cmin(f[s|(1<<j)][i], f[s][i]+w[s][j]);
                    }
                }
                for (int j=0; j<m; ++j) {
                    if (f[s][i]+w[s][j+n] <= a[j+n].t) {
                        cmax(g[s][j], i+1);
                    }
                }
            }
        }
        for (int i=0; i<m; ++i) {
            if (g[s][i] >= 0) {
                for (int j=0; j<n; ++j) {
                    if ((s&(1<<j)) == 0) {
                        cmin(f[s|(1<<j)][g[s][i]], min(dst(i+n, j), w[s][j])+a[i+n].t);
                    }
                }
                for (int j=i+1; j<m; ++j) {
                    if (min(dst(i+n, j+n), w[s][j+n])+a[i+n].t <= a[j+n].t) {
                        cmax(g[s][j], g[s][i]+1);
                    }
                }
                cmax(ans, g[s][i]);
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

link。

注意到 BN-string 长成什么样根本不重要，我们把它表述为 BN-pair $(x, y)$ 即可，两个 BN-strings 相似的充要条件即两者分别映射得到的 BN-pairs 相等。将 BN-pairs 放到平面上来研究，题目中给出的变换就对应 $(x,y)\rightarrow(x\pm1,y),(x,y\pm1),(x\pm1,y\pm1)$，注意到在斜线方向上的移动只能同时加或减。我们可以用这样移动方式的所派生的 $\text{dist}(a, b)$ 函数导出在平面上的「圆」（是一般意义下的 hexagon），如下图

二分「半径」$r$ 我们现在的问题就转化为了，判定原图上所有点以 $r$ 导出「圆」的是否有交。由于这是个凸图形，我们考虑用六条直线围成的图形来描述，于是两个「圆」有交的充要条件即为「在横轴上有交，且在竖轴上有交，且在 $y=x$ 轴上有交」。前两个的判断都不怎么迷惑，在斜轴（即 $y=x$ 轴）上的判断需要小小的考虑一下。不妨用一条 $y=-x+b$ 的直线来切斜线，如下图

这样把 $y=-x+b$ 看作数轴，我们就把问题转化成了前两个判断，但是实际上我们不需要这个算这个六边形斜线与轴交点的坐标再转化（这样算出来还会带根号，很麻烦），等价地，直接看六边形斜线与已有数轴（即横轴和竖轴）的交点即可。

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int n, xx[300100], yy[300100];
char s[500100];
int lx, rx, ly, ry, lz, rz;
bool check(int r) {
    lx = -inf, rx = inf, ly = -inf, ry = inf, lz = -inf, rz = inf;
    for (int i = 1; i <= n; ++i) {
        lx = max(lx, xx[i]-r), rx = min(rx, xx[i]+r);
        ly = max(ly, yy[i]-r), ry = min(ry, yy[i]+r);
        lz = max(lz, xx[i]-yy[i]-r), rz = min(rz, xx[i]-yy[i]+r);
    }
    lx = max(lx, 0), ly = max(ly, 0);
    if (lx > rx || ly > ry || lz > rz) return 0;
    return lx-ry <= rz && rx-ly >= lz;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s;
        for (int j = 0, r = strlen(s); j < r; ++j) {
            if (s[j] == 'B') xx[i]++;
            else yy[i]++;
        }
    }
    int l = 0, r = 1e9, mid, ans = l;
    while (l <= r) {
        if (check(mid = (l+r)/2)) {
            r = mid-1;
            ans = mid;
        }
        else {
            l = mid+1;
        }
    }
    check(ans);
    cout << ans << "\n";
    for (int i=0;i<min(rx, ry+rz);++i) {
        cout << "B";
    }
    for (int i=0;i<min(min(rx, ry+rz)-lz,ry);++i) {
        cout << "N";
    }
}

link。

有点狗，但还算个好题。

设定 $f_i(x)=a_ix-x^3$，$\Delta_i(x)=f_i(x)-f_i(x-1)$，可以洞察到 $\Delta_i(x)$ 在正自然数中是递减的。那么我们就可以贪心了。贪心时我们维护一个向量 $(b_1,\dots,b_n)$，分别表示 $\Delta_i(b_i)$，初始全为零。放进优先队列里面，每次取一个出来（记为 $\textit{id}$）将 $b_{\textit{id}}$ 增量 $1$，再放入优先队列里面。最终我们得到的即是使得答案最优的向量。

复杂度不可接受，我们优化的方向应当是提高生产力，怎样批量决定该做哪些。考虑二分一个标准线 $t$，如果存在向量满足 $\sum b_i\leqslant k$，且我们只做了 $\Delta_i(b_i)\geqslant t$ 的函数，就行了。设 $f(t)$ 为达到标准线的函数个数，最后我们得到的 $t$ 满足 $f(t)\leqslant k<f(t+1)$。

然后通过调整可得到答案。

#include <bits/stdc++.h>
using namespace std;
using ll = __int128;
#define int ll
int n, k, a[100100], b[100100];
ll of(ll x, ll a) {
    return a*x-x*x*x;
}
ll df(ll x, ll i) {
    return of(x, a[i])-of(x-1, a[i]);
}
int f(int i, int stl) {
    int l = 0, r = a[i], mid, res = 0;
    while (l <= r) {
        mid = (l+r)/2;
        if (df(mid, i) >= stl) l = mid+1, res = mid;
        else r = mid-1;
    }
    return res;
}
bool check(ll cur) {
    // @cur stands for the standard line
    ll sm = 0;
    for (int i=1;i<=n;++i) {
        int ret = f(i, cur);
        sm += ret, b[i] = ret;
    }
    return sm <= k;
}
ll bsrh(ll l, ll r) {
    ll mid, res = -1;
    while (l <= r) {
        if(check(mid = (l+r)/2)) r = mid-1, res = mid;
        else l = mid+1;
    }
    return res;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long tmp;
    cin >> tmp;
    n = tmp;
    cin >> tmp;
    k = tmp;
    for (int i=1;i<=n;++i) {
        cin >> tmp;
        a[i] = tmp;
    }
    int t = bsrh(-9e18, 9e18), sum = 0;
    check(t-1);
    for (int i=1;i<=n;++i) sum += b[i];
    for (int i=1;i<=n;++i) {
        int adj = f(i, t-1)-f(i, t);
        if (sum > k) {
            if (sum-adj <= k) {
                b[i] -= (sum-k);
                break;
            }
            else {
                sum -= adj, b[i] -= adj;
            }
        }
    }
    for (int i=1;i<=n;++i) {
        tmp = b[i];
        cout << tmp << " \n"[i == n];
    }
    return 0;
}

link。

点 $A$ 与 $(0,0)$，$B$ 共线的充要条件是 $\frac{y_A}{x_A}=\frac{y_B}{x_B}$，即 $k_{OA}=k_{OB}$。又考虑到题目提出刻画斜率相等双点间的关系，所以不妨把所有斜率相同的点看作一个。再考虑刻画点的移动，由于与共线的点是移动后两者之间的哪一者无妨，所以我们可以在移动后的两点所代表的斜率集合之间连一条边，问题就转化成了在一张无向图中，删除或一条三点二边的链，或一个二点二边的环，询问最多可以删除多少次，并给出可行方案。那么答案中最大值的部分我们可以拿出来，即 $\lfloor\frac{\text{\# edges}}{2}\rfloor$。

论删边的顺序，我们可以建出转化后图的任一生成树，并考虑非树边。考虑任一结点 $x$，设有非树边边 $\lang x,y\rang$，我们可以将 $y$ 给“拖下去”，意即新建一个点，并将 $x$ 连向该点。其正确性并非自明，但是考虑深度可以简单证明。至于答案的求解过程，参见常见 trick 树的最大匹配（但是略有不同，具体见代码）。

说一下如何精简实现，你的代码逻辑可以不是「建出原图 - 得到生成树 - 新建节点 - 求匹配」，更加优秀的逻辑可以是「建出原图并通过动态维护连通性新建节点 - 在求出生成树的同时获得深度信息 - 求匹配」。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, rn, uset[500100], head[500100], to[1000100], nxt[1000100], ent;
ll gcd(ll x, ll y) {
    return y == 0 ? x : gcd(y, x%y);
}
int ldr(int x) {
    while (x != uset[x]) x = uset[x] = uset[uset[x]];
    return x;
}
bool sm(int x, int y) {
    return ldr(x) == ldr(y);
}
void mrg(int x, int y) {
    if (ldr(x) != ldr(y)) {
        uset[ldr(y)] = ldr(x);
    }
}
struct frac {
    ll p, q;
    frac() {}
    explicit frac(ll a, ll b) : p(a), q(b) {
        norm(*this);
    }
    bool operator<(const frac& o) const {
        return p < o.p || (p == o.p && q < o.q);
    }
    void norm(frac& x) {
        ll g = gcd(x.p, x.q);
        x.p /= g, x.q /= g;
    }
};
map<frac, int> mp;
void add(int x, int y) {
    to[++ent] = y, nxt[ent] = head[x], head[x] = ent;
}
bool vis[500100];
int dep[500100], fa[500100], eid[500100], mxd;
set<int> ch[500100], sd[500100];
void dfs(int x) {
    mxd = max(mxd, dep[x]);
    vis[x] = 1;
    sd[dep[x]].insert(x);
    for (int i = head[x], y; i; i = nxt[i]) {
        if (vis[y = to[i]]) {
            continue;
        }
        fa[y] = x, dep[y] = dep[x]+1;
        ch[x].insert(y);
        eid[y] = (i+1)/2;
        dfs(y);
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        frac cur((a+b)*d, b*c);
        if (!mp.count(cur)) {
            ++rn;
            mp[cur] = uset[rn] = rn;
        }
        int u = mp[cur], v;
        cur = frac(a*d, b*(c+d));
        if (!mp.count(cur)) {
            ++rn;
            mp[cur] = uset[rn] = rn;
        }
        v = mp[cur];
        if (sm(u, v)) {
            v = ++rn;
        }
        else mrg(u, v);
        add(u, v), add(v, u);
    }
    for (int i = 1; i <= rn; ++i) {
        if (!vis[i]) dfs(i);
    }
    vector<pair<int, int>> ans;
    for (int d = mxd; d >= 1; --d) {
        for (int x : sd[d]) {
            if (int(ch[fa[x]].size()) >= 2) {
                ch[fa[x]].erase(x);
                int bro = *ch[fa[x]].begin();
                ch[fa[x]].erase(bro), sd[dep[bro]].erase(bro);
                ans.emplace_back(eid[x], eid[bro]);
            }
            else if (fa[fa[x]]) {
                ch[fa[x]].erase(x);
                ch[fa[fa[x]]].erase(fa[x]);
                sd[dep[fa[x]]].erase(fa[x]);
                ans.emplace_back(eid[x], eid[fa[x]]);
            }
        }
    }
    cout << ans.size() << "\n";
    for (auto it : ans) {
        cout << it.first << " " << it.second << "\n";
    }
}

link。

题不错，但是花了很久啊，完全比不过贺题怪。

答案有单调性，转化求每个点被跳到所需的最小 $k_i$，容易想到用整体二分维护一个有 $s$ 的连通块，每次拓展的时候就考虑在值域范围内的点能不能在 $k$ 取 $(l+r)/2$ 的时候跳出去。具体而言，就是看能不能以 $k=(l+r)/2$ 跳到 $k_i<l$ 的点上（1）。

但是这样会少点，因为值域范围内的点能够跳出去，而值域范围内有些不能跳出去的点可以藉由这些点间接跳出去（2）。

现在的问题就是如何维护（1）类点。我们在执行整体二分的时候先递归左子树，这样跑到叶子的时候把叶子加入一个数据结构（std::set is enough），这样我们递归到后面的结点时数据结构中存放的就是所有的（1）类点，跑完（1）类点再把值域范围内剩下的点依次判断能否间接跳出去即可。

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
int n, Q, st, d, a[200100], ans[200100], q[200100];
int q1[200100], q2[200100];
set<int> s;
void solve(int l, int r, int lq, int rq) {
    if (l == r) {
        for (int i=lq; i<=rq; ++i) {
            ans[q[i]] = l;
            s.insert(a[q[i]]);
        }
        return;
    }
    set<P> now;
    for (int i=lq; i<=rq; ++i) {
        now.emplace(a[q[i]], q[i]);
    }
    int mid = (l+r)/2, tl = 0, tr = 0;
    for (int i=lq; i<=rq; ++i) {
        auto it = s.lower_bound(a[q[i]]-d-mid);
        if (it != s.end() && (*it) <= a[q[i]]-d+mid) {
            q1[++tl] = q[i];
            now.erase(P(a[q[i]], q[i]));
        }
        else {
            it = s.lower_bound(a[q[i]]+d-mid);
            if (it != s.end() && (*it) <= a[q[i]]+d+mid) {
                q1[++tl] = q[i];
                now.erase(P(a[q[i]], q[i]));
            }
        }
    }
    for (int i; tl;) {
        i = q1[tl--];
        auto it = now.lower_bound(P(a[i]-d-mid, 0));
        while (it != now.end() && it->first <= a[i]-d+mid) {
            q1[++tl] = it->second;
            it = now.erase(it);
        }
        it = now.lower_bound(P(a[i]+d-mid, 0));
        while (it != now.end() && it->first <= a[i]+d+mid) {
            q1[++tl] = it->second;
            it = now.erase(it);
        }
    }
    tl = 0;
    for (int i=lq; i<=rq; ++i) {
        if (now.count(P(a[q[i]], q[i]))) {
            q2[++tr] = q[i];
        }
        else {
            q1[++tl] = q[i];
        }
    }
    for (int i=1; i<=tl; ++i) q[lq+i-1] = q1[i];
    for (int i=1; i<=tr; ++i) q[lq+tl+i-1] = q2[i];
    solve(l, mid, lq, lq+tl-1);
    solve(mid+1, r, lq+tl, rq);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> Q >> st >> d;
    int cnt = 0;
    for (int i=1; i<=n; ++i) {
        cin >> a[i];
        if (i != st) {
            q[++cnt] = i;
        }
    }
    s.insert(a[st]);
    solve(0, 1e6, 1, cnt);
    for (int i, k; Q--;) {
        cin >> i >> k;
        if (ans[i] <= k) {
            cout << "yEs\n";
        }
        else {
            cout << "nO\n";
        }
    }
    return 0;
}