强行二合一可还行
首先(c)的贡献是不会变的,先考虑求出多少交点被矩形覆盖,交点的话可以按左端点纵坐标从下到上顺序枚举一条线段,然后维护右端点纵坐标的set,把之前处理过线段的右端点放进set里,然后所有 右端点在当前线段右端点上方的线段 都是和当前线段有交点的,直接算出来,并且这样算不会算重
本题中的矩形是斜着的,但是如果我们把所有点绕原点顺时针转(45^circ),那么矩形的四边都会和坐标轴平行,我们可以直接考虑每个点是否被矩形覆盖,把坐标离散化,然后套扫描线扫横坐标,用树状数组维护每个纵坐标是否被覆盖,扫到某个点就直接查对应(y)坐标是否有值就行了
然后考虑(a,b),最大值最小值一定是一个尽量多用「对向交换」,一个尽量多用「擦身而过」,而「对向交换」不会改变飞机在纵坐标的相对顺序,所以可以全部用「对向交换」;然后尽量多用「擦身而过」等价于尽量少用「对向交换」.考虑把左端点纵坐标按大小编号,右端点纵坐标也按大小编号,然后左端点编号(i)向对应的右端点编号(j)连边,我们可以得到若干个环,因为要使得最后的相对顺序和开始的相对顺序一样,也就是要用最少的操作数把那些环转化成(n)个自环,而每次「对向交换」可以对应到交换两点连出去的点,可以发现一个大小为(sz)的环只要操作(sz-1)次,所以最少次数就是(sum_{circle} sz-1),等价于(n-)环的个数
// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#define LL long long
#define db double
using namespace std;
const int N=1e5+10;
const db sb=1.0/sqrt(2),eps=1e-8;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
struct nn
{
db x;
nn(){}
nn(db nx){x=nx;}
bool operator < (const nn &bb) const {return x<bb.x;}
bool operator == (const nn &bb) const {return fabs(x-bb.x)<eps;}
}bk[N*7];
struct point
{
db x,y;
point(){}
point(db nx,db ny){x=nx,y=ny;}
bool operator < (const point &bb) const {return x!=bb.x?x<bb.x:y<bb.y;}
void rot()
{
db xx=x,yy=y;
x=sb*xx+sb*yy,y=sb*yy-sb*xx;
}
}p[N*5],sd;
set<point> s1;
set<point>::iterator i1;
struct matrix
{
point a,b;
bool operator < (const matrix &bb) const {return bb.a<a;}
}qq[N];
priority_queue<matrix> hp;
bool cmp(matrix aa,matrix bb){return aa.a<bb.a;}
int n,A,B,C,sx,tx,a[N],aa[N],b[N],bb[N],m,pt,ttx,tty,cnt,mi;
db ln[N];
point jiao(int i,int j)
{
db x=aa[a[i]]-aa[a[j]],y=bb[b[j]]-bb[b[i]];
return point((db)sx+(db)(tx-sx)*x/(x+y),(db)aa[a[i]]+(db)(bb[b[i]]-aa[a[i]])*x/(x+y));
}
int c[N*7];
void ad(int x,int y){while(x<=tty){c[x]+=y,x+=x&(-x);}}
int gsm(int x){int an=0;while(x){an+=c[x],x-=x&(-x);}return an;}
int ff[N];
int findf(int x){return ff[x]==x?x:ff[x]=findf(ff[x]);}
LL a1,a2;
int main()
{
n=rd(),A=rd(),B=rd(),C=rd(),sx=rd(),tx=rd();
for(int i=1;i<=n;++i) a[i]=aa[i]=rd();
sort(aa+1,aa+n+1);
for(int i=1;i<=n;++i) a[i]=lower_bound(aa+1,aa+n+1,a[i])-aa;
for(int i=1;i<=n;++i) b[i]=bb[i]=rd();
sort(bb+1,bb+n+1);
for(int i=1;i<=n;++i) b[i]=lower_bound(bb+1,bb+n+1,b[i])-bb;
for(int i=1;i<=n;++i)
{
s1.insert(point(bb[b[i]],i));
i1=s1.upper_bound(point(bb[b[i]],i));
for(;i1!=s1.end();++i1)
{
int j=(int)((*i1).y+0.5);
p[++pt]=jiao(i,j);
p[pt].rot();
}
}
m=rd();
for(int i=1;i<=m;++i)
{
db x=rd(),y=rd();
sd=point(x,y),ln[i]=(db)rd()/sb;
sd.rot();
qq[i]=(matrix){point(sd.x-ln[i]/2,sd.x+ln[i]/2),point(sd.y-ln[i]/2,sd.y+ln[i]/2)};
}
bk[++ttx]=nn(1e18);
for(int i=1;i<=pt;++i) bk[++ttx]=nn(p[i].x);
for(int i=1;i<=m;++i) bk[++ttx]=nn(qq[i].a.x),bk[++ttx]=nn(qq[i].a.y);
sort(bk+1,bk+ttx+1),ttx=unique(bk+1,bk+ttx+1)-bk-1;
for(int i=1;i<=pt;++i) p[i].x=upper_bound(bk+1,bk+ttx+1,nn(p[i].x))-bk-1;
for(int i=1;i<=m;++i) qq[i].a.x=upper_bound(bk+1,bk+ttx+1,nn(qq[i].a.x))-bk-1,qq[i].a.y=upper_bound(bk+1,bk+ttx+1,nn(qq[i].a.y))-bk-1;
bk[++tty]=nn(1e18);
for(int i=1;i<=pt;++i) bk[++tty]=nn(p[i].y);
for(int i=1;i<=m;++i) bk[++tty]=nn(qq[i].b.x),bk[++tty]=nn(qq[i].b.y);
sort(bk+1,bk+tty+1),tty=unique(bk+1,bk+tty+1)-bk-1;
for(int i=1;i<=pt;++i) p[i].y=upper_bound(bk+1,bk+tty+1,nn(p[i].y))-bk-1;
for(int i=1;i<=m;++i) qq[i].b.x=upper_bound(bk+1,bk+tty+1,nn(qq[i].b.x))-bk-1,qq[i].b.y=upper_bound(bk+1,bk+tty+1,nn(qq[i].b.y))-bk-1;
sort(p+1,p+pt+1);
sort(qq+1,qq+m+1,cmp);
for(int i=1,j=1,k=1;i<=ttx&&k<=pt;++i)
{
int ll,rr;
while(j<=m&&(int)qq[j].a.x<=i)
{
ll=qq[j].b.x,rr=qq[j].b.y;
ad(ll,1),ad(rr+1,-1);
hp.push((matrix){point(qq[j].a.y,0),point(ll,rr)});
++j;
}
while(k<=pt&&(int)p[k].x<=i)
{
cnt+=(bool)gsm(p[k].y);
++k;
}
while(!hp.empty()&&(int)hp.top().a.x<=i)
{
ll=hp.top().b.x,rr=hp.top().b.y;
ad(ll,-1),ad(rr+1,1);
hp.pop();
}
}
for(int i=1;i<=n;++i) ff[i]=i;
for(int i=1;i<=n;++i) ff[findf(a[i])]=findf(b[i]);
mi=n;
for(int i=1;i<=n;++i) mi-=findf(i)==i;
a1=1ll*cnt*C+1ll*pt*A,a2=1ll*cnt*C+1ll*mi*A+1ll*(pt-mi)*B;
if(a1>a2) swap(a1,a2);
printf("%lld %lld
",a1,a2);
return 0;
}