Reincarnation

正因为梦易碎，才格外美好。

CF803G Periodic RMQ Problem

发表于 更新于 分类于
本文字数： 4.4k 阅读时长 ≈ 4 分钟

「末世追忆」：比较神仙的线段树题目。

：https://codeforces.com/contest/803/problem/G
：https://www.luogu.com.cn/problem/CF803G

就是一个极其简单的 问题，但是序列长度 ，难搞。

可以考虑还是以线段树为主体，但是用一大堆优化即可。

如果是离散化的话，最后能够达到的点个数为 ，然后对于每一个离散区间将其预处理化其中的 值，但是考虑到修改的话，比较麻烦，不优先考虑（但事实是有这种做法的）。

同样的，可以用分块。

学分块没前途。——

虽然似乎有这部分的做法和思路，但考虑到常数过大，就暂且 掉。

如果联想到 的话，应该可以联想到 表，这样可以在 的时间内查询到某一个区间的最小值。然后从离散化，我们有一个同样将空间压缩到 的优化，那就是动态开点。我们可以使用动态开点线段树来进行这个操作，每当我递归到一个区间 的时候，就顺便用 的时间把这个区间的最小值给它找出来，然后即可。

对于修改操作的话，用 Tr[p].tag 来搞就好了，这样的话，无论是修改操作或是查询操作，我们都和原来的线段树一样，但是在 pushDown() 的时候，如果 的子结点不存在的话，我们不能直接 return ，可以考虑直接建新点，省下下次的时间。

AC Code 
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
154
155
156
157
158
159
// Problem: G. Periodic RMQ Problem
// Contest: Codeforces - Educational Codeforces Round 20
// URL: https://codeforces.com/problemset/problem/803/G
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// Written by: Eternity

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
	read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(char c)
{
	putchar(c);
}
template<>
inline void write(char *s)
{
	while(*s!='\0') putchar(*s++);
}
template<>
inline void write(const char *s)
{
	while(*s!='\0') putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
	write(x),write(x1...);
}
template<class T>
inline void checkMax(T &x,T y)
{
	x=x>y?x:y;
}
template<class T>
inline void checkMin(T &x,T y)
{
	x=x<y?x:y;
}
const int MAXN=5e6+10,MAXK=1e4+10,MAXS=64;
const int INF=0x3f3f3f3f;
int N,K,Val[MAXN],Q,Rt,Idx;
#define ls(p) Tr[p].lc
#define rs(p) Tr[p].rc
struct ST
{
	int lc,rc,val,tag;
}Tr[MAXN];
int St[MAXN>>2][MAXS];
inline int segmentMin(int l,int r)
{
	int len=log2(r-l+1);
	return std::min(St[l][len],St[r-(1<<len)+1][len]);
}
inline int getMin(int l,int r)
{
	if(r-l+1>=N) return segmentMin(0,N-1);
	if(l/N==r/N) return segmentMin(l%N,r%N);
	return std::min(segmentMin(l%N,N-1),segmentMin(0,r%N));
}
inline void insert(int &p,int l,int r)
{
	if(p) return ;
	p=++Idx,Tr[p].val=getMin(l,r);
	return ;
}
inline void pushUp(int p)
{
	Tr[p].val=std::min(Tr[Tr[p].lc].val,Tr[Tr[p].rc].val);
}
inline void modifyX(int p,int v)	
{
	Tr[p].tag=Tr[p].val=v;
	return ;
}
inline void pushDown(int p,int l,int r)
{
	int mid=(l+r)>>1;
	insert(Tr[p].lc,l,mid),insert(Tr[p].rc,mid+1,r);
	if(!Tr[p].tag) return ;
	modifyX(ls(p),Tr[p].tag),modifyX(rs(p),Tr[p].tag);
	Tr[p].tag=0;
}
inline void stInit()
{
	for(int i=1;(1<<i)<=N;++i)
		for(int j=0;j+(1<<i)<=N;++j)
			St[j][i]=std::min(St[j][i-1],St[j+(1<<(i-1))][i-1]);
}
void modifyCover(int &p,int ql,int qr,int l,int r,int v)
{
	insert(p,l,r);
	if(ql<=l&&r<=qr)
	{
		modifyX(p,v);
		return ;
	}
	pushDown(p,l,r);
	int mid=(l+r)>>1;
	if(ql<=mid) modifyCover(Tr[p].lc,ql,qr,l,mid,v);
	if(mid<qr) modifyCover(Tr[p].rc,ql,qr,mid+1,r,v);
	pushUp(p);
}
int queryMin(int &p,int ql,int qr,int l,int r)
{
	insert(p,l,r);
	if(ql<=l&&r<=qr) return Tr[p].val;
	pushDown(p,l,r);
	int mid=(l+r)>>1,res=INF;
	if(ql<=mid) checkMin(res,queryMin(Tr[p].lc,ql,qr,l,mid));
	if(mid<qr) checkMin(res,queryMin(Tr[p].rc,ql,qr,mid+1,r));
	return res;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,K);
	for(int i=0;i<N;++i) read(St[i][0]);
	stInit();
	read(Q);
	insert(Rt,0,N*K-1);
	for(int opt,ql,qr,qx;Q--;)
	{
		read(opt,ql,qr),--ql,--qr;
		if(opt==1)
		{
			read(qx);
			modifyCover(Rt,ql,qr,0,N*K-1,qx);
		}
		else write(queryMin(Rt,ql,qr,0,N*K-1),'\n');
	}
	return 0;
}
/*

*/
相关文章