当前位置：首页 > article >正文

线段树维护更多类型的信息

article 2024/9/22 14:42:07

P3870 [TJOI2009] 开关 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

sum维护一段区域的和；revers记录翻转懒信息；

lazy：灯泡翻转后个数就是之前不亮的个数，revers变为原来的反

#include <iostream>
using namespace std;
const int maxn = 100001;
int sum[maxn<<2];
bool revers[maxn << 2];
void up(int i) {
	sum[i] = sum[i << 1] + sum[i << 1 | 1];
}
void lazy(int i, int n) {
	sum[i] = n - sum[i];
	revers[i] = !revers[i];
}
void down(int i, int ln, int rn) {
	if (revers[i]) {
		lazy(i << 1, ln);
		lazy(i << 1 | 1, rn);
		revers[i] = false;
	}
}
void reverse(int jobl,int jobr,int l,int r,int i) {
	if (jobl <= l && jobr >= r)
		lazy(i, r - l + 1);
	else {
		int mid = l + ((r - l) >> 1);
		down(i, mid - l + 1, r - mid);
		if (jobl <= mid)
			reverse(jobl, jobr, l, mid, i << 1);
		if (jobr > mid)
			reverse(jobl, jobr, mid + 1, r, i << 1 | 1);
		up(i);
	}
}
int query(int jobl, int jobr, int l, int r, int i) {
	if (jobl <= l && jobr >= r)
		return sum[i];
	else {
		int mid = l + ((r - l) >> 1);
		down(i, mid - l + 1, r - mid);
		int ans = 0;
		if (jobl <= mid)
			ans += query(jobl, jobr, l, mid, i << 1);
		if (jobr > mid)
			ans += query(jobl, jobr, mid + 1, r, i << 1 | 1);
		return ans;
	}
}
void build(int l, int r, int i) {
	if (l == r) sum[i] = 0;
	else {
		int mid = l + ((r - l) >> 1);
		build(l, mid, i << 1);
		build(mid + 1, r, i << 1 | 1);
		up(i);
	}
	revers[i] = false;
}
int main() {
	int n, m;
	cin >> n >> m;
	int a, b, c;
	int rem[maxn];
	int size = 0;
	build(1, n, 1);
	while (m--) {
		cin >> a >> b >> c;
		if (a == 0) {
			reverse(b, c, 1, n, 1);
		}
		else {
			rem[size++]=query(b, c, 1, n, 1);
		}
	}
	for (int i = 0; i < size; i++)
		cout << rem[i] << endl;
	return 0;
}

P2184 贪婪大陆 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

此题如果一段区域内不同的地雷总数是不能作为线段树信息维护的；所以此题维护的是一段区域内以某种地雷开头的位置数量和以某种地雷结尾的位置的数量两种信息。那么求一段区域 l - r 内地雷的总数，从1 - r地雷的开头数减去1 - l-1地雷的结尾数就是地雷的种类数。

此题是单点增加，所以不需要down和lazy操作

#include <iostream>
#include <vector>
using namespace std;
const int maxn = 100001;
int bomstart[maxn << 2];
int bomends[maxn << 2];
void up(int i) {
	bomstart[i] = bomstart[i << 1] + bomstart[i << 1 | 1];
	bomends[i] = bomends[i << 1] + bomends[i << 1 | 1];
}
void add(int jobt, int jobi, int l, int r, int i) {
	if (l == r) {
		if (jobt == 0)
			bomstart[i]++;
		else
			bomends[i]++;
	}
	else {
		int mid = l + ((r - l) >> 1);
		if (mid >= jobi)
			add(jobt, jobi, l, mid, i << 1);
		else
			add(jobt, jobi, mid + 1, r, i << 1 | 1);
		up(i);
	}
}
int query(int jobt,int jobl, int jobr, int l, int r, int i) {
	if (jobl <= l && jobr >= r)
		return jobt == 0 ? bomstart[i] : bomends[i];
	else {
		int mid = l + ((r - l) >> 1);
		int ans = 0;
		if (mid >= jobl)
			ans += query(jobt, jobl, jobr, l, mid, i << 1);
		if (jobr > mid)
			ans += query(jobt, jobl, jobr,mid + 1, r, i << 1 | 1);
		return ans;
	}
}
void build(int l, int r, int i) {
	if (l < r) {
		int mid = l + ((r - l) >> 1);
		build(l, mid, i << 1);
		build(mid + 1, r, i << 1 | 1);
	}
	bomends[i] = 0;
	bomstart[i] = 0;
}
int main() {
	int n, m;
	cin >> n >> m;
	int a, b, c;
	vector<int>rem;
	while (m--) {
		cin >> a >> b >> c;
		if (a == 1) {
			add(0, b, 1, n, 1);
			add(1, c, 1, n, 1);
		}
		else {
			int s = query(0, 1, c, 1, n, 1);
			int e =b==1?0: query(1, 1, b-1, 1, n, 1);
			rem.push_back(s - e);
		}
	}
	for (auto i : rem)
		cout << i << endl;
	return 0;

}

P1438 无聊的数列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

如果知道一组数的差分数组，在原数组的l - r范围上增加首项为k，公差为d的等差数组，只需要在l上增加k，l+1到r上增加d，r+1减去末项，从1到p求和即可得出原数组操作后p位置上的数。所以对差分信息维护线段树，做add操作和query操作即可

