SdNUoPmOC

CJZJC · 2025-05-01 14:04:58 · 题解

“主播主播，官方题解的思路确实是很好，但是太吃脑力了，有没有更容易上手的操作？”

“有的兄弟，有的。”

“主播，这题要支持区间加和区间取模操作，我只知道如何支持单点加和区间取模怎么做，比如 CF438D，但是支持区间加和区间取模操作是我从未见过的。”

“这位兄弟你是不是没看见它要查询什么，这个两个区间相等显然是用 hash。对于修改，容易发现修改后的一段区间差分数组模 k 的值不变，只会改变左右两端点的差分值，所以在查询的时候……”

“主播，你好强啊！我只要在查询的时候看开头两点的值是否相同以及这两段区间的差分数组是否相同即可，可以用线段树和 hash 实现。”

“哦对了主播你有代码吗？发我吧。”

“有的兄弟，有的。”

#include<bits/stdc++.h>
using namespace std;
#define N 2000010
int n,k,q,a[N],c[N],d[N];
const int mod=998442353;
unsigned long long bas[N];
long long basx[N];
int lowbit(int x){
    return x&(-x);
}
void add(int x,int v){
    if(x==n+1){
        return;
    }
    if(x==0){
        x=1;
    }
    for(;x<=n;x+=lowbit(x)){
        c[x]+=v;
        c[x]+=k;
        c[x]%=k;
    }
}
int sum(int x){
    if(x==n+1){
        x=n;
    }
    if(x==0){
        return 0;
    }
    int s=0;
    for(;x;x-=lowbit(x)){
        s+=c[x];
        s%=k;
    }
    s+=k;
    s%=k;
    return s;
}
struct stu{
    int l,r;
    unsigned long long h;
    long long hx;
    friend stu operator+(stu l,stu r){
        stu p;
        p.l=l.l;
        p.r=r.r;
        p.h=l.h*bas[r.r-r.l+1]+r.h;
        p.hx=(l.hx*basx[r.r-r.l+1]%mod+r.hx)%mod;
        return p;
    }
}t[N<<2];
#define ls p<<1
#define rs p<<1|1
void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        t[p].h=d[l];
        t[p].hx=d[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    t[p]=t[ls]+t[rs];
}
void update(int p,int x,int v){
    if(t[p].l==t[p].r){
        t[p].h=v;
        t[p].hx=v;
        return;
    }
    if(x<=t[ls].r){
        update(ls,x,v);
    }
    else{
        update(rs,x,v);
    }
    t[p]=t[ls]+t[rs];
}
stu ask(int p,int l,int r){
    if(l<=t[p].l&&t[p].r<=r){
        return t[p];
    }
    if(r<=t[ls].r){
        return ask(ls,l,r);
    }
    if(l>=t[rs].l){
        return ask(rs,l,r);
    }
    return ask(ls,l,r)+ask(rs,l,r);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k>>q;
    bas[0]=1;
    basx[0]=1;
    for(int i=1;i<=n+5;i++){
        bas[i]=bas[i-1]*k;
        basx[i]=basx[i-1]*k%mod;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
        add(i,a[i]);
        add(i+1,-a[i]);
    }
    for(int i=1;i<=n;i++){
        d[i]=(a[i+1]-a[i]+k)%k+1;
    }
    build(1,1,n-1);
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int l,r,c;
            cin>>l>>r>>c;
            add(l,c);
            add(r+1,-c);
            if(l>1){
                d[l-1]=((sum(l)%k)-(sum(l-1)%k)+k)%k+1;
                update(1,l-1,d[l-1]);
            }
            if(r<n){
                d[r]=((sum(r+1)%k)-(sum(r)%k)+k)%k+1;
                update(1,r,d[r]);
            }
        }
        else{
            int l1,l2,r1,r2,s1,s2;
            unsigned long long h1,h2;
            long long h1x,h2x;
            cin>>l1>>r1>>l2>>r2;
            s1=sum(l1)%k;
            s2=sum(l2)%k;
            if(r1-l1+1==1){
                if(s1==s2){
                    cout<<"Yes\n";
                }
                else{
                    cout<<"No\n";
                }
            }
            else{
                stu ak1=ask(1,l1,r1-1),ak2=ask(1,l2,r2-1);
                h1=ak1.h;
                h2=ak2.h;
                h1x=ak1.hx;
                h2x=ak2.hx;
                if((s1==s2)&&(h1==h2)&&(h1x==h2x)){
                    cout<<"Yes\n";
                }
                else{
                    cout<<"No\n";
                }
            }
        }
    }
    return 0;
}