社区讨论

一个xiao问题

P3755[CQOI2017] 老C的任务参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mivfvyia
此快照首次捕获于
2025/12/07 16:07
2 个月前
此快照最后确认于
2025/12/10 15:15
2 个月前
查看原帖
RT。用梳妆数组做的。
排序按下面的排:
CPP
	bool operator < (Node y) const{
		if(a==y.a){
			if(b==y.b) return (s>y.s);
			else return (b<y.b);
		}
		else{
			return (a<y.a);
		}
	}
下面的代码AC了:
CPP
	for(int i=1;i<=n;i++){
		mp[{q[i].a,q[i].b}]=sum(q[i].b);
		add(q[i].b,q[i].s);
	}
下面的代码WA了:
CPP
	for(int i=1;i<=n;i++){
		add(q[i].b,q[i].s);
		mp[{q[i].a,q[i].b}]=sum(q[i].b);
	}
区别在于,前者先询问,后者先修改。
但为什么先修改WA了,不应该先修改再询问吗?
完整WA代码:
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define int long long
typedef pair<int,int> PII;
int n,m,tot;
map<int,int> num;
map<PII,int> mp;
struct Node{
	int a,b;
	long long s;
	bool operator < (Node y) const{
		if(a==y.a){
			if(b==y.b) return (s>y.s);
			else return (b<y.b);
		}
		else{
			return (a<y.a);
		}
	}
	bool operator == (Node y) const{
		return (a==y.a&&b==y.b);
	}
}q[N];
struct Question{
	int a,b,c,d;
}Ques[N];
vector<int> Num;
long long tr[N];
void add(int x,int y){
	for(int i=x;i<=tot;i+=(i&(-i))) tr[i]+=y;
}
int sum(int x){
	long long res=0;
	for(int i=x;i;i-=(i&(-i))) res+=tr[i];
	return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int a,b,s;
		cin>>a>>b>>s;
		Num.push_back(a);Num.push_back(b);
		q[i].a=a,q[i].b=b,q[i].s=s;
	}
	for(int i=1;i<=m;i++){
		int a,b,c,d;
		cin>>c>>d>>a>>b;
		Num.push_back(a);Num.push_back(b);
		Num.push_back(c);Num.push_back(d);
		Num.push_back(c-1);Num.push_back(d-1);
		Ques[i]={a,b,c,d};
		q[n+i*4-3].a=a,q[n+i*4-3].b=d-1;
		q[n+i*4-2].a=c-1,q[n+i*4-2].b=b;
		q[n+i*4-1].a=a,q[n+i*4-1].b=b;
		q[n+i*4].a=c-1,q[n+i*4].b=d-1;
	}
	sort(Num.begin(),Num.end());
	vector<int>::iterator pos=unique(Num.begin(),Num.end());
	for(vector<int>::iterator it=Num.begin();it<pos;it++){
		tot++;
		num[*it]=tot;
	}
	for(int i=1;i<=n;i++){
		q[i].a=num[q[i].a],q[i].b=num[q[i].b];
	}
	for(int i=1;i<=m;i++){
		int a=Ques[i].a,b=Ques[i].b,c=Ques[i].c,d=Ques[i].d;
		q[n+i*4-3].a=num[a],q[n+i*4-3].b=num[d-1];
		q[n+i*4-2].a=num[c-1],q[n+i*4-2].b=num[b];
		q[n+i*4-1].a=num[a],q[n+i*4-1].b=num[b];
		q[n+i*4].a=num[c-1],q[n+i*4].b=num[d-1];
	}
	n+=4*m;
	sort(q+1,q+n+1);
	for(int i=1;i<=n;i++){
		add(q[i].b,q[i].s);
		mp[{q[i].a,q[i].b}]=sum(q[i].b);
	}
	for(int i=1;i<=m;i++){
		int a=num[Ques[i].a],b=num[Ques[i].b],c=num[Ques[i].c-1],d=num[Ques[i].d-1];
		cout<<mp[{a,b}]-mp[{c,b}]-mp[{a,d}]+mp[{c,d}]<<'\n';
	}
	return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...