题解 P3792 【由乃与大母神原型和偶像崇拜】
ouuan
2019-01-15 18:45:49
我用的是随机映射+异或和判断连续，由于可以方便地用树状数组维护，混了个最优解..
# 整体思路
1. 把每个数都映射到一个随机数上。
2. 通过求区间内原数的和来判断，这个区间如果连续，值域应该在哪个区间。举个例子，区间长度为 $3$，区间和为 $9$，那么如果这个区间的值连续，值域就应该是 $2$ ~ $4$。
3. 预处理出随机序列的前缀异或和，然后就可以求出，这个区间如果连续，映射到的随机数异或和应该是多少。举个例子，如果值域应该是 $2$ ~ $4$，映射到的随机数分别为 $p_2,\,p_3,\,p_4$，可以通过前缀异或和算出 $p_2\oplus p_3\oplus p_4$（$\oplus$表示异或），如果区间内这三个数映射到的随机数的异或和等于 $p_2\oplus p_3\oplus p_4$，就可以认为这个区间是连续的。
序列的前缀和、序列映射到的随机数的前缀异或和都可以用树状数组维护。
# 具体实现与细节
## 随机数生成
这个随便生成就好了..怕被卡的话可以把 `time(0)` 作为生成随机数的参数之一。推荐用 unsigned long long 自然溢出，也可以用 int 对大质数取模，int 自然溢出貌似过不了。
## 离散化
由于值域是 $10^9$，肯定不能生成 $10^9$ 个随机数，所以需要离散化。
直接离散化的话可能会导致本不连续的值连续，有两种解决方法。
### 一、
这种方法比较优美自然。离散化的时候把每个值+1放到离散化数组里，这样原本不连续的数离散化后也不连续。
### 二、
这种方法稍微麻烦一点，然而常数会小一些。记录一下离散化数组中每个数是否和前一个数一样，如果离散化用的数组叫做 $lsh$（已经排好序），令 $dif_i=[lsh_i=lsh_{i-1}]$，求出 $dif$ 的前缀和 $blo_i$ ，那么 $blo_i$ 相同的数就是在一个连续块里的。令 $f_i=[blo_{a_i}=blo_{a_{i-1}}]$（也就是这一位是否和前一位在一个连续块里），再用一个树状数组维护 $f$ 的前缀和，就可以快速查询一个区间内的所有值是否都在同一个连续块里。
## 修改
修改的时候如果是用方法一离散化的，直接在树状数组里更新和还有异或和就可以了。如果是用方法二离散化的，还要更新修改的位置以及修改的位置的下一个位置的 $f$。
## 树状数组维护前缀异或和
这个跟维护前缀和是一样的..把+换成^就可以了。
# 参考代码
由于我方法二的代码写的太丑了，这里就只放方法一的代码..
```cpp
#include <iostream>
#include <cstdio>
#include <cctype>
#include <ctime>
#include <algorithm>
using namespace std;
const int N=500010;
typedef unsigned long long ull;
int read()
{
int out=0;
char c;
while (!isdigit(c=getchar()));
for (;isdigit(c);c=getchar()) out=out*10+c-'0';
return out;
}
void asum(int p,int x); //维护和的树状数组
ull qsum(int p);
void axor(int p,ull x); //维护异或和的树状数组
ull qxor(int p);
int n,m,a[N],lsh[N<<2],tot,op[N],x[N],y[N]; //op、x、y是先把询问存下来，方便离散化
ull p[N<<2],pre[N<<2],sum[N],xsum[N]; //p是随机数，pre是随机数的前缀异或和，后面两个是树状数组
int main()
{
int i,l,r,mid;
n=read();
m=read();
for (i=1;i<=n;++i)
{
lsh[++tot]=a[i]=read();
lsh[++tot]=a[i]+1; //离散化的时候把值+1也放进去，这样不连续的值离散化后也不连续
}
for (i=1;i<=m;++i)
{
op[i]=read();
x[i]=read();
y[i]=read();
if (op[i]==1)
{
lsh[++tot]=y[i];
lsh[++tot]=y[i]+1;
}
}
sort(lsh+1,lsh+tot+1);
tot=unique(lsh+1,lsh+tot+1)-lsh;
p[0]=time(0); //~~欢迎大家来卡我~~如果真被卡了我就换成梅森旋转好了..
for (i=1;i<tot;++i)
{
p[i]=p[i-1]*1000000007+19260817; //生成随机数
pre[i]=pre[i-1]^p[i]; //求随机序列的前缀异或和
}
for (i=1;i<=n;++i)
{
a[i]=lower_bound(lsh+1,lsh+tot,a[i])-lsh; //离散化
asum(i,a[i]); //初始化前缀和
axor(i,p[a[i]]); //初始化前缀异或和
}
for (i=1;i<=m;++i)
{
if (op[i]==1)
{
y[i] = lower_bound(lsh + 1, lsh + tot, y[i]) - lsh;
asum(x[i],y[i]-a[x[i]]); //更新前缀和
axor(x[i],p[y[i]]^p[a[x[i]]]); //更新前缀异或和
a[x[i]]=y[i]; //更新单点的值
}
else
{
mid=(qsum(y[i])-qsum(x[i]-1))/(y[i]-x[i]+1); //算出l、r，代表如果区间连续，值域的范围
l=mid-(y[i]-x[i])/2;
if ((y[i]-x[i])&1) r=mid+(y[i]-x[i])/2+1;
else r=mid+(y[i]-x[i])/2;
if (l<=0||r>=tot) puts("yuanxing");
else if ((qxor(y[i])^qxor(x[i]-1))==(pre[r]^pre[l-1])) puts("damushen"); //判断实际的区间异或和与值域内异或和是否相等
else puts("yuanxing");
}
}
return 0;
}
void asum(int p,int x)
{
for (;p<=n;p+=(p&-p)) sum[p]+=x;
}
ull qsum(int p)
{
ull out=0;
for (;p;p-=(p&-p)) out+=sum[p];
return out;
}
void axor(int p,ull x)
{
for (;p<=n;p+=(p&-p)) xsum[p]^=x;
}
ull qxor(int p)
{
ull out=0;
for (;p;p-=(p&-p)) out^=xsum[p];
return out;
}
```