[HDU5306]吉司机线段树

吉司机线段树

给每一个点定义一个势能函数为该节点下不同的值的个数

若该操作能够使当前节点的势能降低，那么暴力修改该区间内的所有元素，否则直接打标记

这题每个节点记录最大值mx，最大值个数tot，次大值se，答案sum；

若新来的值比>=mx，那么这个操作是没有意义的，直接return

若新来的值>se并且<mx，那么对mx整体减少，更新答案

若新来的值<=se，那么这次操作会使该节点势能函数降低，暴力递归修改区间内所有元素

tips：

这题卡常，要用读入挂才能过

#include <stdio.h>
#pragma GCC optimize (2)
#define mid ((l+r)>>1)
#define ls l,mid,t<<1
#define rs mid+1,r,t<<1|1
#define N 1000050
typedef long long LL;
struct Node{int mx,tot,se;LL sum;}tr[4*N];
int a[N],n,m;
int ag[4*N];
char *ch, *ch1, buf[40*1024000+5], buf1[40*1024000+5];
void read(int &x)
{
for (++ch; *ch <= 32; ++ch);
for (x = 0; '0' <= *ch; ch++)
x = x * 10 + *ch - '0';
}
inline int max(const int &a,const int &b){return a<b?b:a;}
inline int min(const int &a,const int &b){return a<b?a:b;}
//inline int read(int &x)
//{
//
x=0;char ch=getchar();
//
while(ch<'0'||'9'<ch){ch=getchar();}
//
while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
//
return x;
//}
#define pc(x) putchar(x)
inline void print(LL x)
{
static char b[100];
if(x==0) {pc(48); return;}
if(x<0) {pc('-'); x=-x;}
char *s=b;
while(x) *(++s)=x%10, x/=10;
while(s!=b) pc((*(s--))+48);
}
inline void add(Node &r,const Node &p1,const Node &p2) {
r.sum = p1.sum + p2.sum;
if (p1.mx == p2.mx) {
r.mx = p1.mx;
r.tot = p1.tot + p2.tot;
r.se = max(p1.se,p2.se);
} else {
if (p1.mx < p2.mx)
{
r.mx = p2.mx; r.tot = p2.tot;
r.se = max(p2.se,p1.mx);
}
else
{
r.mx = p1.mx; r.tot = p1.tot;
r.se = max(p1.se,p2.mx);
}
}
}
void build(const int &l,const int &r,const int &t) {
ag[t] = -1;
if (l == r) { tr[t] = (Node){a[l],1,-1,a[l]}; return ; }
build(ls); build(rs);
add( tr[t] , tr[t<<1] , tr[t<<1|1] );
}
inline void push_down(int ,int ,int );
void update(int ,int ,int );
void query(int ,int ,int );
void color(int l,int r,int t) {
if (ag[t] > tr[t].mx) { ag[t] = -1; return ; }
if (ag[t] <= tr[t].se) {
if (ag[t] != -1 && l != r) push_down(l,r,t);
add( tr[t] , tr[t<<1] , tr[t<<1|1] );
return ;
}
tr[t].sum -= (LL)(tr[t].mx - ag[t]) * tr[t].tot;
tr[t].mx = ag[t];
}
inline void push_down(int l,int r,int t) {
ag[t<<1] = (ag[t<<1] != -1) ? min(ag[t<<1],ag[t]) : ag[t];
ag[t<<1|1] = (ag[t<<1|1] != -1) ? min(ag[t<<1|1],ag[t]) : ag[t];
ag[t] = -1;
color(ls); color(rs);
}
int ll,rr,v;
void update(int l,int r,int t) {
if (ll <= l && r <= rr) {
ag[t] = (ag[t] != -1) ? min(ag[t],v) : v;
color(l,r,t);
return ;
}
if (ag[t] != -1) push_down(l,r,t);
if (ll <= mid) update(ls);
if (rr > mid) update(rs);
add( tr[t] , tr[t<<1] , tr[t<<1|1] );
}
LL ans_sum;int ans_max;
void query(int l,int r,int t) {
if (ll <= l && r <= rr) {
ans_sum += tr[t].sum;
ans_max = max(tr[t].mx , ans_max);
return ;
}
if (ag[t] != -1) push_down(l,r,t);
if (ll <= mid) query(ls);
if (mid < rr) query(rs);
add( tr[t] , tr[t<<1] , tr[t<<1|1] );
}
void solve() {
//
memset(tr,0,sizeof(tr));
//
memset(ag,0,sizeof(ag));
read(n); read(m);
for (int i=1;i<=n;i++) read(a[i]);
build(1,n,1);
for (int _=1,cmd;_<=m;_++) {
read(cmd);
if (cmd == 0) {
read(ll); read(rr); read(v);
update(1,n,1);
} else {
ans_sum = ans_max = 0;
read(ll); read(rr);
query(1,n,1);
if (cmd == 1)
print(ans_max);
else
print(ans_sum);
putchar('n');
}
}
}
int main() {
ch = buf - 1;
ch1 = buf1 - 1;
fread(buf, 1, 1000 * 35 * 1024, stdin);
int T;
for (read(T);T--;) solve();
return 0;
} 

最后

以上就是重要花瓣为你收集整理的[HDU5306]吉司机线段树的全部内容，希望文章能够帮你解决[HDU5306]吉司机线段树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。