题目 Ann and Books

用 sort 会 Runtime error on test 68

但换成手写的 qsort 后就过了。

RE code

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N=500005;
int n,m,k,asd[N],mns_k[N],add_k[N],ori[N];
long long a[N],c[3*N],tot,val[N],cnt,ans[N];
struct query{int l,r,id;} q[N];
map<long long,long long>vis;
inline long long readll()
{
	long long x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
bool is_test_68;
bool cmp(query x,query y){return (x.l/k!=y.l/k?x.l/k<y.l/k:(((x.l/k)&1)^(x.r>y.r)));}
void add(int x,int y){tot+=c[y],c[ori[x]]++;}
//void qsort(query a[],int l, int r)
//{
//	if (l>=r)return;
//	int i=l;
//	int j=r;
//	srand(time(0));
//	int k=rand()%(j-i+1)+i; 
//	query key=a[k]; 
//	a[k]=a[l];
//	while (i<j)
//	{
//		while (i<j && !cmp(a[j],key)) j--;  
//		a[i]=a[j];
//		while (i<j && cmp(a[i],key)) i++; 
//		a[j]=a[i];
//	}
//	a[i]=key; 
//	qsort(a,l,i-1);
//	qsort(a,i+1,r);
//}
void sub(int x,int y){c[ori[x]]--,tot-=c[y];}
signed main()
{
//	freopen("a.txt","r",stdin);
	n=read(),m=read();asd[1]=1;
	for(int i=1;i<=n;i++)a[i]=(readll()%2)*2-1;
	is_test_68=(n==100000&&m==0&&a[5]==-1);
	for(int i=1;i<=n;i++)val[i]=val[i-1]+a[i]*readll();
	for(int i=0;i<=n;i++)
	{
		long long x=val[i]+m,y=val[i],z=val[i]+2*m;
		if(!vis[x])vis[x]=++cnt;
		if(!vis[y])vis[y]=++cnt;
		if(!vis[z])vis[z]=++cnt;
		ori[i]=vis[x],mns_k[i]=vis[y],add_k[i]=vis[z];
	}
//	cout<<1;
	int t=read();k=sqrt(t);
	for(int i=1,x,y;i<=t;i++)
	{
		x=read()-1,y=read();
		q[i]={x,y,i};
	}
	int L=1,R=0;
//	cout<<1;
	assert(k>0&&0<=t&&t<=N-5);
//	qsort(q,1,t);
	sort(q+1,q+t+1,cmp);
//	cout<<1;
//	if(is_test_68){cout<<asd[N-1];return 0;}
	for(int i=1;i<=t;i++)
	{
		while(R<q[i].r) R++,add(R,mns_k[R]);
		while(L>q[i].l) L--,add(L,add_k[L]);
		while(R>q[i].r) sub(R,mns_k[R]),R--;
		while(L<q[i].l) sub(L,add_k[L]),L++;
		ans[q[i].id]=tot;
	}
	for(int i=1;i<=t;i++)cout<<ans[i]<<"\n";
	return 0;
}

AC code

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N=500005;
int n,m,k,asd[N],mns_k[N],add_k[N],ori[N];
long long a[N],c[3*N],tot,val[N],cnt,ans[N];
struct query{int l,r,id;} q[N];
map<long long,long long>vis;
inline long long readll()
{
    long long x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
bool is_test_68;
bool cmp(query x,query y){return (x.l/k!=y.l/k?x.l/k<y.l/k:(((x.l/k)&1)^(x.r>y.r)));}
void add(int x,int y){tot+=c[y],c[ori[x]]++;}
void qsort(query a[],int l, int r)
{
	if (l>=r)return;
	int i=l;
	int j=r;
	srand(time(0));
	int k=rand()%(j-i+1)+i; 
	query key=a[k]; 
	a[k]=a[l];
	while (i<j)
	{
		while (i<j && !cmp(a[j],key)) j--;  
		a[i]=a[j];
		while (i<j && cmp(a[i],key)) i++; 
		a[j]=a[i];
	}
	a[i]=key; 
	qsort(a,l,i-1);
	qsort(a,i+1,r);
}
void sub(int x,int y){c[ori[x]]--,tot-=c[y];}
signed main()
{
//	freopen("a.txt","r",stdin);
    n=read(),m=read();asd[1]=1;
    for(int i=1;i<=n;i++)a[i]=(readll()%2)*2-1;
    is_test_68=(n==100000&&m==0&&a[5]==-1);
    for(int i=1;i<=n;i++)val[i]=val[i-1]+a[i]*readll();
    for(int i=0;i<=n;i++)
    {
        long long x=val[i]+m,y=val[i],z=val[i]+2*m;
        if(!vis[x])vis[x]=++cnt;
        if(!vis[y])vis[y]=++cnt;
        if(!vis[z])vis[z]=++cnt;
        ori[i]=vis[x],mns_k[i]=vis[y],add_k[i]=vis[z];
    }
//    cout<<1;
    int t=read();k=sqrt(t);
    for(int i=1,x,y;i<=t;i++)
	{
		x=read()-1,y=read();
		q[i]={x,y,i};
	}
    int L=1,R=0;
//    cout<<1;
	assert(k>0&&0<=t&&t<=N-5);
    qsort(q,1,t);
//    cout<<1;
//    if(is_test_68){cout<<asd[N-1];return 0;}
    for(int i=1;i<=t;i++)
    {
        while(R<q[i].r) R++,add(R,mns_k[R]);
        while(L>q[i].l) L--,add(L,add_k[L]);
        while(R>q[i].r) sub(R,mns_k[R]),R--;
        while(L<q[i].l) sub(L,add_k[L]),L++;
        ans[q[i].id]=tot;
    }
    for(int i=1;i<=t;i++)cout<<ans[i]<<"\n";
    return 0;
}

有知道的大佬能解释一下吗？谢谢