社区讨论
一个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 条回复,欢迎继续交流。
正在加载回复...