[LOJ 6029]「雅礼集训 2017 Day1」市场

rvalue 收录于 cnblogs 题解

2019-03-26 约 812 字预计阅读 2 分钟

迁移提示

本文迁移自博客园, 原文链接

[LOJ 6029] 「雅礼集训 2017 Day1」市场

题意

给定一个长度为 $n$ 的数列(从 $0$ 开始标号), 要求执行 $q$ 次操作, 每次操作为如下四种操作之一:

1 l r c 给 $[l,r]$ 区间内的值全部加上 $c$.
2 l r d 给 $[l,r]$ 区间内的值全部除以 $d$, 向下取整.
3 l r 求 $[l,r]$ 区间内的最小值.
4 l r 求 $[l,r]$ 区间内的值之和.

$n,q\le 1\times 10^5, |c|\le1\times 10^4,d\in[2,1\times 10^9]$, 时限 $2\texttt{s}$.

题解

玄学线段树.

首先看到题目容易想到一个数最多除 $\log $ 次就会变成 $0/1$. 但是区间加法操作让这个势能分析假掉了. (单点加法是滋磁的)

注意到在除法操作中每除一次就会导致区间内的数的浮动量 (即 $\max - \min$) 至少减半. 而加法操作虽然是区间操作, 但是对浮动量造成的变化只有常数个位置(两端). 而相近的一坨数整体除法可以看作是进行了一次区间加法操作.

又因为当 $x$ 递增的时候 $\left \lfloor \frac x d \right \rfloor$ 单调不降, 于是只要 $\left \lfloor \frac \max d \right \rfloor - \max=\left \lfloor \frac \min d \right \rfloor -\min$, 那么整个区间产生的差值都是一样的, 都可以用一次区间加法操作代替. 而一次区间加法是 $O(\log n)$ 的, 于是总复杂度是 $O(q\log n\log V)$.

参考代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166


#include <bits/stdc++.h>

const int MAXN=1e5+10;
typedef long long intEx;

struct Node{
	int l;
	int r;
	int max;
	int min;
	int add;
	intEx sum;
	Node* lch;
	Node* rch;
	Node(int,int);
	void Add(int);
	void PushDown();
	void Maintain();
	void Add(int,int,int);
	void Div(int,int,int);
	int QueryMin(int,int);
	intEx QuerySum(int,int);
};

int n;
int q;
int a[MAXN];

int ReadInt();
inline int FDiv(int,int);

int main(){
	n=ReadInt(),q=ReadInt();
	for(int i=0;i<n;i++)
		a[i]=ReadInt();
	Node* N=new Node(0,n-1);
	for(int i=0;i<q;i++){
		int t=ReadInt(),l=ReadInt(),r=ReadInt();
		if(t==1){
			int d=ReadInt();
			N->Add(l,r,d);
		}
		else if(t==2){
			int d=ReadInt();
			N->Div(l,r,d);
		}
		else if(t==3)
			printf("%d\n",N->QueryMin(l,r));
		else if(t==4)
			printf("%lld\n",N->QuerySum(l,r));
	}
	return 0;
}

intEx Node::QuerySum(int l,int r){
	if(l<=this->l&&this->r<=r)
		return this->sum;
	else{
		this->PushDown();
		if(r<=this->lch->r)
			return this->lch->QuerySum(l,r);
		if(this->rch->l<=l)
			return this->rch->QuerySum(l,r);
		return this->lch->QuerySum(l,r)+this->rch->QuerySum(l,r);
	}
}

int Node::QueryMin(int l,int r){
	if(l<=this->l&&this->r<=r)
		return this->min;
	else{
		this->PushDown();
		if(r<=this->lch->r)
			return this->lch->QueryMin(l,r);
		if(this->rch->l<=l)
			return this->rch->QueryMin(l,r);
		return std::min(this->lch->QueryMin(l,r),this->rch->QueryMin(l,r));
	}
}

void Node::Add(int l,int r,int d){
	if(l<=this->l&&this->r<=r)
		this->Add(d);
	else{
		this->PushDown();
		if(l<=this->lch->r)
			this->lch->Add(l,r,d);
		if(this->rch->l<=r)
			this->rch->Add(l,r,d);
		this->Maintain();
	}
}

void Node::Div(int l,int r,int d){
	if(l<=this->l&&this->r<=r){
		if(this->max-FDiv(this->max,d)==this->min-FDiv(this->min,d))
			this->Add(FDiv(this->max,d)-this->max);
		else{
			this->PushDown();
			this->lch->Div(l,r,d);
			this->rch->Div(l,r,d);
			this->Maintain();
		}
	}
	else{
		this->PushDown();
		if(l<=this->lch->r)
			this->lch->Div(l,r,d);
		if(this->rch->l<=r)
			this->rch->Div(l,r,d);
		this->Maintain();
	}
}

inline void Node::Add(int d){
	this->max+=d;
	this->min+=d;
	this->add+=d;
	this->sum+=1ll*(this->r-this->l+1)*d;
}

inline void Node::Maintain(){
	this->sum=this->lch->sum+this->rch->sum;
	this->max=std::max(this->lch->max,this->rch->max);
	this->min=std::min(this->lch->min,this->rch->min);
}

inline void Node::PushDown(){
	if(this->add!=0){
		this->lch->Add(this->add);
		this->rch->Add(this->add);
		this->add=0;
	}
}

Node::Node(int l,int r):l(l),r(r),max(a[l]),min(a[r]),add(0),sum(a[l]),lch(NULL),rch(NULL){
	if(l!=r){
		int mid=(l+r)>>1;
		this->lch=new Node(l,mid);
		this->rch=new Node(mid+1,r);
		this->Maintain();
	}
}

inline int ReadInt(){
	int x=0,sgn=1;
	register char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')
			sgn=-sgn;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*sgn;
}

inline int FDiv(int x,int d){
	if(x>=0)
		return x/d;
	else
		return (x-d+1)/d;
}

目录

[LOJ 6029]「雅礼集训 2017 Day1」市场

[LOJ 6029] 「雅礼集训 2017 Day1」市场

题意

题解

参考代码