【loj6029】「雅礼集训 2017 Day1」市场线段树+均摊分析

题目描述

给出一个长度为 $n$ 的序列，支持 $m$ 次操作，操作有四种：区间加、区间下取整除、区间求最小值、区间求和。

$n\le 100000$ ，每次加的数在 $[-10^4,10^4]$ 之间，每次除的数在 $[2,10^9]$ 之间。

题解

线段树+均摊分析

和【uoj#228】基础数据结构练习题类似的均摊分析题。

对于原来的两个数 $a$ 和 $b$ ( $a>b$ ) ，原来的差是 $a-b$ ，都除以 $d$ 后的差是 $\frac{a-b}d$ ，相当于差也除了 $d$ 。

而当区间差为 $0$ 或 $a=kd,b=kd-1$ 的 $1$ 时，区间下取整除就变成了区间减。

因此当一个区间下取整除了 $\log(Max-Min)$ 次后就不需要暴力下取整除，直接区间减即可。

定义线段树节点势能为 $\log(Max-Min)$ ，那么每次对 $[l,r]$ 下取整除就是将所有 $l\le x,y\le r$ ，且势能不为 $0$ 的节点 $[x,y]$ 的势能减 $1$ ，代价为势能减少总量。

分析区间加操作：只会修改到经过的节点的势能，影响 $\log$ 个节点，将这些点的势能恢复为 $\log(Max-Min)$ 。

因此总的时间复杂度就是总势能量 $O((n+m\log n)\log a)$ 。

注意C++中的 '/' 并不是下取整，而是向0取整，因此需要按正负分类讨论手写下取整。

#include <cstdio>

#include <algorithm>

#define N 400010

#define lson l , mid , x << 1

#define rson mid + 1 , r , x << 1 | 1

using namespace std;

typedef long long ll;

ll sum[N] , mx[N] , mn[N] , add[N];

inline ll fdiv(ll x , ll y)

{

	return x > 0 ? x / y : (x - y + 1) / y;

}

inline void pushup(int x)

{

	sum[x] = sum[x << 1] + sum[x << 1 | 1];

	mx[x] = max(mx[x << 1] , mx[x << 1 | 1]);

	mn[x] = min(mn[x << 1] , mn[x << 1 | 1]);

}

inline void pushdown(int l , int r , int x)

{

	if(add[x])

	{

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

		sum[x << 1] += add[x] * (mid - l + 1) , sum[x << 1 | 1] += add[x] * (r - mid);

		mx[x << 1] += add[x] , mx[x << 1 | 1] += add[x];

		mn[x << 1] += add[x] , mn[x << 1 | 1] += add[x];

		add[x << 1] += add[x] , add[x << 1 | 1] += add[x];

		add[x] = 0;

	}

}

void build(int l , int r , int x)

{

	if(l == r)

	{

		scanf("%lld" , &sum[x]) , mx[x] = mn[x] = sum[x];

		return;

	}

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

	build(lson) , build(rson);

	pushup(x);

}

void vadd(int b , int e , ll a , int l , int r , int x)

{

	if(b <= l && r <= e)

	{

		sum[x] += a * (r - l + 1) , mx[x] += a , mn[x] += a , add[x] += a;

		return;

	}

	pushdown(l , r , x);

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

	if(b <= mid) vadd(b , e , a , lson);

	if(e > mid) vadd(b , e , a , rson);

	pushup(x);

}

void vdiv(int b , int e , ll d , int l , int r , int x)

{

	if(b <= l && r <= e && mx[x] - fdiv(mx[x] , d) == mn[x] - fdiv(mn[x] , d))

	{

		ll a = mx[x] - fdiv(mx[x] , d);

		sum[x] -= a * (r - l + 1) , mx[x] -= a , mn[x] -= a , add[x] -= a;

		return;

	}

	pushdown(l , r , x);

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

	if(b <= mid) vdiv(b , e , d , lson);

	if(e > mid) vdiv(b , e , d , rson);

	pushup(x);

}

ll qmin(int b , int e , int l , int r , int x)

{

	if(b <= l && r <= e) return mn[x];

	pushdown(l , r , x);

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

	ll ans = 1ll << 62;

	if(b <= mid) ans = min(ans , qmin(b , e , lson));

	if(e > mid) ans = min(ans , qmin(b , e , rson));

	return ans;

}

ll qsum(int b , int e , int l , int r , int x)

{

	if(b <= l && r <= e) return sum[x];

	pushdown(l , r , x);

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

	ll ans = 0;

	if(b <= mid) ans += qsum(b , e , lson);

	if(e > mid) ans += qsum(b , e , rson);

	return ans;

}

int main()

{

	int n , m , opt , x , y;

	ll z;

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

	build(1 , n , 1);

	while(m -- )

	{

		scanf("%d%d%d" , &opt , &x , &y) , x ++ , y ++ ;

		if(opt == 1) scanf("%lld" , &z) , vadd(x , y , z , 1 , n , 1);

		if(opt == 2) scanf("%lld" , &z) , vdiv(x , y , z , 1 , n , 1);

		if(opt == 3) printf("%lld\n" , qmin(x , y , 1 , n , 1));

		if(opt == 4) printf("%lld\n" , qsum(x , y , 1 , n , 1));

	}

	return 0;

}

巴特西

【loj6029】「雅礼集训 2017 Day1」市场线段树+均摊分析

最新文章

热门文章

巴特西

【loj6029】「雅礼集训 2017 Day1」市场 线段树+均摊分析

最新文章

热门文章

【loj6029】「雅礼集训 2017 Day1」市场线段树+均摊分析