蜜雪冰城下架的饮品？

#include<bits/stdc++.h>
using namespace std;
#define re register
const int maxn=1e5+5,B=345;
inline int read(){
char ch=getchar();bool f=0;int x=0;
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
if(f1)x=-x;return x;
}
void print(long long x){
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+'0');
}
struct node{int x,id;}a[maxn],b[maxn];
int n,m,l,r,x,y,t,g,L[B],R[B],lx[maxn],ly[maxn],id[maxn];
int rk[B][B];
int p[maxn][B];
int pre[B][maxn];
int lsh[B][maxn];
long long c[B][B][B];
int sum[B][B][B];
int msort(int l,int r){
int tot=0,res=0;
int i=1,j=1;
for(;i<=l&&j<=r;)
if(lx[i]<ly[j])i++,res+=r-j+1;
else j++;
return res;
}
bool cmp(node a,node b){return a.x<b.x;}
inline int query1(int l,int r,int x,int y){
int res=0,h=id[l];int g=lsh[h][x-1];
for(int i=l;i<=r;i++)
if(a[i].x<=y&&a[i].x>=x){
res+=p[i][lsh[h][a[i].x-1]]-p[i][g];
if(l!=L[h])res=res-p[l-1][lsh[h][a[i].x-1]]+p[l-1][g];
}
return res;
}
inline long long query2(int l,int r,int x,int y){
long long res=0;res=query1(l,R[id[l]],x,y)+query1(L[id[r]],r,x,y);
int s1=0,s2=0;
for(re int i=L[id[l]];i<=R[id[l]];i++)
if(b[i].id>=l&&b[i].x<=y&&b[i].x>=x)lx[s1]=b[i].x,
res+=pre[id[r]-1][y]-pre[id[r]-1][b[i].x]-pre[id[l]][y]+pre[id[l]][b[i].x];
for(re int i=L[id[r]];i<=R[id[r]];i)
if(b[i].id<=r&&b[i].x<=y&&b[i].x>=x)ly[s2]=b[i].x,
res+=pre[id[r]-1][b[i].x]-pre[id[r]-1][x-1]-pre[id[l]][b[i].x]+pre[id[l]][x-1];
res+=msort(s1,s2);int num=0;
for(int i=id[l]+1;i<=id[r]-1;i){
res+=sum[i][lsh[i][x-1]+1][lsh[i][y]];
res+=c[i][i-1][lsh[i][y]]-c[i][id[l]][lsh[i][y]]-c[i][i-1][lsh[i][x-1]]+c[i][id[l]][lsh[i][x-1]]
-num*(lsh[i][y]-lsh[i][x-1]);
num+=lsh[i][x-1];
}
return res;
}
signed main(){
n=read();m=read();t=sqrt(n);g=(n-1)/t+1;
for(re int i=1;i<=n;i++)a[i].x=read(),a[i].id=i,b[i]=a[i],id[i]=(i-1)/t+1;
for(re int i=1;i<=g;i++){
L[i]=R[i-1]+1,R[i]=min(i*t,n);
int l=L[i],r=R[i];
sort(b+l,b+r+1,cmp);int h=1;
for(int j=1;j<b[l].x;j++)lsh[i][j]=0;h=b[l].x;
for(re int j=l;j<=r;j++){
rk[i][j-l+1]=b[j].x,p[b[j].id][j-l+1]=1,pre[i][a[j].x]=1;
int u=b[j+1].x;if(jr)u=n+1;
for(int k=h;k<u;k++)lsh[i][k]=j-l+1;h=b[j+1].x;
}
for(re int j=l;j<=r;j++)
for(re int k=1;k<=r-l+1;k++){
if(j!=l)
p[j][k]=p[j][k]+p[j-1][k]+p[j][k-1]-p[j-1][k-1];
else p[j][k]=p[j][k]+p[j][k-1];
}
for(int j=1;j<=n;j++)
pre[i][j]=pre[i][j]+pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1];
for(re int j=1;j<i;j++)
for(re int k=1;k<=r-l+1;k++)
c[i][j][k]=pre[j][rk[i][k]]+c[i][j][k-1];
for(re int j=1;j<=r-l+1;j++)
for(re int k=j+1;k<=r-l+1;k++)
sum[i][j][k]=sum[i][j][k-1]+p[b[k+l-1].id][k-1]-p[b[k+l-1].id][j-1];
}
for(int i=1;i<=m;i++){
l=read(),r=read(),x=read(),y=read();
if(id[l]==id[r])
print(query1(l,r,x,y)),puts("");
else print(query2(l,r,x,y)),puts("");
}
return 0;
}