隐藏
「UOJ169」元旦老人与数列 - 线段树+区间取最值+历史最值 | Bill Yang's Blog

路终会有尽头，但视野总能看到更远的地方。

0%

「UOJ169」元旦老人与数列 - 线段树+区间取最值+历史最值

发表于 更新于 分类于 Valine：

题目大意

    最开始xyz111有两个长度为$n$的完全相同的数列$A$和$B$，接下来有$m$次操作，每一次操作都是以下的四种之一：
    1.对于所有的$i\in[l,r]$，将$A_i$变成$A_i+c$。
    2.对于所有的$i\in[l,r]$，将$A_i$变成$\max(A_i,d)$。
    3.对于所有的$i\in[l,r]$，询问$A_i$的最小值。
    4.对于所有的$i\in[l,r]$，询问$B_i$的最小值。
    在每一次操作结束之后，xyz111 都会进行一次更新：对于所有的$i\in[1,n]$，将$B_i$变成 $\min(B_i,A_i)$。

题目分析

不难发现本题若使用上题的标记域，是无法合并的。
因为本题询问的是最小值，而$\min$与$\max$结合后无论如何也不可能再写成$\max$的形式，从图像上来看就是论文中的下凸函数取$\min$，不一定还是一个下凸函数，因此我们不能使用上题的做法。

考虑论文中的思想：区间最值转化为区间加减。
我们将最小值和非最小值拆开维护，那么当递归到$min\le v\le sec$时，区间最值其实是一个只对最小值有效的区间加减，而原题的区间加减是对于最小值和非最小值均有效的区间加减。

故我们得出这样的思路：维护最小值所需的信息，维护非最小值所需的信息，区间取最值时暴力递归到$min\le v\le sec$进行打标记维护，而总体的区间加减直接定位后打标记即可。

要维护一些什么信息呢？需要维护最小值，严格次小值，历史最小值，最小值的区间加减标记，最小值的历史区间加减标记，非最小值的区间加减标记，非最小值的历史区间加减标记。

维护了这些信息后，考虑标记下传，历史标记的更新和上题的方式相同，而其他维护的信息也不难，我们考虑一下维护信息的方向。

最小值的标记信息只能传递给最小值，故需要比较左右儿子谁更小，将本身的最小值标记传递到更小的儿子中（若儿子相等都传）。非最小值的标记信息可以传递给左右儿子的非最小值，同样的，若左右儿子有个儿子严格大一些，那么我的非最小值标记也要传递给它的最小值标记。（在编程实现上需要在下传前保存左右儿子的最小值判断方向，否则下传标记后最小值改变了会引起错误）

本题在UOJ上卡时限卡空间，用FastIO+动态开点线段树解决。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;
#define inf LLONG_MAX/3

namespace FastIO {
    const int L=1<<15;
    char buffer[L],*S,*T;
    inline char getchar() {
        if(S==T) {T=(S=buffer)+fread(buffer,1,L,stdin);if(S==T)return EOF;}
		return *S++;
    }
    inline int Get_Int() {
        char c;int rec=0,f=1;
        for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
        while(c>='0'&&c<='9')rec=(rec<<1)+(rec<<3)+(c-'0'),c=getchar();
        return rec*f;
    }
}
using FastIO::Get_Int;

int min(int a,int b) {
	return a<b?a:b;
}

LL min(LL a,LL b) {
	return a<b?a:b;
}

const int maxn=500005;

struct Data {
	LL lazy,hislazy;
};

