官方题解：

不适，这道题蓝？给个说法。

~~秒了。~~

五年级爆切蓝正常吗？~~顶多给个黄~~。

题目大意

给定序列 \(a_1 \dots a_n\)，可对任意元素加减 \(1\)，最多操作 \(k\) 次。求操作后最长的"彩虹子数组"长度。

彩虹子数组：相邻元素差为 \(1\)（长度 \(1\) 的子数组自动满足）。

解题思路

设 \(b_i = a_i - i\)。

原要求 \(a_{i+1} - a_i = 1\) 变为 \(b_{i+1} = b_i\)。

则问题转化为：选一个区间 \([l, r]\)，通过至多 \(k\) 次操作使区间内所有 \(b_i\) 相等。

区间内所有数变成中位数 \(x\) 时，总代价最小 \(= \sum |b_i - x|\)。若代价 \(\le k\)，则区间合法。

因此可以：
- 用两个 multiset 维护区间元素，动态求中位数和总代价。
- 左端点 \(i\) 固定时，右端点 \(now\) 尽可能右移，直到代价 \(>k\)。
- 记录过程中最大窗口长度。

每个元素入堆、出堆各一次，时间复杂度为 \(O(n \log n)\)。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10,inf=1e18;
int T,n,k;
int a[N];
multiset<int> s1,s2;
int l,r,zhong;
bool jiou;
void init()
{
    s1.clear(); s2.clear();
    s1.insert(-inf); s2.insert(inf);
    l=r=zhong=0;
    jiou=0;
}
void add(int x)
{
    if(!jiou)
    {
        int A=*(--s1.end());
        int B=*s2.begin();
        if(A<=x&&x<=B) zhong=x;
        else if(A>x)
        {
            s1.erase(s1.find(A));
            s1.insert(x);
            l+=x-A;
            zhong=A;
        }
        else if(B<x)
        {
            s2.erase(s2.find(B));
            s2.insert(x);
            r+=x-B;
            zhong=B;
        }
    }
    else
    {
        if(x>=zhong)
        {
            s1.insert(zhong); l+=zhong;
            s2.insert(x); r+=x;
        }
        else
        {
            s2.insert(zhong); r+=zhong;
            s1.insert(x); l+=x;
        }
        zhong=0;
    }
    jiou^=1;
}
void del(int x)
{
    int A=*(--s1.end());
    int B=*s2.begin();
    if(!jiou)
    {
        if(A>=x)
        {
            s1.erase(s1.find(x)); l-=x;
            s2.erase(s2.find(B)); r-=B;
            zhong=B;
        }
        else
        {
            s2.erase(s2.find(x)); r-=x;
            s1.erase(s1.find(A)); l-=A;
            zhong=A;
        }
    }
    else
    {
        if(zhong==x){}
        else if(x>zhong)
        {
            s2.erase(s2.find(x));
            s2.insert(zhong);
            r+=zhong-x;
        }
        else
        {
            s1.erase(s1.find(x));
            s1.insert(zhong);
            l+=zhong-x;
        }
        zhong=0;
    }
    jiou^=1;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            a[i]-=i;
        }
        init();
        int now=1,ans=1;
        add(a[1]);jiou=1;
        for(int i=1;i<=n;i++)
        {
            while(r-l<=k&&now<n)
            {
                add(a[++now]);
                if(r-l<=k) ans=max(ans,now-i+1);
            }
            del(a[i]);
        }
        cout<<ans<<"\n";
    }
    return 0;
}