今年的APIO好邪啊。
T1铁人两项
题目大意
给一个无向图，问有多少三元组(三个元素两两不同)使得它们构成一条简单路径 。
题解
无向图这种东西不好直接处理，考虑点双缩点建圆方树。
然后就出现了一个比较神的做法，把方点点权设为点双大小，圆点点权设为-1，那么我们枚举三元组中的起点和终点，那么这条路径的权值就是可能的中间点个数。
为什么？考虑两种圆点。
1、起点和终点，因为它们已经被当成三元组中的元素了，所以我们要在和它们相邻的点双中减掉它们，所以这个减一是对的。
2、其他圆点，这些圆点会被相邻的两个点双算两次，所以我们要减一。
发现我们只需算出每个点的贡献和，然后可以算每个点被覆盖了多少次再乘上权值就可以了。
代码
#include<iostream>
#include<cstdio>
#define N 210002
using namespace std;
typedef long long ll;
ll ans,size[N],val[N],sum;
int head[N],h[N],st[N],tot,tot1,top,n,m,num,dfn[N],low[N],tott;
struct edge{
int n,to;
}e[N*],E[N*];
inline void add(int u,int v){
e[++tot].n=head[u];
e[tot].to=v;
head[u]=tot;
}
inline void add1(int u,int v){
E[++tot1].n=h[u];
E[tot1].to=v;
h[u]=tot1;
}
void tarjan(int u,int fa){
dfn[u]=low[u]=++tott;st[++top]=u;
val[u]=-;sum++;
for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){
int v=e[i].to;
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
add1(u,++num);int x=;val[num]=;
do{
x=st[top--];
val[num]++;
add1(num,x);
}
while(x!=v);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
void dfs(int u){
if(u<=n)size[u]=;
for(int i=h[u];i;i=E[i].n){
int v=E[i].to;
dfs(v);
ans+=2ll*size[u]*size[v]*val[u];
size[u]+=size[v];
}
ans+=2ll*size[u]*(sum-size[u])*val[u];
}
inline int rd(){
int x=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
int main(){
n=rd();m=rd();int u,v;num=n;
for(int i=;i<=m;++i){u=rd();v=rd();add(u,v);add(v,u);}
for(int i=;i<=n;++i)if(!dfn[i]){sum=;tarjan(i,);dfs(i);}
cout<<ans;
return ;
}
T2选圆圈
题目大意
给定n个圆，每次挑出半径最大的圆删除，同时删除和这个圆有交的所有圆，知道所有圆都被删除，求出每个圆是被那个圆删掉的。
题解
如果把它看成一道一般的计算几何题，会很麻烦。
如果会KD-tree的话，就好说了，直接建立KD-tree，每次在上面暴力找就好了。
树上维护最左和最右，找的时候判一下如果和最左最右都没有交就不往下找了。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 300002
using namespace std;
typedef long long ll;
int n,tot,ans[N];
inline ll rd(){
ll x=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
inline ll sq(ll x){return x*x;}
int now_x;
struct zb{
ll x[],r;int id;
bool operator <(const zb &b)const{
return x[now_x]<b.x[now_x];
}
}a[N];
inline bool cmp(zb a,zb b){if(a.r!=b.r)return a.r>b.r;else return a.id<b.id;}
struct node{
zb x;int ls,rs;ll mx[],mi[];
}tr[N];
inline void update(int p){
int ls=tr[p].ls,rs=tr[p].rs;
for(int i=;i<;++i){
tr[p].mx[i]=tr[p].x.x[i]+tr[p].x.r;
tr[p].mi[i]=tr[p].x.x[i]-tr[p].x.r;
if(ls){
tr[p].mx[i]=max(tr[p].mx[i],tr[ls].mx[i]);
tr[p].mi[i]=min(tr[p].mi[i],tr[ls].mi[i]);
}
if(rs){
tr[p].mx[i]=max(tr[p].mx[i],tr[rs].mx[i]);
tr[p].mi[i]=min(tr[p].mi[i],tr[rs].mi[i]);
}
}
}
int build(int l,int r,int tag){
if(l>r)return ;
int mid=(l+r)>>;
now_x=tag;
nth_element(a+l,a+mid+,a+r+);
int p=++tot;
tr[p].x=a[mid];
tr[p].ls=build(l,mid-,tag^);
tr[p].rs=build(mid+,r,tag^);
update(p); return p;
}
inline bool pd(int x,zb y){
if(tr[x].mx[]<y.x[]-y.r)return ;
if(tr[x].mx[]<y.x[]-y.r)return ;
if(tr[x].mi[]>y.x[]+y.r)return ;
if(tr[x].mi[]>y.x[]+y.r)return ;
return ;
}
inline bool check(zb x,zb y){
ll dis1=sq(x.x[]-y.x[])+sq(x.x[]-y.x[]),dis2=sq(x.r+y.r);
if(dis2>=dis1)return ;else return ;
}
void work(int p,zb x){
if(!ans[tr[p].x.id]&&check(tr[p].x,x))ans[tr[p].x.id]=x.id;
if(tr[p].ls&&pd(tr[p].ls,x))work(tr[p].ls,x);
if(tr[p].rs&&pd(tr[p].rs,x))work(tr[p].rs,x);
}
int main(){
n=rd();
for(int i=;i<=n;++i)a[i].x[]=rd(),a[i].x[]=rd(),a[i].r=rd(),a[i].id=i;
int root=build(,n,);
sort(a+,a+n+,cmp);
for(int i=;i<=n;++i)if(!ans[a[i].id]){
ans[a[i].id]=a[i].id;
work(root,a[i]);
}
for(int i=;i<=n;++i)printf("%d ",ans[i]);
return ;
}
T3新家
题目大意
给定n个四元组，表示每个商店的位置，类型，开门时间和关门时间，有若干次询问，每次问一个时间点上的一个位置的代价，代价指所有类型到这个点的最小距离的最大值。
上课时讲了一个NB的线段树分治的做法，但我现在仍不会。
这道题虽并不简单，但仍然有很多套路的地方在里面 。
题解
首先，一个区间我们把它拆成两个，在l和r+1处，然后把他们和询问放在一起按时间排序，这样我们就可以忽略时间的影响了。
然后我们考虑这样一个问题，给出一个数轴，里面有各种类型的点，给定询问点，求一个最小半径，使得半径以内有所有类型的点。
不难想到二分答案，然后直接做非常麻烦，考虑维护一个pre，记录上一个改类型的点出现的位置，这玩意我们可以用multiset维护。
当我们二分的答案mid合法时，需满足mid-pos<=pos-min(mid+1,n）后面的min是指后面区域内所有的pre，这个比较显然。
然后我们用线段树维护所有位置的min，每个节点用一个可删堆去维护在该位置的所有pre。
最好不要(或不能)离散化，要讨论好多种情况，直接动态开点就可以了。
优化
直接做是两个log的，瓶颈在查询上，去膜了kczno1的题解。
由于我们有了线段树，所以可以不用二分答案了，直接在线段树上二分，判一下mid+1是否合法，看一下是往左边走还是往右边走。
但为什么我的一个log跑的比两个log还慢？
代码
#include<iostream>
#include<cstdio>
#include<queue>
#include<set>
#include<algorithm>
#include<cstring>
#define N 300002
#define inf 2e8
using namespace std;
typedef long long ll;
int tr[N*],Ls[N*],Rs[N*],n,k,qu,tot,ans[N],ji,tong[N],gan,top,wei[N*],wen,root;
inline int rd(){
int x=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
struct node{
int tmp,pos,tim,tag;
bool operator <(const node &b)const{
if(tim!=b.tim)return tim<b.tim;
else return tag<b.tag;
}
}q[N<<];
struct HESP{
priority_queue<int,vector<int>,greater<int> >q1,q2;
inline void push(int x){q1.push(x);}
inline void del(int x){
q2.push(x);while(q2.size()&&q1.top()==q2.top())q1.pop(),q2.pop();
}
inline int top(){return q1.top();}
inline int size(){return q1.size()-q2.size();}
}h[N*];
multiset<int>s[N];
multiset<int>::iterator it,it2,it3;
void upd(int &cnt,ll l,ll r,int x,int x1,int x2){
if(!cnt)cnt=++top;
// cout<<cnt<<" "<<l<<" "<<r<<endl;
if(l==r){
// cout<<l<<" ";
if(!wei[cnt])wei[cnt]=++wen;
if(~x1)h[wei[cnt]].push(x1);
if(~x2)h[wei[cnt]].del(x2);
if(h[wei[cnt]].size())tr[cnt]=h[wei[cnt]].top();else tr[cnt]=inf;
// cout<<r<<endl;
return;
}
int mid=(l+r)>>;
if(mid>=x)upd(Ls[cnt],l,mid,x,x1,x2);
else upd(Rs[cnt],mid+,r,x,x1,x2);
tr[cnt]=min(tr[Ls[cnt]],tr[Rs[cnt]]);
}
inline int query(int pos){
int cnt=,l=,r=top,now=inf;
while(l<r){
int mid=(l+r)>>;int tmp=min(now,tr[cnt<<|]);
if(pos<=mid&&tmp+mid>=*pos)cnt=Ls[cnt],r=mid,now=tmp;
else cnt=Rs[cnt],l=mid+;
}
return l-pos;
}
int check(int cnt,ll l,ll r,int L,int R){
if(!cnt)return inf;
if(l>=L&&r<=R)return tr[cnt];
int mid=(l+r)>>,ans=2e9;
if(mid>=L)ans=min(ans,check(Ls[cnt],l,mid,L,R));
if(mid<R)ans=min(ans,check(Rs[cnt],mid+,r,L,R));
return ans;
}
int main(){
n=rd();k=rd();qu=rd();int x,t,a,b;
memset(tr,0x7f,sizeof(tr));
for(int i=;i<=n;++i){
x=rd();t=rd();a=rd();b=rd();
q[++tot]=node{t,x,a,};
q[++tot]=node{t,x,b+,-};
}
for(int i=;i<=qu;++i){
q[++tot].pos=rd(),q[tot].tim=rd(),q[tot].tmp=i;
q[tot].tag=inf;
}
sort(q+,q+tot+);
for(int i=;i<=k;++i){
s[i].insert(inf);s[i].insert(-inf);
upd(root,,inf,inf,-inf,-);
}
sort(q+,q+tot+);
for(int i=;i<=tot;++i){
int pos=q[i].pos;
if(q[i].tag==){
if(!tong[q[i].tmp])ji++;tong[q[i].tmp]++;
it=s[q[i].tmp].upper_bound(pos);it2=it--;
upd(root,,inf,*it2,pos,*it);
upd(root,,inf,pos,*it,-);
s[q[i].tmp].insert(pos);
}
else if(q[i].tag==-){
tong[q[i].tmp]--;if(!tong[q[i].tmp])ji--;
it=s[q[i].tmp].find(pos);
it2=it3=it;it2--;it3++;
upd(root,,inf,*it3,*it2,pos);
upd(root,,inf,*it,-,*it2);
s[q[i].tmp].erase(it);
}
else{
if(ji!=k){ans[q[i].tmp]=-;continue;}
int l=pos,r=inf,as=-;
while(l<=r){
int mid=(l+r)>>;
if(pos-check(,,inf,mid+,inf)<=mid-pos){
r=mid-;as=mid;
}else l=mid+;
}
ans[q[i].tmp]=as-pos;
// ans[q[i].tmp]=query(pos);
}
}
for(int i=;i<=qu;++i)printf("%d\n",ans[i]);
return ;
}