A.山

xyz現在站在一個斜坡面前
這個斜坡上依次排布這n座山峰，xyz打算爬上其中的一座
因為xyz體力不好，所以他只能爬上最矮的一座山
又因為xyz不擅長分類討論，因此即使山的海拔為負，他也只打算爬海拔最低的那座，而不是海拔的絕對值最小的那座
然而xyz智商拙計，只帶了一張相對海拔高度地圖，于是要來求助你
現在他知道這個斜坡有m種可能的斜率，請你對于每種斜率輸出海拔最低的山峰的高度
我們定義每兩座山之間的水平距離都為1，第0座山所在的土地海拔高度為0

輸入格式：
第一行兩個數n,m
第二行有n個數 表示每座山峰的高度
接下來m行每行有一個數p，表示這個斜坡可能的斜率(可能小于0)

輸出格式：
對于每個詢問輸出一行，表示最矮的山峰的海拔高度

樣例輸入：
3 1
3 2 1
10

樣例輸出：
13

數據范圍：
30%的數據 n,m<=1000
100%的數據 n,m<=300000,max(|h[i]|)<10^12,max(|h[i]+i*p|)<10^18,

時間限制：
1s

空間限制：
64MB

解

考慮離線，把斜率 \(k\) 從小到大排序。
對于兩座山 \(i,j(i<j)\) ，當且僅當 \(\frac{h[i]-h[j]}{j-i}<k\) ， \(j\) 才會超過 \(i\) 。
因此先維護一個雙向鏈表，然后1~n掃一遍，把 \(i\) 及其后繼加入到priority_queue中。每次掃到一個 \(k\) ，把臨界值 \(\le k\) 的彈出，再更新鏈表，再把新的臨界值插入。

Code

#include<bits/stdc++.h> using namespace std; typedef long long D; const int maxn=300003; const double eps=1e-8; int sgn(double x){return x<-eps?-1:x>eps;} int n,Q,L[maxn],R[maxn]; D a[maxn],ANS[maxn]; bool vis[maxn]; struct QQ{D k;int num;bool operator<(QQ x)const{return k<x.k;} }qq[maxn]; struct T{int l,r;double b;T(){}T(int _l,int _r,double _b):l(_l),r(_r),b(_b){}bool operator<(T x)const{return b>x.b;} }; priority_queue<T> q; int main(){scanf("%d%d",&n,&Q);for(int i=1;i<=n;i++)scanf("%lld",a+i);for(int i=1;i<=Q;i++)scanf("%lld",&qq[i].k),qq[i].num=i;sort(qq+1,qq+Q+1);for(int i=1;i<=n+1;i++){L[i]=i-1;R[i]=i+1;}for(int i=1;i<n;i++){q.push(T(i,i+1,a[i]-a[i+1]));}for(int i=1;i<=Q;i++){while(!q.empty()&&sgn(q.top().b-qq[i].k)<0){T tp=q.top();q.pop();if(vis[tp.l]||vis[tp.r])continue;vis[tp.r]=1;R[L[tp.r]]=R[tp.r];L[R[tp.r]]=L[tp.r];if(R[tp.r]<=n)q.push(T(tp.l,R[tp.r],double(a[tp.l]-a[R[tp.r]])/(R[tp.r]-tp.l)));}ANS[qq[i].num]=a[L[n+1]]+L[n+1]*qq[i].k;}for(int i=1;i<=Q;i++)printf("%lld\n",ANS[i]);return 0; }/* 3 5 4 16 29 10 0 -11 -12 -13 */

B.ctps

4維空間中有1個點集A，|A|=n,用(a,b,c,d)表示每個點。
共有m個詢問，每次詢問輸入一個點(a,b,c,d)，求最大的S,其中S={p|p∈A且ap<=a,bp<=b,cp<=c,dp<=d}，輸出|S|

輸入格式：
第一行n
接下來n行有n個4維點對
第n+2行有一個數m
再接下來m行每行有一個四維點對，表示每個詢問
輸出格式：
對于每個詢問輸出一個數
樣例輸入：
1
0 0 0 0
2
1 1 1 1.0
1 1 1 -1
樣例輸出：
1
0
數據范圍：
n,m<=30000
時間限制：
2s
空間限制：
256MB

解 1

cdq套cdq

Code

