Link.
Description.
给一个初始为空的整点集, 现在有 \(n\) 次操作
- 向点集中插入点 \((x,y)\)
- 从点集中删除点 \((x,y)\)
- 问至少需添加多少点满足图像关于 \((0,0)\) 和 \((x,y)\) 连成的直线对称
每次询问并没有把点加入点集中，每个询问是独立的。
Solution.
牛逼题。
首先有一个 \(O(Q^2\text{poly}(\log))\) 的做法。
就是插入一个点 \(O(Q)\) 更新它和它所在圆上所有点所形成的直线的答案。
删除同理。
经过一通分析，它能过！
因为 \(x,y\in\mathbb N\)，所以 \(x^2+y^2=r\) 的解数很少。
然后就做完了。
Coding.
点击查看代码
//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
if(f) x=-x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
struct pt
{
int x,y;char operator<(pt b) const {return x^b.x?x<b.x:y<b.y;}
inline pt operator+(pt b) {return(pt){x+b.x,y+b.y};}
inline pt operator-(pt b) {return(pt){x-b.x,y-b.y};}
inline pt fac() {int g=__gcd(x,y);return(pt){x/g,y/g};}
inline void fc() {int g=__gcd(x,y);x/=g,y/=g;}
};
map<pt,int>mp;
map<ll,set<pt> >vc;
int main()
{
int Ca,tot=0;for(read(Ca);Ca--;)
{
int fg,x,y;read(fg,x,y);
if(fg==3) {printf("%d\n",tot-mp[((pt){x,y}).fac()]);continue;}
if(fg==1)
{
tot++;set<pt>&r=vc[1ll*x*x+1ll*y*y];
for(auto w:r) mp[(w+(pt){x,y}).fac()]+=2;
mp[((pt){x,y}).fac()]++,r.insert((pt){x,y});
}
else
{
tot--;set<pt>&r=vc[1ll*x*x+1ll*y*y];
r.erase((pt){x,y}),mp[((pt){x,y}).fac()]--;
for(auto w:r) mp[(w+(pt){x,y}).fac()]-=2;
}
}return 0;
}