感谢这一篇博客的指导(Orzwxh)
$PS$：默认数组下标为$1$到$N$
首先很明显的贪心：每一次都选择尽可能长的区间
不妨设$d_i$表示在取当前$K$的情况下，左端点为$i$的所有满足条件的区间中最大的右端点$+1$，然后连边$(i,d_i)$
那么我们就需要求一条链的长度，并支持动态修改某一些边
是不是有些印象？与弹飞绵羊极为相似，没有做过的可以先去感受一下……
上面那道题有两种做法：$LCT$与分块，所以这一道题就衍生出了$O(n\sqrt{n}logn)$的基于$LCT$的做法（安利chd的题解qaq）和$O(n^\frac{5}{3} + n^\frac{4}{3}logn)$的基于分块的做法。下面要谈的是后者。
首先因为输入中$K$的变化是无序的，所以修改会十分麻烦。不妨将询问离线，按照$W-K$从小到大排序，那么$d_i$的改变就是不降的。
设块长为$a$，又设$pre_i$，它需满足$pre_i - i \leq a$、$d_{pre_i} - i > a$、$pre_i$与$i$在同一条链上（如果对于链上的所有点都不满足条件，则令$pre_i=N+1$表示可以直接从$i$点经过不超过一个块长跳出去），维护$cnt_i$表示$i$与$pre_i$之间的点的个数（不计$pre_i$）。
对于每一次查询操作，我们就从$1$开始跳$pre$，每一次都加上对应的$cnt$，那么询问的答案就是$\sum cnt - 1$（$1$不需要被算进去）。
但是会发现如果$d_i - i > a$，$pre_i=i$就会死循环，所以我们对与$pre_i=i$的情况使用倍增找到它下一次要跳到哪一个点。
可以知道查询的复杂度是$O(\frac{n}{a}qlogn)$
对于修改，每一个点$i$最多都会被修改$a$次，每一次对于点$i$的修改我们只需要维护$i-a$到$i-1$的$pre$和$cnt$，修改的复杂度就是$O(na^2)$
可知在$a = n^\frac{1}{3}$时该算法取到最小复杂度$O(n^\frac{5}{3} + n^\frac{5}{3}logn)$
喂这个算法和暴力有什么区别啊
可以发现我们的复杂度瓶颈在查询的倍增上，考虑如何优化倍增的复杂度。
因为当$d_i - i > n^\frac{1}{3}$时，前面的所有点的$pre$都是不会因为$d_i$的改变而改变的，所以当$d_i - i > n^\frac{1}{3}$时，单次修改的复杂度变为了O(1)
所以我们可以考虑：当$n^\frac{1}{3} < d_i - i \leq b$时暴力移动$d_i$的值进行更新，当$d_i - i > b$时进行倍增
那么查询的复杂度就变为$O(n^\frac{5}{3} + \frac{n}{b}qlogn)$，修改的复杂度变为了$O(n^\frac{5}{3} + nb)$当$b=n^\frac{2}{3}$时总复杂度取到最小值$O(n^\frac{5}{3} + n^\frac{4}{3}logn)$
然后这道题就做完了
所以这道题的思路就是一个奇怪的与根号分治相似的东西，有点三合一的意思：
①$d_i-i \leq n^\frac{1}{3}$，通过维护$pre_i$与$cnt_i$压缩路径
②$n^\frac{1}{3} < d_i-i \leq n^\frac{2}{3}$，暴力移动$d_i$位置进行更新
③$n^\frac{2}{3} < d_i-i$，倍增找到下一次更新的点
一些实现上的细节：
①在$d_i - i \leq n ^ \frac{1}{3}$部分判断哪一些点需要修改可以使用堆进行维护(再在这里Orzwxh)，维护$[i,d_i]$的极差然后扔到堆里面，每一次小于等于当前$W-K$的堆中的点就是需要重新更新$pre$与$cnt$的点
②倍增使用$ST$表进行实现
③维护$n^\frac{1}{3} < d_i - i \leq n^\frac{2}{3}$的部分在计算答案时进行更新即可，不需要额外维护
④根据③，在$d_i - i \leq n ^ \frac{1}{3}$时，不能直接把$pre_i$的贡献算上然后跳到$nxt_{pre_i}$，因为$nxt_{pre_i}$可能还没有更新导致跳到一些奇怪的地方
#include<bits/stdc++.h>
#define PII pair < int , int >
#define st first
#define nd second
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
inline int max(int a , int b){
return a > b ? a : b;
}
inline int min(int a , int b){
return a < b ? a : b;
}
;
int N , W , Q , logN , j_small , j_big;
][MAXN][] , pre[MAXN] , nxt[MAXN] , nMax[MAXN] , nMin[MAXN] , cnt[MAXN] , len[MAXN] , ans[MAXN];
bool vis[MAXN];
priority_queue < PII > q , mod;
deque < int > v;
void input(){
N = read();
j_small = pow(N , );
j_big = pow(N , );
W = read();
Q = read();
; i <= N ; ++i)
num[i] = ST[][i][] = ST[][i][] = read();
; i <= Q ; ++i)
q.push(PII(read() , i));
}
void init(){
; << i <= N ; ++i)
; j + ( << i) - <= N ; ++j){
ST[i][j][] = min(ST[i - ][j][] , ST[i - ][j + ( << (i - ))][]);
ST[i][j][] = max(ST[i - ][j][] , ST[i - ][j + ( << (i - ))][]);
}
logg2[] = -;
; i <= N ; ++i){
logg2[i] = logg2[i >> ] + ;
nxt[i] = i + ;
pre[i] = min(N + , j_small + i);
cnt[i] = pre[i] - i;
nMax[i] = max(num[i] , num[i + ]);
nMin[i] = min(num[i] , num[i + ]);
if(i != N)
mod.push(PII(nMin[i] - nMax[i] , i));
}
logN = ;
<= N)
logN <<= ;
logN = logg2[logN];
}
void upd(int p , PII t){
mod.pop();
while(nxt[p] <= N && nMax[p] - nMin[p] <= t.st && nxt[p] - p <= j_big){
++nxt[p];
if(nxt[p] <= N){
if(nMax[p] < num[nxt[p]])
nMax[p] = num[nxt[p]];
if(nMin[p] > num[nxt[p]])
nMin[p] = num[nxt[p]];
}
}
if(nxt[p] <= N && nxt[p] - p <= j_small)
mod.push(PII(nMin[p] - nMax[p] , p));
pre[p] = p;
cnt[p] = len[p] = ;
v.clear();
v.push_back(p);
vis[p] = ;
while(pre[p] <= N && nxt[pre[p]] - p <= j_small){
pre[p] = nxt[pre[p]];
++cnt[p];
v.push_back(pre[p]);
}
; i && i >= p - j_small ; --i)
if(vis[nxt[i]]){
while(v.back() - i > j_small)
v.pop_back();
pre[i] = v.back();
cnt[i] = len[nxt[i]] + v.size();
len[i] = len[nxt[i]] + ;
vis[i] = ;
}
memset(vis + max(p - j_small , ) , , ));
}
void work(){
while(!q.empty()){
PII t = q.top();
q.pop();
t.st = W - t.st;
while(!mod.empty() && -mod.top().st <= t.st)
upd(mod.top().nd , t);
, all = ;
while(p <= N){
int cur = nxt[p] - p;
if(cur <= j_small){
all += cnt[p];
p = pre[p];
}
else{
++all;
while(nxt[p] <= N && nMax[p] - nMin[p] <= t.st && cur <= j_big){
++nxt[p];
++cur;
if(nxt[p] <= N){
if(nMax[p] < num[nxt[p]])
nMax[p] = num[nxt[p]];
if(nMin[p] > num[nxt[p]])
nMin[p] = num[nxt[p]];
}
}
if(cur <= j_big)
p = nxt[p];
else{
, cMin = 1e9;
; --j)
<< j) - <= N){
]) , n = min(cMin , ST[j][p][]);
if(m - n <= t.st){
cMax = m;
cMin = n;
p += << j;
}
}
}
}
}
ans[t.nd] = all;
}
}
void output(){
; i <= Q ; ++i)
printf();
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in" , "r" , stdin);
freopen("out" , "w" , stdout);
#endif
input();
init();
work();
output();
;
}