How Many Hougong题解

发表于 2018-04-07 更新于 2018-04-08 分类于 OI

题目简述

给定一串长度为 $n$ 的序列，每个点上有一个权值 $a_i$ ，现在你需要处理 $q$ 个操作，有以下两种操作：

$1$ $val$

表示你需要构造一个序列，序列中每一个元素 $seq_i$ 小于等于 $a_i$ 且大于 $0$，问所有合法的序列中 $val$ 出现了几次。

$2$ $pos$ $val$

表示把 $pos$ 号节点的点权修改为 $val$，点的编号从 $0$ 开始。

对于每一个询问 $2$ ，请输出操作的结果 $mod$ $p$，$p$ 为质数。

Solution

考虑每个节点对答案的贡献：显然总方案数为 \[\prod_{i=0}^{n-1} a_i\] 显然若第 $i$ 号节点的 $a_i < val$ ，则 $i$ 节点对答案贡献为 $0$ 若第 $i$ 号节点 $a[i] >= val$ ，则 $i$ 节点对答案的贡献为 \[\frac{\prod_{i=0}^{n-1}a_i}{a_i}\]

考虑一次询问，我们要求的就是：

\[\frac{\prod_{i=0}^{n-1}a_i}{a_{i1}} + \frac{\prod_{i=0}^{n-1}a_i}{a_{i2}} + \frac{\prod_{i=0}^{n-1}a_i}{a_{i3}} + \cdots + \frac{\prod_{i=0}^{n-1}a_i}{a_{im}}\]

并且

\[a_{i1},a_{i2},a_{i3},\cdots,a_{im} >= val\]

这显然是不能快速求的。观察题目发现 $p$ 为质数，考虑使用费马小定理求解，则得到：

\[\prod_{i=0}^{n-1}a_i \times (a_{i1}^{mod - 2} + a_{i2}^{mod - 2} + \cdots + a_{im}^{mod - 2})\]

有人可能会说： > Wen_kr, 你这样不会重复累计吗？

实际上并不会，由于 \[\prod_{i=0}^{n-1}a_i \times a_{i1}^{mod-2}\] 累积的是当 $a_{i1}$ 为 $val$ 时对答案的贡献，即在其他所有情况时， $a_{i1}$ 对答案的贡献，因此，这样的统计是无重复无遗漏的。

这样一来，我们只需要把 $a_{i}^{mod - 2}$ 用数据结构维护起来就可以求解了！考虑使用线段树。把所有的 $a_i$ 与所有询问的 $val$ 插入同一个数组排序，再把数组 $unique$ 一下，我们设现在的数组大小为 $tot$ ，修改操作，我们把 $a_i$ $lowerbound$ 一下，在 $lowerbound$ 的位置处修改。对于查询操作，我们把查询的 $val$ $lowerbound$ 一下，设$lowerbound$结果为 $p$，则最终结果即为从 $p$ 到 $tot$ 所有元素的和。这样使用线段树就十分方便。

接着考虑操作 $2$

线段树的修改是很好完成的，只需要回滚一次+修改一次即可得到解。

就只剩下一个问题：怎么维护新的累乘之积。

考虑使用费马小定理，新的累乘之和即为：

\[\prod_{i=0}^{n-1}a_i \times a_{pos}^{mod - 2} \times val\]

就可以完成啦...吗？

当你欣喜地写完程序，测完样例，却发现，样例都无法过去……

因此，我们目前的方法，仍然有严重的漏洞。

是什么呢？

我们考虑一个数 $a_i$ ，假设$a_i % mod = 0 $，当我们修改 $a_i$ 回滚操作的时候，能显然发现这样是不对的，因为这样回滚，就是把累乘之积除上了一个 $0$ !

考虑用一个新的变量 $c$ 来记录当前序列中有多少个 $a_i$ 使 $a_i \% mod = 0$ 新开一棵线段树，维护一段区间内有多少个 $a_i$ 满足这个条件。对于每个满足条件的 $a_i$ ，因为 $a_i^{mod - 2} = 0$ ，因此我们没有必要将它插入原线段树，并且因为乘了 $a_i$ 之后，我们维护累乘之积的变量会始终为零并会出现错误，因此累计累乘时也不累计 $a_i$。

查询操作，若 $c = 0$ ，我们就像如上文所述的查询查值。若 $c = 1$ ，我们在 $p$ 到 $tot$ 上求一遍有多少个 $a_i$ 满足条件，$p$的意义如上文所述。这样一来，假如查询的结果为 $0$ ，那么无论如何，累乘的结果 $ % mod$ 始终为 $0$ ，这样结果为 $0$ 否则由于当且仅当 $a_i$ ($a_i$ 符合上文条件) 对答案的贡献为 $1$，即当 $a_i = val$ 时，我们的答案才有值，因此答案为 $\prod_{i=0}^{n-1}a_i,a_i\text{不符合上文条件}$ 可以看出这个答案为上文的累乘之和。