#include<bits/stdc++.h> using namespace std; const int maxn=60003; const double eps=1e-8; int sgn(double x){return x<-eps?-1:x>eps;} bool dbless(double x,double y){return sgn(x-y)<0;} bool dbeq(double x,double y){return sgn(x-y)==0;} struct T{int a,b,c,d,num;bool isleft,isadd;bool operator ==(const T &x)const{return a==x.a&&b==x.b&&c==x.c&&d==x.d;} }a[maxn],b[maxn],c[maxn]; int n,Q,cntmp,t[maxn<<2],ANS[maxn]; double mp[maxn<<2],tmpa[maxn][4]; bool cmpa(const T &x,const T &y){return x.a!=y.a?x.a<y.a:(x.b!=y.b?x.b<y.b:(x.c!=y.c?x.c<y.c:(x.d!=y.d?x.d<y.d:x.isadd>y.isadd)));} bool cmpb(const T &x,const T &y){return x.b!=y.b?x.b<y.b:(x.a!=y.a?x.a<y.a:(x.c!=y.c?x.c<y.c:(x.d!=y.d?x.d<y.d:x.isadd>y.isadd)));} bool cmpc(const T &x,const T &y){return x.c!=y.c?x.c<y.c:(x.a!=y.a?x.a<y.a:(x.b!=y.b?x.b<y.b:(x.d!=y.d?x.d<y.d:x.isadd>y.isadd)));} void add(int pos,int k){while(pos<=cntmp)t[pos]+=k,pos+=pos&-pos;} int query(int pos){int ret=0;while(pos)ret+=t[pos],pos-=pos&-pos;return ret;} void CDQ(int l,int r){if(l==r)return;int mid=(l+r)>>1,cnt=0,i,j;CDQ(l,mid),CDQ(mid+1,r);for(i=l,j=mid+1;i<=mid&&j<=r;){if(!cmpc(b[j],b[i])){if(b[i].isadd&&b[i].isleft)add(b[i].d,1);c[++cnt]=b[i];i++;}else{if(!b[j].isleft)ANS[b[j].num]+=query(b[j].d);c[++cnt]=b[j];j++;}}while(i<=mid){if(b[i].isadd&&b[i].isleft)add(b[i].d,1);c[++cnt]=b[i];i++;}while(j<=r){if(!b[j].isleft)ANS[b[j].num]+=query(b[j].d);c[++cnt]=b[j];j++;}for(i=l;i<=mid;i++)if(b[i].isadd&&b[i].isleft)add(b[i].d,-1);for(i=1;i<=cnt;i++)b[l+i-1]=c[i]; } void cdq(int l,int r){if(l==r)return;int mid=(l+r)>>1,cnt=0,i,j;cdq(l,mid),cdq(mid+1,r);for(i=l,j=mid+1;i<=mid&&j<=r;){if(!cmpb(a[j],a[i])){b[++cnt]=a[i];b[cnt].isleft=1;i++;}else{b[++cnt]=a[j];b[cnt].isleft=0;j++;}}while(i<=mid){b[++cnt]=a[i];b[cnt].isleft=1;i++;}while(j<=r){b[++cnt]=a[j];b[cnt].isleft=0;j++;}for(i=1;i<=cnt;i++)a[l+i-1]=b[i];CDQ(1,cnt); } int main(){scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=0;j<=3;j++)scanf("%lf",&tmpa[i][j]),mp[++cntmp]=tmpa[i][j];scanf("%d",&Q);for(int i=n+1;i<=n+Q;i++)for(int j=0;j<=3;j++)scanf("%lf",&tmpa[i][j]),mp[++cntmp]=tmpa[i][j];sort(mp+1,mp+cntmp+1,dbless);cntmp=unique(mp+1,mp+cntmp+1,dbeq)-mp-1;n+=Q;for(int i=1;i<=n;i++){a[i].a=lower_bound(mp+1,mp+cntmp+1,tmpa[i][0],dbless)-mp;a[i].b=lower_bound(mp+1,mp+cntmp+1,tmpa[i][1],dbless)-mp;a[i].c=lower_bound(mp+1,mp+cntmp+1,tmpa[i][2],dbless)-mp;a[i].d=lower_bound(mp+1,mp+cntmp+1,tmpa[i][3],dbless)-mp;a[i].num=i;a[i].isadd=(i<=n-Q);}sort(a+1,a+n+1,cmpa);cdq(1,n);for(int i=n-Q+1;i<=n;i++)printf("%d\n",ANS[i]);return 0; }/* 1 -2 -4 1 -4 2 2 -4 4 -2 0 0 0 5 */

解 2

cdq套樹套樹

Code \(\color{white}{(大括號換行異端)}\)

