Hihocoder 1116 计算

这题最开始的时候看到线段树吧,没找到好的做法

想了下既然是乘积和

(-)

(--)

(---)

在脑子里就是这种线条位于各个位置，然后各种长度代表连续的乘积个数

然后把所有情况累加起来，但是并不好算

这题每次单点修改最开始就想到肯定是算贡献

然后总和是所有连续积和

然后就想是不是能用到前缀积呢，然后发现修改a[p] ai...ap...aj 1<=i<=p && n=>j>=p

(--ap---)

(-ap--)

然后分配律化简下，就是ap的后缀积和ap右边一位的前缀积和，这就是贡献

但是我直接把先算树的节点用前缀积表示pre[p]表示到p的前缀积，然后修改a[p]的时候就是修改p到n记录之前值改为现在的，就相当于a[p]/a[p]，a[p]是以前的

但是不好处理为0的情况以前为0.就。。。后面看了别人的发现可以算总和，前后缀积也可以分区间分节点向上推倒

#include <cstdio>

#include <memory>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <vector>

#include <cassert>

#include <string>

#include <ctime>

#include <map>

#include <queue>

#include <algorithm>

#include <iostream>

#include <cassert>

using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define req(i,a,b) for(int i=a;i>=b;i--)

#define rp(i,a) for(int i=head[a];i+1;i=edge[i].next)

#define cl(a,b) memset(a,b,sizeof a);

#define ll long long

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define mod 10007

const int inf = ~0u >> 2;

const ll INF = (1LL << 62) - 1;

double eps = 1e-9;

const int N = 1e6 + 5;

const int M = 21;

int ans, cnt;

vector<int>g[N];

int n, m;

int in[N];

map<string, int>mp;

string S[N];

int pre[N];

int suf[N];

int sum[N];

int mul[N];

void up(int rt) {

	mul[rt] = (mul[rt << 1] * mul[rt << 1 | 1]) % mod;

	pre[rt] = (pre[rt << 1] + pre[rt << 1 | 1 ] * mul[rt << 1]) % mod;

	suf[rt] = (suf[rt << 1 | 1] + suf[rt << 1] * mul[rt << 1 | 1]) % mod;

	sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1] + suf[rt << 1] * pre[rt << 1 | 1]) % mod;

}

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

	mul[rt] = pre[rt] = suf[rt] = sum[rt] = 0;

	if (l == r) {

		//scanf("%d", &c[rt]);

		return;

	}

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

	build(l, m, rt * 2);

	build(m + 1, r, rt * 2 + 1);

	up(rt);

}

void update(int p, int value, int l, int r, int rt) {

	if (l == r) {

		if (l != p)

			return;

		pre[rt] = value%mod+mod;

		suf[rt] = value%mod+mod;

		sum[rt] = value%mod+mod;

		mul[rt] = value%mod+mod;

		return;

	}

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

	if (p <= m)

		update(p, value, lson);

	if (m < p)

		update(p, value, rson);

	up(rt);

}

int main() {

	while (~scanf("%d%d", &n, &m)) {

		build(1, n, 1);

		ans = 0;

		while (m--) {

			int op, l, r;

			int p, val;

			scanf("%d%d", &p, &val);

			update(p, val, 1, n, 1);

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

		}

	}

	return 0;

}

巴特西

Hihocoder 1116 计算

最新文章

热门文章