疑问
查看原帖
疑问
448884
快乐的大童楼主2023/8/15 20:46

两份代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0);
#define OTIE cout.tie(0);
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P__ puts("")
#define PU puts("--------------------")
#define popc __builtin_popcount
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)
#define reprange(a,b,c,d) for(int a=b;a<=c;a+=d)
#define perrange(a,b,c,d) for(int a=b;a>=c;a-=d)
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x);
#define int long long
//#define int __int128
using namespace std;
inline int rd(){
	int x=0,f=1;int ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;
}
inline void write(int x,char ch='\0'){
	if(x<0){x=-x;putchar('-');}
	int y=0;char z[40];
	while(x||!y){z[y++]=x%10+48;x/=10;}
	while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
const int maxn=5e6+5,maxm=2147483648;
int n,m,ans[maxn];
struct node{
	int x,y,c,id,ans;
	bool tp;
}a[maxn],b[maxn];
bool operator<(node p,node q){
	if(p.x!=q.x) return p.x<q.x;
	else if(p.y!=q.y) return p.y<q.y;
	return p.c>q.c;
}
bool cmp(node p,node q){
	if(p.y!=q.y) return p.y<q.y;
	return p.c>q.c;
}
void cdq(int l,int r){
	if(l==r) return;
	int mid=l+r>>1;cdq(l,mid),cdq(mid+1,r);
	int p=l,sum=0;
	rep(i,mid+1,r)if(a[i].tp){
		while(p<=mid&&a[p].y<=a[i].y){
			if(!a[p].tp) sum+=a[p].c;
			p++;
		}
		a[i].ans+=sum;
	}
	int pp=mid+1,tot=0;p=l;
	while(p<=mid&&pp<=r){
		if(cmp(a[p],a[pp])) b[++tot]=a[p++];
		else b[++tot]=a[pp++];
	}
	while(p<=mid)b[++tot]=a[p++];
	while(pp<=r)b[++tot]=a[pp++];
	rep(i,1,tot)a[i+l-1]=b[i];
}
signed main(){
	n=rd(),m=rd();int tot=0;
	rep(i,1,n){
		int x=rd(),y=rd(),c=rd();
		a[++tot]=(node){x,y,c,0,0,0};
	}
	rep(i,1,m){
		int x1=rd(),y1=rd(),x2=rd(),y2=rd();
		a[++tot]=(node){x2,y2,1,i,0,1};
		a[++tot]=(node){x1-1,y2,-1,i,0,1};
		a[++tot]=(node){x2,y1-1,-1,i,0,1};
		a[++tot]=(node){x1-1,y1-1,1,i,0,1};
	}
	sort(a+1,a+tot+1);cdq(1,tot);
	rep(i,1,tot)if(a[i].tp)ans[a[i].id]+=a[i].c*a[i].ans;
	rep(i,1,m)write(ans[i],10);
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0);
#define OTIE cout.tie(0);
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P__ puts("")
#define PU puts("--------------------")
#define popc __builtin_popcount
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)
#define reprange(a,b,c,d) for(int a=b;a<=c;a+=d)
#define perrange(a,b,c,d) for(int a=b;a>=c;a-=d)
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x);
#define int long long
//#define int __int128
using namespace std;
inline int rd(){
	int x=0,f=1;int ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;
}
inline void write(int x,char ch='\0'){
	if(x<0){x=-x;putchar('-');}
	int y=0;char z[40];
	while(x||!y){z[y++]=x%10+48;x/=10;}
	while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
const int maxn=5e6+5,maxm=2147483648;
int n,m,ans[maxn];
struct node{
	int x,y,c,id,ans;
	bool tp;
}a[maxn],b[maxn];
bool operator<(node p,node q){
	if(p.x!=q.x) return p.x<q.x;
	else if(p.y!=q.y) return p.y<q.y;
	return p.c<q.c;
}
bool cmp(node p,node q){
	if(p.y!=q.y) return p.y<q.y;
	return p.c<q.c;
}
void cdq(int l,int r){
	if(l==r) return;
	int mid=l+r>>1;cdq(l,mid),cdq(mid+1,r);
	int p=l,sum=0;
	rep(i,mid+1,r)if(a[i].tp){
		while(p<=mid&&a[p].y<=a[i].y){
			if(!a[p].tp) sum+=a[p].c;
			p++;
		}
		a[i].ans+=sum;
	}
	int pp=mid+1,tot=0;p=l;
	while(p<=mid&&pp<=r){
		if(cmp(a[p],a[pp])) b[++tot]=a[p++];
		else b[++tot]=a[pp++];
	}
	while(p<=mid)b[++tot]=a[p++];
	while(pp<=r)b[++tot]=a[pp++];
	rep(i,1,tot)a[i+l-1]=b[i];
}
signed main(){
	n=rd(),m=rd();int tot=0;
	rep(i,1,n){
		int x=rd(),y=rd(),c=rd();
		a[++tot]=(node){x,y,c,0,0,0};
	}
	rep(i,1,m){
		int x1=rd(),y1=rd(),x2=rd(),y2=rd();
		a[++tot]=(node){x2,y2,1,i,0,1};
		a[++tot]=(node){x1-1,y2,-1,i,0,1};
		a[++tot]=(node){x2,y1-1,-1,i,0,1};
		a[++tot]=(node){x1-1,y1-1,1,i,0,1};
	}
	sort(a+1,a+tot+1);cdq(1,tot);
	rep(i,1,tot)if(a[i].tp)ans[a[i].id]+=a[i].c*a[i].ans;
	rep(i,1,m)write(ans[i],10);
}

两份代码的唯一区别在于,前者 cmp 函数中在坐标相同的前提下是优先前置询问,后者是优先前置修改,前者 100 分,后者 70 分(WA on 1,2,3),但题解区前面几篇题解都说要前置修改。求大佬解答。

2023/8/15 20:46
加载中...