[DS记录]P4692 [Ynoi2016] 谁的梦
command_block
2021-06-30 14:44:29
**题意** ： 定义一个序列的权值为不同数字的个数。
给出 $n$ 个序列 $A_{1\sim n}$ ，在每个序列中选择一个连续非空子串，拼接起来。
求所有选法得到的序列的权值总和。如果一个序列能通过多种方法被选择出来，要计算多次。
需要支持单点修改。答案对 $19260817$ 取模。
允许离线，$m,\sum |A|\leq 10^5$ ，时限$\texttt{1.5s}$。
------------
简单题。
将所有作为值的数字离散化。
先不考虑修改。
记不同的数的总数为 $n_0$ ，分别考虑每个数的贡献。
正难则反，对于每个数 $k$ ，计数其没有出现的所有选法。
总选法是 $\prod_{i=1}^n\frac{(|A_i|+1)|A_i|}{2}$ ，记 $C_i=\frac{(|A_i|+1)|A_i|}{2}$。
对于序列 $i$ ，记 $s_{i,k}$ 表示在 $i$ 中选一个不包含 $k$ 的区间的方案数。
则答案为 ：
$$p\prod_{i=1}^nC_i-\sum\limits_{k=1}^{n_0}\prod_{i=1}^ns_{i,k}$$
然而 $n,n_0$ 可能都很大，不能处理到每个 $s$。
注意到当 $A_i$ 中有数 $k$ 时， $s_{i,k}$ 才会 $\neq C_i$ 。这类特殊位置的个数是 $O\big(\sum |A|\big)$ 的。
记 $P_k=\prod_{i=1}^ns_{i,k}$。初始时令 $P_k=\prod_{i=1}^nC_i$。
逐个考虑 $k$ 出现过的序列的贡献，将 $P_k$ 除去 $C_i$ 后，乘上特殊计算的 $s_{i,k}$。
接下来考虑如何动态维护。
我们单点修改序列 $i$ 后，会影响两个 $s_{i,k}$ 的计算。
我们需要支持 ： 插入，删除，计算不包含关键位置的数的个数。
注意到答案与极长不含关键点连续段有关，用 `std::set` 维护即可。
为了方便，可以将 $n$ 个序列拼在一起，这样每个颜色就只需要开一个 `set` 了。
对于那些不等于 $C_i$ 的 $s_{i,k}$ ，用 `std::map` 维护。
注意可能有某个 $s_{i,k}=0$ ，此时不便于做除法，要特殊记零因子的个数。
复杂度 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
#define itor set<int>::iterator
#define Itor map<int,int>::iterator
#define sec second
#define ll long long
#define MaxN 100500
using namespace std;
const int mod=19260817;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
inline int C(int n){return 1ll*n*(n+1)/2%mod;}
set<int> p[MaxN<<1];
map<int,int> s[MaxN<<1];
int buf[MaxN<<1],c0[MaxN<<1],ret
,tl[MaxN],tr[MaxN],tb[MaxN],len[MaxN];
void add(int i,int c)
{
p[c].insert(i);
itor it=p[c].find(i);
int l,r,k=tb[i];
l=max(*(--it),tl[i]);it++;
r=min(*(++it),tr[i]);
if (!s[c].count(k))
s[c][k]=C(len[k]-len[k-1]);
Itor it2=s[c].find(k);
ret=(ret+(c0[c] ? 0 : buf[c]))%mod;
buf[c]=1ll*buf[c]*powM(it2->sec)%mod;
it2->sec=((ll)it2->sec+C(r-i-1)+C(i-l-1)-C(r-l-1))%mod;
if (it2->sec==0)c0[c]++;
else buf[c]=1ll*buf[c]*(it2->sec)%mod;
ret=(ret-(c0[c] ? 0 : buf[c]))%mod;
}
void del(int i,int c)
{
itor it=p[c].find(i);
int l,r,k=tb[i];
l=max(*(--it),tl[i]);it++;
r=min(*(++it),tr[i]);
p[c].erase(i);
Itor it2=s[c].find(k);
ret=(ret+(c0[c] ? 0 : buf[c]))%mod;
if (it2->sec==0)c0[c]--;
else buf[c]=1ll*buf[c]*powM(it2->sec)%mod;
it2->sec=((ll)it2->sec+C(r-l-1)-C(r-i-1)-C(i-l-1))%mod;
buf[c]=1ll*buf[c]*(it2->sec)%mod;
ret=(ret-(c0[c] ? 0 : buf[c]))%mod;
}
int n,m,x[MaxN<<1],tn,to[MaxN],tx[MaxN],a[MaxN];
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{scanf("%d",&len[i]);len[i]+=len[i-1];}
for (int i=1;i<=n;i++)
for (int j=len[i-1]+1;j<=len[i];j++){
scanf("%d",&a[j]);x[++tn]=a[j];
tl[j]=len[i-1];tr[j]=len[i]+1;tb[j]=i;
}
for (int i=1,id,pos;i<=m;i++){
scanf("%d%d%d",&id,&pos,&tx[i]);
to[i]=len[id-1]+pos;x[++tn]=tx[i];
}
sort(x+1,x+tn+1);
tn=unique(x+1,x+tn+1)-x-1;
ret=1;
for (int i=1;i<=n;i++)
ret=1ll*ret*C(len[i]-len[i-1])%mod;
for (int i=1;i<=tn;i++){
buf[i]=ret;
p[i].insert(0);
p[i].insert(len[n]+1);
}ret=0;
for (int i=1;i<=len[n];i++){
a[i]=lower_bound(x+1,x+tn+1,a[i])-x;
add(i,a[i]);
}
printf("%d\n",(ret+mod)%mod);
for (int i=1;i<=m;i++){
int wfc=lower_bound(x+1,x+tn+1,tx[i])-x;
del(to[i],a[to[i]]);add(to[i],a[to[i]]=wfc);
printf("%d\n",(ret+mod)%mod);
}return 0;
}
```