ouuan 的博客

ouuan 的博客

题解 P3792 【由乃与大母神原型和偶像崇拜】

posted on 2019-01-15 18:45:49 | under 题解 |

我用的是随机映射+异或和判断连续,由于可以方便地用树状数组维护,混了个最优解..

整体思路

  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$ 。

树状数组维护前缀异或和

这个跟维护前缀和是一样的..把+换成^就可以了。

参考代码

由于我方法二的代码写的太丑了,这里就只放方法一的代码..

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