线段树求调
查看原帖
线段树求调
106559
_MLE_自动机楼主2021/2/18 18:55

Rt,经测试是如下代码出了问题,但是调不出问题了,求助。

struct node {
	int val,l,r;
	int tag;
}tree[N << 2];

#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define push_up(x) tree[x].val = tree[ls(x)].val + tree[rs(x)].val

int n,m,len,w;
int a[N],l,r,k,d,opt;

inline void build(int u,int l,int r)  {
	tree[u].l = l; tree[u].r = r; tree[u].tag = 0;
	if(l == r) {
		tree[u].val = a[l] - a[l - 1];
		return;
	}
	int mid = (l + r) >> 1;
	build(ls(u),l,mid);
	build(rs(u),mid + 1,r);
	push_up(u);
}

inline void push_down(int u) {
	tree[ls(u)].tag += tree[u].tag;
	tree[rs(u)].tag += tree[u].tag;
	tree[ls(u)].val += tree[u].tag * (tree[ls(u)].r - tree[ls(u)].l + 1);
	tree[rs(u)].val += tree[u].tag * (tree[rs(u)].r - tree[rs(u)].l + 1);
	tree[u].tag = 0;
}

inline void upload(int u,int l,int r,int k) {
	if(tree[u].l >= l && tree[u].r <= r) {
		tree[u].val += k * (tree[u].r - tree[u].l + 1);
		tree[u].tag += k;
		return;
	}
	push_down(u);
	int mid = (tree[u].l + tree[u].r) >> 1;
	if(mid >= l) upload(ls(u),l,r,k);
	if(mid < r) upload(rs(u),l,r,k);
	push_up(u);
}

inline int query(int u,int l,int r) {
	if(tree[u].l >= l && tree[u].r <= r) {
		return tree[u].val;
	}
	int cnt = 0,mid = (tree[u].l + tree[u].r) >> 1;
	if(mid >= l) cnt += query(ls(u),l,r);
	if(mid < r) cnt += query(rs(u),l,r);
	return cnt;
}
2021/2/18 18:55
加载中...