P12389 COmPoUNdS 题解

hzoi_Shadow · 2025-05-05 14:31:08 · 题解

题目传送门

前置知识

前缀和 & 差分 | 线段树基础

解法

修改只有区间加操作，套路性地想到维护差分数组的哈希值来将区间修改简化至单点修改，同时维护端点处的原值用于判相等。

具体地，设 b 为 a 的差分数组，则 a_{l_{1} \dots r_{1}},a_{l_{2} \dots r_{2}} 完全相等当且仅当 a_{l_{1}}=a_{l_{2}} 且 b_{l_{1}+1 \dots r_{1}},b_{l_{2}+1 \dots r_{2}} 完全相等。

前者是一个区间加单点查的形式，后者是一个单点加区间查询的形式，可以使用线段树维护。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
const int mod=1000003579,base=13331;
int jc[1000010],a[1000010],p;
struct SMT
{
    struct SegmentTree
    {
        int lazy,hsh,len;
    }tree[4000010];
    #define lson(rt) (rt<<1)
    #define rson(rt) (rt<<1|1)
    void pushup(int rt)
    {
        tree[rt].hsh=(1ll*tree[lson(rt)].hsh*jc[tree[rson(rt)].len]%mod+tree[rson(rt)].hsh)%mod;
    }
    void build(int rt,int l,int r)
    {
        tree[rt].len=r-l+1;
        if(l==r)  
        {
            tree[rt].lazy=a[l];
            tree[rt].hsh=(a[l]-a[l-1]+p)%p;
            return;
        }
        int mid=(l+r)/2;
        build(lson(rt),l,mid);  build(rson(rt),mid+1,r);
        pushup(rt);
    }
    void update1(int rt,int l,int r,int pos,int val)
    {
        if(l==r)
        {
            tree[rt].hsh=(tree[rt].hsh+val)%p;
            return;
        }
        int mid=(l+r)/2;
        if(pos<=mid)  update1(lson(rt),l,mid,pos,val);
        else  update1(rson(rt),mid+1,r,pos,val);
        pushup(rt);
    }
    void update2(int rt,int l,int r,int x,int y,int val)
    {
        if(x<=l&&r<=y)
        {
            tree[rt].lazy=(tree[rt].lazy+val)%p;
            return;
        }
        int mid=(l+r)/2;
        if(x<=mid)  update2(lson(rt),l,mid,x,y,val);
        if(y>mid)  update2(rson(rt),mid+1,r,x,y,val);
    }
    int query1(int rt,int l,int r,int pos)
    {
        if(l==r)  return tree[rt].lazy;
        int mid=(l+r)/2;
        if(pos<=mid)  return (query1(lson(rt),l,mid,pos)+tree[rt].lazy)%p;
        else  return (query1(rson(rt),mid+1,r,pos)+tree[rt].lazy)%p;
    }
    pair<int,int> query2(int rt,int l,int r,int x,int y)
    {
        if(x<=l&&r<=y)  return make_pair(tree[rt].hsh,tree[rt].len);
        int mid=(l+r)/2;
        if(y<=mid)  return query2(lson(rt),l,mid,x,y);
        if(x>mid)  return query2(rson(rt),mid+1,r,x,y);
        pair<int,int>p=query2(lson(rt),l,mid,x,y);
        pair<int,int>q=query2(rson(rt),mid+1,r,x,y);
        return make_pair((1ll*p.first*jc[q.second]%mod+q.first)%mod,p.second+q.second);
    }
}T;
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    int n,m,pd,l1,r1,l2,r2,x,i;
    scanf("%d%d%d",&n,&p,&m);  jc[0]=1;
    for(i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        jc[i]=1ll*jc[i-1]*base%mod;
    }
    T.build(1,1,n);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&pd,&l1,&r1);
        if(pd==1)
        {
            scanf("%d",&x);
            T.update1(1,1,n,l1,x);
            if(r1+1<=n)  T.update1(1,1,n,r1+1,(p-x)%p);
            T.update2(1,1,n,l1,r1,x);
        }
        else
        {
            scanf("%d%d",&l2,&r2);
            if(T.query1(1,1,n,l1)==T.query1(1,1,n,l2))
            {
                if(r1>l1)
                {
                    if(T.query2(1,1,n,l1+1,r1).first==T.query2(1,1,n,l2+1,r2).first)  printf("Yes\n");
                    else  printf("No\n");
                }
                else  printf("Yes\n");
            }
            else  printf("No\n");
        }
    }
    return 0;
}