题目
给定一个序列，每次询问：给定 (l,r,x,y) ，问 ([l,r]) 有多少个子区间满足其区间所有数使得 (xleq a_i leq y)。
(n,qleq 10^5)。
分析
回滚莫队+序列分块。
首先这道题限制很多，但是可以离线，数据范围又是 (1e5) ，于是理所当然可以想一下莫队。
发现直接莫队就可以去除 (l,r) 的限制条件，现在问题变成了，询问当前序列有多少个这样的子区间满足 (xleq a_i leq y)。
由于 (x,y) 都是一个静态的给定值，于是可以想到把这个不等关系变成 01 变量来表示，那么这里就可以这样转化成：
定义 (b_i=(xleq a_i leq y)) ，接下来就是询问所有极长连续 1 子区间的 (siz*(siz+1)/2) 的和，同时还有单点修改，每次 (0->1) 或者 (1->0)。
那么这里我们要支持这样 (O(1)) 的单点修改和 (O(sqrt{n})) 的单次查询才行，可以考虑序列分块或者链表，这里使用序列分块。
因为 (1->0) 非常的不好处理，于是我们要想怎么把这个东西去掉。
发现这样的情况只会在这种情况下出现：由于我们使用的是普通莫队，所以我们会导致有一个删除操作，就是这个删除操作会导致有 (1->0) 这种情况。
那么不删除不就好了？再加上分块可以支持撤回操作（可撤销分块（雾））（像可撤销并查集一样拿一个栈记录操作就好了），于是我们就直接回滚莫队来把删除操作变成撤销操作即可。
块大小取 (sqrt{n})，这样时间复杂度是 (O(nsqrt{n})) （假设 (n,q) 同阶）。
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
const int N=3e5+5,M=3e5+5;
#define ll long long
ll calc[N];
int n,m,cnt1,cnt2,a[N],blocks;
struct Query{int l,r,x,y,id;}Q[M];
bool b[N];
int L[M],R[M],id[N],p[N],sum[M],top,T[N];
struct Node{
int id,t1[2],t2[2];
ll Ans;
bool type;
inline void clear(){t1[0]=t2[0]=t1[1]=t2[1]=type=0;}
}sta[M];
Node tmp;
inline void modify(const int &pos,bool type){//把pos位置修改成1，如果type为1则表示需要删除
if(b[pos]) return ;
p[pos]=pos,b[pos]=1;
tmp.id=pos;
const int las=pos-1,nex=pos+1,nowp=p[las];//las是上一个位置，nex是下一个位置，nowp是下一个位置最远的点
const bool flag1=(b[las]&&L[id[pos]]!=pos),flag2=(b[nex]&&R[id[pos]]!=pos);//分别表示这个pos和两个点都属于同一个块并且可以连接
if(!flag1&&!flag2) tmp.clear(),tmp.Ans=1;//如果都没有，那么这个点只贡献 1
else{
tmp.type=1;
if(flag1&&flag2){//如果都有，那么相当于串起来了两边
tmp.Ans=(nex-p[las])*(p[nex]-las);
tmp.t1[0]=p[las],tmp.t1[1]=p[p[las]],p[p[las]]=p[nex],
tmp.t2[0]=p[nex],tmp.t2[1]=p[p[nex]],p[p[nex]]=nowp;
}
else{
if(flag1){//只有左边
tmp.Ans=pos-p[las]+1,//这里记录的是增加量，对于原来的情况 n*(n+1)/2=(n^2+n)/2，现在就是(n+1)*(n+2)/2=(n^2+3n+2)/2，增加了 n+1
tmp.t1[0]=pos,tmp.t1[1]=p[pos],p[pos]=p[las],
tmp.t2[0]=p[las],tmp.t2[1]=p[p[las]],p[p[las]]=pos;
}
else{//只有右边
tmp.Ans=p[nex]-pos+1,//和上面同理
tmp.t1[0]=pos,tmp.t1[1]=p[pos],p[pos]=p[nex],
tmp.t2[0]=p[nex],tmp.t2[1]=p[p[nex]],p[p[nex]]=pos;
}
}
}
sum[id[pos]]+=tmp.Ans;//把变化量加上
if(type) sta[++top]=tmp;//是否需要撤回（临时修改）
return ;
}
inline void Remove(int now){//撤回修改
while(top>now){
tmp=sta[top],top--;
sum[id[tmp.id]]-=tmp.Ans,b[tmp.id]=0;
if(tmp.type==1) p[tmp.t2[0]]=tmp.t2[1],p[tmp.t1[0]]=tmp.t1[1];
}
return ;
}
inline ll query(const int &l,const int &r){
ll Ans=0;
if(id[l]==id[r]){//如果在同一块直接暴力
int cnt=0;
for(int i=l;i<=r;i++) if(b[i]) cnt++; else Ans+=calc[cnt],cnt=0;
return Ans+calc[cnt];
}
const int &BL=id[l],&BR=id[r];
int cnt1=0,cnt2=0;
for(int i=l;i<=R[BL];i++) if(b[i]) cnt1++; else Ans+=calc[cnt1],cnt1=0;//暴力两边
for(int i=r;i>=L[BR];i--) if(b[i]) cnt2++; else Ans+=calc[cnt2],cnt2=0;
int tot=cnt1;//先从第一个开始接
for(int i=BL+1;i<=BR-1;i++){
const int posl=L[i],posr=R[i];
if(p[posl]==posr) tot+=posr-posl+1;//如果一整块都是 1，直接给目前最左边区间个数加上块个数
else{
if(b[posl]) tot+=p[posl]-posl+1,Ans-=calc[p[posl]-posl+1];//如果可以继承前面的，那就继承上一个块的末尾，然后减掉这一段开头对于本身的额外贡献
Ans+=calc[tot]+sum[i],tot=0; //继承上一部分的和本身的块的贡献
if(b[posr]) tot+=posr-p[posr]+1,Ans-=calc[posr-p[posr]+1];//如果可以给后面的继承，那就存下来，把这个后继对于块的贡献减去
}
}
return Ans+calc[tot+cnt2];//不要忘记最后还有一个末尾块没加，同时还有cnt2！！
}
ll Ans[M];
bool vis[N];
int sqrtm,op,l,r,x,y;
inline bool Cmp(const Query &x,const Query &y){
if(id[x.x]^id[y.x]) return id[x.x]<id[y.x];
return x.y<y.y;
}
signed main(){
read(n),read(m);
sqrtm=sqrt(m);
int sqrtn=sqrt(n*(1.0*3/4)+1);
for(int i=1,c=1,j;i<=n;i=j+1,c++){
L[c]=i,R[c]=j=min(n,i+sqrtn);
for(int t=L[c];t<=R[c];t++) id[t]=c;
blocks=c;
}
for(int i=1;i<=n;i++) calc[i]=1ll*i*(i+1)/2;
for(int i=1;i<=n;i++) read(a[i]),T[a[i]]=i;
for(int i=1;i<=m;i++) read(l),read(r),read(x),read(y),Q[i]=(Query){l,r,x,y,i};
sort(Q+1,Q+m+1,Cmp);
for(int i=1,j=1;j<=blocks;j++){
int BR=R[j],l=BR+1,r=BR;
for(;id[Q[i].x]==j;i++){
if(id[Q[i].y]==j){
Remove(0);
int Top=top;
for(int k=Q[i].x;k<=Q[i].y;k++) modify(T[k],1);
Ans[Q[i].id]=query(Q[i].l,Q[i].r);
Remove(Top);
continue;
}
while(r<Q[i].y) r++,modify(T[r],1);
int Top=top;
while(l>Q[i].x) l--,modify(T[l],1);
Ans[Q[i].id]=query(Q[i].l,Q[i].r);
Remove(Top);
l=BR+1;
}
Remove(0);
}
for(int i=1;i<=m;i++) write(Ans[i]),putchar('
');
return 0;
}