#include <iostream>
using namespace std;
const int maxn = 100001;
int diff[maxn];
long sum[maxn << 2];
long add[maxn << 2];
void up(int i) {
	sum[i] = sum[i << 1] + sum[i << 1 | 1];
}
void lazy(int i, int  n, int v) {
	add[i] += v;
	sum[i] += v * n;
}
void down(int i, int ln, int rn) {
	if (add[i] != 0) {
		lazy(i << 1, ln, add[i]);
		lazy(i << 1 | 1, rn, add[i]);
		add[i] = 0;
	}
}
void build(int l, int r, int i) {
	if (l == r)
		sum[i] = diff[l];
	else {
		int mid = l + ((r - l) >> 1);
		build(l, mid, i << 1);
		build(mid + 1, r, i << 1 | 1);
		up(i);
	}
	add[i] = 0;
}
void add1(int jobl, int jobr, int jobv, int l, int r, int i) {
	if (jobl <= l && jobr >= r) {
		lazy(i, r - l + 1, jobv);
	}
	else {
		int mid = l + ((r - l) >> 1);
		down(i, mid - l + 1, r - mid);
		if(mid>=jobl)
		add1(jobl, jobr, jobv, l, mid, i << 1);
		if(mid<jobr)
		add1(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);
		up(i);
	}
}
long query(int jobl, int jobr, int l, int r, int i) {
	if (jobl <= l && jobr >= r)
		return sum[i];
	else {
		int mid = l + ((r - l) >> 1);
		long ans = 0;
		down(i, mid - l + 1, r - mid);
		if (jobl <= mid)
			ans += query(jobl, jobr, l, mid, i << 1);
		if (jobr > mid)
			ans += query(jobl, jobr, mid + 1, r, i << 1 | 1);
		return ans;
	}
}
int main() {
	int n, m;
	cin >> n >> m;
	int a;
	for (int i = 1,pre=0; i <= n; i++) {
		cin >> a;
		diff[i] = a - pre;
		pre = a;
	}
	build(1, n, 1);
	int b;
	int l, r, k, d;
	while (m--) {
		cin >> b;
		if (b == 1) {
			cin >> l >> r >> k >> d;
			int e = k + (r - l) * d;
			add1(l, l, k, 1, n, 1);
			if (l + 1 <= r)
				add1(l + 1, r, d, 1, n, 1);
			if (r < n)
				add1(r + 1, r + 1, -e, 1, n, 1);
		}
		else {
			int p;
			cin >> p;
			cout << query(1, p, 1, n, 1)<<endl;
		}
	}
	return 0;
}

P1471 方差 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

若求平均数和方差，只需要维护好累加和数组和平方和数组即可：累加和和平方和都可以成为线段树的维护信息。

add操作：累加和容易修改；平方和根据分析也可以O(1)修改

方差：拆开方差公式，用累加和和平方和就可以求出

#include <cstdio>
using namespace std;

const int MAXN = 100001;

double arr[MAXN];
double sum1[MAXN << 2];
double sum2[MAXN << 2];
double addv[MAXN << 2];

void up(int i) {
    sum1[i] = sum1[i << 1] + sum1[i << 1 | 1];
    sum2[i] = sum2[i << 1] + sum2[i << 1 | 1];
}

void lazy(int i, double v, int n) {
    sum2[i] += sum1[i] * v * 2 + v * v * n;
    sum1[i] += v * n;
    addv[i] += v;
}

void down(int i, int ln, int rn) {
    if (addv[i] != 0) {
        lazy(i << 1, addv[i], ln);
        lazy(i << 1 | 1, addv[i], rn);
        addv[i] = 0;
    }
}

void build(int l, int r, int i) {
    if (l == r) {
        sum1[i] = arr[l];
        sum2[i] = arr[l] * arr[l];
    } else {
        int mid = (l + r) >> 1;
        build(l, mid, i << 1);
        build(mid + 1, r, i << 1 | 1);
        up(i);
    }
    addv[i] = 0;
}

void add(int jobl, int jobr, double jobv, int l, int r, int i) {
    if (jobl <= l && r <= jobr) {
        lazy(i, jobv, r - l + 1);
    } else {
        int mid = (l + r) >> 1;
        down(i, mid - l + 1, r - mid);
        if (jobl <= mid) {
            add(jobl, jobr, jobv, l, mid, i << 1);
        }
        if (jobr > mid) {
            add(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);
        }
        up(i);
    }
}

double query(double *sum, int jobl, int jobr, int l, int r, int i) {
    if (jobl <= l && r <= jobr) {
        return sum[i];
    }
    int mid = (l + r) >> 1;
    down(i, mid - l + 1, r - mid);
    double ans = 0;
    if (jobl <= mid) {
        ans += query(sum, jobl, jobr, l, mid, i << 1);
    }
    if (jobr > mid) {
        ans += query(sum, jobl, jobr, mid + 1, r, i << 1 | 1);
    }
    return ans;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &arr[i]);
    }
    build(1, n, 1);
    for (int i = 1; i <= m; i++) {
        int op, jobl, jobr;
        scanf("%d", &op);
        if (op == 1) {
            double jobv;
            scanf("%d %d %lf", &jobl, &jobr, &jobv);
            add(jobl, jobr, jobv, 1, n, 1);
        } else if (op == 2) {
            scanf("%d %d", &jobl, &jobr);
            double ans = query(sum1, jobl, jobr, 1, n, 1) / (jobr - jobl + 1);
            printf("%.4f\n", ans);
        } else {
            scanf("%d %d", &jobl, &jobr);
            double a = query(sum1, jobl, jobr, 1, n, 1);
            double b = query(sum2, jobl, jobr, 1, n, 1);
            double size = jobr - jobl + 1;
            double ans = b / size - (a / size) * (a / size);
            printf("%.4f\n", ans);
        }
    }
    return 0;
}

查看全文

http://www.kler.cn/news/284282.html