社区讨论
P2163为什么一直调不出来qwq,求助+玄关
题目总版参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mhj0qod4
- 此快照首次捕获于
- 2025/11/03 18:50 4 个月前
- 此快照最后确认于
- 2025/11/03 18:50 4 个月前
我是用的扫描线求二维数点的法。
大致想法是离散化一下,然后就按照P10814的模板做法写
CPP#include <bits/stdc++.h>
#define lowbit (-i&i)
using namespace std;
const int N=5e5+10;
struct node1{
int x,id,val,id2;
};
struct node2{
int a,b,c,d;
}q[N];
int n,m,ans[N][2],t[N],X[N],Y[N],cntx,cnty,numx,numy;
pair<int,int> p[N];
vector<int> vec[N];
vector<node1> ques[N];
inline void add(int x)
{
for(int i=x;i<=numy;i+=lowbit) t[i]++;
}
inline int ask(int x)
{
int res=0;
for(int i=x;i>=1;i-=lowbit) res+=t[i];
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;x++,y++;
p[i]={x,y};
X[++cntx]=x,Y[++cnty]=y;
}
for(int i=1;i<=m;i++)
{
cin>>q[i].c>>q[i].b>>q[i].a>>q[i].d;
q[i].a++,q[i].b++,q[i].c++,q[i].d++;
X[++cntx]=q[i].a,X[++cntx]=q[i].c,X[++cntx]=q[i].a-1,X[++cntx]=q[i].c-1;
Y[++cnty]=q[i].b,Y[++cnty]=q[i].d,Y[++cnty]=q[i].b-1,Y[++cnty]=q[i].d-1;
}
sort(X+1,X+cntx+1),sort(Y+1,Y+cnty+1);
numx=unique(X+1,X+cntx+1)-X-1;
numy=unique(Y+1,Y+cnty+1)-Y-1;
for(int i=1;i<=n;i++)
{
p[i].first=lower_bound(X+1,X+numx+1,p[i].first)-X;
p[i].second=lower_bound(Y+1,Y+numy+1,p[i].second)-Y;
vec[p[i].first].push_back(p[i].second);
}
for(int i=1;i<=m;i++)
{
q[i].a=lower_bound(X+1,X+numx+1,q[i].a)-X;
q[i].c=lower_bound(X+1,X+numx+1,q[i].c)-X;
q[i].b=lower_bound(Y+1,Y+numy+1,q[i].b)-Y;
q[i].d=lower_bound(Y+1,Y+numy+1,q[i].d)-Y;
}
for(int i=1;i<=m;i++)
{
ques[q[i].b-1].push_back({q[i].a,i,-1,0});
ques[q[i].b-1].push_back({q[i].c-1,i,-1,1});
ques[q[i].d].push_back({q[i].a,i,1,0});
ques[q[i].d].push_back({q[i].c-1,i,1,1});
}
for(int i=0;i<=numx;i++)
{
for(int j=0;j<vec[i].size();j++) add(vec[i][j]);
for(int j=0;j<ques[i].size();j++)
{
ans[ques[i][j].id][ques[i][j].id2]+=ques[i][j].val*ask(ques[i][j].x);
}
}
//调试开始:
cerr<<"vec:"<<'\n';
for(int i=0;i<=numx;i++)
{
cerr<<i<<": ";
for(int j=0;j<vec[i].size();j++) cerr<<vec[i][j]<<" ";
cerr<<'\n';
}
cerr<<"ques:"<<'\n';
for(int i=0;i<=numx;i++)
{
for(int j=0;j<ques[i].size();j++)
{
cerr<<i<<": ";
cerr<<ques[i][j].x<<" "<<ques[i][j].id<<" "<<ques[i][j].val<<" "<<ques[i][j].id2<<'\n';
}
cerr<<'\n';
}
cerr<<"anser:"<<'\n';
for(int i=1;i<=m;i++) cerr<<i<<": "<<ans[i][0]<<" "<<ans[i][1]<<'\n';
//调试结束。
for(int i=1;i<=m;i++) cout<<ans[i][0]-ans[i][1]<<'\n';
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...