这样本地过，提交全WA

#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int n,m,a[N],s,tmp[N],bel[N],fr[N];
LL b[N],d[N],c[N],ans[N],sum[N];
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return res;
}
struct p{
	int l,r,id;
}q[N];
inline bool cmp(p x,p y){
	if(bel[x.id]!=bel[y.id])return bel[x.id]<bel[y.id];return x.r<y.r;
}
struct data{
	int l,r,v,id;
};
inline void add(int x,int y){
	while(x<=n)c[x]+=y,x+=(x&-x);
}
inline int ask(int x){
	int res=0;
	while(x)res+=c[x],x-=(x&-x);
	return res;
}
vector<data>v1[N],v2[N];
inline void add_k(int l,int r,int z){
//	if(l>r) return;
	for(int i=l;i<=min(s*fr[l],r);++i)c[i]+=z;
	if(fr[l]!=fr[r])for(int i=s*(fr[r]-1)+1;i<=r;++i)c[i]+=z;
	for(int i=fr[l]+1;i<fr[r];++i)sum[i]+=z;
}
signed main(){
//	freopen("aa.in", "r", stdin);
//	freopen("aa.out", "w", stdout);
	n=read(),m=read();s=sqrt(n);
	for(int i=1;i<=n;++i)a[i]=tmp[i]=read(),fr[i]=(i-1)/s+1;
	sort(tmp+1,tmp+n+1);int ll=unique(tmp+1,tmp+n+1)-tmp-1;
	for(int i=1;i<=n;++i)a[i]=lower_bound(tmp+1,tmp+ll+1,a[i])-tmp;
	for(int i=1;i<=m;++i)q[i].l=read(),q[i].r=read(),q[i].id=i,bel[i]=(q[i].l-1)/s+1;
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;++i){
		if(r<q[i].r)v1[l].push_back(data{r+1,q[i].r,1,q[i].id});
		if(r>q[i].r)v1[l].push_back(data{q[i].r+1,r,-1,q[i].id});
		r=q[i].r;
		if(l<q[i].l)v2[r].push_back(data{l,q[i].l-1,-1,q[i].id});
		if(l>q[i].l)v2[r].push_back(data{q[i].l,l-1,1,q[i].id});
		l=q[i].l;
	}
	for(int i=1;i<=n;++i)b[i]=ask(n)-ask(a[i]),add(a[i],1);
	memset(c,0,sizeof(c));
	for(int i=n;i;--i)d[i]=ask(a[i]-1),add(a[i],1);
	memset(c,0,sizeof(c));
	for(int i=1;i<=n;++i){
		for(int j=0;j<v1[i].size();++j)
		for(int k=v1[i][j].l;k<=v1[i][j].r;++k)
		ans[v1[i][j].id]+=v1[i][j].v*(b[k]-c[a[k]]-sum[fr[a[k]]]);
		add_k(1,a[i]-1,1);
	}
	memset(c,0,sizeof(c)),memset(sum,0,sizeof(sum));
	for(int i=n;i;--i){
		for(int j=0;j<v2[i].size();++j)
		for(int k=v2[i][j].l;k<=v2[i][j].r;++k)
		ans[v2[i][j].id]+=v2[i][j].v*(d[k]-c[a[k]]-sum[fr[a[k]]]);
		add_k(a[i]+1,ll,1);
	}
	for(int i=2;i<=m;++i)ans[q[i].id]+=ans[q[i-1].id];
	for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
	return 0;
}

但是把ans开大400能过

#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int n,m,a[N],s,tmp[N],bel[N],fr[N];
LL b[N],d[N],c[N],ans[N+400],sum[N];
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return res;
}
struct p{
	int l,r,id;
}q[N];
inline bool cmp(p x,p y){
	if(bel[x.id]!=bel[y.id])return bel[x.id]<bel[y.id];return x.r<y.r;
}
struct data{
	int l,r,v,id;
};
inline void add(int x,int y){
	while(x<=n)c[x]+=y,x+=(x&-x);
}
inline int ask(int x){
	int res=0;
	while(x)res+=c[x],x-=(x&-x);
	return res;
}
vector<data>v1[N],v2[N];
inline void add_k(int l,int r,int z){
//	if(l>r) return;
	for(int i=l;i<=min(s*fr[l],r);++i)c[i]+=z;
	if(fr[l]!=fr[r])for(int i=s*(fr[r]-1)+1;i<=r;++i)c[i]+=z;
	for(int i=fr[l]+1;i<fr[r];++i)sum[i]+=z;
}
signed main(){
//	freopen("aa.in", "r", stdin);
//	freopen("aa.out", "w", stdout);
	n=read(),m=read();s=sqrt(n);
	for(int i=1;i<=n;++i)a[i]=tmp[i]=read(),fr[i]=(i-1)/s+1;
	sort(tmp+1,tmp+n+1);int ll=unique(tmp+1,tmp+n+1)-tmp-1;
	for(int i=1;i<=n;++i)a[i]=lower_bound(tmp+1,tmp+ll+1,a[i])-tmp;
	for(int i=1;i<=m;++i)q[i].l=read(),q[i].r=read(),q[i].id=i,bel[i]=(q[i].l-1)/s+1;
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;++i){
		if(r<q[i].r)v1[l].push_back(data{r+1,q[i].r,1,q[i].id});
		if(r>q[i].r)v1[l].push_back(data{q[i].r+1,r,-1,q[i].id});
		r=q[i].r;
		if(l<q[i].l)v2[r].push_back(data{l,q[i].l-1,-1,q[i].id});
		if(l>q[i].l)v2[r].push_back(data{q[i].l,l-1,1,q[i].id});
		l=q[i].l;
	}
	for(int i=1;i<=n;++i)b[i]=ask(n)-ask(a[i]),add(a[i],1);
	memset(c,0,sizeof(c));
	for(int i=n;i;--i)d[i]=ask(a[i]-1),add(a[i],1);
	memset(c,0,sizeof(c));
	for(int i=1;i<=n;++i){
		for(int j=0;j<v1[i].size();++j)
		for(int k=v1[i][j].l;k<=v1[i][j].r;++k)
		ans[v1[i][j].id]+=v1[i][j].v*(b[k]-c[a[k]]-sum[fr[a[k]]]);
		add_k(1,a[i]-1,1);
	}
	memset(c,0,sizeof(c)),memset(sum,0,sizeof(sum));
	for(int i=n;i;--i){
		for(int j=0;j<v2[i].size();++j)
		for(int k=v2[i][j].l;k<=v2[i][j].r;++k)
		ans[v2[i][j].id]+=v2[i][j].v*(d[k]-c[a[k]]-sum[fr[a[k]]]);
		add_k(a[i]+1,ll,1);
	}
	for(int i=2;i<=m;++i)ans[q[i].id]+=ans[q[i-1].id];
	for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
	return 0;
}

