簡單重述一次問題為：數線上有一堆紅線和藍線，每條藍線有他的價值，並且當取一紅一藍時獲得的價值為藍線價值乘上兩條線段相交部份的長度，求最大價值還有是哪兩條。我們之後的策略會是：對於每條藍線都求出和他交集最長的紅線的交集部份有多長，然後拿他去更新答案。
對於所有的兩條線段相交的情形可以分成以下四種：紅線包含藍線，紅線只和藍線交於藍線的左段，紅線只和藍線交於藍線的右段，還有藍線包含紅線。而對於這幾種情況都可以用掃描線搭配一個資料結構的方法處理（在這裡是線段樹）。首先看第一和第二種情形，考慮把所有的紅線和藍線都按照左端點由小到大排序，當在計算某條特定藍線 $[ L , R ]$ 的答案時，對於所有滿足左端點 $\leq L$ 的紅線 $[ l , r ]$ ，把線段樹上 $l$ 到 $r$ 之間的值都和 $r$ 取 $max$ ，然後查詢時指需查詢此時 $L$ 的值，拿去和 $R$ 取 min 即可。而要注意到的是：首先要對所有數做離散化，才可以用線段樹（或是不離散化 + 線段樹動態開點應該也是可以），還有線段樹上還必須紀錄造成這個節點最大值的是哪條紅線，因為題目還要求輸出一組解。再來是第三種情形，這只要把所有的線段一起全部左右顛倒就可以了（意思是類似把所有的 $[ L , R ]$ 都改成 $[ -R , -L ]$ 然後求一次答案的概念），而我為了不要再重做一次離散化，就直接把所有的 $[ L , R ]$ 改成 $[ SZ - 1 - R , SZ - 1 - L ]$ 然後重新排序，其中 $SZ$ 為離散後的數字個數。但這樣之後在計算座標差時會有問題（區間長度當然是看離散化前的數值），而解決這個的方法就是當在計算區間長度時，發現此時是第二次求解，那麼就要把當前的 $id$ 值用 $SZ-1$ 扣掉。最後是第四種情形，這次處理的方法比較不一樣，不過主體還是掃描線。把所有紅線和藍線都照右端點排序，當處理到一條藍線 $[ L , R ]$ 時，對於所有滿足右端點 $\leq R$ 的紅線 $[ l , r ]$ ，把線段樹上 $0$ ~ $l$ 的值都和 $r - l$ 取 max （因為此時交集部份長度就等於紅線長，並且要注意到設的值必須是原線段的長度而不是離散化後的線段長度），那麼查詢時只要查詢 $L$ 位置的值就可以了。
code :
#include<bits/stdc++.h> #define LL long long using namespace std; const int maxn=200000+10 ; struct P { int l,r,id ; bool operator < (const P &rhs) const { return l<rhs.l ; } }a[maxn]; bool cmp1(const P &x,const P &y) { return x.r==y.r ? x.l<y.l : x.r<y.r ; } struct Q { int l,r,c,id ; bool operator < (const Q &rhs) const { return l<rhs.l ; } }b[maxn]; bool cmp2(const Q &x,const Q &y) { return x.r==y.r ? x.l<y.l : x.r<y.r ; } int ST[16*maxn],ID[16*maxn] ; void Setmax(int l,int r,int L,int R,int id,int val,int nid) { if(l==L && r==R) { if(val>ST[id]) ST[id]=val , ID[id]=nid ; return ; } int mid=(L+R)/2 ; if(r<=mid) Setmax(l,r,L,mid,2*id,val,nid) ; else if(l>mid) Setmax(l,r,mid+1,R,2*id+1,val,nid) ; else Setmax(l,mid,L,mid,2*id,val,nid) , Setmax(mid+1,r,mid+1,R,2*id+1,val,nid) ; } void query(int L,int R,int id,int pos,int &res,int &resid) { if(L==R){res=ST[id] ; resid=ID[id] ; return ;} int mid=(L+R)/2 ; if(pos<=mid) query(L,mid,2*id,pos,res,resid) ; else query(mid+1,R,2*id+1,pos,res,resid) ; if(ST[id]>res) res=ST[id] , resid=ID[id] ; } int n,m,SZ ; int ans1,ans2 ; LL ans=0LL ; vector<int> v0 ; void solve1(int tp) { memset(ST,-1,sizeof(ST)) ; memset(ID,0,sizeof(ID)) ; for(int i=1,j=1;i<=m;i++) { while(j<=n && a[j].l<=b[i].l) Setmax(a[j].l,a[j].r,0,SZ-1,1,a[j].r,a[j].id) , j++ ; int res,resid ; query(0,SZ-1,1,b[i].l,res,resid) ; if(res>b[i].l) { res=min(res,b[i].r) ; LL val ; if(tp==1) val=(LL)(v0[res]-v0[b[i].l])*b[i].c ; else val=(LL)(v0[SZ-1-b[i].l]-v0[SZ-1-res])*b[i].c ; if(val>ans) ans1=resid , ans2=b[i].id , ans=val ; } } } void solve2() { memset(ST,-1,sizeof(ST)) ; memset(ID,0,sizeof(ID)) ; for(int i=1,j=1;i<=m;i++) { while(j<=n && a[j].r<=b[i].r) Setmax(0,a[j].l,0,SZ-1,1,v0[a[j].r]-v0[a[j].l],a[j].id) , j++ ; int res,resid ; query(0,SZ-1,1,b[i].l,res,resid) ; if(res>0) { LL val=(LL)res*b[i].c ; if(val>ans) ans1=resid , ans2=b[i].id , ans=val ; } } } main() { scanf("%d%d",&n,&m) ; for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].l,&a[i].r) , a[i].id=i ; v0.push_back(a[i].l) ; v0.push_back(a[i].r) ; } for(int i=1;i<=m;i++) { scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].c) , b[i].id=i ; v0.push_back(b[i].l) ; v0.push_back(b[i].r) ; } sort(v0.begin(),v0.end()) ; v0.resize(unique(v0.begin(),v0.end())-v0.begin()) ; SZ=v0.size() ; for(int i=1;i<=n;i++) a[i].l=lower_bound(v0.begin(),v0.end(),a[i].l)-v0.begin() , a[i].r=lower_bound(v0.begin(),v0.end(),a[i].r)-v0.begin() ; for(int i=1;i<=m;i++) b[i].l=lower_bound(v0.begin(),v0.end(),b[i].l)-v0.begin() , b[i].r=lower_bound(v0.begin(),v0.end(),b[i].r)-v0.begin() ; sort(a+1,a+n+1) ; sort(b+1,b+m+1) ; solve1(1) ; sort(a+1,a+n+1,cmp1) ; sort(b+1,b+m+1,cmp2) ; solve2() ; for(int i=1;i<=n;i++) { int tl=a[i].l , tr=a[i].r ; a[i].l=SZ-1-tr , a[i].r=SZ-1-tl ; } for(int i=1;i<=m;i++) { int tl=b[i].l , tr=b[i].r ; b[i].l=SZ-1-tr , b[i].r=SZ-1-tl ; } sort(a+1,a+n+1) ; sort(b+1,b+m+1) ; solve1(2) ; if(ans) printf("%I64d\n%d %d\n",ans,ans1,ans2) ; else printf("0\n") ; }
沒有留言:
張貼留言