题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5306
题目大意：给你n个数，你有3种操作，操作如下：
$0,x,y,v$，对区间$a[x]-a[y]$取$min(v,a[i])$
$1,x,y$，询问区间最大值
$2,x,y$，询问区间和
Sample Input
1 5 5 1 2 3 4 5 1 1 5 2 1 5 0 3 5 3 1 1 5 2 1 5
Sample Output
5 15 3 12
吉司机线段树，通常就是比正常的线段树多维护了个次的东西，比若说这题，我们可以维护一个次大值，如果该区间的最大值小于修改的v，那么直接return，如果大于次大值，那么也就是说只有最大值需要修改，那么我们记录一下最大值的个数，修改的时候我们直接对sum+（最大值-val）乘上最大值的数量就好了，然后将该区间的最大值修改为val，然后开始push_down了，如下所示：
void solve(int rt,int val) { if (val>=tree[rt].mx) return; tree[rt].sum+=1LL*(val-tree[rt].mx)*tree[rt].mxnb; tree[rt].mx=val; } void push_down(int rt) { solve(lc,tree[rt].mx);solve(rc,tree[rt].mx); } void update(int l,int r,int rt,int L,int R,int val) { if (val>=tree[rt].mx) return; if (l>=L && r<=R && val>tree[rt].cimx){ solve(rt,val); return; } int mid=(l+r)>>1; push_down(rt); if (mid>=L) update(lson,L,R,val); if (mid<R) update(rson,L,R,val); push_up(rt); }
这样看起来似乎复杂度还是有点高，但对于随机数据来讲，他的平均复杂度还是不错的
以下是AC代码：
#include <algorithm> #include <cstring> #include <cstdio> #include <iostream> using namespace std; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define lc rt<<1 #define rc rt<<1|1 typedef long long ll; const int mac=1e6+10; struct node { int mx,cimx,mxnb; ll sum; }tree[mac<<2]; void push_up(int rt) { tree[rt].sum=tree[lc].sum+tree[rc].sum; if (tree[lc].mx==tree[rc].mx){ tree[rt].mx=tree[lc].mx; tree[rt].mxnb=tree[lc].mxnb+tree[rc].mxnb; tree[rt].cimx=max(tree[lc].cimx,tree[rc].cimx); } else { if (tree[lc].mx>tree[rc].mx) { tree[rt].mxnb=tree[lc].mxnb; tree[rt].cimx=max(tree[rc].mx,tree[lc].cimx); } else { tree[rt].mxnb=tree[rc].mxnb; tree[rt].cimx=max(tree[lc].mx,tree[rc].cimx); } tree[rt].mx=max(tree[lc].mx,tree[rc].mx); } } void solve(int rt,int val) { if (val>=tree[rt].mx) return; tree[rt].sum+=1LL*(val-tree[rt].mx)*tree[rt].mxnb; tree[rt].mx=val; } void push_down(int rt) { solve(lc,tree[rt].mx);solve(rc,tree[rt].mx); } void build(int l,int r,int rt) { tree[rt].cimx=-1; if (l==r){ int x; scanf ("%d",&x); tree[rt].mx=tree[rt].sum=x; tree[rt].mxnb=1; return; } int mid=(l+r)>>1; build(lson);build(rson); push_up(rt); } void update(int l,int r,int rt,int L,int R,int val) { if (val>=tree[rt].mx) return; if (l>=L && r<=R && val>tree[rt].cimx){ solve(rt,val); return; } int mid=(l+r)>>1; push_down(rt); if (mid>=L) update(lson,L,R,val); if (mid<R) update(rson,L,R,val); push_up(rt); } ll query(int l,int r,int rt,int L,int R,int id) { ll ans=0; if (l>=L && r<=R) { if (!id) return 1LL*tree[rt].mx; else return tree[rt].sum; } push_down(rt); int mid=(l+r)>>1; if (mid>=L) { if (!id) ans=max(ans,query(lson,L,R,id)); else ans+=query(lson,L,R,id); } if (mid<R) { if (!id) ans=max(ans,query(rson,L,R,id)); else ans+=query(rson,L,R,id); } return ans; } int main() { //freopen("in.txt","r",stdin); int t; scanf ("%d",&t); while (t--){ int n,q; scanf ("%d%d",&n,&q); build(1,n,1); while (q--){ int opt,l,r,v; scanf ("%d%d%d",&opt,&l,&r); if (!opt) { scanf ("%d",&v); update(1,n,1,l,r,v); } else if (opt==1) printf("%lld ",query(1,n,1,l,r,0)); else printf("%lld ",query(1,n,1,l,r,1)); } } return 0; }