HDU 5239 Doom 线段树

题意：

有\(n(1 \leq n \leq 10^5)\)个数，和\(m(1 \leq m \leq 10^5)\)操作，和一个计算\(s\)，一切运算都在模\(MOD\)进行的。

操作\(l, \, m\)表示先将区间\([l, r]\)的数字之和累加到\(s\)上，然后将区间的每个数平方。

输出每次操作后的\(s\)。

分析：

虽然原理不是特别懂，但是有这样一个事实：

任意一个数\(x\)平方超过\(30\)次之后再平方就不会变了。

所以我们维护区间和的同时，再维护一个区间平方次数的最小值。

如果这个区间都平方不少于\(30\)次，那么就不用更新了，因为整个区间的数都不会变。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef unsigned long long LL;

const LL MOD = 9223372034707292160ULL;

LL add(LL a, LL b) { a += b; if(a >= MOD) a -= MOD; return a; }

LL mul(LL a, LL b) {

	LL ans = 0;

	while(b) {

		if(b & 1) ans = add(ans, a);

		a = add(a, a);

		b >>= 1;

	}

	return ans;

}

const int maxn = 100000 + 10;

const int maxnode = maxn * 4;

int n, m;

LL sumv[maxnode], mcnt[maxnode], s;

void build(int o, int L, int R) {

	if(L == R) {

		scanf("%llu", &sumv[o]);

		mcnt[o] = 0;

		return;

	}

	int M = (L + R) / 2;

	build(o<<1, L, M);

	build(o<<1|1, M+1, R);

	sumv[o] = add(sumv[o<<1], sumv[o<<1|1]);

	mcnt[o] = 0;

}

void query(int o, int L, int R, int qL, int qR) {

	if(qL <= L && R <= qR) {

		s = add(s, sumv[o]);

		return;

	}

	int M = (L + R) / 2;

	if(qL <= M) query(o<<1, L, M, qL, qR);

	if(qR > M) query(o<<1|1, M+1, R, qL, qR);

}

void update(int o, int L, int R, int qL, int qR) {

	if(mcnt[o] >= 30) return;

	if(L == R) {

		sumv[o] = mul(sumv[o], sumv[o]);

		mcnt[o]++;

		return;

	}

	int M = (L + R) / 2;

	if(qL <= M) update(o<<1, L, M, qL, qR);

	if(qR > M) update(o<<1|1, M+1, R, qL, qR);

	sumv[o] = add(sumv[o<<1], sumv[o<<1|1]);

	mcnt[o] = min(mcnt[o<<1], mcnt[o<<1|1]);

}

int main()

{

	int T; scanf("%d", &T);

	for(int kase = 1; kase <= T; kase++) {

		printf("Case #%d:\n", kase);

		scanf("%d%d", &n, &m);

		build(1, 1, n);

		s = 0;

		while(m--) {

			int qL, qR; scanf("%d%d", &qL, &qR);

			query(1, 1, n, qL, qR);

			update(1, 1, n, qL, qR);

			printf("%llu\n", s);

		}

	}

	return 0;

}

巴特西

HDU 5239 Doom 线段树

题意：

分析：

最新文章

热门文章