P4864 Jerry Loves Lines

题意：给定$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; } ```