温暖的签到题，西北大学集训队选拔赛（重现赛），线段树区间修改

53 阅读 0 评论 35 点赞

我是靠谱客的博主温暖书本，最近开发中收集的这篇文章主要介绍温暖的签到题，西北大学集训队选拔赛（重现赛），线段树区间修改，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：https://ac.nowcoder.com/acm/contest/892/D
来源：牛客网

题目:温暖的签到题

给你一个长度为n的序列，初始为1,2,3…n，对其进行m次操作。
操作有两种：
1 l r 表示将区间[l,r]用 [1,2…r-l+1] 覆盖
2 l r 查询[l,r]的区间和
输入描述:
第一行包含2个数字，n,m（1 <= n,m <= 1e5）

接下来包含m行，格式如题面所示
输出描述:
对于每个操作2，输出一行一个整数表示答案

输入

复制
10 5
2 1 10
1 3 6
2 1 10
1 1 10
2 1 10

输出

55
47
55

题目叫温暖的签到题，但我感受到了浓浓的恶意，比赛时知道要用线段树做，但自己的线段树只会基本的，区间修改和懒惰节点自己不会，而所学的线段树模式是左开右闭的很容易出错，趁着这个题，把线段树好好搞了下，调bug调了好久，比较复杂容易出错

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;

const int maxn = 100005;
ll s[4 * maxn], f[4 * maxn];//s为线段树节点数据， f用于存储懒惰节点
int n, m, Q; //Q为所要修改为的值

void init(int k, int l, int r)  //初始化操作
{
	if (l == r)
	{
		s[k] = r;
		return;
	}

	int mid = (l + r) / 2;

		init(k * 2, l, mid);
		init(k * 2 + 1, mid + 1, r);
		s[k] = s[k * 2] + s[k * 2 + 1];//所学的代码把这一操作建了个函数pushup，做到后来确实好很多， 而且也可以与pushdown相对应。
	
}

ll cal(ll t, int len)//求区间值， 等差数列
{
	return (t + t + len - 1)* len / 2;
}

void pushdown(int k, int l, int r)//懒惰节点下传
{
	if (f[k] == 0) return;

	int mid = (l + r) /2;
	f[k * 2] = f[k];
	s[k * 2] = cal(f[k], mid - l + 1);

	f[k * 2 + 1] = f[k] + mid - l + 1;
	s[k * 2 + 1] = cal(f[k * 2 + 1], r - mid);

	f[k] = 0;//懒惰节点传下去了， 故置零
}


void update(int a, int b, int k, int l, int r)
{
	if (l >= a && r <= b)
	{
		f[k] = Q;//l需要变为Q故在k存储懒惰节点值为Q
		s[k] = cal(Q, r - l + 1);
		Q += (r - l + 1);//Q更新
		return;
	}
	pushdown(k, l, r);懒惰节点下传

	int mid = (l + r) / 2;
	if (a <= mid) update(a, b, k * 2, l, mid);
	if (b > mid) update(a, b, k * 2 + 1, mid + 1, r);
	s[k] = s[k * 2] + s[k * 2 + 1];
}


ll sum(int a, int b, int k, int l, int r)
{
	if (l >= a && r <= b)
		return s[k];

	pushdown(k, l, r);//懒惰节点下传因为更新过程中值可能没有传到底

	ll left = 0, right = 0;
	int mid = (l + r) / 2;;
	if (a <= mid) left = sum(a, b, k * 2, l, mid);
	if (b > mid) right = sum(a, b, k * 2 + 1, mid + 1, r);
	s[k] = s[k * 2] + s[k * 2 + 1];
	return left + right;
}



int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> m;
	init(1, 1, n);

	for (int i = 0; i < m; i++)
	{
		int x, l, r;
		cin >> x >> l >> r;
		if (x == 1)
			Q = 1, update(l, r, 1, 1, n);//每次更新Q重置为1
		else
			cout << sum(l, r, 1, 1, n) << endl;
	}
}

更新一个更加成熟的代码

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;
const int maxn = 100005;
ll s[maxn * 4], f[maxn * 4];
int n, m, Q;

void pushup(int k)
{
	s[k] = s[k * 2 + 1] + s[k * 2];
}

void init(int k, int l, int r)
{
	if (l == r) s[k] = r;
	else
	{
		int mid = (l + r) >> 1;
		init(k * 2, l, mid);
		init(k * 2 + 1, mid + 1, r);
		pushup(k);
	}
}

ll cal(ll a, int len)
{
	return (a + a + len - 1)* len / 2;
}

void pushdown(int k, int l, int r)
{
	if (!f[k]) return;

	int mid = (l + r) >> 1;

	f[k * 2] = f[k];
	s[k * 2] = cal(f[k], mid - l + 1);

	f[k * 2 + 1] = f[k] + mid - l + 1;
	s[k * 2 + 1] = cal(f[k * 2 + 1], r - mid);

	f[k] = 0;
}

void update(int a, int b, int k, int l, int r)
{
	if (l >= a && r <= b)
	{
		f[k] = Q;
		s[k] = cal(Q, r - l + 1);
		Q += (r - l + 1);
	}
	else
	{
		pushdown(k, l, r);
		int mid = (l + r) >> 1;
		if (a <= mid) update(a, b, k * 2, l, mid);
		if (b > mid) update(a, b, k * 2 + 1, mid + 1, r);
		pushup(k);
	}
}

ll sum(int a, int b, int k, int l, int r)
{
	if (l >= a && r <= b) return s[k];

	pushdown(k, l, r);
	int mid = (l + r) >> 1;
	ll left = 0, right = 0;
	if (a <= mid) left =  sum(a, b, k * 2, l, mid);
	if (b > mid) right =  sum(a, b, k * 2 + 1, mid + 1, r);
	return left + right;
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> m;
	init(1, 1, n);
	for (int i = 0; i < m; i++)
	{
		int x, l, r;
		cin >> x >> l >> r;
		if (x == 1)
		{
			Q = 1;
			update(l, r, 1, 1, n);
		}
		else
			cout << sum(l, r, 1, 1, n) << endl;
	}
}