刷题记录:牛客NC22593签到题

传送门:牛客

题目描述:

恭喜你找到了本场比赛的签到题
为了让大家都有抽奖的机会只需要复制粘贴以下代码并且稍微填下空即可 AC
我超良心的
输入:
6 13
1 1 2
1 4 5
1 4 7
1 6 9
1 12 13
3 3 3
输出:
10

一道线段树维护区间加的题目,我不会告诉你我因为lazy忘记传递了调试了一个小时

首先观察题目,我们发现可以使用线段树来维护我们的区间线段是否存在,一条线段存在,我们只需要将线段中的所有点在线段树中+1即可(还好线段的跨度不大,不需要进行离散化).一条线段被删除,只需要将所有线段中的点-1即可(题目保证删除线段存在).接下来我们的问题就是如何计算线段的总长度了.但是我们怎么用线段树进行快速查询呢.我们可以用线段树维护一个区间被完全覆盖几次.那么对于我们的一个区间来说,显然这个区间被覆盖的次数等于两个儿子被覆盖的次数取$min$.

对于每一条线段加入时,我们update的区间显然是会被完全覆盖的,然后我们更新一下update的区间的父亲节点即可.对于我们的儿子区间,显然也多了一次完全覆盖次数,对于这个我们使用懒标记进行更新

对于每一条线段减少时,我们update的区间显然是减少了一次覆盖,此时顺便更新一下我们的父亲节点的覆盖次数.对于我们的儿子区间,依旧采用懒标记进行更新即可

查询时,如果该区间被完全覆盖,那么显然这整个区间应加入贡献;如果这个区间没有被完全覆盖,那么它的儿子区间可能被覆盖,我们查询它的儿子区间

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 101000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{
	int l,r,lazy,cover;
}tree[maxn*4];
int n,L;
void build(int l,int r,int rt) {
	tree[rt].l=l;tree[rt].r=r;
	if(l==r) {
		return ;
	}
	int mid=(l+r)>>1;
	build(lson);build(rson);
}
void pushdown(int rt) {
	tree[ls].cover+=tree[rt].lazy;
	tree[rs].cover+=tree[rt].lazy;
	tree[ls].lazy+=tree[rt].lazy;
	tree[rs].lazy+=tree[rt].lazy;
	tree[rt].lazy=0;
}
void pushup(int rt) {
	int v=min(tree[ls].cover,tree[rs].cover);
	tree[rt].cover=v;
}
void update(int l,int r,int rt,int v) {
	if(tree[rt].l==l&&tree[rt].r==r) {
		tree[rt].cover+=v;
		tree[rt].lazy+=v;
		return ;
	}
	if(tree[rt].lazy) pushdown(rt);
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(r<=mid) update(l,r,ls,v);
	else if(l>mid) update(l,r,rs,v);
	else update(l,mid,ls,v),update(mid+1,r,rs,v);
	pushup(rt);
}
int query(int l,int r,int rt) {
	if(tree[rt].l==l&&tree[rt].r==r) {
		if(tree[rt].cover) return r-l+1;
		else if(tree[rt].l==tree[rt].r) return 0;
	}
	if(tree[rt].lazy) pushdown(rt);
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(r<=mid) return query(l,r,ls);
	else if(l>mid) return query(l,r,rs);
	else return query(l,mid,ls)+query(mid+1,r,rs);
}
int main() {
	set<pair<int,int> >st;
	n=read();L=read();
	build(1,L+1,1);
	for(int i=1;i<=n;i++) {
		int opt=read(),l=read(),r=read();
		l++;r++;//会有0出现,所以将0改为1
		if(opt==1) {
			if(st.find(make_pair(l,r))!=st.end()) continue;
			st.insert(make_pair(l,r));
			update(l,r,1,1);
		}
		else if(opt==2) {
			if(st.find(make_pair(l,r))==st.end()) continue;
			st.erase(make_pair(l,r));
			update(l,r,1,-1);
		}
		else {
			printf("%d\n",query(1,L+1,1));
		}
	}
	return 0;
}