己所欲者，杀而夺之，亦同天赐

解题思路

一定不要用自动溢出的 Hash！！！！！！！

我真的是调吐了。。。

思路非常简单明了 : 需要我们创新一下 Hash。

首先我们的 Hash 要满足无序性。。

因此我们可以把 Hash 值的意义更改一下。

例如： \(x\) 的 Hash 值是 \(base^x\)

在每两个区间维护两个值：原序列最小值以及 Hash 值的加和

这里不可以记录 Hash 因为取 \(\bmod\) 之后大小就不一定了。。

然后直接线段树维护就好了。。。

一定不要用自动溢出的 Hash！！！！！！！

不然哪怕是用 6 个 Hash 也过不了（记录）

然后拍了大概 1e5 组数据，也没拍出错来。。。

感谢@OMA dalao 指出要取 \(\bmod\)，不然我就要 N Hash 了。。

code

#include<bits/stdc++.h>

#define int long long

#define ull unsigned long long

#define f() cout<<"Pass"<<endl

#define ls x<<1

#define rs x<<1|1

using namespace std;

inline int read()

{

	int x=0,f=1;

	char ch=getchar();

	while(ch>'9'||ch<'0')

	{

		if(ch=='-')	f=-1;

		ch=getchar();

	}

	while(ch>='0'&&ch<='9')

	{

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return x*f;

}

const int N=1e6+10,INF=1e18,mod=998244353;

const ull base=168717137ull;

int n,m,s[N];

ull p[N];

long double p6[N];

struct Node

{

	int mn;

	ull has;

	long double has6;

	Node friend operator + (Node x,Node y)

	{

		return (Node){min(x.mn,y.mn),(x.has+y.has)%mod};

	}

};

struct Segment_Tree

{

	int mn;

	ull has;

	long double has6;

}tre[N<<2];

void push_up(int x)

{

	tre[x].has=(tre[ls].has+tre[rs].has)%mod;

	tre[x].mn=min(tre[ls].mn,tre[rs].mn);

}

void insert(int x,int l,int r,int pos,int num)

{

	if(l==r)

	{

		tre[x].has=p[num]%mod;

		tre[x].mn=num;

		return ;

	}

	int mid=(l+r)>>1;

	if(pos<=mid)	insert(ls,l,mid,pos,num);

	else	insert(rs,mid+1,r,pos,num);

	push_up(x);

}

Node query(int x,int l,int r,int L,int R)

{

	if(L<=l&&r<=R)	return (Node){tre[x].mn,tre[x].has};

	int mid=(l+r)>>1;

	Node ans1=(Node){INF,0ull},ans2=(Node){INF,0ull};

	if(L<=mid)	ans1=query(ls,l,mid,L,R);

	if(R>mid)	ans2=query(rs,mid+1,r,L,R);

	return ans1+ans2;

}

signed main()

{

	n=read();

	m=read();

	p[0]=1;

	for(int i=1;i<N;i++)	p[i]=p[i-1]*base%mod;

	for(int i=1;i<=n;i++)

		s[i]=read();

	for(int i=1;i<=n;i++)

		insert(1,1,n,i,s[i]);

	for(int i=1,opt,x,y,l1,r1,l2,r2;i<=m;i++)

	{

		opt=read();

		if(!opt)

		{

			x=read();y=read();

			insert(1,1,n,x,y);

			continue;

		}

		l1=read();r1=read();l2=read();r2=read();

		Node ans1=query(1,1,n,l1,r1);

		Node ans2=query(1,1,n,l2,r2);

		if(ans1.mn<ans2.mn)	swap(ans1,ans2);

		if(p[ans1.mn-ans2.mn]*ans2.has%mod==ans1.has%mod)

			printf("YES\n");

		else	printf("NO\n");

	}

	return 0;

}

巴特西

题解 P6688 可重集

解题思路

code

最新文章

热门文章