传奇团子吃家 / Legendary Dango Eater JOI Final 2026

[JOI Final 2026] 传奇团子吃家 / Legendary Dango Eater

题目链接：[JOI Final 2026] 传奇团子吃家 / Legendary Dango Eater。

给定长度为 $n$ 的序列 $a$，然后进行变换：令所有偶数下标的位置变为相反数，即 $a_i\leftarrow-a_i$。

$m$ 次询问，每次询问区间 $[l,r]$，求不交的甜菜的区间的最大个数，其中甜菜区间定义为区间和 $\ge k$ 的区间。

$n,m\le 5\times10^5$。

首先贪心的想，我们可以进行一个类似于“分段”的操作：每次只要最大子段和 $\ge k$ 就切一个区间，然后一直到最大子段和为 $0$，那么这个就为“一段”。

那么询问时我可以一直跳这个段。然而这个是 $\mathcal{O}(n^2)$ 的。

然后你就发现：其实可以倍增的跳（我为什么没有想到！）。

想到这个后就做完了，只需要求出这个每一次“分段”到哪里即可。这个可以使用 ODT 搞一搞，倒序遍历，每次找出可以使得 $[i,j]$ 不合法的最小的 $j$ 就行。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=500010;
int n,m,k,a[N],sum[N],pre[N],f[N][21],g[N][21];
struct node{int l,r,x;bool operator<(const node &a)const{return l<a.l;}};
set<node>s;
using sti=set<node>::iterator;
sti split(int pos){
    sti it=s.lower_bound({pos,0,0});
    if(it!=s.end()&&it->l==pos)return it;
    --it;
    if(it->r<pos)return s.end();
    int l=it->l,r=it->r,x=it->x;
    s.erase(it);
    s.insert({l,pos-1,x});
    return s.insert({pos,r,x}).first;
}
void assign(int l,int r,int x){
    l=max(l,0ll),r=min(r,k-1);
    if(l>r)return ;
    sti itr=split(r+1);
    sti itl=split(l);
    s.erase(itl,itr);
    s.insert({l,r,x});
}
signed main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=n;i++)scanf("%lld",a+i);
    for(int i=1;i<=n;i++){
        if(i&1^1)a[i]=-a[i];
        sum[i]=((sum[i-1]+a[i])%k+k)%k;
        pre[i]=pre[i-1]+a[i];
    }
    s.insert({0,k-1,n+1});
    for(int i=n;i;i--){
        if(i&1^1){
            assign(sum[i-1]+a[i],sum[i-1],i);
            assign(max(sum[i-1]+a[i]+k,sum[i-1]+1),k-1,i);
        }
        f[i][0]=prev(s.upper_bound({sum[i-1],0,0}))->x+1;
        g[i][0]=(pre[f[i][0]-2]-pre[i-1])/k;
    }
    for(int i=0;i<=20;i++)f[n+1][i]=f[n+2][i]=n+2;
    for(int j=1;j<=20;j++)for(int i=1;i<=n;i++)
        f[i][j]=f[f[i][j-1]][j-1],g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1];
    while(m--){
        int l,r,res=0;
        scanf("%lld%lld",&l,&r);
        for(int i=20;~i;i--)if(f[l][i]<=r+1&&l<=r)
            res+=g[l][i],l=f[l][i];
        printf("%lld\n",res+(l<=r?(pre[r]-pre[l-1])/k:0));
    }
    return 0;
}