[CF915E]Physical Education Lessons（线段树）

原题

This year Alex has finished school, and now he is a first-year student of Berland State University. For him it was a total surprise that even though he studies programming, he still has to attend physical education lessons. The end of the term is very soon, but, unfortunately, Alex still hasn‘t attended a single lesson!

Since Alex doesn‘t want to get expelled, he wants to know the number of working days left until the end of the term, so he can attend physical education lessons during these days. But in BSU calculating the number of working days is a complicated matter:

There are n days left before the end of the term (numbered from 1 to n), and initially all of them are working days. Then the university staff sequentially publishes q orders, one after another. Each order is characterised by three numbers l, r and k:

• If k?=?1, then all days from l to r (inclusive) become non-working days. If some of these days are made working days by some previous order, then these days still become non-working days;
• If k?=?2, then all days from l to r (inclusive) become working days. If some of these days are made non-working days by some previous order, then these days still become working days.

Help Alex to determine the number of working days left after each order!

Input

The first line contains one integer n, and the second line — one integer q (\(1?≤?n?≤?10^9\), \(1?≤?q?≤?3·10^5\)) — the number of days left before the end of the term, and the number of orders, respectively.

Then q lines follow, i-th line containing three integers \(l_i\), \(r_i\) and \(k_i\) representing i-th order (\(1?≤?l_i?≤?r, i ≤ n, 1 ≤?k_i?≤?2\)).

Output

Print q integers. i-th of them must be equal to the number of working days left until the end of the term after the first i orders are published.

Example

input

4
6
1 2 1
3 4 1
2 3 2
1 3 2
2 4 1
1 4 2

output

2
0
2
3
1
4

思路

n <= 1e9, 离散化处理， 对题目中提到的点，用一个l == r的结点表示，对于题目没提到的点，用一个结点把一个连续区间覆盖，其它操作和线段树涂色一致。（不会动态开点线段树和珂朵莉树）

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <list>
#include <map>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f
#define PI 3.1415926535898
#define F first
#define S second
#define endl ‘\n‘
#define lson  rt << 1
#define rson  rt << 1 | 1
#define f(x, y, z) for (int x = (y), __ = (z); x < __; ++x)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std;

const int maxn = 3e5 + 7;
const int maxm = 1e9 + 7;

int n, q, cnt;
int b[maxn * 3], c[maxn * 6];
vector<pair<int, int>> v;

struct quer
{
	int kind, x, y;
}que[maxn];

struct node
{
	int l, r, daz;
}tree[maxn * 20];

int lz[maxn * 20];

LL read()
{
	LL x = 0, f = 1;char ch = getchar();
	while (ch < ‘0‘ || ch>‘9‘) { if (ch == ‘-‘)f = -1;ch = getchar(); }
	while (ch >= ‘0‘ && ch <= ‘9‘) { x = x * 10 + ch - ‘0‘;ch = getchar(); }
	return x * f;
}

void build(int rt, int l, int r)
{
	if (l == r)
	{
		tree[rt].l = v[l - 1].first;
		tree[rt].r = v[l - 1].second;
		tree[rt].daz = tree[rt].r - tree[rt].l + 1;
		return;
	}
	int mid = (l + r) / 2;
	build(lson, l, mid);
	build(rson, mid + 1, r);
	tree[rt].l = tree[lson].l;
	tree[rt].r = tree[rson].r;
	tree[rt].daz = tree[rt].r - tree[rt].l + 1;
}

void push_down(int rt, int l, int r) {
	if (lz[rt]) {
		int mid = (l + r) / 2;
		lz[lson] = lz[rt];
		lz[rson] = lz[rt];
		tree[lson].daz = (lz[rt] == 1 ? tree[lson].r - tree[lson].l + 1 : 0);
		tree[rson].daz = (lz[rt] == 1 ? tree[rson].r - tree[rson].l + 1 : 0);
		lz[rt] = 0;
	}
}

void update(int cl, int rt, int l, int r, int L, int  R)
{
	if (l <= L && r >= R)
	{
		lz[rt] = cl;
		tree[rt].daz = (cl == 1 ? tree[rt].r - tree[rt].l + 1 : 0);
		return;
	}
	push_down(rt, L, R);
	int mid = (L + R) / 2;
	if (mid >= l) update(cl, lson, l, r, L, mid);
	if (mid < r) update(cl, rson, l, r, mid + 1, R);
	tree[rt].daz = tree[lson].daz + tree[rson].daz;
}

LL query_range(int rt, int l, int r, int L, int R) {
	if (l <= L && r >= R) return tree[rt].daz;
	push_down(rt, L, R);
	int mid = (L + R) / 2;
	LL sum = 0;
	if (mid >= l) sum += query_range(lson, l, r, L, mid);
	if (mid < r) sum += query_range(rson, l, r, mid + 1, R);
	return sum;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	n = read(), q = read();
	int tot = 0;
	_rep(i, 1, q)
	{
		que[i].x = read(), que[i].y = read(), que[i].kind = read();
		b[++tot] = que[i].x;
		b[++tot] = que[i].y;
	}
	sort(b + 1, b + tot + 1);
	tot = unique(b + 1, b + tot + 1) - b - 1;
	int num = 0;
	if (b[1] != 1)
	{
		v.push_back({ 1, b[1] - 1 });
		cnt++;
		c[++num] = 1;
	}
	_rep(i, 1, tot - 1)
	{
		v.push_back({ b[i], b[i] });
		cnt++;
		c[++num] = b[i];
		if (b[i] + 1 <= b[i + 1] - 1)
		{
			c[++num] = b[i] + 1;
			v.push_back({ b[i] + 1, b[i + 1] - 1 });
			cnt++;
		}
	}
	v.push_back({ b[tot], b[tot] });
	c[++num] = b[tot];
	cnt++;
	if (b[tot] != n)
	{
		v.push_back({ b[tot] + 1, n });
		cnt++;
		c[++num] = b[tot] + 1;
	}
	build(1, 1, cnt);
	_rep(i, 1, q)
	{
		int x = que[i].x;
		int y = que[i].y;
		if (que[i].kind == 1)
		{
			x = lower_bound(c + 1, c + num + 1, x) - c;
			y = lower_bound(c + 1, c + num + 1, y) - c;
			update(-1, 1, x, y, 1, cnt);
		}
		else if (que[i].kind == 2)
		{
			x = lower_bound(c + 1, c + num + 1, x) - c;
			y = lower_bound(c + 1, c + num + 1, y) - c;
			update(1, 1, x, y, 1, cnt);
		}
		cout << tree[1].daz << endl;
	}
}

[CF915E]Physical Education Lessons（线段树）

原文：https://www.cnblogs.com/hfcdyp/p/13765126.html