gym101630a

http://codeforces.com/gym/101630/attachments

一道树套树的题目。

先考虑把x轴坐标离散化。由于里面的圆不能相交，我们可以惊喜的发现：同一个纵坐标的圆最多是log个数的！！

具体证明：http://neerc.ifmo.ru/archive/2017/neerc-2017-analysis.pdf

然后呢。。我们可以线段树维护区间，每个节点维护set（vector也可以的！！）

然后呢。。就可以直接写了。。。

反省：还是想不到思路。。看了题解。。并且和别人写的比起来，我的长了一倍。代码能力？？？

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cctype>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iomanip>
#include<sstream>
#include<cstdlib>
#include<ctime>
#include<list>
#include<deque>
#include<bitset>
#include<fstream>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair<int,int >
#define iiii pair<int,pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i,x) for(int (i)=0;(i)<(x);(i)++)
#define all(x) (x).begin(),(x).end()
inline int getint()
{
int x=0,p=1;char c=getchar();
while (c<=32)c=getchar();
if(c==45)p=-p,c=getchar();
while (c>32)x=x*10+c-48,c=getchar();
return x*p;
}
using namespace std;
//
const int maxn=4e5+5;
int t,n;
int X[maxn],Y[maxn],op[maxn];
set<int>dat[maxn<<2];
vector<int>ord;
//
inline bool isok(int id1,int id)
{
ull ans1=1ll*(1ull*X[id1]-X[id])*(1ull*X[id1]-X[id])+(1ull*Y[id1]-Y[id])*(1ull*Y[id1]-Y[id]),ans2=1ull*Y[id]*Y[id];
if(ans1<ans2)return true;
return false;
}
void fM(int x,int y,int l,int r,int k,int id)
{
if(r<=x||y<=l)return;
if(x<=l&&r<=y)
{
if(id<0)id=-id-1,dat[k].erase(id);
else dat[k].insert(id-1);
}
else
{
fM(x,y,l,(l+r)>>1,2*k+1,id);
fM(x,y,(l+r)>>1,r,2*k+2,id);
}
}
int fQ(int id,int x,int l,int r,int k)
{
//cout<<l<<" "<<r<<" "<<k<<endl;
if(x<l||x>=r)return -2;
else
{
for(set<int>::iterator it=dat[k].begin();it!=dat[k].end();it++)
{
if(isok(id,*it))
{
int ans=*it;
int L=lower_bound(all(ord),X[ans]-Y[ans])-ord.begin();
int R=lower_bound(all(ord),X[ans]+Y[ans])-ord.begin();
fM(L,R+1,0,n,0,-(ans+1));
return ans;
}
}
if(r-l==1)return -2;
int lx=fQ(id,x,l,(l+r)>>1,2*k+1);
int ly=fQ(id,x,(l+r)>>1,r,2*k+2);
return max(lx,ly);
}
}
int main()
{
t=getint();
rep(i,t)
{
op[i]=getint(),X[i]=getint(),Y[i]=getint();
if(op[i]==2)ord.emplace_back(X[i]);
else ord.emplace_back(X[i]-Y[i]),ord.emplace_back(X[i]+Y[i]);
}
sort(ord.begin(),ord.end());
ord.resize(unique(ord.begin(),ord.end())-ord.begin());n=ord.size();
rep(i,t)
{
if(op[i]==2)printf("%dn",fQ(i,lower_bound(all(ord),X[i])-ord.begin()+1,0,n,0)+1);
else
{
int L=lower_bound(all(ord),X[i]-Y[i])-ord.begin();
int R=lower_bound(all(ord),X[i]+Y[i])-ord.begin();
fM(L,R+1,0,n,0,i+1);
}
}
return 0;
}

最后

以上就是想人陪楼房为你收集整理的gym101630a的全部内容，希望文章能够帮你解决gym101630a所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。