社区讨论

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 条回复,欢迎继续交流。

正在加载回复...