#include<bits/stdc++.h> using namespace std; const int N=500005; const double eps=1e-8; struct ab {double x,y,z,h;int id,ans,q; } a[N]; int ans[N],tot,tt[N<<4],lson[N<<4],rson[N<<4],h; double b[N]; queue<int>q; int cmp(double x,double y){return x-y<-eps;} int cmpp(double x,double y){return abs(x-y)<eps;} int cmp1(ab x,ab y) {if(x.x!=y.x) return x.x<y.x;return x.id<y.id; } int cmp2(ab x,ab y) {if(x.y!=y.y) return x.y<y.y;return x.id<y.id; } struct seg {int rt;seg(){rt=0;}void add(int y,int z,int l,int r,int &x){if(!x) x=++tot;tt[x]+=z;if(l!=r){int mid=(l+r)>>1;if(mid>=y) add(y,z,l,mid,lson[x]);else add(y,z,mid+1,r,rson[x]);}}int que(int L,int R,int l,int r,int now){if(L>R) return 0;if(!now) return 0;if(l>=L&&r<=R) return tt[now];int mid=(l+r)>>1,ans=0;if(mid>=L) ans+=que(L,R,l,mid,lson[now]);if(mid<R) ans+=que(L,R,mid+1,r,rson[now]);return ans;} } t[N]; void add(int x,int y,int z) {for(;x<=h;x+=x&-x){t[x].add(y,z,1,h,t[x].rt);} } int que(int x,int y) {int anss=0;for(;x>=1;x-=x&-x){anss+=t[x].que(1,y,1,h,t[x].rt);}return anss; } void cdq(int l,int r) {if(l==r) return;int mid=(l+r)>>1;cdq(l,mid);cdq(mid+1,r);sort(a+l,a+r+1,cmp2);for(int i=l;i<=r;i++){if(a[i].x<=mid&&a[i].id==1) add(a[i].z,a[i].h,1);if(a[i].x>mid&&a[i].id==2) a[i].ans+=que(a[i].z,a[i].h);}for(int i=l;i<=r;i++){if(a[i].x<=mid&&a[i].id==1) add(a[i].z,a[i].h,-1);} } int main() {int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z,&a[i].h);a[i].id=1;b[++h]=a[i].x;b[++h]=a[i].y;b[++h]=a[i].z;b[++h]=a[i].h;}int m;scanf("%d",&m);for(int i=n+1;i<=n+m;i++){scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z,&a[i].h);a[i].id=2;a[i].q=i-n;b[++h]=a[i].y;b[++h]=a[i].z;b[++h]=a[i].h;}sort(b+1,b+1+h,cmp);h=unique(b+1,b+1+h,cmpp)-b-1;sort(a+1,a+1+n+m,cmp1);for(int i=1;i<=n+m;i++){a[i].x=i;a[i].y=lower_bound(b+1,b+1+h,a[i].y,cmp)-b;a[i].z=lower_bound(b+1,b+1+h,a[i].z,cmp)-b;a[i].h=lower_bound(b+1,b+1+h,a[i].h,cmp)-b;}cdq(1,n+m);for(int i=1;i<=n+m;i++){ans[a[i].q]=a[i].ans;}for(int i=1;i<=m;i++){printf("%d\n",ans[i]);}return 0; }

解 3

bitset

Code 3

#include<bits/stdc++.h> using namespace std; const int maxn=30003; const double eps=1e-8; int sgn(double x){return x<-eps?-1:x>eps;} struct T{int num;double a,b,c,d;bool isadd; }a[maxn<<1]; int n,Q,ANS[maxn]; bitset<maxn> b[maxn],c; int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&a[i].a,&a[i].b,&a[i].c,&a[i].d),a[i].num=i,a[i].isadd=1;scanf("%d",&Q);for(int i=n+1;i<=n+Q;i++)scanf("%lf%lf%lf%lf",&a[i].a,&a[i].b,&a[i].c,&a[i].d),a[i].num=i-n;n+=Q;for(int i=1;i<=n;i++)if(!a[i].isadd)b[a[i].num].set();sort(a+1,a+n+1,[](const T &x,const T &y){return sgn(x.a-y.a)?sgn(x.a-y.a)<0:x.isadd>y.isadd;});c.reset();for(int i=1;i<=n;i++){if(a[i].isadd)c.set(a[i].num);else b[a[i].num]&=c;}sort(a+1,a+n+1,[](const T &x,const T &y){return sgn(x.b-y.b)?sgn(x.b-y.b)<0:x.isadd>y.isadd;});c.reset();for(int i=1;i<=n;i++){if(a[i].isadd)c.set(a[i].num);else b[a[i].num]&=c;}sort(a+1,a+n+1,[](const T &x,const T &y){return sgn(x.c-y.c)?sgn(x.c-y.c)<0:x.isadd>y.isadd;});c.reset();for(int i=1;i<=n;i++){if(a[i].isadd)c.set(a[i].num);else b[a[i].num]&=c;}sort(a+1,a+n+1,[](const T &x,const T &y){return sgn(x.d-y.d)?sgn(x.d-y.d)<0:x.isadd>y.isadd;});c.reset();for(int i=1;i<=n;i++){if(a[i].isadd)c.set(a[i].num);else b[a[i].num]&=c;}for(int i=1;i<=n;i++)if(!a[i].isadd)ANS[a[i].num]=b[a[i].num].count();for(int i=1;i<=Q;i++)printf("%d\n",ANS[i]);return 0; }

解 4

k-dtree

轉載于:https://www.cnblogs.com/BlogOfchc1234567890/p/11303551.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的20190805的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。