附一份代码,如果是我写的常数太大了请大佬们指正
```php
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2000005;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
struct node
{
int a;
int b;
int c;
bool f1,f2,qk;
int to;
}p[N];
int asknum,tot;
int sf1,sf2;
bool cmp1(node g1,node g2)
{
if(g1.a!=g2.a)
return g1.a*sf1<g2.a*sf1;
return g1.qk<g2.qk;
}
bool cmp2(node g1,node g2)
{
if(g1.b!=g2.b)
return g1.b*sf2<g2.b*sf2;
return g1.f1+g1.qk<g2.f1+g2.qk;
}
bool cmp3(node g1,node g2)
{
if(g1.c!=g2.c)
return g1.c<g2.c;
return g1.f1+g1.f2+g1.qk<g2.f1+g2.f2+g2.qk;
}
node p1[N];
int ans[N];
void cdq2(int l,int r)
{
if(l==r)
return;
int mid=(l+r)/2;
cdq2(l,mid);
cdq2(mid+1,r);
for(int i=l;i<=r;i++)
{
if(i<=mid)
p[i].f2=0;
else
p[i].f2=1;
}
int zk=l-1;
for(int i=l,j=mid+1;i<=mid||j<=r;)
{
zk++;
if(i>mid)
{
p1[zk]=p[j];
j++;
}
else if(j>r)
{
p1[zk]=p[i];
i++;
}
else
{
if(cmp3(p[i],p[j]))
{
p1[zk]=p[i];
i++;
}
else
{
p1[zk]=p[j];
j++;
}
}
}
for(int i=l;i<=r;i++)
p[i]=p1[i];
int now=1e18;
//cout<<l<<" "<<r<<"______________________"<<endl;
for(int i=l;i<=r;i++)
{
// cout<<"a: "<<p[i].a<<" b: "<<p[i].b<<" c: "<<p[i].c<<endl;
// cout<<"** "<<p[i].f1<<" "<<p[i].f2<<" "<<p[i].qk<<"**"<<endl;
if(p[i].f1+p[i].f2+p[i].qk==0)
{
now=min(now,(sf1*p[i].a+sf2*p[i].b)*(-1));
// cout<<"add "<<" "<<(sf1*p[i].a+sf2*p[i].b)*(-1)<<" "<<now<<endl;
}
if(p[i].f1+p[i].f2+p[i].qk==3)
{
ans[p[i].to]=min(ans[p[i].to],(p[i].a*sf1+p[i].b*sf2)+now);
// cout<<"query "<<now<<" "<<(p[i].a*sf1+p[i].b*sf2)+now<<endl;
}
}
}
void cdq1(int l,int r)
{
if(l==r)
return;
int mid=(l+r)/2;
cdq1(l,mid);
cdq1(mid+1,r);
for(int i=l;i<=r;i++)
{
if(i<=mid)
p[i].f1=0;
else
p[i].f1=1;
}
sort(p+l,p+r+1,cmp2);
// cout<<l<<" "<<r<<"******************"<<endl;
cdq2(l,r);
}
void solve(int s1,int s2)
{
sf1=s1;
sf2=s2;
sort(p+1,p+tot+1,cmp1);
// cout<<"((((((((((((((((((((( "<<sf1<<" "<<sf2<<" )))))))))))))))))))))))))))"<<endl;
cdq1(1,tot);
}
signed main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
tot++;
p[tot].a=read();
p[tot].b=read();
p[tot].c=0;
p[tot].qk=0;
}
for(int i=1;i<=m;i++)
{
int op;
cin>>op;
if(op==1)
{
tot++;
p[tot].a=read();
p[tot].b=read();
p[tot].c=i;
p[tot].qk=0;
}
else
{
tot++;
asknum++;
p[tot].a=read();
p[tot].b=read();
p[tot].c=i;
p[tot].qk=1;
p[tot].to=asknum;
}
}
for(int i=1;i<=asknum;i++)
ans[i]=1e18;
solve(-1,-1);
solve(1,-1);
solve(-1,1);
solve(1,1);
for(int i=1;i<=asknum;i++)
printf("%lld\n",ans[i]);
return 0;
}
```
by u______n @ 2024-01-03 07:44:23
这一题的o2优化很神奇,经测试题解能缩减四倍左右的时间,但我开了也过不掉,4s7e8还是太勉强了
by u______n @ 2024-01-03 07:50:59
@[realskc](/user/35672)
by u______n @ 2024-01-03 07:56:15
@[u______n](/user/965755)
写了快读你不用？
by Miss_SGT @ 2024-01-03 08:29:32
@[zhouchenqiao1](/user/705012) ?我没有用吗???
by u______n @ 2024-01-03 08:32:20
@[u______n](/user/965755) 额看见你n，m没用，这题你可以尝试cdq用归并排序
by Miss_SGT @ 2024-01-03 08:52:49
我这边完全不卡常，建议换成归并试试
by naroanah @ 2024-01-03 10:07:23
好的,我试试
by u______n @ 2024-01-03 10:09:10
但理论上也确实需要777,600,000次
by u______n @ 2024-01-03 10:09:47
归并快了点,但还是卡
by u______n @ 2024-01-03 10:14:36