[数据结构与算法]牛客练习赛90-妄想集合-(并查集维护路径+数论)

D

题意:
就是给你n个集合，有两种操作，一种是让l到r的集合都加入x。一种是擦查询l到r内的集合内是否可以选择3个数组成三角形。

思考：
首先看一下不能组成三角形的集合就是1 1 2 3 5 8，也就是斐波那契数列，当到46个的时候值已经很大了，所以如果这一段区间内的总数>=46了就肯定能组成三角形了。所以查询很好办了，那么就是插入了，如果每次枚举l到r那么是nn的复杂度太高，所以每个点的acc代表数的个数还不够46的下一个集合到底是谁。所以最多也只会枚举46n次。那么维护的话就可以用并查集维护路径或者线段树去维护个数，但是并查集会更好操作。以前做过的一道并查集记录路径的：Recommendations。

代码：

int T,n,m,k;
int va[N];
int acc[N];

vector<int > v[N];

int find(int x)
{
	if(x!=acc[x]) acc[x] = find(acc[x]);
	return acc[x];	
}

signed main()
{
	IOS;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>va[i];
		v[i].pb(va[i]);
	}
	for(int i=1;i<=n+1;i++) acc[i] = i;
	while(m--)
	{
		int a,b;
		string op;
		cin>>op>>a>>b;
		if(op=="Ask")
		{
			if(b-a+1>=46)
			{
				cout<<"YES\n";
				continue;
			}
			int sum = 0;
			for(int i=a;i<=b;i++) sum += v[i].size();
			if(sum>=46)
			{
				cout<<"YES\n";
				continue;
			}
			vector<int > can;
			for(int i=a;i<=b;i++)
			{
				for(auto t:v[i]) can.pb(t);
			}
			sort(can.begin(),can.end());
			int suc = 0;
			for(int i=0;i<can.size();i++)
			{
				if(i+2>=can.size()) break;
				if(can[i]+can[i+1]>can[i+2])
				{
					suc = 1;
					break;
				}
			}
			if(suc) cout<<"YES\n";
			else cout<<"NO\n";
		}
		else
		{
			int x;
			cin>>x;
			for(int i=a;i<=b;i=find(i+1))
			{
				if(v[i].size()>=46) continue;
				v[i].pb(x);
				if(v[i].size()==46) acc[i] = find(i+1);
			}
		}
	}
	return 0;
}

总结：
多多思考多多掌握技巧。