吉老师线段树（HDU5306）

给定一个数组a，实现三种操作：
1.将[l,r]区间的数修改为min（a_i,t）
2.求[l,r]区间最大值
3.求[l,r]区间和

之前der了几个细节问题，下次左右子节点一定在函数开头算出lchild和rchild。
解法不难理解，使用线段树维护区间和、区间最大值、区间最大值的个数和区间次大值。当要修改的数（t）大于等于区间最大值的时候，直接返回。大于区间次大值但小于区间最大值，我们可以利用已经维护的区间最大值个数去更新区间和，并下放懒标记。否则继续递归。
可以证明时间复杂度是O(mlog^2 n)，证明过程详见吉老师当年在国家集训队的论文。
代码如下：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, m;

ll a[1000005];

struct treenode{

ll cha;

ll sum,max,maxcount,secmax;

#define sum(x) tree[x].sum

#define cha(x) tree[x].cha

#define segmax(x) tree[x].max

#define maxc(x) tree[x].maxcount//统计区间内最大值的个数

#define secm(x) tree[x].secmax//区间次大值

}tree[1000005<<2];

void pushup(ll p){

sum(p)=sum(p<<1)+sum(p<<1|1);

if(segmax(p<<1)==segmax(p<<1|1)){

secm(p)=max(secm(p<<1),secm(p<<1|1));

segmax(p)=segmax(p<<1);

maxc(p)=maxc(p<<1)+maxc(p<<1|1);

}

else if(segmax(p<<1)<segmax(p<<1|1)){

secm(p)=max(segmax(p<<1),secm(p<<1|1));

segmax(p)=segmax(p<<1|1);

maxc(p)=maxc(p<<1|1);

}

else{

secm(p)=max(segmax(p<<1|1),secm(p<<1));

segmax(p)=segmax(p<<1);

maxc(p)=maxc(p<<1);

}

}

void pushdown(ll p){

if(cha(p)!=-1)

{

ll lc=p<<1;

ll rc=p<<1|1;

if(cha(p)<segmax(lc)&&cha(p)>secm(lc)){

sum(lc)-=1ll*(segmax(lc)-cha(p))*maxc(lc);

cha(lc)=cha(p);

segmax(lc)=cha(p);



}

if(cha(p)<segmax(rc)&&cha(p)>secm(rc)){

sum(rc)-=1ll*(segmax(rc)-cha(p))*maxc(rc);

cha(rc)=cha(p);

segmax(rc)=cha(p);

}

cha(p)=-1;

}

}

void build(ll s, ll t, ll p) {

//[s,t]区间建树，节点编号为p

cha(p)=-1;

if (s == t) {

secm(p)=-1;

maxc(p)=1;

sum(p) = a[s];

segmax(p) = a[s];

return;

}

ll mid = s + t >>1;

build(s, mid, p<<1);

build(mid + 1, t, p <<1| 1);

pushup(p);

}

ll getsum(ll l, ll r, ll s, ll t, ll p) {

// [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号

if (l <= s && t <= r)

return sum(p);

ll mid = s + t >>1, sum = 0;

pushdown(p);

if (l <= mid) sum += getsum(l, r, s, mid, p <<1);

if (r > mid) sum += getsum(l, r, mid + 1, t, p <<1|1);

return sum;

}

ll getmax(ll l, ll r, ll s, ll t, ll p) {

// [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号

if (l <= s && t <= r)

return segmax(p);

ll mid = (s + t) >>1, sum = 0;

pushdown(p);

if (l <= mid) sum = max(sum,getmax(l, r, s, mid, p <<1));

if (r > mid) sum = max(sum,getmax(l, r, mid + 1, t, p <<1| 1));

return sum;

}

//updateto为区间修改为某个值

void updateto(ll l, ll r, ll c, ll s, ll t, ll p) {

if(c>=segmax(p))return;

if (l <= s && t <= r&&c>secm(p)) {

sum(p)-=1ll*(segmax(p)-c)*maxc(p);

segmax(p)=c;

cha(p)=c;

return;

}

int mid = (s + t) >> 1;

pushdown(p);

if (l <= mid) updateto(l, r, c, s, mid, p<<1);

if (r > mid) updateto(l, r, c, mid + 1, t, p<<1|1 );

pushup(p);

}

int main() {

int _;

scanf("%d",&_);

while(_--) {

ll aa, l, r,t;

scanf("%lld%lld",&m,&n);

for (int i = 1; i <= m; i++) {

scanf("%lld",&a[i]);

}

build(1, m, 1);

while (n--) {

scanf("%lld%lld%lld",&aa,&l,&r);

if (aa == 0) {

scanf("%lld",&t);

updateto(l, r, t, 1, m, 1);

} else if (aa == 1) {

printf("%lld\n",getmax(l, r, 1, m, 1) );

} else {

printf("%lld\n",getsum(l, r, 1, m, 1) );

}

}

}



}