题意
要求维护一个直线序列，支持以下操作：
- 操作 \(1\)，在 \(K\) 这个位置用一条直线 \(y=Zx+S-Z\times T\) 覆盖这个点原来的直线。
- 操作 \(2\)，查询区间 \([A,B]\) 内的直线在 \(T\) 处的最大值。
思路
看到加入直线求最大值想到李超线段树。
但是发现题目的查询是区间查询，李超树只能做全局查询。
然后可以想到线段树套李超树。但是题目毒瘤的空间让树套树变得不可行。
既然复杂度瓶颈出现在空间复杂度的话，考虑使用时间换空间，采用分块套李超树。
具体实现
以下设块长为 \(B\)。
每个块开一个李超树，修改操作直接在对应位置单点修改，在李超树上插入即可。如果覆盖了原来的这个位置上的直线，则整块暴力重构。也可以打标记留到查询时再重构。单次时间复杂度 \(\mathcal{O}(\log n)\) 到 \(\mathcal{O}(B\log T)\)。
查询时散块直接遍历，整块在李超树上查询即可。单次时间复杂度 \(\mathcal{O}(B)\) 到 \(\mathcal{O}(\frac{n}{B}\log T+B)\)。
总时间复杂度 \(\mathcal{O}(mB\log n+\frac{mn}{B}\log T)\)，\(B=\sqrt{n}\) 时最优，为 \(\mathcal{O}(m\sqrt{n}\log n)\)。李超树动态开点，空间复杂度 \(\mathcal{O}(n)\)。
实际 \(B=230\) 左右最优。跑得飞快。
代码实现
#include <bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int N=1e5+5,len=230,nel=435,inf=1e9;
#define id(x) ((x-1)/len)
#define pl(x) ((x)*len+1)
#define pr(x) (((x)+1)*len)
struct Line{ll k,b; // y=k*x+bll calc(ll x){return x*k+b;}
}a[N];
struct SegmentTree{Line val[len];int cnt,rt,ls[len],rs[len];void update(int &p,Line x,int pl,int pr){if(!p){p=++cnt;val[p]=Line{-inf,-1ll*inf*inf};ls[p]=rs[p]=0; // 动态开点记得清空}// 因为插入的一定是 [1,1e6] 所以不用判断 l<=pl&&pr<=rconst int mid=(pl+pr)>>1;if(x.calc(mid)-val[p].calc(mid)>0)swap(val[p],x);if(x.calc(pl)-val[p].calc(pl)>0)update(ls[p],x,pl,mid);if(x.calc(pr)-val[p].calc(pr)>0)update(rs[p],x,mid+1,pr);}ll query(int p,int pos,int pl,int pr){ll ans=-1e18;while(p&&pl!=pr){ans=max(ans,val[p].calc(pos));const int mid=(pl+pr)>>1;if(mid>=pos)p=ls[p],pr=mid;else p=rs[p],pl=mid+1;}if(p)ans=max(ans,val[p].calc(pos));return ans;}
}tr[nel+1];
bool vis[nel];
int n,m;
void update(int pos,Line x){if(a[pos].b!=-1e18){vis[id(pos)]=1;a[pos]=x;return;}a[pos]=x;tr[id(pos)].update(tr[id(pos)].rt,x,1,1e6); // 因为保证 T 递增所以直接插入 [1,1e6] 节省空间
}
ll query(int t,int l,int r){ll ans=-1e18;if(id(l)==id(r)){for(int i=l;i<=r;i++)ans=max(ans,a[i].calc(t));return ans;}for(int i=l;i<=pr(id(l));i++)ans=max(ans,a[i].calc(t));for(int i=pl(id(r));i<=r;i++)ans=max(ans,a[i].calc(t));for(int i=id(l)+1;i<id(r);i++){if(vis[i]){ // 重构整块tr[i].rt=tr[i].cnt=0;for(int j=pl(i);j<=pr(i);j++){if(a[j].b!=-1e18)tr[i].update(tr[i].rt,a[j],1,1e6);}vis[i]=0;}ans=max(ans,tr[i].query(tr[i].rt,t,1,1e6));}return ans;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)a[i]={-inf,-1ll*inf*inf};for(int i=1;i<=m;i++){int op,t,x,y,z;cin>>op>>t>>x>>y;if(op==1)cin>>z,update(x,Line{y,z-1ll*t*y});if(op==2){if(x>y)swap(x,y);ll ans=query(t,x,y);if(ans<-1e15)cout<<"nema\n"; // 判断区间中没有直线else cout<<ans<<'\n';}}return 0;
}