LOJ 6029（雅礼集训2017 Day1）市场（线段树）

发表于 |
字数统计: 1,344字 | 阅读时长 ≈ 7min

「雅礼集训 2017 Day1」市场

问题描述

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

有 $ n $ 个商贩，从 $ 0 \sim n - 1 $ 编号，每个商贩的商品有一个价格 $ a_i $，有两种政令：

  1. $ l, r, c $，对于 $ i \in [l, r], a_i \leftarrow a_i + c $
  2. $l, r, d $，对于 $ i \in [l, r], a_i \leftarrow \lfloor {a_i}/{d} \rfloor $

现在有一个外乡的旅客想要了解贸易市场的信息，有两种询问方式：

  1. 给定 $ l, r $，求 $ \min_{i \in [l, r]} a_i $
  2. 给定 $ l, r $，求 $ \sum_{i\in [l, r]} a_i $

输入格式

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

第二行包含 $ n $ 个由空格隔开的整数 $ a_0 \sim a_{n - 1} $

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

输出格式

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

样例输入

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

样例输出

-2

-2

-2

-2

0

1

1

提示

对于 $ 30\% $ 的数据，$ n, q \leq 10 ^ 3 $；

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

对于 $ 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，打个lazy就行了，对于操作二，直接在线段树上暴力下放，然后需要加一个优化。

令$Max,Min$分别为当前区间中最大值和最小值，如果$Max-\lfloor\frac{Max}{d}\rfloor=Min-\lfloor\frac{Min}{d}\rfloor$，此时相当于区间整体减一个数，打个lazy返回就行了。

这个复杂度我算不来，但根据一些理论，他是不会$TLE$的。

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 100005
#define ll long long
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R()
{
	char t=GC;int x;bool f=0;
	while(t!='-'&&(t<48||t>57))t=GC;
	if(t=='-')t=GC,f=1;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
	return f?-x:x;
}
int n,m,tot;ll A[N];
struct node{node *ls,*rs;ll Max,Min,Sum,lazy;}Seg[N<<2],*rt;
void Div(ll &x,ll y)
{
	if(x>=0)x=x/y;
	else x=(x-y+1)/y;
}
void MT(node *p)
{
	p->Max=max(p->ls->Max,p->rs->Max);
	p->Min=min(p->ls->Min,p->rs->Min);
	p->Sum=p->ls->Sum+p->rs->Sum;
}
void PD(node *p,int l,int r)
{
	if(l==r)return;
	int mid=l+r>>1;ll d=p->lazy;
	node *ls=p->ls,*rs=p->rs;
	ls->Max+=d;rs->Max+=d;
	ls->Min+=d;rs->Min+=d;
	ls->Sum+=d*(mid-l+1);rs->Sum+=d*(r-mid);
	ls->lazy+=d;rs->lazy+=d;
	p->lazy=0;
}
void BT(node *p,int x,int y)
{
	if(x==y){p->Max=p->Min=p->Sum=A[x];return;}
	int mid=x+y>>1;
	p->ls=&Seg[++tot];
	p->rs=&Seg[++tot];
	BT(p->ls,x,mid);
	BT(p->rs,mid+1,y);
	MT(p);
}
void ADD(node *p,int l,int r,int x,int y,ll d)
{
	if(p->lazy)PD(p,l,r);
	if(x<=l&&y>=r)
	{
		p->Max+=d;p->Min+=d;p->Sum+=(r-l+1)*d;p->lazy+=d;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid&&y>=l)ADD(p->ls,l,mid,x,y,d);
	if(x<=r&&y>mid)ADD(p->rs,mid+1,r,x,y,d);
	MT(p);
}
void Div(node *p,int l,int r,int x,int y,ll d)
{
	if(p->lazy)PD(p,l,r);
	if(l==r){Div(p->Max,d);Div(p->Min,d);Div(p->Sum,d);return;}
	if(x<=l&&y>=r)
	{
		ll a=p->Max,b=p->Min;Div(a,d);Div(b,d);
		if(p->Max-a==p->Min-b)
		{
			int k=a-p->Max;
			p->Max+=k;p->Min+=k;p->Sum+=(r-l+1)*k;
			p->lazy+=k;return;
		}
	}
	int mid=l+r>>1;
	if(x<=mid&&y>=l)Div(p->ls,l,mid,x,y,d);
	if(x<=r&&y>mid)Div(p->rs,mid+1,r,x,y,d);
	MT(p);
}
ll Gmin(node *p,int l,int r,int x,int y)
{
	if(p->lazy)PD(p,l,r);
	if(x<=l&&y>=r)return p->Min;
	int mid=l+r>>1;ll lmin=1e18,rmin=1e18;
	if(x<=mid&&y>=l)lmin=Gmin(p->ls,l,mid,x,y);
	if(x<=r&&y>mid)rmin=Gmin(p->rs,mid+1,r,x,y);
	return min(lmin,rmin);
}
ll Gsum(node *p,int l,int r,int x,int y)
{
	if(p->lazy)PD(p,l,r);
	if(x<=l&&y>=r)return p->Sum;
	int mid=l+r>>1;ll sum=0;
	if(x<=mid&&y>=l)sum+=Gsum(p->ls,l,mid,x,y);
	if(x<=r&&y>mid)sum+=Gsum(p->rs,mid+1,r,x,y);
	return sum;
}
int main()
{
	int i,j,k,x,y;ll z;
	n=_R();m=_R();
	for(i=1;i<=n;i++)A[i]=_R();
	rt=&Seg[++tot];BT(rt,1,n);
	for(i=1;i<=m;i++)
	{
		k=_R();
		if(k==1)
		{
			x=_R();y=_R();z=_R();
			ADD(rt,1,n,x+1,y+1,z);
		}
		if(k==2)
		{
			x=_R();y=_R();z=_R();
			Div(rt,1,n,x+1,y+1,z);
		}
		if(k==3)
		{
			x=_R();y=_R();
			printf("%lld\n",Gmin(rt,1,n,x+1,y+1));
		}
		if(k==4)
		{
			x=_R();y=_R();
			printf("%lld\n",Gsum(rt,1,n,x+1,y+1));
		}
	}
}