2024 CSP J/S RP++

都这么折磨我了必须给复赛 rp++ 好吧...

优先队列+结构体排序

重点的放前面

如果要用 $r$ 的小根堆：

struct Node {
	int l,r;
	friend bool operator < (const Node &x,const Node &y) {
		return x.r>y.r;
	}
};
priority_queue<Node> q;

---

愤怒源头-[USACO06FEB] Stall Reservations S

看提交记录去，反正用线段树做的最少解法应该是过了的，不不知道为什么路径有问题（wrong plan）...

就强调一个问题，端点是会重复的，所以在计算线段树的时候需要添加一个变量 $cnt$ 来记录当前端点的个数，不能直接删掉端点：

错误的：

inline void update(int rt,int l,int r,int s,int t,int k,int v) {
	if(l>t||r<s)
		return ;
	if(s<=l&&r<=t) {
		if(v==-1) {
			tree[rt].maxx=0;
			tree[rt].pos=0;
		} else {
			tree[rt].maxx=l;
			tree[rt].pos=k;
		}
		return ;
	}
	int mid=(l+r)>>1;
	update(lson,l,mid,s,t,k,v);
	update(rson,mid+1,r,s,t,k,v);
	push_up(rt);
	return ;
}

正确的：

inline void update(int rt,int l,int r,int s,int t,int k,int v) {
	if(l>t||r<s)
		return ;
	if(s<=l&&r<=t) {
		if(v==-1) {
			if(tree[rt].cnt==1) {
				tree[rt].maxx=0;
				tree[rt].pos=0;
			}
			tree[rt].cnt--;
		} else {
			tree[rt].maxx=l;
			tree[rt].pos=k;
			tree[rt].cnt++;
		}
		return ;
	}
	int mid=(l+r)>>1;
	update(lson,l,mid,s,t,k,v);
	update(rson,mid+1,r,s,t,k,v);
	push_up(rt);
	return ;
}

关于路径问题：

终于破解了，同样由于那个问题，右端点会重复，会有多个牛棚在同一个右端点，即 $cnt>1$ 时，而 $pos$ 只记录了一个，所以我们会重复选择一个牛棚，而这样选是不符合要求，故路径会错！！！

我的方法是用线段树维护每个端点，时间大，空间大，路径不好打...

现在引用ljs给出的优化解法：

可以用线段树维护每个牛棚，记录最后一个端点，空间时间小，也可以记录路径。

就先说到这了...