一个神奇的问题
查看原帖
一个神奇的问题
925818
hjhAKIOI楼主2024/10/22 21:38

我的代码在 Luogu 能过,为啥在 AcWing 上会 Segmentation Fault?(数组明明开得很大了 QAQ

#include<iostream>
#include<algorithm>
using namespace std;
const int Q=2e5+5,N=2e6+5;
int s,n,tq,tot;
int c[N],ans[Q];

struct Query{
	int x,y,z,op;
}q[Q],tmp[Q];

bool cmp(Query a,Query b){
	if(a.x!=b.x) return a.x<b.x;
	if(!a.op) return 1;
	if(!b.op) return 0;
	return a.y<b.y;
}

void add(int x,int v){
	for(;x<=n;x+=x&-x) c[x]+=v;
}

int ask(int x){
	int res=0;
	for(;x;x-=x&-x) res+=c[x];
	return res;
}

void solve(int ed){
	for(int i=1;i<=ed;i++){
		if(!tmp[i].op){
			add(tmp[i].y,tmp[i].z);
		}
		else{
			ans[tmp[i].z]+=ask(tmp[i].y)*tmp[i].op;
		}
	}
	for(int i=1;i<=ed;i++){
		if(!tmp[i].op){
			add(tmp[i].y,-tmp[i].z);
		}
	}
}

void cdq(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	int t=0;
	for(int i=l;i<=r;i++){
		if(i<=mid&&!q[i].op||i>mid&&q[i].op){
			tmp[++t]=q[i];
		}
	}
	sort(tmp+1,tmp+t+1,cmp);
	solve(t);
}

int main(){
	cin>>s>>n;
	int op;
	while(cin>>op){
		if(op==3) break;
		if(op==1){
			int x,y,d;
			cin>>x>>y>>d;
			q[++tq]={x,y,d,0};
		}
		else{
			int x,y,x2,y2;
			cin>>x>>y>>x2>>y2;
			tot++;
			q[++tq]={x2,y2,tot,1};
			q[++tq]={x2,y-1,tot,-1};
			q[++tq]={x-1,y2,tot,-1};
			q[++tq]={x-1,y-1,tot,1};
		}
	}
	cdq(1,tq);
	for(int i=1;i<=tot;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}
2024/10/22 21:38
加载中...