离线询问,建立时间线段树,那么每条直线存在的时间是一个区间,对应时间线段树上$\mathcal{O}(\log n)$个节点,每个询问对应时间线段树上某个叶子到根的$\mathcal{O}(\log n)$ 个节点。
对于时间线段树中的某个节点,它代表的直线集合是静态的,问题转化为静态区间查询。对于静态区间查询的子问题,可以通过线段树记录区间凸壳的方式在$\mathcal{O}(n\log n)$的时间内预处理出每个线段树区间对应的凸壳,父节点的凸壳由两个子节点的凸壳线性归并得到。对于每个静态区间查询,在线段树上找到$\mathcal{O}(n\log n)$个节点,在每个节点记录的凸壳上二分查找答案。
如此一来,按时间分治、静态区间线段树以及凸壳上二分都有$\log$,总时间复杂度为$\mathcal{O}(n\log^3n)$,不能接受。如果将所有询问按$x$提前排好序的话,那么可以均摊地在$\mathcal{O}(1)$时间内找到凸壳上的答案,去掉一个$\log$。
时间复杂度$\mathcal{O}(n\log^2n)$。
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int BUF=30000000; char Buf[BUF],*buf=Buf; inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;} const int OUT=10000000; char Out[OUT],*ou=Out;int Outn[30],Outcnt; inline void write(ll x){ if(!x)*ou++=48; else{ for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48; while(Outcnt)*ou++=Outn[Outcnt--]; } } inline void writeln(ll x){write(x);*ou++='\n';} const int N=500005,M=500005,K=21,MAXT=M*K*2; int _,n,m,ct,i,op,x,y,z,last[N];ll ans[M]; int idx[M],tmp[M],pool[K][M],pos[N],ST,EN; struct Line{ int k,b; ll get(ll x)const{return k*x+b;} }line[N],hull[N],cur[N]; struct Tag{int x,l,r;Line v;}tag[N+M]; struct Qry{ int x,l,r; bool contain(int a,int b){return l<=a&&r>=b;} bool cross(int a,int b){return l<=b&&r>=a;} }qry[M]; int ed,g[1111111],nxt[MAXT];Tag tags[MAXT]; inline void up(ll&a,ll b){a<b?(a=b):0;} inline bool cmptag(const Tag&A,const Tag&B){ return A.x>B.x; } inline bool cmpline(const Line&A,const Line&B){ if(A.k!=B.k)return A.k<B.k; return A.b>B.b; } inline void addtag(int x,int l,int r,const Line&p){ if(l>r)return; tag[++ct].x=x; tag[ct].l=l; tag[ct].r=r; tag[ct].v=p; } void ins(int x,int a,int b,const Tag&p){ if(p.l<=a&&b<=p.r){ tags[++ed]=p; nxt[ed]=g[x]; g[x]=ed; return; } int mid=(a+b)>>1; if(p.l<=mid)ins(x<<1,a,mid,p); if(p.r>mid)ins(x<<1|1,mid+1,b,p); } inline void ext(const Line&p){ if(ST<=EN&&cur[EN].k==p.k)return; while(ST<EN&&1LL*(cur[EN-1].b-cur[EN].b)*(p.k-cur[EN].k)>=1LL*(cur[EN].b-p.b)*(cur[EN].k-cur[EN-1].k))EN--; cur[++EN]=p; } inline int makehull(int al,int ar,int bl,int br){ ST=al; EN=ST-1; while(al<=ar&&bl<=br)ext(cmpline(hull[al],hull[bl])?hull[al++]:hull[bl++]); while(al<=ar)ext(hull[al++]); while(bl<=br)ext(hull[bl++]); for(int i=ST;i<=EN;i++)hull[i]=cur[i]; return EN; } int solve(int d,int a,int b,int len){ int i,o,L=pos[a],R=pos[b]; if(a==b){ for(i=0;i<len;i++){ o=pool[d][i]; if(qry[o].l<=L&&L<=qry[o].r)up(ans[o],hull[a].get(qry[o].x)); } return a; } if(!len){ sort(hull+a,hull+b+1,cmpline); return makehull(a,b,1,0); } int mid=(a+b)>>1,ML=pos[mid],MR=pos[mid+1],cq; for(cq=i=0;i<len;i++){ o=pool[d][i]; if(!qry[o].contain(L,R)&&qry[o].cross(L,ML))pool[d+1][cq++]=o; } int el=solve(d+1,a,mid,cq); for(cq=i=0;i<len;i++){ o=pool[d][i]; if(!qry[o].contain(L,R)&&qry[o].cross(MR,R))pool[d+1][cq++]=o; } int er=solve(d+1,mid+1,b,cq); int en=makehull(a,el,mid+1,er); int st=a; for(i=0;i<len;i++){ o=pool[d][i]; if(!qry[o].contain(L,R))continue; int x=qry[o].x; while(st<en&&hull[st].get(x)<hull[st+1].get(x))st++; up(ans[o],hull[st].get(x)); } return en; } void dfs(int x,int a,int b){ if(a==b)idx[a]=a; else{ int mid=(a+b)>>1; dfs(x<<1,a,mid); dfs(x<<1|1,mid+1,b); int i=a,j=mid+1,k=a; while(i<=mid&&j<=b)tmp[k++]=qry[idx[i]].x<qry[idx[j]].x?idx[i++]:idx[j++]; while(i<=mid)tmp[k++]=idx[i++]; while(j<=b)tmp[k++]=idx[j++]; for(i=a;i<=b;i++)idx[i]=tmp[i]; } if(!g[x])return; for(int i=a;i<=b;i++)pool[0][i-a]=idx[i]; int m=0; for(int i=g[x];i;i=nxt[i]){ pos[m]=tags[i].x; hull[m]=tags[i].v; m++; } solve(0,0,m-1,b-a+1); } int main(){ fread(Buf,1,BUF,stdin); read(n);read(_); for(i=1;i<=n;i++){ read(line[i].k); read(line[i].b); last[i]=1; } while(_--){ read(op);read(x);read(y);read(z); if(op==1){ addtag(x,last[x],m,line[x]); line[x].k=y; line[x].b=z; last[x]=m+1; }else{ m++; qry[m].x=x; qry[m].l=y; qry[m].r=z; } } if(!m)return fwrite(Out,1,ou-Out,stdout),0; for(i=1;i<=n;i++)addtag(i,last[i],m,line[i]); sort(tag+1,tag+ct+1,cmptag); for(i=1;i<=ct;i++)ins(1,1,m,tag[i]); dfs(1,1,m); for(i=1;i<=m;i++)writeln(ans[i]); fwrite(Out,1,ou-Out,stdout); }
- Regionals Multiply Contest Problem Onlineregionals multiply contest problem regionals contest online 2022 regionals contest online 2023 regionals contest online mdielk regionals contest online string regionals游记contest online periodicity regionals contest problem regionals contest online abefj multiply mountain regional contest contest problem 20035 http