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

[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,qle 1 imes 10^5, |c|le1 imes 10^4,din[2,1 imes 10^9]), 时限 (2 exttt{s}).

题解

玄学线段树.

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

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

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

参考代码

#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->QueryMin(l,r));
		else if(t==4)
			printf("%lld
",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;
}