题面

从前有一个学校，在

\rm OneInDark

OneInDark 到任之前风气都是非常良好的，自从他来了之后，发布了一系列奇怪的要求，挟制了整个学校，导致风气的衰落。

有

n 个班级，从

∼

−

0\sim n-1

0∼n−1 编号，每个班级的学生人数上限是

a_i

ai。有两种要求；同时，校长助理别里手魔

HandInDevil

HandInDevil 想要了解实时的信息，有两种询问方式：

（要求）

l

,

r

,

c

l,r,c

l,r,c，对于

i

∈

[

l

,

r

]

,

a

i

←

a

i

+

c

i\in[l,r],a_i\leftarrow a_i+c

i∈[l,r],ai←ai+c
（要求）
l

,

r

,

d

l,r,d

l,r,d，对于

i

∈

[

l

,

r

]

,

a

i

←

⌊

a

i

d

⌋

i\in[l,r],a_i\leftarrow \left\lfloor\frac{a_i}{d}\right\rfloor

i∈[l,r],ai←⌊dai⌋
（询问）给定
l

,

r

l,r

l,r，求

min

⁡

i

∈

[

l

,

r

]

a

i

\min_{i\in[l,r]}a_i

mini∈[l,r]ai
（询问）给定
l

,

r

l,r

l,r，求

∑

i

∈

[

l

,

r

]

a

i

\sum_{i\in[l,r]}a_i

∑i∈[l,r]ai

输入格式

第一行为两个空格隔开的整数

n,q

n,q 分别表示班级个数和要求 + 询问个数。
第二行包含

n 个由空格隔开的整数

∼

−

a_0\sim a_{n-1}

a0∼an−1
接下来

q 行，每行表示一个操作，第一个数表示操作编号

∼

1\sim4

1∼4，接下来的输入和问题描述一致。

输出格式

对于每个

3,4

3,4 操作，输出询问答案。

数据范围与提示

对于

100

100\%

100% 的数据，

≤

−

∈

[

−

]

∈

[

]

1\leq n,q\leq 10^5,0\leq l\leq r\leq n-1,c\in[-10^4,10^4],d\in[2,10^9]

1≤n,q≤105,0≤l≤r≤n−1,c∈[−104,104],d∈[2,109]

题解

是一道运用运算规律的题。

操作有区间加区间除，要维护区间和以及区间最小值。最难办的是区间除。

我们会发现，两个数同时除以大于 1 的数，他们的差会在大约

log

⁡

\log

log 次运算后

≤

\leq 1

≤1。因为下取整的原因，变为零很难做到，但是变为 1 可以很快。

如果一个区间最大值和最小值的差大于 1，那么就暴力递归下去，递归直到单点进行区间除，或者递归遇到一个极差小于等于 1 的区间时，进行下一步操作：

如果极差为 0 ，那么就是一个区间赋值了。
如果极差为 1，分情况讨论：若最大值和最小值除后下取整相等，那也是区间赋值，否则一定是最大值仍比最小值大 1 ，变化量相等，相当于区间加减。

我们在线段树上用

ax+b

ax+b 的形式表示懒标记，可以同时解决区间赋值和区间加减。

时间复杂度

(

log

⁡

)

\rm O(n\log^{_2}n)

O(nlog2n) 。可以感性理解复杂度，也可以势能分析。

CODE

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<ctime>

#include<queue>

#include<bitset>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 100005

#define LL long long

#define DB double

#define ENDL putchar('\n')

#define lowbit(x) (-(x) & (x))

#define FI first

#define SE second

#define eps (1e-4)

#define BI bitset<MAXN>

LL read() {

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

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

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

	return f*x;

}

void putpos(LL x) {

	if(!x) return ;

	putpos(x/10); putchar('0'+(x%10));

}

void putnum(LL x) {

	if(!x) putchar('0');

	else if(x < 0) putchar('-'),putpos(-x);

	else putpos(x);

}

inline void AIput(LL x,char c) {

	putnum(x); putchar(c);

}

int n,m,s,o,k;

int A[MAXN];

struct it{

	LL s,lza,lzb,le;

	LL ma,mi;

	it(){s=le=0;lza=1;lzb=0;ma=mi=0;}

	it(LL nm) {

		s=ma=mi=nm; lza=1;lzb=0; le=1;

	}

}tre[MAXN<<2];

void update(int a) {

	int ls = a<<1,rs = a<<1|1;

	tre[a].s = tre[ls].s + tre[rs].s;

	tre[a].ma = max(tre[ls].ma,tre[rs].ma);

	tre[a].mi = min(tre[ls].mi,tre[rs].mi);

	tre[a].le = tre[ls].le + tre[rs].le;

	return ;

}

