xlpri @ 2024-11-15 21:27:38
两份代码,一份之前写的,一份RE,没检查出漏了哪句
之前的:
#include <bits/stdc++.h>
using namespace std;
int n,m,k,num[100007];
struct node
{
long long num;
long long laz;
}tre[400028];
void pushup(int u)
{
tre[u].num = tre[u*2].num + tre[u*2 + 1].num;
}
void build(int u,int l,int r)
{
if(l == r)
{
tre[u].num = num[l];
return;
}
int mid = (l + r)/2;
build(u*2,l,mid);
build(u*2 + 1,mid + 1,r);
pushup(u);
}
bool ifin(int L,int R,int l,int r) /*l,r查询区间,L,R树区间*/
{
return (l <= L) && (R <= r);
}
bool ifout(int L,int R,int l,int r)
{
return (L > r) || (R < l);
}
void maketag(int u,int len,long long x)
{
tre[u].laz += x;
tre[u].num += len*x;
return;
}
void pushdown(int u,int l,int r)
{
int mid = (l + r)/2;
maketag(u*2,mid - l + 1,tre[u].laz);
maketag(u*2 + 1,r - mid,tre[u].laz);
tre[u].laz = 0;
}
long long query(int u,int L,int R,int l,int r)
{
if(ifin(L,R,l,r))
{
return tre[u].num;
}
else if(!ifout(L,R,l,r))
{
int mid = (L + R)/2;
pushdown(u,L,R);
return query(u*2,L,mid,l,r) + query(u*2 + 1,mid + 1,R,l,r);
}
else return 0;
}
void update(int u,int L,int R,int l,int r,long long x)
{
if(ifin(L,R,l,r))
{
maketag(u,R - L + 1,x);
}
else if(!ifout(L,R,l,r))
{
int mid = (L + R)/2;
pushdown(u,L,R);
update(u*2,L,mid,l,r,x);
update(u*2 + 1,mid + 1,R,l,r,x);
pushup(u);
}
else return;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++) cin >> num[i];
build(1,1,n);
while(m--)
{
int t,x,y;
cin >> t >> x >> y;
if(t == 1)
{
cin >> k;
update(1,1,n,x,y,k);
}
else cout << query(1,1,n,x,y) << endl;
}
return 0;
}
RE:
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,m,x,y,num[100007];
struct Tree
{
ll num;
ll laz;
} tre[400028];
void pushnum(int u)
{
tre[u].num = tre[u*2].num + tre[u*2+1].num;
}
void build(int u,int l,int r)
{
if(l == r)
{
tre[u].num = num[l];
return;
}
int mid = (l + r)/2;
build(u*2, l, mid);
build(u*2+1, mid+1, r);
pushnum(u);
}
bool ifin(int L,int R,int l,int r) //L,R大区间 r,l查找区间
{
return (l <= L && R <= r);
}
bool ifout(int L,int R,int l,int r)
{
return (R < l || r < L);
}
void maketag(int u,int l,int r,ll x)
{
tre[u].laz += x;
tre[u].num += (r - l + 1)*x;
return;
}
void update_laz(int u,int l,int r)
{
int mid = (l + r)/2;
maketag(u*2, l, mid, tre[u].laz);
maketag(u*2+1, mid+1, r, tre[u].laz);
tre[u].laz = 0;
}
ll ffind(int u,int L,int R,int l,int r)
{
if(ifin(L,R,l,r))
{
return tre[u].num;
}
else if(!ifout(L,R,l,r))
{
int mid = (l + r)/2;
update_laz(u,L,R);
return ffind(u*2, L, mid, l, r) + ffind(u*2+1, mid+1, R, l, r);
}
else return 0;
}
void update(int u,int L,int R,int l,int r,ll x)
{
if(ifin(L,R,l,r))
{
maketag(u,l,r,x);
}
else if(!ifout(L,R,l,r))
{
int mid = (l + r)/2;
update_laz(u,L,R);
update(u*2, L, mid, l, r, x);
update(u*2+1, mid+1, R, l, r, x);
pushnum(u);
}
return;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++) cin >> num[i];
build(1,1,n);
while(m--)
{
int t;
cin >> t >> x >> y;
if(t == 1)
{
int k;
cin >> k;
update(1,1,n,x,y,k);
}
else cout << ffind(1,1,n,x,y) << endl;
}
return 0;
}
by qazsedcrfvgyhnujijn @ 2024-11-15 21:31:32
RE 的那份修改和查询函数里面的 mid
都写错了;
你可能需要一个文件对比工具。
by IRIDESCENTqwq @ 2024-11-15 21:48:20
@xlpri query和update中的mid写错了,把小写l打成大写L了……(我的习惯是在线段树结构体中加两个变量l和r,代表当前区间的左右界,这样就不会和参数l、r搞混了)
by xlpri @ 2024-11-15 21:52:24
@qazsedcrfvgyhnujijn@IRIDESCENTqwq
感谢,已AC
by qazsedcrfvgyhnujijn @ 2024-11-15 21:57:06
@xlpri 补充:我的习惯是把当前节点的 l
,r
表示,正操作/询问的区间用 queryl -> ql
,queryr -> qr
表示,然后直接在线段树最前面 #define mid ((l + r) >> 1)
。