加上add_k中的if(l==r)return;也能过

#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int n,m,a[N],s,tmp[N],bel[N],fr[N];
LL b[N],d[N],c[N],ans[N],sum[N];
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return res;
}
struct p{
	int l,r,id;
}q[N];
inline bool cmp(p x,p y){
	if(bel[x.id]!=bel[y.id])return bel[x.id]<bel[y.id];return x.r<y.r;
}
struct data{
	int l,r,v,id;
};
inline void add(int x,int y){
	while(x<=n)c[x]+=y,x+=(x&-x);
}
inline int ask(int x){
	int res=0;
	while(x)res+=c[x],x-=(x&-x);
	return res;
}
vector<data>v1[N],v2[N];
inline void add_k(int l,int r,int z){
	if(l>r) return;
	for(int i=l;i<=min(s*fr[l],r);++i)c[i]+=z;
	if(fr[l]!=fr[r])for(int i=s*(fr[r]-1)+1;i<=r;++i)c[i]+=z;
	for(int i=fr[l]+1;i<fr[r];++i)sum[i]+=z;
}
signed main(){
//	freopen("aa.in", "r", stdin);
//	freopen("aa.out", "w", stdout);
	n=read(),m=read();s=sqrt(n);
	for(int i=1;i<=n;++i)a[i]=tmp[i]=read(),fr[i]=(i-1)/s+1;
	sort(tmp+1,tmp+n+1);int ll=unique(tmp+1,tmp+n+1)-tmp-1;
	for(int i=1;i<=n;++i)a[i]=lower_bound(tmp+1,tmp+ll+1,a[i])-tmp;
	for(int i=1;i<=m;++i)q[i].l=read(),q[i].r=read(),q[i].id=i,bel[i]=(q[i].l-1)/s+1;
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;++i){
		if(r<q[i].r)v1[l].push_back(data{r+1,q[i].r,1,q[i].id});
		if(r>q[i].r)v1[l].push_back(data{q[i].r+1,r,-1,q[i].id});
		r=q[i].r;
		if(l<q[i].l)v2[r].push_back(data{l,q[i].l-1,-1,q[i].id});
		if(l>q[i].l)v2[r].push_back(data{q[i].l,l-1,1,q[i].id});
		l=q[i].l;
	}
	for(int i=1;i<=n;++i)b[i]=ask(n)-ask(a[i]),add(a[i],1);
	memset(c,0,sizeof(c));
	for(int i=n;i;--i)d[i]=ask(a[i]-1),add(a[i],1);
	memset(c,0,sizeof(c));
	for(int i=1;i<=n;++i){
		for(int j=0;j<v1[i].size();++j)
		for(int k=v1[i][j].l;k<=v1[i][j].r;++k)
		ans[v1[i][j].id]+=v1[i][j].v*(b[k]-c[a[k]]-sum[fr[a[k]]]);
		add_k(1,a[i]-1,1);
	}
	memset(c,0,sizeof(c)),memset(sum,0,sizeof(sum));
	for(int i=n;i;--i){
		for(int j=0;j<v2[i].size();++j)
		for(int k=v2[i][j].l;k<=v2[i][j].r;++k)
		ans[v2[i][j].id]+=v2[i][j].v*(d[k]-c[a[k]]-sum[fr[a[k]]]);
		add_k(a[i]+1,ll,1);
	}
	for(int i=2;i<=m;++i)ans[q[i].id]+=ans[q[i-1].id];
	for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
	return 0;
}

这是怎么一回事?