若$c > 1$ 无论我们把哪个值对累乘的贡献置为 $1$，让其等于 $val$，最终的结果均为 $0$

对于修改操作，若被修改的原值 $\% mod = 0$，我们则更新 $c$ 值与另一棵线段树的值，否则则按原操作方法处理。对于修改后的值，我们同样考虑其 $\% mod%$ 的值，分类处理即可。

AC Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

long long all[400050],a[400050];
long long tot,sum[800050],cnt[800050];
long long mod,n,q,t,c;

struct Caozuo
{
    long long op,pos,val;
}op[400050];

long long qpow(long long base,long long tms)
{
    long long tmp = 1;
    base %= mod;
    while(tms)
    {
        if(tms & 1) tmp = tmp * base % mod;
        base = base * base % mod;
        tms >>= 1;
    }
    return tmp;
}

void Update(long long val[],long long rt,long long pos,long long l,long long r,long long valx)
{
    if(l == r)
    {
        val[rt] = ((val[rt] + valx) % mod + mod) % mod;
        return ;
    }
    long long mid = (l + r) >> 1;
    if(mid >= pos) Update(val,rt << 1,pos,l,mid,valx);
    else Update(val,rt << 1 | 1,pos,mid + 1,r,valx);
    val[rt] = val[rt << 1] + val[rt << 1 | 1];
    val[rt] %= mod;
}

long long Query(long long val[],long long rt,long long l,long long r,long long l1,long long r1)
{
    if(l >= l1 && r <= r1) return val[rt] % mod;
    long long mid = (l + r) >> 1;
    long long tmp = 0;
    if(mid >= l1) tmp = (tmp + Query(val,rt << 1,l,mid,l1,r1)) % mod;
    if(mid < r1) tmp = (tmp + Query(val,rt << 1 | 1,mid + 1,r,l1,r1)) % mod;
    return tmp;
}

void Input()
{
    tot = 0;
    memset(sum,0,sizeof(sum));memset(cnt,0,sizeof(cnt));
    scanf("%lld%lld%lld",&n,&mod,&q);
    for(long long i = 1;i <= n; ++ i)
    {
        scanf("%lld",&a[i]);
        all[++tot] = a[i];
    }
    for(long long i = 1;i <= q; ++ i)
    {
        scanf("%lld",&op[i].op);
        if(op[i].op == 1)
        {
            scanf("%lld",&op[i].val);
            all[++tot] = op[i].val;
        }
        else
        {
            scanf("%lld%lld",&op[i].pos,&op[i].val);
            all[++tot] = op[i].val;
            op[i].pos ++;
        }
    }
}

void Work()
{
    sort(all + 1,all + tot + 1);
    long long mul = 1;
    c = 0;
    tot = unique(all + 1,all + tot + 1) - all - 1;
    for(long long i = 1;i <= n; ++ i)
    {
        long long p = lower_bound(all + 1,all + 1 + tot,a[i]) - all;
        if(a[i] % mod == 0)
        {
            c ++;
            Update(cnt,1,p,1,tot,1);
        }
        else
        {
            mul = mul * a[i] % mod;
            Update(sum,1,p,1,tot,qpow(a[i],mod - 2));
        }
    }
    for(long long i = 1;i <= q; ++ i)
    {
        long long val = op[i].val;
        long long p = lower_bound(all + 1,all + 1 + tot,val) - all;
        if(op[i].op == 1)
        {
            if(c == 0) printf("%lld\n",mul * Query(sum,1,1,tot,p,tot) % mod);
            else if(c == 1)
            {
                if(Query(cnt,1,1,tot,p,tot) > 0)
                    printf("%lld\n",mul);
                else
                    printf("0\n");
            }
            else
                printf("0\n");
        }
        else
        {
            long long pos = op[i].pos;
            long long px = lower_bound(all + 1,all + 1 + tot,a[pos]) - all;
            if(a[pos] % mod == 0)
            {
                c --;
                Update(cnt,1,px,1,tot,-1);
            }
            else
            {
                mul = mul * qpow(a[pos],mod - 2) % mod;
                Update(sum,1,px,1,tot,-qpow(a[pos],mod - 2));
            }
            if(val % mod == 0)
            {
                c ++;
                Update(cnt,1,p,1,tot,1);
            }
            else
            {
                mul = mul * val % mod;
                Update(sum,1,p,1,tot,qpow(val,mod - 2));
            }
            a[pos] = val;
        }
    }
}

int main()
{
    long long T;
    scanf("%lld",&T);
    while(T--)
    {
        Input();
        Work();
    }
}