题解：CF2206E Parallel Sums

· · 题解

不妨假定 a_1=x_1,a_2=x_2,\cdots,a_m=x_m，那么 a_{m+1}=s_2-s_1+a_1=x_1+s_2-s_1，以此类推，a_{m+i}=s_{i+1}-s_i+a_i，最终，所有的 a_i 均可以写成 x_{i\bmod m}+t_i 的形式，其中 t_i 是个递推出来的常数数列。

接下来去考虑区间 [l,r] 中的最大值，显然如果存在两个下标 x,y 满足 x=y\pmod m，那么只需要保留 t_x,t_y 中较大的那个即可。
回忆一下我们有限制 x_1+x_2+\cdots+x_m=s_1，而其余限制都被我们用来递推了。这个限制有 m 个自由变量，因此如果区间长度 <m，变量数就 <m，此时最大值可以任意小，即输出 unbounded。

否则，我们记录每个颜色最大的 m 个，其下标分别为 l_1,l_2,\cdots,l_m，根据限制 x_1+x_2+\cdots+x_m=s_1，可以写出 a_{l_1}-t_{l_1}+a_{l_2}-t_{l_2}+\cdots+a_{l_m}-t_{l_m}=s_1，也就是 a_{l_1}+a_{l_2}+\cdots+a_{l_m}=s_1+t_{l_1}+t_{l_2}+\cdots+t_{l_m}。
要求最大值最小，我们尽量平均分答案，也就是 \lceil(s_1+t_{l_1}+t_{l_2}+\cdots+t_{l_m})/m\rceil。

现在问题转化为每个点有个颜色，每次询问给定一段区间 [l,r]，求出区间内每个颜色的 t_i 的 \max 之和。
官方 sol 采取分块，不好写，有一个好写的 \mathcal O((n+q)\log n) 的做法。

将所有区间离线下来，按照右端点从小到大去枚举。
假设仅考虑当前颜色，可以发现这个颜色的每个数字的贡献区间是一个单调栈的形式，进行更新就是从单调栈中弹出比当前元素小的元素，并且取消它们的贡献，最后改为新元素的贡献。
而不同颜色的贡献不会相互干扰，因此可以使用树状数组来维护区间加，单点查。

#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
#define int loli
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=2e5+7;
int n,m,Q,a[N],s[N],ans[N];
vector<pii>v[N];
vector<int>b[N];
int d[N];
void add(int x,int y){for(;x<=n;x+=x&-x)d[x]+=y;}
void add(int l,int r,int k){add(l,k);add(r+1,-k);}
int ask(int x){int y=0;for(;x;x-=x&-x)y+=d[x];return y;}
template<typename T1,typename T2>constexpr T1 ceyl(T1 x,T2 y){return x>0?(x+y-1)/y:x/y;}
template<typename T1,typename T2>constexpr T1 flor(T1 x,T2 y){return x>0?x/y:(x-y+1)/y;}
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n-m+1;i++)cin>>s[i];
    for(int i=1;i<=n-m;i++)a[i+m]=a[i]+s[i+1]-s[i];
    cin>>Q;
    for(int i=1;i<=Q;i++){
        int l,r;cin>>l>>r;
        if(r-l+1<m)ans[i]=-1;
        else v[r].emplace_back(l,i);
    }
    a[0]=0x3f3f3f3f3f3f3f3f;
    for(int i=0;i<m;i++)
        b[i].push_back(0);
    for(int i=1;i<=n;i++){
        auto&q=b[i%m];
        while(a[q.back()]<a[i]){
            int x=q.back();q.pop_back();
            add(q.back()+1,x,-a[x]);
        }
        add(q.back()+1,i,a[i]);
        q.push_back(i);
        for(auto[x,id]:v[i])
            ans[id]=ask(x);
    }
    for(int i=1;i<=Q;i++)
        if(~ans[i])cout<<ceyl(ans[i]+s[1],m)<<'\n';
        else cout<<"unbounded\n";
    return 0;
}