P15939 [JOI Final 2026] 传奇团子吃家题解

思路

考虑前缀和 $P_i$ 表示前 $i$ 段甜减辣的净甜度。则对于固定的左端点，贪心策略为：每口都恰好吃到净甜度增加量 $\ge K$ 的最早位置。这等价于在模 $K$ 意义下推进状态。

我们离线处理询问，按右端点扫描。维护一棵模 $K$ 的权值线段树，存储每个余数状态对应的答案，并利用并查集合并等价状态。遇到奇数段（甜）时执行区间加操作；遇到偶数段（辣）时执行区间合并与删除。

动态开点线段树维护区间加法与单点查询，下标域 $[0, K-1]$。
用 set 维护当前仍有效的模余数集合。
带权并查集维护状态间的差值关系。
扫描 $i$：
- 若 $i$ 为奇数，计算甜团子带来的增量，执行线段树区间加，并尝试与已有代表合并。
- 若 $i$ 为偶数，将受辣团子影响的一段余数全部合并到新余数上，并从集合中删除旧余数。
- 回答所有右端点为 $i$ 的询问。

时间复杂度 $O((N+Q)\log K)$，空间 $O(N\log K)$，可以通过本题。

代码

▶ [过长，故折叠]

#include<bits/stdc++.h>
#define fir first
#define sec second 
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
    template<typename T>inline void read(T &x){
        x=0;int f=1;char c=getchar();
        for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
        for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
    }
    template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
    template<typename T>void print(T x){
        if(x<0)x=-x,putchar('-');
        if(x>9)print(x/10);
        putchar((x%10)^48);
    }
}
using namespace std;
using namespace FastIO;
const int N=5e5+5;
const int logN=47;
int n,q,k,rt=1;
int a[N],ans[N],mp[N];
vector<pii>Q[N];
map<int,int>rep;
struct seg{
    int t[N*logN];
    int lc[N*logN],rc[N*logN];
    int tot=1;
    void push_down(int p){
        if(t[p]){
            if(lc[p])t[lc[p]]+=t[p];
            if(rc[p])t[rc[p]]+=t[p];
            t[p]=0;
        }
    }
    void update(int &p,int l,int r,int L,int R,int v){
        if(!p)return;
        if(L<=l&&r<=R){
            t[p]+=v;
            return;
        }
        push_down(p);
        int mid=(l+r)/2;
        if(L<=mid)update(lc[p],l,mid,L,R,v);
        if(R>mid)update(rc[p],mid+1,r,L,R,v);
    }
    void point_update(int &p,int l,int r,int x,int v){
        if(!p)p=++tot;
        if(l==r){
            rep[x]=v;
            if(v)mp[v]=x;
            t[p]=0;
            return;
        }
        push_down(p);
        int mid=(l+r)/2;
        if(x<=mid)point_update(lc[p],l,mid,x,v);
        else point_update(rc[p],mid+1,r,x,v);
    }
    int point_query(int &p,int l,int r,int x){
        if(!p)return 0;
        if(l==r)return t[p];
        push_down(p);
        int mid=(l+r)/2;
        if(x<=mid)return point_query(lc[p],l,mid,x);
        else return point_query(rc[p],mid+1,r,x);
    }
}G;
int fa[N],val[N];
int find(int x){
    if(fa[x]==x)return x;
    int p=find(fa[x]);
    val[x]+=val[fa[x]];
    fa[x]=p;return p;
}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return;
    fa[x]=y;
    int left;
    if(rep[mp[x]]==x)left=G.point_query(rt,0,k-1,mp[x]);
    else left=0;
    int right;
    if(rep[mp[y]]==y)right=G.point_query(rt,0,k-1,mp[y]);
    else right=0;
    val[x]=left-right;
}
int get_sum(int x){
    int p=find(x);
    int sum;
    if(rep[mp[p]]==p)sum=G.point_query(rt,0,k-1,mp[p]);
    else sum=0;
    return val[x]+sum;
}
signed main(){
    read(n,q,k);
    rep(i,1,n)read(a[i]),fa[i]=i;
    rep(i,1,q){
        int l,r;read(l,r);
        Q[r].push_back(make_pair(l,i));
    }
    set<int>s;
    int las=0;
    rep(i,1,n){
        if(i&1){
            int tmp=a[i]/k;
            int lim=k-a[i]%k;
            int u=rep[las];
            if(u)merge(i,u);
            else G.point_update(rt,0,k-1,las,i);
            auto add1=[&](int l,int r,int v){
                l=(l+las)%k;
                r=(r+las)%k;
                if(l<=r)G.update(rt,0,k-1,l,r,v);
                else{
                    G.update(rt,0,k-1,l,k-1,v);
                    G.update(rt,0,k-1,0,r,v);
                }
            };
            if(lim<k)add1(lim,k-1,1);
            add1(0,k-1,tmp);
            s.insert(las);
            las=(las-a[i]%k+k)%k;
        }
        else{
            int las1=(las+a[i])%k;
            int u=rep[las1];
            if(u)merge(i,u);
            else G.point_update(rt,0,k-1,las1,i),u=i;
            a[i]=min(a[i],k-1);
            int l=las,r=(las+a[i])%k;
            auto del=[&](int x){
                if(x==las1)return;
                merge(rep[x],u);
                rep[x]=mp[rep[x]]=0;
                G.point_update(rt,0,k-1,x,0);
            };
            if(l<=r){
                auto it=s.lower_bound(l);
                while(it!=s.end()&&*it<=r){
                    del(*it);
                    it=s.erase(it);
                }
                las=las1;
            }
            else{
                auto it=s.lower_bound(l);
                while(it!=s.end()){
                    del(*it);
                    it=s.erase(it);
                }
                it=s.begin();
                while(it!=s.end()&&*it<=r){
                    del(*it);
                    it=s.erase(it);
                }
                las=las1;
            }
            s.insert(las1);
        }
        for(int j=0;j<Q[i].size();j++){
            int l=Q[i][j].fir,id=Q[i][j].sec;
            ans[id]=get_sum(l);
        }
    }
    rep(i,1,q)print(ans[i]),puts("");
    return 0;
}