LOJ6029「雅礼集训 2017 Day1」市场

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

LOJ6029「雅礼集训 2017 Day1」市场

img

img

做这道题的时候首先想到了另一道线段树区间取模的题。那道题就是因为每次有意义的取模操作后数的大小至少变成原来的一半从而保证了复杂度。这道题是区间整体除，似乎有类似的性质。虽然看起来线段树不可做，但实际上即使是分块也处理不了区间除法操作。

题解正是线段树。差不多就是把能想到的优化都加上去就可过了。听说用势能分析可以证明复杂度是有保证的。

首先想到的优化是，如果区间里的数只有0或-1，那么就直接停止操作，然而仅仅是这样的话只有30分，不如写暴力。

正解是，把部分区间除法改为区间减法。众所周知，区间加减法使用lazy标记的复杂度是$O(logn)$的。如果整个区间里的最大的数和最小的数执行除法操作后减少的值相同，那就转换为区间减法。

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
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MAXN 200005
#define MAXT 1600005
#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(){
	int sign=0,v=0;char s=GC;
	while((s!='-')&&(s>57||s<48))s=GC;
	if(s=='-')sign=1,s=GC;
	for(;s>47&&s<58;s=GC)v=v*10+s-48;
	return sign?-v:v;
}

void Div(int &x,int y){
	if(x>=0)x=x/y;
	else x=(x-y+1)/y;
}

int N,Q,A[MAXN];

int tot,a[MAXT],b[MAXT],ls[MAXT],rs[MAXT],mx[MAXT],mn[MAXT],lazy[MAXT];
ll sum[MAXT];
void update(int p){
	sum[p]=sum[ls[p]]+sum[rs[p]];
	mx[p]=max(mx[ls[p]],mx[rs[p]]);
	mn[p]=min(mn[ls[p]],mn[rs[p]]);
}

void putdown(int p){
	sum[ls[p]]+=(ll)(b[ls[p]]-a[ls[p]]+1)*lazy[p];
	sum[rs[p]]+=(ll)(b[rs[p]]-a[rs[p]]+1)*lazy[p];
	mx[ls[p]]+=lazy[p];mx[rs[p]]+=lazy[p];
	mn[ls[p]]+=lazy[p];mn[rs[p]]+=lazy[p];
	lazy[ls[p]]+=lazy[p];lazy[rs[p]]+=lazy[p];
	lazy[p]=0;
}

int build(int l,int r){
	int p=++tot,mid=l+r>>1;
	a[p]=l;b[p]=r;
	if(l==r){
		sum[p]=mx[p]=mn[p]=A[l];
		return p;
	}
	ls[p]=build(l,mid);
	rs[p]=build(mid+1,r);
	update(p);
	return p;
}

void divide(int p,int x,int y,int d){
	if(lazy[p])putdown(p);
	if((mx[p]==0&&mn[p]==0)||(mx[p]==-1&&mn[p]==-1)||(mx[p]==0&&mn[p]==-1))return;
	int d1=mx[p],d2=mn[p];
	Div(mx[p],d);Div(mn[p],d);
	swap(mx[p],d1);swap(mn[p],d2);
	if(a[p]>=x&&b[p]<=y&&mx[p]-d1==mn[p]-d2){
		int tmp=mx[p];
		mx[p]=d1;mn[p]=d2;
		sum[p]-=(ll)(b[p]-a[p]+1)*(tmp-d1);
		lazy[p]=mx[p]-tmp;
		return;
	}
	if(a[p]==b[p]){
		Div(mx[p],d);mn[p]=sum[p]=mx[p];
		return;
	}
	int mid=a[p]+b[p]>>1;
	if(x<=mid)divide(ls[p],x,y,d);
	if(y>mid)divide(rs[p],x,y,d);
	update(p);
}

void add(int p,int x,int y,int d){
	if(lazy[p])putdown(p);
	if(a[p]>=x&&b[p]<=y){
		mx[p]+=d;mn[p]+=d;sum[p]+=(b[p]-a[p]+1)*d;
		lazy[p]=d;
		return;
	}
	int mid=a[p]+b[p]>>1;
	if(x<=mid)add(ls[p],x,y,d);
	if(y>mid)add(rs[p],x,y,d);
	update(p);
}

ll getsum(int p,int x,int y){
	if(lazy[p])putdown(p);
	if(x<=a[p]&&b[p]<=y)return sum[p];
	int mid=a[p]+b[p]>>1;ll ret=0;
	if(x<=mid)ret+=getsum(ls[p],x,y);
	if(y>mid)ret+=getsum(rs[p],x,y);
	return ret;
}

int getmin(int p,int x,int y){
	if(lazy[p])putdown(p);
	if(x<=a[p]&&b[p]<=y)return mn[p];
	int mid=a[p]+b[p]>>1,ret=1e9;
	if(x<=mid)ret=min(ret,getmin(ls[p],x,y));
	if(y>mid)ret=min(ret,getmin(rs[p],x,y));
	return ret;
}

int main(){
	int i,ty,l,r,d;
	N=_R();Q=_R();
	for(i=1;i<=N;i++)A[i]=_R();
	build(1,N);
	for(i=1;i<=Q;i++){
		ty=_R();l=_R();r=_R();
		l++;r++;
		if(ty==1){
			d=_R();
			add(1,l,r,d);
		}
		else if(ty==2){
			d=_R();
			divide(1,l,r,d);
		}
		else if(ty==3)printf("%d\n",getmin(1,l,r));
		else printf("%lld\n",getsum(1,l,r));
	}
}