P9571 Horizon Blue 题解

78km / 2023-08-19 / 原文

原题链接

题目大意：

有三个操作，分别为

加入一条直线。
查询与一条直线相交但不重合的直线条数。
删除所有与一条直线相交或重合的直线。

注意:后面两个操作的直线并不需要加入。
显然，两条直线相交不重合，当且仅当其 \(k\) 值不同。
所以可以把所有直线按 \(k\) 值分类，则第二个操作的查询答案显而易见，为直线总数减去 \(k\) 为给出 \(k\) 值相同的直线条数。
然后看到第三个操作，需要删除与其 \(k\) 值不同的直线以及与其 \(k\)， \(b\)都相同的直线。
可以考虑对每一个 \(k\) 值开一个 map 用于储存当前 \(k\) 值下，每个 \(b\) 值有多少条直线，删除重合直线时即可直接删除。
再看相交的情况，即 \(k\) 值不同，对于每个 \(k\) 只需将其 map 进行 clear 即可。
最后还要用栈存储下所有存在且未被删除的 \(k\) 值，复杂度 \(O(n log n)\)。
注：\(k\) 值可能有负数，所以需要加上一个很大的数使其变为正数。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int q[N],top;//栈，用于存储存在的k值，降低复杂度 
struct Node
{
	map<int,int>b;
	int cnt;//记录当前k值一共有多少条直线 
}a[N<<1];
int n,sum;//sum记录总共多少直线 
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int opt,k,b;
		cin>>opt>>k>>b;
		k+=100000;
		if(opt==1)
		{
			if(a[k].cnt==0)
			q[++top]=k;//如果k没入栈，将其入栈 
			a[k].b[b]++; 
			a[k].cnt++;
			sum++;
		}
		else
		if(opt==2)
		{
			cout<<sum-a[k].cnt<<'\n';
		}
		else
		{
			while(top)
			{
				if(q[top]==k)
				{
					top--;
				}
				else
				{
					a[q[top]].cnt=0;
					a[q[top]].b.clear();//清空 
					top--;
				}
			}
			sum=a[k].cnt=a[k].cnt-a[k].b[b];
			a[k].b[b]=0;
			if(sum)
			q[++top]=k;//k不一定被清空了 ,可能要加回去 
		}
	}
	return 0;
}