Dangerise @ 2024-01-23 19:49:17
这是一道简单线段树的题目,为节省各位时间,以下简述题目大意
题目要求支持三种操作
50pts代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll qread() {
ll ans=0;
char c=getchar();
bool f=0;
while(c<'0'||c>'9') {
if(c=='-') {
f=1;
}
c=getchar();
}
while(c>='0'&&c<='9') {
ans=ans*10+c-'0';
c=getchar();
}
if(f) {
return -ans;
} else {
return ans;
}
}
struct Node {
int l,r;
};
Node nodes[4004000];
ll add_tag[4004000];
ll set_to[4004000];
bool set_tag_exist[4004000];
ll maxn[4004000];
inline int left_child(int x) {
return x<<1;
}
inline int right_child(int x) {
return (x<<1)|1;
}
inline int node_size(int x) {
return nodes[x].r-nodes[x].l+1;
}
inline int middle(int x) {
return (nodes[x].l+nodes[x].r)>>1;
}
ll ini[4004000];
int n,m;
inline void build(int node,int l,int r) {
nodes[node].l=l;
nodes[node].r=r;
if(l==r) {
maxn[node]=ini[l];
return;
}
int mid=middle(node);
build(left_child(node),l,mid);
build(right_child(node),mid+1,r);
maxn[node]=max(maxn[left_child(node)],maxn[right_child(node)]);
}
inline void tad(int node,int x) {
if(set_tag_exist[node]) {
set_to[node]+=x;
} else {
add_tag[node]+=x;
}
maxn[node]+=x;
}
inline void pushdown(int node) {
int l=left_child(node),r=right_child(node);
if(add_tag[node]) {
tad(l,add_tag[node]);
tad(r,add_tag[node]);
add_tag[node]=0;
}
if(set_tag_exist[node]) {
add_tag[l]=add_tag[r]=0;
set_to[l]=set_to[r]=set_to[node];
set_tag_exist[l]=set_tag_exist[r]=1;
maxn[l]=maxn[r]=set_to[node];
set_to[node]=set_tag_exist[node]=0;
}
}
int a,b;
ll v;
inline void add_opt(int node) {
int l=nodes[node].l,r=nodes[node].r;
if(a<=l&&r<=b) {
tad(node,v);
return;
}
pushdown(node);
int mid=middle(node);
if(a<=mid) {
add_opt(left_child(node));
}
if(mid<b) {
add_opt(right_child(node));
}
maxn[node]=max(maxn[left_child(node)],maxn[right_child(node)]);
}
inline void set_opt(int node) {
int l=nodes[node].l,r=nodes[node].r;
if(a<=l&&r<=b) {
add_tag[node]=0;
set_tag_exist[node]=1;
set_to[node]=v;
maxn[node]=v;
return;
}
pushdown(node);
int mid=middle(node);
if(a<=mid) {
set_opt(left_child(node));
}
if(mid<b) {
set_opt(right_child(node));
}
maxn[node]=max(maxn[left_child(node)],maxn[right_child(node)]);
}
const ll llmin=-0x3f3f3f3f3f3f3f3f;
inline ll query(int node) {
int l=nodes[node].l,r=nodes[node].r;
if(a<=l&&r<=b) {
return maxn[node];
}
pushdown(node);
int mid=middle(node);
ll ans=llmin;
if(a<=mid) {
ll t=query(left_child(node));
ans=t;
}
if(mid<b) {
ll t=query(right_child(node));
ans=max(ans,t);
}
return ans;
}
int main() {
n=qread(),m=qread();
for(int i=1; i<=n; i++) {
ini[i]=qread();
}
build(1,1,n);
for(int i=1; i<=m; i++) {
int p=qread();
if(p==1) {
a=qread(),b=qread(),v=qread();
set_opt(1);
} else if(p==2) {
a=qread(),b=qread(),v=qread();
add_opt(1);
} else {
a=qread(),b=qread();
ll ans=query(1);
printf("%lld\n",ans);
}
}
return 0;
}
问题在于下放标记的操作,当某个节点将要添加一个add的标记时,我认为,如果已经存在set的标记,可以直接将set标记的值加上将要加上的add标记的值,就不需要添加add标记了
inline void tad(int node,int x) {
if(set_tag_exist[node]) {
set_to[node]+=x;
} else {
add_tag[node]+=x;
}
maxn[node]+=x;
}
而题解的做法是现将当前set标记下传,再为当前节点添加add标记,请问我的想法有何问题?
AC代码,并且还有一个疑问
inline void tad(int node,int x) {
add_tag[node]+=x;
maxn[node]+=x;
}
inline void pushdown(int node) {
int l=left_child(node),r=right_child(node);
if(set_tag_exist[node]) {
add_tag[l]=add_tag[r]=0;
set_to[l]=set_to[r]=set_to[node];
set_tag_exist[l]=set_tag_exist[r]=1;
maxn[l]=maxn[r]=set_to[node];
set_to[node]=set_tag_exist[node]=0;
}
if(add_tag[node]) {
// tad(l,add_tag[node]);
// tad(r,add_tag[node]);
add_tag[l]+=add_tag[node];
add_tag[r]+=add_tag[node];
maxn[l]+=add_tag[node];
maxn[r]+=add_tag[node];
//为什么以上4行代码不能 替换成注释中的代码呢?
add_tag[node]=0;
}
}
by 杜都督 @ 2024-01-30 04:10:59
大致看了一下,如果说得不对欢迎指正
关于疑问1:根据逻辑可以推断出set和add两个tag不可能同时出现,所以你原来tad()中的if判断完全多余
关于疑问2:因为add_tag[node]是ll,但你tad()的x是int,导致传参之后精度损失