【1】题解：P12389 COmPoUNdS【差分】【线段树】【哈希】

ExFish · 2025-11-20 19:49:42 · 题解

你发现做完差分后操作其实变成了单点修改。然后线段树维护哈希值即可。要注意的是传入时 -c+k 以及区间长度限制了查询哈希的时候要动态修改区间端点，不然会搞到错误的区间长度导致哈希匹配失败。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
const int N=1e6+10;
int n,k,q,a[N];
ull pw[N];
struct sgn{ ull hv; ll tv; }t[N<<2];
void pushup(int p,int l,int r){
    int mid=(l+r)>>1;
    t[p].hv=t[p<<1].hv*pw[r-mid]+t[p<<1|1].hv;
    t[p].tv=(t[p<<1].tv+t[p<<1|1].tv)%k;
}
void build(int p,int l,int r){
    if(l==r){
        t[p].hv=t[p].tv=(a[l]-a[l-1]+k)%k;
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p,l,r);
    return;
}
void update(int p,int l,int r,int pos,ll uv){
    if(pos>n) return;
    if(l==r){
        t[p].hv=(t[p].tv=(t[p].tv+uv)%k);
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(p<<1,l,mid,pos,uv);
    else         update(p<<1|1,mid+1,r,pos,uv);
    pushup(p,l,r);
    return;
}
ll query_tv(int p,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)
        return t[p].tv;
    ll res=0;
    int mid=(l+r)>>1;
    if(ql<=mid) res=(res+query_tv(p<<1,l,mid,ql,qr))%k;
    if(qr>mid ) res=(res+query_tv(p<<1|1,mid+1,r,ql,qr))%k;
    return res;
}
ull query_hs(int p,int l,int r,int ql,int qr){
    if(ql>qr) return 0;
    if(ql<=l&&r<=qr)
        return t[p].hv;
    ull res=0;
    int mid=(l+r)>>1;
    if(ql>mid) return query_hs(p<<1|1,mid+1,r,ql,qr);
    if(qr<=mid)return query_hs(p<<1,l,mid,ql,qr);
    ull res_l=query_hs(p<<1,l,mid,ql,mid),  
        res_r=query_hs(p<<1|1,mid+1,r,mid+1,qr);
    return res_l*pw[qr-mid]+res_r;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i], a[i]%=k;
    pw[0]=1;
    for(int i=1;i<=n;i++)
        pw[i]=pw[i-1]*131;
    build(1,1,n);
    while(q--){
        int op,l,r,x,y;
        ll c;
        cin>>op;
        if(op==1){
            cin>>l>>r>>c;
            update(1,1,n,l,c);
            update(1,1,n,r+1,-c+k);
        }else{
            cin>>l>>r>>x>>y;
            ull h1=query_tv(1,1,n,1,l),   h2=query_tv(1,1,n,1,x),
                m1=query_hs(1,1,n,l+1,r), m2=query_hs(1,1,n,x+1,y);
            if(h1==h2&&m1==m2)
                cout<<"Yes\n";
            else
                cout<<"No\n";
        }
    }
    return 0;
}