【xsy3423】党² 线段树+李超线段树or动态半平面交

本来并不打算出原创题的，此题集CF542A和sk的灵感而成，算个半原创吧。

题目大意：

给定有$n$个元素的集合$P$，其中第$i$个元素中包含$L_i,R_i,V_i$三个值。

给定另一个有$n$个元素的集合$Q$，其中第$i$个元素包含$A_i,B_i,C_i$三个值。

选择集合$P$中第$x$个元素和集合$Q$中第$y$个元素的收益为$(r-l+1)*V_x*C_y$，其中$[l,r]$为$[L_i,R_i]$和$[A_i,B_i]$的交集。你需要在集合$P$，$Q$中分别选出一个元素，使得收益最大

数据范围：

子任务一：满足$n≤5000$

子任务二：满足$V_i=1$。

子任务三：满足$L_i=A_i=1$。

子任务四：满足$n≤10^5$

对于全部数据，所有数$≤10^5$，且$L_i≤R_i,A_i≤B_i$。

子任务一：暴力

子任务二：该子任务为CF542A：

这里有一个题解，看情况三和情况四就行了

子任务三：

不难发现该情况下，对于任意的$i,j$必有$L_i≤A_j,B_j≤R_i$，或者$A_j≤L_i,R_i≤B_j$。

我们把$P$和$Q$中所有元素都丢入一个数组中按右端点排序，同时我们种一棵线段树。

若当前元素原先在$P$中，我们用$(R_i-L_i+1) imes V_i$更新第$L_i$个位置的值（取max）

否则，我们查询区间$[A_i,B_i]$中的最大值，将该值乘上$C_i$后更新答案。

不难发现此方法可以处理所有$Q_i$包含$P_j$的情况。

对于$P_i$包含$Q_j$的情况，我们交换下两个集合再处理一次就好了。

子任务四：

首先要处理一下$P_i$包含$Q_i$或者$Q_i$包含$P_i$的情况，直接用子任务三的方式处理一下就行了。

我们将$P$中第$i$个元素看成一个定义域在$[L_i,R_i]$间的函数，我们把这个函数写作$F_i(x)$。

不难发现$F_i(x)=V_ix-(L_i-1) imes V_i$。

为了方便接下来的表述，我们将$F_i(x)$更改为如下形式：

$F_i(x)=egin{cases} V_ix-(L_i-1) imes V_i xin[L_i,R_i] \ 0 x otin[L_i,R_i]end{cases}$

这是个分段函数

我们在$Q$中找出第y个元素$Q_y$，若存在$i$满足$A_y≤L_i$，则$Q_y$与$P_i$产生的收益为$C_y imes F_i(B_y)$。

最终答案显然为$max(C_y imes F_i(B_y))$。

按照子任务三的套路，我们把$P$和$Q$中所有元素都丢入一个数组中按左端点排序，维护一个保存函数的集合$S$

定义$S(x)=max_{F∈S}F(x)$

我们从大到小从数组中取出元素

若当前元素原先在$P$中，我们求出该元素对应的函数，并把它丢入$S$中。

否则，我们用$C_i imes S(B_i)$更新答案。

该做法复杂度显然是$O(nT_s)$，其中$T_s$表示求$S(x)$的复杂度。

我们不难想到$T_s=O(n)$的做法，但是不够优美。

我们考虑种一棵线段树，线段树的每个节点分别维护一个支持插入函数的半平面交。

如果我们要加入一个定义域在$[l,r]$的一次函数$f(x)$，就在线段树对应的区间上插入这个函数即可。

对于$S(x)$操作，我们只需要找出所有包含$x$的区间，在这些区间上的半平面交上求值即可。

单次插入的复杂度均摊为$O(log^2 n)$ 单次查询的复杂度为$O(log^2 n)$。

然而该方法只能处理出$Q_i$在$P_j$左边的情况。$Q_i$在$P_j$右边的情况我们交换一下两个集合再跑一遍就行了。

