P4864 Jerry Loves Lines

2018-09-04 19:01:25


题意:给定 $n$ 个一次函数,询问在某一位置的第 $k$ 大函数值

第 $k$ 大?难道是主席树?好像并不是。。

有一个比较明显的结论:若两条直线相交,则在交点后的部分两条直线的大小关系与之前相反(貌似是初中数学)

由此,将询问离线存储,按照 $x$ 大小排序

然后算出 $n$ 条直线在最左端的函数值,根据这个值排序

$n^2$ 枚举,算出直线的两两交点

(在按照左端函数值排好序的情况下,如果后面直线在最右端的函数值比前面小,则两直线相交)

将每两条相交的直线放到结构体中,按照交点的位置从小到大排序

之后可以处理询问

对于每一个询问,对它有影响的就是交点在它之前并且在上一个询问之后的直线

用 $rk$ 表示每一条直线在此处的排名, $num$ 表示每个排名对应的直线

显然两条直线相交只会使各自的排名变化 $1$

询问的答案即为 $x$ 处排名为 $k$ 的函数值

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=2005,M=5e5+5;
struct line
{
    int k,b,id; ll y;
    inline friend bool operator < (line a,line b) {return a.y<b.y;}
}c[N];
struct Q
{
    int x,id;
    inline friend bool operator < (Q a,Q b) {return a.x<b.x;}
}q[M];
struct node
{
    int x,y; ll p;
    inline friend bool operator < (node a,node b)
    {
        return a.p==b.p?a.x<b.x:a.p<b.p;
    }
}t[2000005];
int n,m,k,cnt,num[N],rk[N];
ll ans[M];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline ll calc(int x,int k){return (ll)c[k].k*x+c[k].b;}
inline ll getpos(int p,int q){return (ll)(c[q].b-c[p].b)/(c[p].k-c[q].k)+1;}
int main()
{
    n=read(),m=read(),k=read();
    for (reg int i=1;i<=n;i++) c[i].k=read(),c[i].b=read();
    for (reg int i=1;i<=m;i++) q[i].x=read(),q[i].id=i; sort(q+1,q+m+1);
    for (reg int i=1;i<=n;i++) c[i].y=calc(q[1].x,i); sort(c+1,c+n+1);
    for (reg int i=1;i<=n;i++)
    {
        c[i].id=num[i]=rk[i]=i;
        for (reg int j=i+1;j<=n;j++)
          if (c[i].k!=c[j].k&&calc(q[m].x,i)>=calc(q[m].x,j))
          {
              ll pos=getpos(i,j);
              if (pos>=q[1].x) t[++cnt]=(node){i,j,pos};
          }
    }
    sort(t+1,t+cnt+1);
    for (reg int i=1,now=1;i<=m;i++)
    {
        while (now<=cnt&&t[now].p<=q[i].x)
        {
            num[++rk[t[now].x]]=t[now].x; 
            num[--rk[t[now].y]]=t[now].y;
            ++now;
        }
        ans[q[i].id]=calc(q[i].x,num[k]);
    }
    for (reg int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}