题目
题目链接：https://www.luogu.com.cn/problem/P6688
给出一个长度为 (n) 的非负整数序列 (a_1,a_2,a_3,ldots, a_n)，给出 (q) 次操作，每次先给出一个参数 (op)：
-
(op=0)，接下来给出 (2) 个参数 (x,y)，把 (a_x) 修改为 (y)。
-
(op=1)，接下来给出 (4) 个参数 (l_1,r_1,l_2,r_2)（保证 (r_1-l_1=r_2-l_2)），你需要判断区间 ([l_1,r_1]) 与区间 ([l_2,r_2]) 是否本质相同，如果本质相同输出
YES，否则输出NO。
本质相同的定义：令区间长度为 ( ext{len}) ，序列 (p_{1}dots p_{ ext{len}}) 为 (a_{l_1}dots a_{r_1}) 升序排序后的结果，序列 (q_{1}dots q_ ext{len}) 为 (a_{l_2}dots a_{r_2}) 升序排序后的结果，存在一个整数 (k) 使得满足 (forall i,p_i+k=q_i)。
思路
显然这个 (k) 只有可能是 (frac{sum^{r_2}_{i=l_2}a[i]-sum^{r_1}_{i=l_1}a[i]}{r_1-l_1+1})。
考虑给每一个数字一个特征值 (f(x))，这样我们就只需要判断 (sum^{r_1}_{i=l_1}f(a[i]+k)) 是否等于 (sum^{r_2}_{i=l_2}f(a[i])) 即可。
发现这个特征值需要通过若干个已知的数的特征值，得到这中间所有数加上一个整数后的特征值。
所以我们取 (f(x)=b^x)，其中 (b) 最好是质数。这样的话，如果需要求全部加上 (k) 的特征值，就只需要再乘 (b^k) 即可。
注意这道题卡自然溢出。
时间复杂度 (O(mlog n))。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010;
const ll base1=5801519,prm1=35807437,base2=13331,prm2=999999491;
int n,m,a[N];
struct BIT
{
ll c[N];
void add(int x,ll v)
{
for (int i=x;i<=n;i+=i&-i)
c[i]+=v;
}
ll query(int x)
{
ll ans=0;
for (int i=x;i;i-=i&-i)
ans+=c[i];
return ans;
}
}bit1,bit2,bit3;
ll fpow(ll x,ll k,ll p)
{
ll ans=1;
for (;k;k>>=1,x=x*x%p)
if (k&1) ans=ans*x%p;
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
bit1.add(i,a[i]);
bit2.add(i,fpow(base1,a[i],prm1));
bit3.add(i,fpow(base2,a[i],prm2));
}
while (m--)
{
int opt,l1,l2,r1,r2;
scanf("%d",&opt);
if (!opt)
{
scanf("%d%d",&l1,&l2);
bit1.add(l1,l2-a[l1]);
bit2.add(l1,((fpow(base1,l2,prm1)-fpow(base1,a[l1],prm1))%prm1+prm1)%prm1);
bit3.add(l1,((fpow(base2,l2,prm2)-fpow(base2,a[l1],prm2))%prm2+prm2)%prm2);
a[l1]=l2;
}
else
{
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
ll k=((bit1.query(r2)-bit1.query(l2-1))-(bit1.query(r1)-bit1.query(l1-1)))/(r1-l1+1);
if (k<0) k=-k,swap(l1,l2),swap(r1,r2);
ll s1=(bit2.query(r1)-bit2.query(l1-1))%prm1*fpow(base1,k,prm1)%prm1;
ll s2=(bit2.query(r2)-bit2.query(l2-1))%prm1;
ll s3=(bit3.query(r1)-bit3.query(l1-1))%prm2*fpow(base2,k,prm2)%prm2;
ll s4=(bit3.query(r2)-bit3.query(l2-1))%prm2;
if ((s1+prm1)%prm1==(s2+prm1)%prm1 && (s3+prm2)%prm2==(s4+prm2)%prm2) printf("YES
");
else printf("NO
");
}
}
return 0;
}