题目
题目大意
维护一个有一次函数组成的序列
具体来说，对于位置xxx，现在的值为sx+zx∗(T−tx)s_x+z_x*(T-t_x)sx+zx∗(T−tx)
有两个操作，修改某个位置上的一次函数，还有询问一段区间内的当前最大值。
思考历程&正解
（说实在的，感觉这场比赛三题中这题最简单，因为我一开始只想出了这题……）
首先，看到这一次函数，我们自然会想到斜率优化。
设zi<zjz_i<z_jzi<zj且jjj优于iii，然后……随便推一下就好了。
假如题目询问的区间是整个区间，并且没有修改操作，直接一个队列推过去就好了。
接下来想一下如何处理区间询问？
然后我就立即想到了莫队，但这样问题似乎就有些复杂了。
我们这个单调队列的顺序是按照zzz来排的，现在左右边界的删减，使我们不得不找出它在按zzz排序后的位置，然后……二分？可是队列要支持插入删除，所以……难道要维护平衡树？
还有要动态维护斜率……然后是修改咋搞……
我也不明白我一开始是怎么认为它是对的，不过后来我就发现，莫队似乎不行。
所以我就开始思考分块。
分块大法好，对于每一个块，维护一个按zzz排序的序列和单调队列。
在询问时直接扫单调队列，在修改时暴力重构。
暴力重构的时候先重构按zzz排序的序列，不需要再次进行快排，只需要线性地直接插入。
插入之后重新建立单调队列。
这个做法的正确性显然是对的。
可是复杂度？
我一开始也有这样的疑问，但后来我才知道，由于单调队列是线性的（每个进出一次），最多会暴力重构mmm次，一共重构mnm\sqrt nmn个值，那么单调队列就是O(mn)O(m\sqrt n)O(mn)的。
总之，时间复杂度是O(mn)O(m\sqrt n)O(mn)
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <cmath>
#include <climits>
#include <algorithm>
#define N 100010
#define M 300010
int n,m,K;
int bel[N];
long long T[N],Z[N],S[N];
int rnk[320][320],q[320][320];
int siz[320],head[320],tail[320];
inline long long get(int x,long long t){
return T[x]?S[x]+Z[x]*(t-T[x]):LLONG_MIN;
}
inline long long bf(long long t,int l,int r){
long long ans=LLONG_MIN;
for (int i=l;i<=r;++i)
ans=max(ans,get(i,t));
return ans;
}
inline bool calc1(int i,int j,long long t){
return S[i]-Z[i]*T[i]-S[j]+Z[j]*T[j]<=t*(Z[j]-Z[i]);
}
inline bool calc2(int i,int j,int k){
return (S[i]-Z[i]*T[i]-S[j]+Z[j]*T[j])*(Z[k]-Z[j])>=(S[j]-Z[j]*T[j]-S[k]+Z[k]*T[k])*(Z[j]-Z[i]);
}
inline void repair(int k,long long t){
while (head[k]<tail[k] && calc1(q[k][head[k]],q[k][head[k]+1],t))
head[k]++;
}
inline void rebuild(int k,long long t){
q[k][head[k]=tail[k]=0]=rnk[k][0];
for (int i=1;i<siz[k];++i){
while (head[k]<tail[k] && calc2(q[k][tail[k]-1],q[k][tail[k]],rnk[k][i]))
tail[k]--;
q[k][++tail[k]]=rnk[k][i];
}
}
int main(){
scanf("%d%d",&n,&m);
K=sqrt(n);
for (int i=0;i<n;++i)
bel[i]=i/K;
while (m--){
int op;
scanf("%d",&op);
if (op==1){
long long t,k,z,s;
scanf("%lld%lld%lld%lld",&t,&k,&z,&s);
k--;
T[k]=t,Z[k]=z,S[k]=s;
int i;
for (i=0;i<siz[bel[k]];++i)
if (rnk[bel[k]][i]==k){
for (++i;i<siz[bel[k]];++i)
rnk[bel[k]][i-1]=rnk[bel[k]][i];
siz[bel[k]]--;
break;
}
for (i=0;i<siz[bel[k]];++i)
if (Z[rnk[bel[k]][i]]>z){
for (int j=siz[bel[k]];j>i;--j)
rnk[bel[k]][j]=rnk[bel[k]][j-1];
rnk[bel[k]][i]=k;
siz[bel[k]]++;
break;
}
if (i>=siz[bel[k]])
rnk[bel[k]][siz[bel[k]]++]=k;
rebuild(bel[k],t);
}
else{
long long t,a,b,ans=LLONG_MIN;
scanf("%lld%lld%lld",&t,&a,&b);
a--,b--;
if (a>b)
swap(a,b);
if (bel[a]==bel[b])
ans=bf(t,a,b);
else{
ans=max(bf(t,a,bel[a]*K+K-1),bf(t,bel[b]*K,b));
for (int i=bel[a]+1;i<=bel[b]-1;++i)
if (siz[i]){
repair(i,t);
ans=max(ans,get(q[i][head[i]],t));
}
}
if (ans!=LLONG_MIN)
printf("%lld\n",ans);
else
printf("nema\n");
}
}
return 0;
}
总结
一句话：分块大法好！