题目链接

U161009 [雅礼集训 2017 Day1] 市场

题目背景

从前有一个贸易市场，在一位执政官到来之前都是非常繁荣的，自从他来了之后，发布了一系列奇怪的政令，导致贸易市场的衰落。

题目描述

有 \(n\) 个商贩，从 \(0\) ~ \(n – 1\) 编号，每个商贩的商品有一个价格 \(a_i\)，有两种政令；同时，有一个外乡的旅客想要了解贸易市场的信息，有两种询问方式：

1. （政令）\(l,r,c\)，对于 \(i \in [l,r]\)，\(a_i \gets a_i + c\)
2. （政令）\(l,r,d\)，对于 \(i \in [l,r]\)，\(a_i \gets \left\lceil\dfrac{a_i}{d}\right\rceil\)
3. （询问）给定 \(l,r\)，求 \(\min\limits_{i \in [l,r]} a_i\)
4. （询问）给定 \(l,r\)，求 \(\sum\limits_{i \in [l,r]} a_i\)

输入格式

第一行为两个空格隔开的整数 \(n,q\)，分别表示商贩个数和政令和询问个数。

第二行包含 \(n\) 个由空格隔开的整数 \(a_0,a_1,…,a_{n-1}\)

接下来 \(q\) 行，每行表示一个操作，第一个数表示操作编号 \(1\) ~ \(4\)，接下来的输入和问题描述一致。

输出格式

对于每个 \(3\)、\(4\) 操作，输出询问答案。

样例 #1

样例输入 #1

10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9

样例输出 #1

-2
-2
-2
-2
0
1
1

提示

【数据范围】

对于 \(30\%\) 的数据，\(n,q \le 10^3\)；

对于 \(60\%\) 的数据，保证数据随机；

对于 \(100\%\) 的数据，\(1 \le n,q \le 10^5\)，\(0 \le l \le r \le n – 1\)，\(c \in [-10^4,10^4]\)，\(d \in [2,10^9]\)。

解题思路

势能线段树

同 势能线段树模板题二，由于 \(n-\left\lceil\dfrac{n}{d}\right\rceil\) 是一个增函数，记录线段树每个区间节点的最大值 \(mx\) 和最小值 \(mn\)，如果 \(mx-\left\lceil\dfrac{mx}{d}\right\rceil=mn-\left\lceil\dfrac{mn}{d}\right\rceil\)，说明该区间中每个数的值变化相等，对该区间节点打上懒标记，其他节点暴力递归即可

• 时间复杂度：\(O(mlog^2n)\)

代码

// Problem: U161009 [雅礼集训 2017 Day1] 市场
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/U161009
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e5+5,inf=0x3f3f3f3f;
int n,m,a[N];
struct Tr
{
	int l,r,add;
	LL sum,mx,mn;
}tr[N<<2];
void pushup(int p)
{
	tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
	tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);
	tr[p].mn=min(tr[p<<1].mn,tr[p<<1|1].mn);
}
void pushdown(int p)
{
	if(tr[p].add)
	{
		tr[p<<1].sum+=1ll*tr[p].add*(tr[p<<1].r-tr[p<<1].l+1);
		tr[p<<1|1].sum+=1ll*tr[p].add*(tr[p<<1|1].r-tr[p<<1|1].l+1);
		tr[p<<1].mx+=tr[p].add,tr[p<<1|1].mx+=tr[p].add;
		tr[p<<1].mn+=tr[p].add,tr[p<<1|1].mn+=tr[p].add;
		tr[p<<1].add+=tr[p].add,tr[p<<1|1].add+=tr[p].add;
		tr[p].add=0;
	}
}
void build(int p,int l,int r)
{
	tr[p]={l,r};
	if(l==r)
	{
		tr[p].sum=tr[p].mx=tr[p].mn=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	pushup(p);
}
void add(int p,int l,int r,int x)
{
	if(l<=tr[p].l&&tr[p].r<=r)
	{
		tr[p].sum+=x*(tr[p].r-tr[p].l+1);
		tr[p].mx+=x,tr[p].mn+=x;
		tr[p].add+=x;
		return ;
	}
	pushdown(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(l<=mid)add(p<<1,l,r,x);
	if(r>mid)add(p<<1|1,l,r,x);
	pushup(p);
}
void divide(int p,int l,int r,int d)
{
	if(l<=tr[p].l&&tr[p].r<=r)
	{
		int dmx=tr[p].mx-(int)floor((double)tr[p].mx/d);
		int dmn=tr[p].mn-(int)floor((double)tr[p].mn/d);
		if(dmx==dmn)
		{
			tr[p].sum-=1ll*dmx*(tr[p].r-tr[p].l+1);
			tr[p].mx-=dmx,tr[p].mn-=dmn;
			tr[p].add-=dmx;
			return ;
		}
	}
	pushdown(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(l<=mid)divide(p<<1,l,r,d);
	if(r>mid)divide(p<<1|1,l,r,d);
	pushup(p);
}
int ask_min(int p,int l,int r)
{
	if(l<=tr[p].l&&tr[p].r<=r) return tr[p].mn;
	pushdown(p);
	int mid=tr[p].l+tr[p].r>>1;
	int res=inf;
	if(l<=mid)res=min(res,ask_min(p<<1,l,r));
	if(r>mid)res=min(res,ask_min(p<<1|1,l,r));
	return res;
}
LL ask_sum(int p,int l,int r)
{
	if(l<=tr[p].l&&tr[p].r<=r) return tr[p].sum;
	pushdown(p);
	int mid=tr[p].l+tr[p].r>>1;
	LL res=0;
	if(l<=mid)res+=ask_sum(p<<1,l,r);
	if(r>mid)res+=ask_sum(p<<1|1,l,r);
	return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,1,n);
    while(m--)
    {
    	int op,l,r,x,d;
    	scanf("%d%d%d",&op,&l,&r);
    	l++,r++;
    	if(op==1)
    	{
    		scanf("%d",&x);
    		add(1,l,r,x);
    	}
    	else if(op==2)
    	{
    		scanf("%d",&d);
    		divide(1,l,r,d);
    	}
    	else if(op==3)
    		printf("%d\n",ask_min(1,l,r));
    	else
    		printf("%lld\n",ask_sum(1,l,r));
    }
    return 0;
}

原文地址：http://www.cnblogs.com/zyyun/p/16809387.html