loj2028 「SHOI2016」随机序列

定义区间是内部只含有乘号的区间。

对于区间左端点是 \(l \geq 2\) 的情况，左端点前头是加号的情况和前头是减号的情况的个数是相同的。因此这些区间不对答案产生贡献。

所以区间左端点必定是 \(1\)。当 \(r=n\) 时，这个区间产生一次贡献。当 \(r < n\) 时，这个区间产生 \(2 \times 3^{n-r-1}\) 次贡献。

掏出一棵支持区间乘，整体求和的线段树。

#include <iostream>

#include <cassert>

#include <cstdio>

using namespace std;

typedef long long ll;

int n, m, a[100005], mi3[100005], v[100005], uu, vv;

const int mod=1e9+7;

int ksm(int a, int b){

	int re=1;

	while(b){

		if(b&1)	re = (ll)re * a % mod;

		a = (ll)a * a % mod;

		b >>= 1;

	}

	return re;

}

struct SGT{

	int sum[400005], tag[400005];

	void pushUp(int o, int lson, int rson){

		sum[o] = (sum[lson] + sum[rson]) % mod;

	}

	void build(int o, int l, int r){

		tag[o] = 1;

		if(l==r)	sum[o] = v[l];

		else{

			int mid=(l+r)>>1;

			int lson=o<<1;

			int rson=lson|1;

			if(l<=mid)	build(lson, l, mid);

			if(mid<r)	build(rson, mid+1, r);

			pushUp(o, lson, rson);

		}

	}

	void pushDown(int o, int l, int r, int lson, int rson, int mid){

		sum[lson] = (ll)sum[lson] * tag[o] % mod;

		sum[rson] = (ll)sum[rson] * tag[o] % mod;

		tag[lson] = (ll)tag[lson] * tag[o] % mod;

		tag[rson] = (ll)tag[rson] * tag[o] % mod;

		tag[o] = 1;

	}

	void update(int o, int l, int r, int x, int y, int k){

		if(l>=x && r<=y){

			sum[o] = (ll)sum[o] * k % mod;

			tag[o] = (ll)tag[o] * k % mod;

		}

		else{

			int mid=(l+r)>>1;

			int lson=o<<1;

			int rson=lson|1;

			if(tag[o]!=1)	pushDown(o, l, r, lson, rson, mid);

			if(x<=mid)	update(lson, l, mid, x, y, k);

			if(mid<y)	update(rson, mid+1, r, x, y, k);

			pushUp(o, lson, rson);

		}

	}

}sgt;

int main(){

	cin>>n>>m;

	mi3[0] = v[n] = 1;

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

		scanf("%d", &a[i]);

		mi3[i] = (ll)mi3[i-1] * 3 % mod;

	}

	int lia=1;

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

		lia = (ll)lia * a[i] % mod;

		v[i] = (ll)lia * 2 * mi3[n-i-1] % mod;

	}

	lia = (ll)lia * a[n] % mod;

	v[n] = lia;

	sgt.build(1, 1, n);

	while(m--){

		scanf("%d %d", &uu, &vv);

		sgt.update(1, 1, n, uu, n, ksm(a[uu],mod-2));

		a[uu] = vv;

		sgt.update(1, 1, n, uu, n, a[uu]);

		printf("%d\n", sgt.sum[1]);

	}

	return 0;

}

巴特西

loj2028 「SHOI2016」随机序列

最新文章

热门文章