所以这是一道扫描线+线段树维护动态半平面的题目

总复杂度就是$O(n log^2 n)$，空间复杂度$O(n log n)$。

完结撒花

  1 #include<bits/stdc++.h>
  2 #define M 100010
  3 #define L long long
  4 #define mid ((aa[x].l+aa[x].r)>>1)
  5 #define S set<line>::iterator
  6 using namespace std;
  7 
  8 int n,N=0,up=0; L ans=0;
  9 struct lr{
 10     int l,r,val;
 11     void rd(){scanf("%d%d%d",&l,&r,&val); up=max(up,r);}
 12 }a[M],b[M];
 13 void swapAB(){for(int i=1;i<=n;i++) swap(a[i],b[i]);}
 14 struct ask{
 15     int id,isa; ask(){id=isa=0;}
 16     ask(int ID,int ISa){id=ID; isa=ISa;}
 17     friend bool operator <(ask A,ask B){
 18         int vala=A.isa?a[A.id].l:b[A.id].l;
 19         int valb=B.isa?a[B.id].l:b[B.id].l;
 20         if(vala!=valb) return vala<valb;
 21         return A.isa>B.isa;
 22     }
 23 }p[M*2];
 24 
 25 namespace SolveContains{
 26     struct seg{int l,r;L maxn;}aa[1<<18];
 27     void build(int x,int l,int r){
 28         aa[x].l=l; aa[x].r=r; aa[x].maxn=0; if(l==r) return;
 29         build(x<<1,l,mid); build(x<<1|1,mid+1,r);
 30     }
 31     void updata(int x,int k,L val){
 32         aa[x].maxn=max(aa[x].maxn,val); 
 33         if(aa[x].l==aa[x].r) return;
 34         if(k<=mid) updata(x<<1,k,val); 
 35         else updata(x<<1|1,k,val);
 36     }
 37     L query(int x,int l,int r){
 38         if(l<=aa[x].l&&aa[x].r<=r) return aa[x].maxn;
 39         L res=0;
 40         if(l<=mid) res=max(res,query(x<<1,l,r));
 41         if(mid<r) res=max(res,query(x<<1|1,l,r));
 42         return res;
 43     }
 44     bool cmp(ask A,ask B){
 45         int vala=A.isa?a[A.id].r:b[A.id].r;
 46         int valb=B.isa?a[B.id].r:b[B.id].r;
 47         if(vala!=valb) return vala<valb;
 48         return A.isa<B.isa;
 49     }
 50     void sub(){
 51         build(1,1,up);
 52         N=0; for(int i=1;i<=n;i++) p[++N]=ask(i,1),p[++N]=ask(i,0);
 53         sort(p+1,p+N+1,cmp);
 54         for(int i=1;i<=N;i++){
 55             int id=p[i].id;
 56             if(p[i].isa){
 57                 L now=query(1,a[id].l,a[id].r);
 58                 ans=max(ans,now*a[id].val);
 59             }else{
 60                 L val=1LL*b[id].val*(b[id].r-b[id].l+1);
 61                 updata(1,b[id].l,val);
 62             }
 63         }
 64     }
 65     void solve(){sub();swapAB();sub();swapAB();}
 66 }
 67 
 68 void ReadData(){
 69     cin>>n;
 70     for(int i=1;i<=n;i++) a[i].rd();
 71     for(int i=1;i<=n;i++) b[i].rd();
 72 }
 73 
 74 struct line{
 75     L k,b; line(){k=b=0;}
 76     line(L _k,L _b){b=_b; k=_k;}
 77     L f(L x){return k*x+b;}
 78     friend bool operator <(line a,line b){
 79         if(a.k==b.k) return a.b<b.b;
 80         return a.k<b.k;
 81     }
 82     friend double operator *(line a,line b){
 83         return 1.*(b.b-a.b)/(a.k-b.k);
 84     }
 85 };
 86 bool under(line a,line b,line c){
 87     double x=a*b;
 88     if(a.f(x)>=c.f(x)) return 1;
 89     return 0;
 90 }
 91 struct plane{//半平面
 92     set<line> s;
 93     map<double,line> mp;
 94     void clear(){
 95         s.clear(); mp.clear();
 96         s.insert(line(0,0));
 97         mp[-100]=line(0,0);
 98     }
 99     L f(int x){
100         map<double,line>::iterator it=mp.upper_bound(x); it--;
101         line now=it->second;
102         return now.f(x);
103     }
104     void remove(S it){
105         S nxt=it,pre=it; nxt++; pre--;
106         if(nxt!=s.end()){
107             double l=(*it)*(*nxt);
108             mp.erase(mp.find(l));
109             double x=(*nxt)*(*pre);
110             mp[x]=*nxt;
111         }
112         double r=(*it)*(*pre);
113         mp.erase(mp.find(r));
114         s.erase(it);
115     }
116     void insert(line l){
117         S nxt=s.upper_bound(l),pre=nxt; pre--;
118         if(nxt!=s.end()){
119             double x=(*nxt)*(*pre);
120             mp.erase(mp.find(x));
121             double r=l*(*nxt);
122             mp[r]=(*nxt);
123         }
124         double x=l*(*pre);
125         s.insert(l); mp[x]=l;
126     }
127     void add(line l){
128         S it=s.upper_bound(l),nx=it,ls=it,hh; ls--;
129         if(it!=s.end()&&under(*it,*ls,l)) return;
130         for(nx++;it!=s.end()&&nx!=s.end();it=nx,nx++){
131             double x=(*it)*(*nx);
132             line now=*it;
133             if(now.k==l.k) return;
134             if(l.f(x)>=now.f(x)) remove(it);
135             else break;
136         }
137         it=s.upper_bound(l); it--; ls=it;
138         for(ls--;it!=s.begin();){
139             double x=(*it)*(*ls);
140             line now=(*it);
141             if(now.k==l.k||l.f(x)>=now.f(x)){
142                 hh=it; hh--; ls--;
143                 remove(it);
144                 it=hh;
145             }
146             else break;
147         }
148         insert(l);
149     }
150 };
151 
152 namespace seg{
153     struct hhh{
154         int l,r; plane p;
155         void insert(line now){return p.add(now);}
156         L f(L x){return p.f(x);}
157     }aa[1<<18];
158     
159     void build(int x,int l,int r){
160         aa[x].l=l; aa[x].r=r; aa[x].p.clear();
161         if(l==r) return;
162         build(x<<1,l,mid); build(x<<1|1,mid+1,r);
163     }
164     void updata(int x,int l,int r,line now){
165         if(l<=aa[x].l&&aa[x].r<=r) return aa[x].insert(now);
166         if(l<=mid) updata(x<<1,l,r,now);
167         if(mid<r) updata(x<<1|1,l,r,now);
168     }
169     L query(int x,int k){
170         L res=aa[x].f(k);
171         if(aa[x].l==aa[x].r) return res;
172         if(k<=mid) res=max(res,query(x<<1,k));
173         else res=max(res,query(x<<1|1,k));
174         return res;
175     }
176 }
177 
178 namespace SolveOthers{
179     void sub(){
180         seg::build(1,1,up);
181         N=0; for(int i=1;i<=n;i++) p[++N]=ask(i,1),p[++N]=ask(i,0);
182         sort(p+1,p+N+1);
183         for(int i=N;i;i--){
184             int id=p[i].id;
185             if(p[i].isa){
186                 L now=seg::query(1,a[id].r);
187                 ans=max(ans,now*a[id].val);
188             }else{
189                 line hh=line(b[id].val,-1LL*b[id].val*(b[id].l-1));
190                 seg::updata(1,b[id].l,b[id].r,hh);
191             }
192         }
193     }
194     void solve(){sub();swapAB();sub();}
195 }
196 
197 main(){
198     ReadData();
199     SolveContains::solve();
200     SolveOthers::solve();
201     cout<<ans<<endl;
202 }