社区讨论

什么我线段树全wa!快来踩爆这个蒟蒻(bushi)

P2357守墓人参与者 3已保存回复 10

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@lo3bqsie
此快照首次捕获于
2023/10/24 04:02
2 年前
此快照最后确认于
2023/10/24 04:02
2 年前
查看原帖
我输出了换行,样例能过,就是会爆0
CPP
#include <bits/stdc++.h>
#define wccc inline
#define lid (id << 1)
#define rid (id << 1 | 1)
#define int long long
//id >> 1 lid id >> 1 | 1 rid
using namespace std;
const int MAX = 500000;
struct seg_tr{
	int l,r;
	int mx,sum;
	int lazy,lazy2;
}tr[MAX * 2];
int a[MAX];
void pushdown(int id){
	if(tr[id].lazy && tr[id].l != tr[id].r){
		tr[lid].lazy += tr[id].lazy;
		tr[rid].lazy += tr[id].lazy;
		tr[lid].sum += tr[id].lazy * (tr[lid].r - tr[lid].l + 1);//左儿子的sum+父亲节点lazy*(左儿子的右节点-左儿子的左节点+1)(个数)
        tr[rid].sum += tr[id].lazy * (tr[rid].r - tr[rid].l + 1);//同上
        tr[id].lazy = 0;//父亲节点的lazy清空
	}
}
wccc void bulid_tr(int id,int l,int r){
	tr[id].l = l;
	tr[id].r = r;
	if(l == r){//放置到最后节点
		tr[id].mx = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	bulid_tr(lid,l,mid);
	bulid_tr(rid,mid + 1,r);//递归搜索
	tr[id].mx = max(tr[lid].mx,tr[rid].mx);//max为左右节点的最大值
}
void modfi(int id,int a,int b){
	if(tr[id].l==tr[id].r){
		if(tr[id].mx<b)tr[id].mx=b;
		return;
	}
	int mid=(tr[id].l+tr[id].r)>>1;
	modfi(a <= mid?lid:rid,a,b);
	tr[id].mx = max(tr[lid].mx,tr[rid].mx);
	return ;
}
int qur(int id,int l,int r){
	pushdown(id);
	if(tr[id].l == l && tr[id].r == r){
		return tr[id].sum;
	}
	int mid = (tr[id].l + tr[id].r) >> 1;
	if(r <= mid){
		return qur(lid,l,r);
	}
	if(l > mid){
		return qur(rid,l,r);
	}
	return qur(lid,l,mid) + qur(rid,mid + 1,r);
}
void add(int id ,int l,int r,int val){
	tr[id].mx = max(tr[lid].mx,tr[rid].mx);//max为左右节点的最大值
	pushdown(id);
    if(l==tr[id].l && r==tr[id].r) //匹配到后
    {
        tr[id].lazy += val;//lazy累计
       	tr[id].sum+=(tr[id].r-tr[id].l+1)*val;
        return;
    }
    int mid = (tr[id].l + tr[id].r) >> 1;//中点
    if(r <= mid){
        add(lid, l, r, val);//左儿子
    }
  	else if(l>mid)add(rid,l,r,val);
	else {
		add(lid,l,mid,val);
		add(rid,mid+1,r,val);
	}
    tr[id].sum = tr[lid].sum + tr[rid].sum;//pushup  回溯之前更新每个点的信息
}
signed main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
	bulid_tr(1,1,n);
	for (int i = 1; i <= m; i++)
	{
		int op,x,y,z;
		cin >> op;
		if(op == 1){
			cin >> x >> y >> z;
			add(1,x,y,z);
		}
		if(op == 2){
			cin >> x;
			add(1,1,1,x);
		}
		if(op == 3){
			cin >> x;
			add(1,1,1,-x);
		}
		if(op == 4){
			cin >> x >> y ;
			cout << qur(1,x,y)<<endl;
		}
		if(op == 5){
			cout << qur(1,1,1) << endl;
		}				
	}
}

回复

10 条回复,欢迎继续交流。

正在加载回复...