题解 P3865 【【模板】ST表】
Juan_feng
2018-10-24 20:11:35
## 虽然这道题是ST表的模板，但小蒟蒻认为~~这道题的数据太水了~~可以练练别的方法。
### 小蒟蒻就用线段树，分块和莫队AC了此题（大雾
**不过线段树和普通分块的做法看起来都有人写过题解了呀QAQ而且也都是比较简单的操作，这里就不详细说了，代码放在题解最后供大家参考。**
## 小蒟蒻今天主要讲一下莫队的做法
**那么问题来了，怎么用莫队查询区间最大值？**
**不用想也知道普通的莫队是不行的，当前的最大值被删除了之后并不能找到次大值来衔接上。**
## 那么就该回滚莫队登场了qwqwq
**回滚莫队= =**
**
敲阔耐的名字呢qwqwq**
### 具体实现：
还是要先分根号n个块，对所有询问以左端点所在的块的前后为第一关键字，以右端点的前后为第二关键字进行**排序**；
然后针对每个块进行处理，**对于每一个块**，枚举左端点在这个块上面的所有询问，这时候就可以**分两种情况**来讨论了，一种是左右两端点都在该块内的情况，另一种是右端点在后面的块里面的情况。
**对于左右端点都在一个块上的询问**：直接暴力求答案就好owo
**对于右端点不在该块上的的询问**： 因为我们是对询问以询问的右端点的位置前后为第二关键字进行的排序，所以该块内各个询问的右端点位置一定是**递增**的，这样对于每个块一开始就可以把**右端点设在该块的末尾**，每次向后移动统计答案就好啦qwq;
**那么左端点呢= =，左端点的位置可不是递增的呀qwqwq？**
我们也可以先把初始的**左端点设在该块的末尾处**，对于每一个询问，先**保存当前的答案**，再把**左端点向左跳直到跳到该询问的左端点处**，**统计并保存询问的答案**，**最后再跳回原处**(该块的末尾处），**消除**这一次操作对路径上的**影响**，再把**答案修改回之前保存的答案**就行啦QωQ
### 再强调一下步骤>_<，对于每个块：
#### 一.左右端点初始化，答案初始化
#### 二.开始处理
**1.右端点向询问的右端点移动并处理答案**
**2.记录当前答案**
**3.左端点向询问的左端点移动并处理答案**
**4.保存答案**
**
5.左端点移回原处，消除路径上的影响，还原答案到步骤2**
#### 最后把保存好的答案按序号输出，这个问题就愉快的解决啦QωQ
**要是想练习回滚莫队的话可以看一下这道题：
[历史研究](https://www.lydsy.com/JudgeOnline/problem.php?id=4241)**
(以上内容部分借鉴于网络上几位dalao对回滚莫队的讲解）
**那么代码如下qwq：**
```
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define maxn 1000001
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;
int n, m, c, r, t, x, y, z, sq, anss;
int a[maxn], b[maxn], ans[maxn], cnt[maxn];
struct hz { //这个结构体用于保存询问的各项信息
int l;
int r;
int id;
inline bool operator <(const hz &o)const {
return (b[l] == b[o.l])? r < o.r : l < o.l;
} //重载一下排序的关键字
}h[maxn];
inline char nc(){ //无处不在的快读qwq
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf)+fread(buf, 1, 100000, stdin), p1 == p2)?EOF : *p1++;
}
inline int read(){
re char ch = nc();
re int sum = 0;
while(!(ch >= '0'&&ch <= '9')) ch = nc();
while(ch >= '0'&&ch <= '9') sum = sum*10+ch-48, ch = nc();
return sum;
}
void out(int a){
if(a >= 10)out(a/10);
putchar(a%10+'0');
}
int query(int x, int y) { //对于左右端点在一个块内的询问暴力求出答案
int res = 0;
FOR(i, x, y)
if(a[i] > res)
res = a[i];
return res;
}
void add(int x) { //统计答案......
anss = max(anss, a[x]);
}
int doit(int qnum, int x) { //阔耐的回滚莫队owo
int L = min(x*sq, n);
int i = qnum, l = L+1, r = L; //初始化左右端点
anss = 0; //初始化答案
for(; b[h[i].l] == x; ++i) {
if(b[h[i].l] == b[h[i].r]) { //处理左右端点同块的情况
ans[h[i].id] = query(h[i].l, h[i].r);
continue;
}
while(r < h[i].r) //右端点向后跳至询问的右端点
add(++r);
int qwq = anss; //记录当前答案+卖萌qwqwq
while(l > h[i].l) //左端点向前移动到询问的左端点
add(--l);
ans[h[i].id] = anss; //保存答案
l = L+1; //左端点移会原处
anss = qwq; //将答案复原
}
return i; //意为目前处理询问的序号
}
int main() {
n = read(), m = read();
sq = n/sqrt(m*3/2); //这样分块似乎跑的更快QωQ
FOR(i, 1, n) {
a[i] = read(),
b[i] = (i-1)/sq+1;
}
FOR(i, 1, m) { //保存询问的各项信息
h[i].l = read(),
h[i].r = read(),
h[i].id = i;
}
sort(h+1,h+m+1);
int qnum = 1;
FOR(i, 1, b[n]) { //处理每一个块内的询问
qnum = doit(qnum, i);
}
FOR(i, 1, m) { //输出答案ovo
out(ans[i]);
puts("");
}
return 0; //功德圆满。
}
```
**普通分块：**
**（就是简单的区间最大值就不具体细讲了QAQAQ）**
```
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define maxn 1000001
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;
int n, m, c, r, t, x, y, z, sq;
int a[maxn], b[maxn], ans[maxn];
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
re char ch=nc();
re int sum=0;
while(!(ch>='0'&&ch<='9'))ch=nc();
while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
return sum;
}
void out(re int a){
if(a>=10)out(a/10);
putchar(a%10+'0');
}
inline int query(re int x,re int y) {
int res = 0;
FOR(i, x, min(y, b[x]*sq))
res = max(res, a[i]);
if(b[x] != b[y])
FOR(i, (b[y]-1)*sq+1, y)
res = max(res, a[i]);
FOR(i, b[x]+1, b[y]-1)
res = max(res, ans[i]);
return res;
}
int main() {
n=read(), m=read();
sq=sqrt(n);
FOR(i, 1, n)
a[i] = read(), b[i] = (i-1)/sq+1, ans[b[i]] = max(ans[b[i]], a[i]);
FOR(i, 1, m) {
x = read(),
y = read(),
out(query(x, y));
puts("");
}
}
```
**线段树：**
**（线段树做的时间有点早码风可能有点小差异请见谅呀qwqwq）**
```
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 8000001
#define re register
#define FOR(i,l,r) for(re int i=l;i<=r;i++)
using namespace std;
int a[maxn],b[maxn],ans[maxn],tag[maxn],m,n,maxx,minn,c,t,x,y;
inline int in(){
char ch;
int a=0,w=1;
while(!(((ch=getchar())>='0')&&(ch<='9')));
a*=10;a+=ch-'0';
while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0';
return a*w;
}
inline void out(int a){
if(a>=10)out(a/10);
putchar(a%10+'0');
}
inline int ls(int k){
return k<<1;
}
inline int rs(int k){
return k<<1|1;
}
inline void push_up(int k){
ans[k]=max(ans[ls(k)],ans[rs(k)]);
}
void build(int p,int l,int r){
if(l==r){
ans[p]=a[l];
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
int query(int q_x,int q_y,int l,int r,int p){
int res=0;
if(q_x<=l&&r<=q_y)
return ans[p];
int mid=(l+r)>>1;
if(q_x<=mid) res=max(res,query(q_x,q_y,l,mid,ls(p)));
if(q_y>mid) res=max(res,query(q_x,q_y,mid+1,r,rs(p)));
return res;
}
int main(){
n=in(),m=in();
FOR(i,1,n)
a[i]=in();
build(1,1,n);
FOR(i,1,m){
x=in(),y=in();
out(query(x,y,1,n,1));
puts("");
}
}
```
**那么今天的题解就到这里啦qwq，有什么意见和建议欢迎私信小蒟蒻来指出呀qwqwq。**
### 最后祝大家NOIP RP++!