csapp-shlab-WP
新人蒟蒻前来水一次博客
emmmmm线段树真是个耗头发的好东西。
话不多说上代码【语文差的555】
#### 头文件及定义等 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19//其实用不到这么多
using namespace std;
ll n,m,a,b,c,f;//不解释
ll tr[N<<1],//本体
R[N<<1],L[N<<1],//左右子树
Lazy[N<<1],//懒标
cnt,root,now;//节点个数，根节点，当前节点
//线段树动态开点一般二倍即可【听说静态开点要四倍】
ll tp;//存储某些临时变量以备不时之需1
2
3
4
5
6
7
8
9ill insert_sgl(ll &now,ll l,ll r,ll nu,ll po)
//num(插入值),position(插入位置)
{
if(!now)now=++cnt;
tr[now]+=nu;if(!(r-l))return nu;
ll mid=(l+r)>>1;
if(po<=mid)return insert_sgl(L[now],l,mid,nu,po);
else return insert_sgl(R[now],mid+1,r,nu,po);
}1
2
3
4
5
6
7
8
9
10
11
12
13
14ill insert_ivl(ll &now,ll l,ll r,ll nu,ll pl,ll pr)
{
if(now==0)now=++cnt;
if(pl<=l&&pr>=r)//当前区间完全属于查询区间时
{tr[now]+=nu*(r-l+1);//区间长度=右端点-左端的+1；
Lazy[now]+=nu;//打上lazytag
return nu;}
pushdown(now,l,r);//顺手下推
ll mid=(l+r)>>1;
if(pl<=mid) insert_ivl(L[now],l,mid,nu,pl,pr);
if(pr>mid) insert_ivl(R[now],mid+1,r,nu,pl,pr);
pushup(now);
return nu;
}
先介绍下懒人标记：
所谓懒人标记其实是一种延迟性质的操作用来显示自己与众不同 ，把所有的修改操作堆积起来，等到查询的时候统一完成像不像开学前一晚上的你，这里我们需要两个辅（zhong）助（yao）函数：下推（pushdown）,上拉（pushup）操作;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25ill pushdown(ll& now,ll l,ll r)//下推
//把自己的lazytag下发给左右儿子，并清除标记
{
if(Lazy[now])
{
ll mid=(l+r)>>1;
if(L[now]==0)L[now]=++cnt;//动态开点操作
Lazy[L[now]]+=Lazy[now];
tr[L[now]]+=Lazy[now]*(mid-l+1);
//标记打在哪，区间就更新到哪
if(R[now]==0)R[now]=++cnt;
Lazy[R[now]]+=Lazy[now];
tr[R[now]]+=Lazy[now]*(r-mid);
//有标记的区间一定是运算过的
Lazy[now]=0;
}
return now;
}
ill pushup(ll &now)
{
return tr[now]=tr[L[now]]+tr[R[now]];
}
//个人觉得这个完全可以宏定义或者一行代码写在程序后，
//但为了不让下推单着【误】，故写在这里博君一笑。1
2
3
4
5
6
7
8
9
10
11
12ill query_ivl(ll &now,ll l,ll r,ll ql,ll qr)
{
if(l>=ql&&r<=qr)return tr[now];
//如果区间完全被包含在查询区间内则必然被更新过，
//可直接返回
pushdown(now,l,r);
ll mid=(l+r)>>1;
ll ls=0;
if(ql<=mid) ls+=query_ivl(L[now],l,mid,ql,qr);
if(qr>mid) ls+=query_ivl(R[now],mid+1,r,ql,qr);
return ls;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24int main()
{
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&tp);
insert_sgl(root,1,n,tp,i);//一切都要从头来
}
for(ll i=1;i<=m;i++)
{
scanf("%lld",&f);
if(f==1)
{
scanf("%lld%lld%lld",&a,&b,&c);
insert_ivl(root,1,n,c,a,b);
}
if(f==2)
{
scanf("%lld%lld",&a,&b);
printf("%lld\n",query_ivl(root,1,n,a,b));
}
}
return 0;
}小小声说一句，现在的我已经会手撸线段树了hhhhhhhhh Enter text in Markdown. Use the toolbar above, or click the ? button for formatting help.