struct Tree {
	int left,right,ls,rs;
	Data min,notmin;
	LL val,sec,hisval;
	Tree(int l=0,int r=0,LL v=inf,LL hisv=inf):left(l),right(r),val(v),sec(inf),hisval(hisv) {
		notmin.lazy=min.lazy=notmin.hislazy=min.hislazy=ls=rs=0;
	}
};
struct Segment_Tree {
	Tree tree[maxn*2];
	#define ls tree[index].ls
	#define rs tree[index].rs
	int size;
	void push_up(int index) {
		tree[index].val=min(tree[ls].val,tree[rs].val);
		if(tree[ls].val>tree[rs].val)tree[index].sec=min(tree[ls].val,tree[rs].sec);
		if(tree[ls].val<tree[rs].val)tree[index].sec=min(tree[rs].val,tree[ls].sec);
		if(tree[ls].val==tree[rs].val)tree[index].sec=min(tree[ls].sec,tree[rs].sec);
		tree[index].hisval=min(tree[ls].hisval,tree[rs].hisval);
	}
	void build(int& index,int Left,int Right,int* a) {
		index=++size;
		tree[index]=Tree(Left,Right);
		if(Left==Right) {
			tree[index].val=tree[index].hisval=a[Left];
			return;
		}
		int mid=(Left+Right)>>1;
		build(ls,Left,mid,a);
		build(rs,mid+1,Right,a);
		push_up(index);
	}
	void mupdate(int index,Data x) {
		tree[index].hisval=min(tree[index].hisval,tree[index].val+x.hislazy);
		tree[index].min.hislazy=min(tree[index].min.hislazy,tree[index].min.lazy+x.hislazy);
		tree[index].val+=x.lazy;
		tree[index].min.lazy+=x.lazy;
	}
	void update(int index,Data x) {
		tree[index].notmin.hislazy=min(tree[index].notmin.hislazy,tree[index].notmin.lazy+x.hislazy);
		tree[index].sec+=x.lazy;
		tree[index].notmin.lazy+=x.lazy;
	}
	void mpush_down(int index,int lv,int rv) {
		if(!tree[index].min.lazy&&!tree[index].min.hislazy)return;
		if(lv<=rv)mupdate(ls,tree[index].min);
		if(rv<=lv)mupdate(rs,tree[index].min);
		tree[index].min.lazy=tree[index].min.hislazy=0;
	}
	void push_down(int index) {
		if(tree[index].left==tree[index].right)return;
		int lv=tree[ls].val,rv=tree[rs].val;
		mpush_down(index,lv,rv);
		if(!tree[index].notmin.lazy&&!tree[index].notmin.hislazy)return; 
		if(lv>rv)mupdate(ls,tree[index].notmin);
		if(rv>lv)mupdate(rs,tree[index].notmin);
		update(ls,tree[index].notmin);
		update(rs,tree[index].notmin);
		tree[index].notmin.lazy=tree[index].notmin.hislazy=0;
	}
	void modify(int index,int Left,int Right,int v) { //区间+
		if(Left>tree[index].right||Right<tree[index].left)return;
		if(Left<=tree[index].left&&Right>=tree[index].right) {
			mupdate(index,(Data) {v,v});
			update(index,(Data) {v,v});
			return;
		}
		push_down(index);
		modify(ls,Left,Right,v);
		modify(rs,Left,Right,v);
		push_up(index);
	}
	void mmodify(int index,int Left,int Right,int v) { //最小+
		if(tree[index].left>Right||tree[index].right<Left)return;
		if(v<=tree[index].val)return;
		if(Left<=tree[index].left&&tree[index].right<=Right&&v<tree[index].sec) {
			mupdate(index,(Data) {v-tree[index].val,v-tree[index].val});
			return;
		}
		push_down(index);
		mmodify(ls,Left,Right,v);
		mmodify(rs,Left,Right,v);
		push_up(index);
	} 
	LL query(int index,int Left,int Right,bool flag) {
		if(Left>tree[index].right||Right<tree[index].left)return inf;
		if(Left<=tree[index].left&&Right>=tree[index].right)return flag?tree[index].val:tree[index].hisval;
		push_down(index);
		return min(query(ls,Left,Right,flag),query(rs,Left,Right,flag));
	}
} st;

int n,m,root,a[maxn];

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++)a[i]=Get_Int(); 
	st.build(root,1,n,a);
	for(int i=1; i<=m; i++) {
		int opt=Get_Int(),x=Get_Int(),y=Get_Int();
		if(opt==1)st.modify(root,x,y,Get_Int());
		else if(opt==2)st.mmodify(root,x,y,Get_Int());
		else if(opt==3)printf("%lld\n",st.query(root,x,y,1));
		else printf("%lld\n",st.query(root,x,y,0));
	}
	return 0;
}
相关文章
姥爷们赏瓶冰阔落吧~