D - 温暖的签到题

https://ac.nowcoder.com/acm/contest/892/D

线段树水题，mark标记顺带维护一下需要操作的区间的左端点的值就好了。

Code：

#include <bits/stdc++.h>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
const int MAXN = 1e5 + 5;
struct node
{
	int l;
	int r;
	int mark;
	ll sum;
}que[MAXN * 4];
int n, m, ql, qr;
void up(int k)
{
	que[k].sum = que[k << 1].sum + que[k << 1 | 1].sum;
}
void down(int k)
{
	if (que[k].mark != 0)
	{
		que[k << 1].mark = que[k].mark;
		que[k << 1].sum = (ll)(2 * que[k << 1].mark + que[k << 1].r - que[k << 1].l) * (que[k << 1].r - que[k << 1].l + 1) / 2;
		que[k << 1 | 1].mark = que[k].mark + (que[k << 1].r - que[k << 1].l + 1);
		que[k << 1 | 1].sum = (ll)(2 * que[k << 1 | 1].mark + que[k << 1 | 1].r - que[k << 1 | 1].l) * (que[k << 1 | 1].r - que[k << 1 | 1].l + 1) / 2;
		que[k].mark = 0;
	}
}
void build(int left = 1, int right = n, int k = 1)
{
	que[k].l = left;
	que[k].r = right;
	que[k].mark = 0;
	if (left == right)
	{
		que[k].sum = left;
		return;
	}
	imid;
	build(lson);
	build(rson);
	up(k);
}
void update(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].mark = left - ql + 1;
		que[k].sum = (ll)(que[k].r - que[k].l + 2 * que[k].mark) * (que[k].r - que[k].l + 1) / 2;
		return;
	}
	down(k);
	imid;
	update(lson);
	update(rson);
	up(k);
}
ll query(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return 0;
	if (ql <= left && right <= qr)
		return que[k].sum;
	down(k);
	imid;
	return query(lson) + query(rson);
}
int main()
{
	scanf("%d%d", &n, &m);
	build();
	while (m--)
	{
		int op;
		scanf("%d%d%d", &op, &ql, &qr);
		if (op == 1)
			update();
		else
			printf("%lld\n", query());
	}
}