还在吗？
by BVVD_FM @ 2023-11-14 16:56:40
我分块过了
这是代码
```cpp
#include<bits/stdc++.h>//区间修改+区间查询最值
using namespace std;
#define re register
const int N=5e4+10,K=250,INF=0x3f3f3f3f;
struct node{
int l,r;
int maxx,minn;
int lazy;
}kuai[K];
int n,q,cnt,len,a[N],cop[N],loc[N];
inline int read(){
int f=0,fu=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')fu=-1;c=getchar();}
while(c>='0'&&c<='9'){f=(f<<3)+(f<<1)+c-48;c=getchar();}
return f*fu;
}
inline void write(int x){
if(x<0)x=(x^-1)+1,putchar('-');
if(x>9)write(x/10);
putchar(x%10+'0');
}
void reset(int x){
for(int i=kuai[x].l;i<=kuai[x].r;i=-~i){
a[i]+=kuai[x].lazy;
cop[i]=a[i];
}
kuai[x].lazy=0;
stable_sort(cop+kuai[x].l,cop+kuai[x].r+1);
kuai[x].maxx=cop[kuai[x].r];
kuai[x].minn=cop[kuai[x].l];
}
void update(int l,int r,int k){
int st=loc[l],en=loc[r];
for(int i=l;i<=min(r,kuai[st].r);i=-~i)a[i]+=k;
reset(st);
if(st!=en){
for(int i=kuai[en].l;i<=r;i=-~i)a[i]+=k;
reset(en);
for(int i=st+1;i<en;i=-~i)kuai[i].lazy+=k;
}
}
int query(int l,int r){
int st=loc[l],en=loc[r],maxx=-INF,minn=INF;
for(int i=l;i<=min(r,kuai[st].r);i=-~i){
maxx=max(maxx,a[i]+kuai[st].lazy);
minn=min(minn,a[i]+kuai[st].lazy);
}
if(st!=en){
for(int i=kuai[en].l;i<=r;i=-~i){
maxx=max(maxx,a[i]+kuai[en].lazy);
minn=min(minn,a[i]+kuai[en].lazy);
}
for(int i=st+1;i<en;i=-~i){
maxx=max(maxx,kuai[i].maxx);
minn=min(minn,kuai[i].minn);
}
}
return maxx-minn;
}
int main(){
n=read(),q=read();len=sqrt(n);
for(int i=1;i<=n;i++){
a[i]=read();
if(i%len==1){
kuai[++cnt].l=i;
kuai[cnt].minn=INF;
kuai[cnt].maxx=-INF;
}
loc[i]=cnt;
kuai[cnt].r=i;
kuai[cnt].maxx=max(kuai[cnt].maxx,a[i]);
kuai[cnt].minn=min(a[i],kuai[cnt].minn);
cop[i]=a[i];
}
for(int i=1;i<=cnt;i++)reset(i);
/*
for(int i=1;i<=cnt;i++){
cout<<kuai[i].l<<" "<<kuai[i].r;
cout<<"\n"<<kuai[i].maxx<<" "<<kuai[i].minn<<"\n";
}
*/
while(q--){
//int op;cin>>op;
int l,r,k;l=read(),r=read();
//k=read();
//if(op==1)update(l,r,k);
//else
write(query(l,r)),puts("");
}
return 0;
}//板子
```
by BVVD_FM @ 2023-11-14 16:57:35