hdu Naive Operations 线段树

题目大意

题目链接Naive Operations

题目大意:

    区间加1(在a数组中)

   区间求ai/bi的和

   ai初值全部为0，bi给出，且为n的排列，多组数据(<=5),n,q<=1e5

axmorz

思路

因为是整除，所以一次加法可以对ans 没有影响

当ai是bi的倍数，对ans会有贡献

所以我们维护一个sum，初值为bi(只对于线段树的叶子节点有用)

当区间+1的时候

我们对sum-1

当sum=0的时候（倍数）

ans++，sum=bi

然后再维护一个区间最小值

当区间内的mi>0时

显然、对答案没有贡献

当区间内的mi<=0时

对答案一定有贡献

所以再在l到r内进行递归

对于g()函数的复杂度为

ans=n/1+n/2+n/3+n/4````+n/n=nlogn级别（看的别的题解护臂逼的）

代码

#include <iostream>

#include <cstring>

#include <cstdio>

#define ls rt<<1

#define rs rt<<1|1

using namespace std;

const int maxn = 1e5 + 7;

const int maxm = 4e5 + 7;

const int inf = 0x3f3f3f3f;

int n, m, b[maxn];

struct node {

	int l, r;

	int ans, sum, mi, lazy;

} e[maxm];

int read() {

	int x = 0, f = 1; char s = getchar();

	for (; s < '0' || s > '9'; s = getchar()) if (s == '-') f = -1;

	for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';

	return x * f;

}

void pushup(int rt) {

	e[rt].ans = e[ls].ans + e[rs].ans;

	e[rt].mi = min(e[ls].mi, e[rs].mi);

}

void pushdown(int rt) {

	if (e[rt].lazy) {

		e[ls].lazy += e[rt].lazy;

		e[rs].lazy += e[rt].lazy;

		e[ls].mi -= e[rt].lazy;

		e[rs].mi -= e[rt].lazy;

		e[rt].lazy = 0;

	}

}

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

	e[rt].l = l, e[rt].r = r;

	if (l == r) {

		e[rt].sum = e[rt].mi = b[l];

		return;

	}

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

	build(l, mid, ls);

	build(mid + 1, r, rs);

	pushup(rt);

}

void g(int L, int R, int rt) {

	if (e[rt].mi > 0) {

		return ;

	} else {

		if (e[rt].l == e[rt].r) {

			e[rt].ans++;

			e[rt].mi = e[rt].sum = b[e[rt].l];

			return ;

		}

	}

	pushdown(rt);

	if (e[ls].mi <= 0) g(L, R, ls);

	if (e[rs].mi <= 0) g(L, R, rs);

	pushup(rt);

}

void add(int L, int R, int rt) {

	if (L <= e[rt].l && e[rt].r <= R) {

		e[rt].mi--;

		e[rt].lazy++;

		g(e[rt].l, e[rt].r, rt);

		//cout<<e[rt].l<<" "<<e[rt].r<<" "<<e[rt].mi<<"<M<<<<<\n";

		return;

	}

	pushdown(rt);

	int mid = (e[rt].l + e[rt].r) >> 1;

	if (L <= mid) add(L, R, ls);

	if (R > mid) add(L, R, rs);

	pushup(rt);

}

void debug() {

	printf("debug\n");

	printf("               %d\n", e[1].mi);

	printf("       %d               %d\n", e[2].mi, e[3].mi );

	printf("   %d       %d       %d       %d\n", e[4].mi, e[5].mi, e[6].mi, e[7].mi );

	printf(" %d   %d   %d   %d   %d   %d   %d   %d\n", e[8].mi,

	 e[9].mi, e[10].mi, e[11].mi, e[12].mi, e[13].mi, e[14].mi, e[15].mi);

}

int query(int L, int R, int rt) {

	if (L <= e[rt].l && e[rt].r <= R) {

		return e[rt].ans;

	}

	pushdown(rt);

	int mid = (e[rt].l + e[rt].r) >> 1, ans = 0;

	if (L <= mid) ans += query(L, R, ls);

	if (R > mid) ans += query(L, R, rs);

	pushup(rt);

	return ans;

}

int main() {

	while(scanf("%d%d",&n,&m)!=EOF) {

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

		b[i] = read();

		memset(e,0,sizeof(e));

		build(1, n, 1);

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

			char s[10];

			scanf("%s", s);

			int a = read(), b = read();

			if (s[0] == 'a') {

				add(a, b, 1);

			} else {

				printf("%d\n", query(a, b, 1));

			}

		}

	}

	return 0;

}

巴特西

hdu Naive Operations 线段树

题目大意

题目链接Naive Operations

题目大意:

思路

因为是整除，所以一次加法可以对ans 没有影响

当ai是bi的倍数，对ans会有贡献

所以我们维护一个sum，初值为bi(只对于线段树的叶子节点有用)

当区间+1的时候

我们对sum-1

当sum=0的时候（倍数）

ans++，sum=bi

然后再维护一个区间最小值

当区间内的mi>0时

显然、对答案没有贡献

当区间内的mi<=0时

对答案一定有贡献

所以再在l到r内进行递归

对于g()函数的复杂度为

ans=n/1+n/2+n/3+n/4````+n/n=nlogn级别（看的别的题解护臂逼的）

代码

最新文章

热门文章