前置知识

解法

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

具体地，设

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}}

完全相等。

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

代码

CPP

#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;
}

P12389 COmPoUNdS 题解

文章操作

前置知识

解法

代码

相关推荐

评论

P12389 COmPoUNdS 题解