[Ynoi2016]谁的梦-白红宇

[Ynoi2016]谁的梦

阅读量：5300 次

发布时间：2019-06-14

本文共 2828 字，大约阅读时间需要 9 分钟。

题目大意：

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

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

解题思路：

窝又来切Ynoi辣

STL题。

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

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

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

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

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

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

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

C++ Code：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             using namespace std;typedef pair
             
              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
              
               s[N];map
               
                gx;vector
                
                 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<
                 
                  <<'\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<
                  
                   <<'\n'; } return 0;}

转载于:https://www.cnblogs.com/Mrsrz/p/10519309.html

你可能感兴趣的文章