void maketree(int a,int l,int r) {

	tre[a] = it();

	if(l == r) {

		tre[a].s = A[l]; tre[a].le = 1;

		tre[a].ma = tre[a].mi = A[l];

		return ;

	}

	else {

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

		maketree(a<<1,l,mid); maketree(a<<1|1,mid+1,r);

		update(a);

	}return ;

}

void adda(int a,LL m,LL k) {

	tre[a].s *= m;

	tre[a].s += k*1ll*tre[a].le;

	tre[a].ma *= m; tre[a].mi *= m;

	tre[a].ma += k; tre[a].mi += k;

	tre[a].lza *= m; tre[a].lzb *= m;

	tre[a].lzb += k; return ;

}

void seta(int a,LL k) {

	tre[a].s = k*1ll*tre[a].le;

	tre[a].ma = tre[a].mi = k;

	tre[a].lza = 0; tre[a].lzb = k; return ;

}

void sdiva(int a,LL k) {

	LL Mx = tre[a].ma,Mi = tre[a].mi;

	if(Mx > Mi+1) return ;

	if(floor((DB)Mx/k) == floor((DB)Mi/k)) {

		seta(a,floor((DB)Mx/k));

	}

	else {

		LL mut = Mx - floor((DB)Mx/k);

		adda(a,1,-mut);

	}return ;

}

void pushdown(int a) {

	if(tre[a].lza != 1 || tre[a].lzb != 0) {

		adda(a<<1,tre[a].lza,tre[a].lzb);

		adda(a<<1|1,tre[a].lza,tre[a].lzb);

		tre[a].lza = 1; tre[a].lzb = 0;

	}return ;

}

void addtree(int a,int l,int r,int al,int ar,LL c) {

	if(l > r || al > r || ar < l) return ;

	if(al >= l && ar <= r) {

		adda(a,1,c); return ;

	}

	int mid = (al + ar) >> 1;

	pushdown(a);

	addtree(a<<1,l,r,al,mid,c);addtree(a<<1|1,l,r,mid+1,ar,c);

	update(a); return ;

}

void divtree(int a,int l,int r,int al,int ar,LL d) {

	if(l > r || al > r || ar < l) return ;

	if(al >= l && ar <= r && tre[a].ma <= tre[a].mi+1) {

		sdiva(a,d); return ;

	}

	if(al == ar) {

		tre[a] = it(floor((DB)tre[a].s/d)); return ;

	}

	int mid = (al + ar) >> 1;

	pushdown(a);

	divtree(a<<1,l,r,al,mid,d); divtree(a<<1|1,l,r,mid+1,ar,d);

	update(a); return ;

}

LL mintree(int a,int l,int r,int al,int ar) {

	if(l > r || al > r || ar < l) return (LL)1e18;

	if(al >= l && ar <= r) return tre[a].mi;

	int mid = (al + ar) >> 1;pushdown(a);

	return min(mintree(a<<1,l,r,al,mid),mintree(a<<1|1,l,r,mid+1,ar));

}

LL sumtree(int a,int l,int r,int al,int ar) {

	if(l > r || al > r || ar < l) return 0;

	if(al >= l && ar <= r) return tre[a].s;

	int mid = (al + ar) >> 1;pushdown(a);

	return sumtree(a<<1,l,r,al,mid) + sumtree(a<<1|1,l,r,mid+1,ar);

}

int main() {

	n = read();m = read();

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

		A[i] = read();

	}

	maketree(1,1,n);

	while(m --) {

		k = read();

		s = read()+1;o = read()+1;

		if(k == 1) {

			k = read();

			addtree(1,s,o,1,n,k);

		}

		else if(k == 2) {

			k = read();

			divtree(1,s,o,1,n,k);

		}

		else if(k == 3) {

			AIput(mintree(1,s,o,1,n),'\n');

		}

		else AIput(sumtree(1,s,o,1,n),'\n');

	}

	return 0;

}

巴特西

LOJ6029「雅礼集训 2017 Day1」市场（线段树）

题面

输入格式

输出格式

数据范围与提示

题解

CODE

最新文章

热门文章

巴特西

LOJ6029「雅礼集训 2017 Day1」市场 （线段树）

题面

输入格式

输出格式

数据范围与提示

题解

CODE

最新文章

热门文章

LOJ6029「雅礼集训 2017 Day1」市场（线段树）