P7894 题解

· · 题解

良心 C 题，不接受反驳。

首先我们看只有 3 颗棋子的情况。

\Box\blacksquare\Box\Box\blacksquare\Box\Box{\color{red}{\Box}}{\color{red}{\Box}}\blacksquare\Box

其中黑色表示有棋子。

我们观察到一旦我们的棋子被放到红色位置上之后它肯定无法再向左走了。

\Box\blacksquare\Box\Box\Box\Box\blacksquare\Box\Box\blacksquare\Box

这种情况就是啥事没有。

所以我们只要考虑棋子最早会在哪里落到一个红色位置上。

我们让棋子去找红色位置，不如让红色位置反过来去找棋子。

比如下图：

\Box\blacksquare\Box\Box\blacksquare\Box\Box{\color{red}{\Box}}{\color{red}{\Box}}\blacksquare\Box\Box\Box\blacksquare\Box

红点可以向右去找棋子：

\Box\blacksquare\Box\Box\blacksquare\Box\Box{\color{red}{\Box}}{\color{red}{\Box}}\blacksquare{\color{red}{\Box}}{\color{red}{\Box}}\Box\blacksquare\Box

这样我们只要在一开始的时候看一下棋子脚下的颜色就可以知道会不会在某一刻不能再往左走了。

等等，这样没法处理最早。

解决方法就是直接覆盖。从左到右处理红色位置的时候顺带记录一下是哪两个不动棋子之间的红色位置转移出去的。这样可以完整地查询，向右转移的时候直接覆盖就可以了。

对于两个相邻的不动棋，从左边开始会有若干段连续的红点，他们的生成时间越来越早。我们把它看作单调队列结构。从右边也有相同的结构。左边和右边可能重叠，但不重要，查询时两边各查询一次，去最小值即可。

举个例子，比如我们有三段从左边开始的红色位置，从短到长，生成距离当前越来越远。

第一段：

\Box\blacksquare{\color{red}{\Box}}{\color{red}{\Box}}\Box\Box\Box\blacksquare\Box

第二段：

\Box\blacksquare{\color{red}{\Box}}{\color{red}{\Box}}{\color{red}{\Box}}\Box\Box\blacksquare\Box

第三段：

\Box\blacksquare{\color{red}{\Box}}{\color{red}{\Box}}{\color{red}{\Box}}{\color{red}{\Box}}\Box\blacksquare\Box

单调队列里按 [1,2,3] 排列。

具体的，红色位置如何转移？

1.

\Box\blacksquare\Box{\color{red}{\Box}}{\color{red}{\Box}}\blacksquare\Box\Box\Box\blacksquare\Box

对于这种情况，我们只需要找到红色位置中从中间这个黑点出发延申的最长段，它可能在转移过程中因为过长而消失或消失其中一段，在单调队列中直接从队末修改即可。

2.

\Box\blacksquare{\color{red}{\Box}}{\color{red}{\Box}}\Box\blacksquare\Box\Box\Box{\color{blue}{\Box}}{\color{blue}{\Box}}\blacksquare\Box

对于这种情况，我们在转移过去之后发现从右边开始并不连续，实际上我们直接添加一段红色位置在那些被标蓝的位置就连续了，所属位置是最新的位置。

3.

\Box\blacksquare{\color{red}{\Box}}{\color{red}{\Box}}\Box\Box\blacksquare\Box\Box\Box\blacksquare\Box

这种情况和第一种情况很类似，只不过是从单调队列的对头进行修改。

我们发现这个单调队列是动态的，所以询问得离线，刚好到自己所处的两个不动棋的区间的时候查询。这个查询得二分。总复杂度：O(n+q\log n)。

部分分很良心吧？

#include <bits/stdc++.h>
#define ll long long
#define inf (0x3f3f3f3f3f3f3f3f)
using namespace std;
const int N = 6e6+100;
int n, Q;
ll a[N];
pair<ll, int> b[N];
int l[2], r[2];
ll d[2];
pair<ll, int> q[2][N];
int ans[N];
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<25],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (*O++=x)
inline ll read() {
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
inline void write(int X){
    if(X<0) {putchar('-'); X=~(X-1);}
    int s[20],top=0;
    while(X) {s[++top]=X%10; X/=10;}
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
}
int main(){
//  std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//  freopen("data/in20.in", "r", stdin);
//  freopen("data/out6.out", "w", stdout);
    n = read(), Q = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    a[++n] = inf;
    for (int i = 1; i <= Q; i++){
        b[i].first = read();
        b[i].second = i;
    }
    sort(b+1, b+1+Q);
    q[0][l[0]=r[0]=3e6+50] = make_pair(inf, 0);
    q[1][l[1]=r[1]=3e6+50] = make_pair(inf, 0);
    int p = 1; 
    for (int i = 1; i < n; i++){
        const ll len1 = (i==1?inf:a[i]-a[i-1]-1), len2 = a[i+1]-a[i]-1;
        if (len1 > len2){
            const int j = i&1;
            while (l[j] < r[j] && q[j][r[j]-1].first+d[j] > len2)
                r[j]--;
            q[j][r[j]].first = min(len2-d[j], q[j][r[j]].first);
            while (l[j^1] <= r[j^1] && q[j^1][l[j^1]].first+d[j^1] <= len1-len2)
                l[j^1]++;
            d[j^1] -= len1-len2;
        }else{
            const int j = (i&1)^1;
            d[j] += len2-len1;
            if (len2 > len1)
                q[j][--l[j]] = make_pair(len2-len1-d[j], i);
        }
        const int j = i&1;
        while (p <= Q && b[p].first <= a[i+1]){
            if (b[p].first <= a[i]){
                p++;
                continue;
            }
            const pair<ll, int> _1(b[p].first-a[i]-d[j], 0), _2(a[i+1]-b[p].first-d[j^1], 0);
            const int res1 = lower_bound(q[j]+l[j], q[j]+r[j]+1, _1)-q[j];
            const int res2 = lower_bound(q[j^1]+l[j^1], q[j^1]+r[j^1]+1, _2)-q[j^1];
            ans[b[p].second] = i-max(q[j][res1].second, q[j^1][res2].second);
            p++;
        }
    }
    for (int i = 1; i <= Q; i++)
        write(ans[i]), putchar('\n');
    fwrite(obuf, O-obuf, 1, stdout);
    return 0;
}