[CSP-S模拟测试]:甜圈（线段树）

题目描述

　　$D$先生，是一个了不起的甜甜圈制造商。今天，他的厨房准备在日出之前制作甜甜圈。$D$先生瞬间完成了$N$个油炸圈饼。但是，这些油炸圈饼得先经过各种装饰任务才可以成为甜甜圈销售:填充奶油，浸入巧克力，打顶可爱，丰富多彩的东西等等。
　　装饰任务有$K$个，任务编号为$1$到$K$，并且每一个甜甜圈都必须严格按照$K$个任务以$1,2,...,K$的顺序仅完成一次，才能成为销售物品。
　　$D$先生将$N$个甜甜圈排成一列，他似乎打算一次完成每个装饰任务。但是，昨天晚上熬夜的$D$先生每个任务只装饰了部分连续区间的甜甜圈。这显然是一个错误!不仅如此，他还可能是做了几次同一任务，任务的顺序也是混乱的。
　　没有经过正确流程装饰的甜甜圈不能作为销售物品提供，所以他应该把它们丢掉。幸运的是，有数据依次记录了他所做的一系列任务。数据包含以下信息:对于每个任务，装饰的甜甜圈的连续区间$[l,r]$和任务的$ID\ x$。
　　请编写一个程序，列举可在展示柜中显示的甜甜圈的数量，作为销售给定记录数据的答案。

输入格式

第一行两个整数$N$和$K$，表示有$N$个甜甜圈和$K$个任务。
第二行一个整数$T$，表示$D$先生依次完成了$T$个区间的装饰。
接下来$T$行，每行三个正整数$l_i,r_i,x_i$，分别表示区间$[l_i,r_i]$的甜甜圈完成了$ID$为$x_i$的装饰任务。

输出格式

一个整数，表示能作为展示的甜甜圈的数量。

样例

样例输入：

5 3
5
2 3 1
1 3 2
4 5 1
2 4 3
3 5 2

样例输出：

数据范围与提示

样例解释：

$1$号甜甜圈没有完成任务$1$就完成了任务$2$所以抛弃，$3$号甜甜圈的任务$2$被重复完成了$2$次，抛弃！$4$号甜甜圈先完成了任务$3$再完成任务$2$，抛弃！$5$号甜甜圈没有完成任务$3$，抛弃！所以只有$2$可以展示。

数据范围：

对于$40\%$的数据，$N,K,T\leqslant 5,000$
对于另外$20\%$的数据，$K\leqslant 100$
对于另外$10\%$的数据，$l_i=r_i$
对于$100\%$的数据，$1\leqslant N,K,T\leqslant 200,000,x_i\leqslant K,1\leqslant l_i\leqslant r_i\leqslant N$

题解

显然是一道线段树，我们考虑如何维护。

用两个懒标记，分别表示其上端点和下端点，$-1$表示没有懒标记，$-2$表示这段区间已经不合法即可。

最后将整棵树跑一边即可统计答案。

时间复杂度：$\Theta(N\log N+T\log N)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

#define L(x) x<<1

#define R(x) x<<1|1

using namespace std;

int N,K,T;

int tr[1000000],lz1[1000000],lz2[1000000];

int ans;

void build(int x,int l,int r)

{

	lz1[x]=lz2[x]=-2;

	if(l==r)return;

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

	build(L(x),l,mid);

	build(R(x),mid+1,r);

}

void pushdown(int x)

{

	if(lz1[x]==-2)return;

	if(lz1[x]==-1)

	{

		tr[L(x)]=tr[R(x)]=lz1[L(x)]=lz1[R(x)]=lz2[L(x)]=lz2[R(x)]=-1;

		return;

	}

	if(tr[L(x)]!=-1)

	{

		if(tr[L(x)]+1==lz1[x])tr[L(x)]=lz2[x];

		else tr[L(x)]=-1;

	}

	if(tr[R(x)]!=-1)

	{

		if(tr[R(x)]+1==lz1[x])tr[R(x)]=lz2[x];

		else tr[R(x)]=-1;

	}

	if(lz1[L(x)]!=-1)

	{

		if(lz1[L(x)]==-2){lz1[L(x)]=lz1[x];lz2[L(x)]=lz2[x];}

		else if(lz2[L(x)]+1==lz1[x])lz2[L(x)]=lz2[x];

		else lz1[L(x)]=lz2[L(x)]=-1;

	}

	if(lz1[R(x)]!=-1)

	{

		if(lz1[R(x)]==-2){lz1[R(x)]=lz1[x];lz2[R(x)]=lz2[x];}

		else if(lz2[R(x)]+1==lz1[x])lz2[R(x)]=lz2[x];

		else lz1[R(x)]=lz2[R(x)]=-1;

	}

	lz1[x]=lz2[x]=-2;

}

void change(int x,int l,int r,int L,int R,int w)

{

	if(r<L||R<l)return;

	if(L<=l&&r<=R)

	{

		if(tr[x]!=-1)

		{

			if(tr[x]+1==w)tr[x]++;

			else tr[x]=-1;

		}

		if(lz1[x]!=-1)

		{

			if(lz1[x]==-2)lz1[x]=lz2[x]=w;

			else if(lz2[x]+1==w)lz2[x]++;

			else lz1[x]=lz2[x]=-1;

		}

		return;

	}

	pushdown(x);

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

	change(L(x),l,mid,L,R,w);

	change(R(x),mid+1,r,L,R,w);

}

void ask(int x,int l,int r)

{

	if(l==r)

	{

		if(tr[x]==K)ans++;

		return;

	}

	pushdown(x);

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

	ask(L(x),l,mid);

	ask(R(x),mid+1,r);

}

int main()

{

	scanf("%d%d%d",&N,&K,&T);

	build(1,1,N);

	while(T--)

	{

		int l,r,x;

		scanf("%d%d%d",&l,&r,&x);

		change(1,1,N,l,r,x);

	}

	ask(1,1,N);

	printf("%d",ans);

	return 0;

}

rp++

巴特西