[Ynoi2016]谁的梦

题目大意：

给定$n$个序列，要你从每个序列中选一个非空子串然后拼起来，拼成的序列的贡献为不同元素个数。

支持单点修改，在开始时和每次修改完后，输出所有不同选取方案的贡献和。

解题思路：

窝又来切Ynoi辣

STL题。

考虑每种元素的贡献，相当于求出有多少种方案包含这个数。补集转化成有多少种方案不包含这个数。

求有多少种方案不包含这个数，就相当于求每个序列有多少子区间不包含这个数，然后乘法原理。

而求有多少子区间不包含这个数，就相当于用这个数把序列分成若干区间，每个区间内部可以任意选取。

用一个数组存每种数有多少方案不包含，用map存每个序列里每种数有多少方案不包含，对每种数开个set存其位置。

插入的时候，相当于把一个大区间分裂成两个小区间，在set里查找前驱后继，更新map里的值即可。同时更新数组里的值和答案。删除的时候同理。

注意当一个序列只有一种数的时候，map里值为0，所以需要特殊处理一下，打个标记。

时间复杂度$O((n+m)\log n)$。

C++ Code：

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#include<map>

#include<set>

#include<vector>

#include<iostream>

using namespace std;

typedef pair<int,int>pii;

const int md=19260817,N=2e5+5;

typedef long long LL;

int L[N],R[N],bel[N],len[N],a[N],n,m,inv[300005],LN[N],Ynoi=1,ept[N],P[N];

int ans=0;

set<int>s[N];

map<pii,int>gx;

vector<int>lr;

struct opts{

	int x,y,z;

}q[N];

inline int C2(int len){return(len*(len-1LL)>>1)%md;}

inline int INV(int i){return(i<300000)?inv[i]:((LL)md-md/i)*INV(md%i)%md;}

void insert(int col,int pos){

	int pre=*--s[col].lower_bound(pos),suf=*s[col].upper_bound(pos);

	pre=max(pre,L[bel[pos]]-1),suf=min(suf,R[bel[pos]]+1);

	const pii xb=make_pair(bel[pos],col);

	if(!gx.count(xb))gx[xb]=C2(len[bel[pos]]+1);

	int&v=gx[xb];

	ans=(ans+((ept[col])?0:LN[col]))%md;

	LN[col]=(LL)LN[col]*INV(v)%md;

	v=(v-C2(suf-pre)+C2(pos-pre)+C2(suf-pos)+md)%md;

	if(v)

	LN[col]=(LL)LN[col]*v%md;else ++ept[col];

	ans=(ans-((ept[col])?0:LN[col])+md)%md;

	s[col].insert(pos);

}

void erase(int col,int pos){

	int pre=*--s[col].lower_bound(pos),suf=*s[col].upper_bound(pos);

	pre=max(pre,L[bel[pos]]-1),suf=min(suf,R[bel[pos]]+1);

	const pii xb=make_pair(bel[pos],col);

	if(!gx.count(xb))gx[xb]=C2(len[bel[pos]]+1);

	int&v=gx[xb];

	ans=(ans+((ept[col])?0:LN[col]))%md;

	if(!v)--ept[col];else

	LN[col]=(LL)LN[col]*INV(v)%md;

	v=(v+C2(suf-pre)-C2(pos-pre)-C2(suf-pos)+md+md)%md;

	LN[col]=(LL)LN[col]*v%md;

	ans=(ans-((ept[col])?0:LN[col])+md)%md;

	s[col].erase(pos);

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	inv[1]=1;

	for(register int i=2;i<300000;++i)inv[i]=((LL)md-md/i)*inv[md%i]%md;

	for(int i=1;i<=n;++i)cin>>len[i],L[i]=R[i-1]+1,R[i]=R[i-1]+len[i],Ynoi=(LL)Ynoi*C2(len[i]+1)%md,P[i]=P[i-1]+len[i];

	for(int i=1;i<=n;++i)

	for(int j=L[i];j<=R[i];++j)bel[j]=i,cin>>a[j],lr.push_back(a[j]);

	for(int i=1;i<=m;++i){

		cin>>q[i].x>>q[i].y>>q[i].z;

		lr.push_back(q[i].z);

	}

	sort(lr.begin(),lr.end());

	lr.erase(unique(lr.begin(),lr.end()),lr.end());

	for(int i=0;i<=lr.size();++i)s[i].insert(0),s[i].insert(R[n]+1),LN[i]=Ynoi;

	for(int i=1;i<=R[n];++i){

		a[i]=lower_bound(lr.begin(),lr.end(),a[i])-lr.begin();

		insert(a[i],i);

	}

	cout<<ans<<'\n';

	for(int i=1;i<=m;++i){

		const int id=P[q[i].x-1]+q[i].y;

		erase(a[id],id);

		insert(a[id]=lower_bound(lr.begin(),lr.end(),q[i].z)-lr.begin(),id);

		cout<<ans<<'\n';

	}

	return 0;

}

巴特西

[Ynoi2016]谁的梦

最新文章

热门文章