【题解】Luogu P4340 [SHOI2016] 随机序列

标签：res int 题解 mid P4340 il Luogu rid id

简单手摸后发现，答案就是这么一个式子：

\[(3^{n-1}-3^{n-2})a_1+(3^{n-2}-3^{n-3})a_1a_2+\dots+(3^1-3^0)a_1a_2\dots a_{n-1}+a_1a_2\dots a_n \]

啊当然证明也是好证的，对于 \(a_1\) 这一项，它后面放 + 或 - 都会对系数加一，而放 * 不会影响系数，因此系数就是总数的三分之二。其它前缀乘积的系数都是类似的算法。

然后为什么没有别的项了呢？可以认为 * 不产生贡献，而 + 和 - 是相同数量的，因此都消掉了。

简单预处理，修改时取逆元区间乘就行了。

但其实不行，因为输入的是非负数，而不是正整数，而 \(0\) 是没逆元的。

观察式子，发现从第一个 \(0\) 往后的项就都是 \(0\) 了。因此可以用一个 set 来维护 \(0\) 的位置。操作时正常操作，把 \(0\) 当成 \(1\) 就行了。查询时只查 \(1\) 到第一个 \(0\) 的位置前面。

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
	char ch;\
	int fu=1;\
	while(!isdigit(ch=getchar()))\
		fu-=(ch=='-')<<1;\
	x=ch&15;\
	while(isdigit(ch=getchar()))\
		x=(x<<1)+(x<<3)+(ch&15);\
	x*=fu;\
}
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5,mod=1e9+7;
int n,m,a[maxn],b[maxn],pw3[maxn];
int sum[maxn<<2],tag[maxn<<2];
il void pushup(int id){
	sum[id]=(sum[lid]+sum[rid])%mod;
}
il void pushtag(int id,int val){
	tag[id]=tag[id]*1ll*val%mod;
	sum[id]=sum[id]*1ll*val%mod;
}
il void pushdown(int id){
	if(tag[id]>1){
		pushtag(lid,tag[id]);
		pushtag(rid,tag[id]);
		tag[id]=1;
	}
}
il void build(int id,int l,int r){
	tag[id]=1;
	if(l==r){
		sum[id]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(lid,l,mid);
	build(rid,mid+1,r);
	pushup(id);
}
il void upd(int id,int L,int R,int l,int r,int val){
	if(L>=l&&R<=r){
		pushtag(id,val);
		return ;
	}
	pushdown(id);
	int mid=(L+R)>>1;
	if(l<=mid){
		upd(lid,L,mid,l,r,val);
	}
	if(r>mid){
		upd(rid,mid+1,R,l,r,val);
	}
	pushup(id);
}
il int query(int id,int L,int R,int l,int r){
	if(L>=l&&R<=r){
		return sum[id];
	}
	pushdown(id);
	int mid=(L+R)>>1,res=0;
	if(l<=mid){
		(res+=query(lid,L,mid,l,r))%=mod;
	}
	if(r>mid){
		(res+=query(rid,mid+1,R,l,r))%=mod;
	}
	return res;
}
il void debug(int id,int l,int r){
	cout<<id<<" "<<l<<" "<<r<<" "<<sum[id]<<"\n";
	if(l==r){
		return ;
	}
	pushdown(id);
	int mid=(l+r)>>1;
	debug(lid,l,mid);
	debug(rid,mid+1,r);
}
il int qpow(int x,int y){
	int res=1;
	while(y){
		if(y&1){
			res=res*1ll*x%mod;
		}
		x=x*1ll*x%mod,y>>=1;
	}
	return res;
}
set<int> zero;
namespace cplx{
	bool end;
	il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
	read(n)read(m);
	pw3[0]=1;
	for(int i=1;i<=n;i++){
		read(a[i]);
		if(!a[i]){
			a[i]=1;
			zero.insert(i);
		}
		b[i]=a[i];
		pw3[i]=pw3[i-1]*3ll%mod;
	}
	zero.insert(n+1);
	for(int i=n;i;i--){
		(pw3[i]+=mod-pw3[i-1])%=mod;
	}
	for(int i=2;i<=n;i++){
		a[i]=a[i]*1ll*a[i-1]%mod;
	}
	for(int i=1;i<=n;i++){
		a[i]=a[i]*1ll*pw3[n-i]%mod;
	}
	build(1,1,n);
	while(m--){
		int pos,val;
		read(pos)read(val);
		zero.erase(pos);
		if(!val){
			val=1,zero.insert(pos);
		}
		upd(1,1,n,pos,n,val*1ll*qpow(b[pos],mod-2)%mod);
		b[pos]=val;
		printf("%d\n",*zero.begin()==1?0:query(1,1,n,1,*zero.begin()-1));
	}
	return 0;
}
}
int main(){return asbt::main();}
/*
4 1
1 2 3 4
1 2
*/

标签：res,int,题解,mid,P4340,il,Luogu,rid,id
From： https://www.cnblogs.com/zhangxyhp/p/18683588