P6105 [Ynoi2010] y-fast trie

[Ynoi2010] y-fast trie - 洛谷

• 这道题让我学到了一些之前看过但没总结出来的 \(trick\)

• 显然加入集合中数要先取模

• 对于 \(x+y \geq C\) 的部分，直接取最大和次大即可

• 对于 \(x + y < C\) 的部分，我们先考虑暴力枚举 \(x\)，二分找到每一个 \(y\) 取最优即可

• 若此题离线，考虑线段树分治，每次加入一个数时把这个数的最佳匹配取出来，对答案取 \(\max\)，\(O(n \log^2 n)\)

• 现在在线，对于最优化数对问题，通常是先弄出 \(O(n^2)\) 的解法，然后看数对中满足什么条件，使得 \((i,j)\) 一定比 \((j,k)\) 优，从而大量减少维护数对的次数

• 对于此题，如果 \(i < k\)，那我们可以只考虑 \((j,k)\) 这一数对

• 因此数对最多有 \(O(n)\) 个，用 \(multiset\) 维护最优数对，时间 \(O(n \log n)\)

• 不过代码坑点挺多的毕竟是 lxl 出的题

• 首先要注意的是 \(multiset\) 删除的时候要先找到位置再删除，不然会都删了。s.erase(s.find(x));

• void add(int x){
  	int y = best(x, 0), z = best(y, 1), w = best(z, 1);
  	
  	if(y >= 0 && x > z){
  		if(z >= 0 && y == w)
  			val.erase(val.find(y + z));
  		val.insert(x + y);
  	}
  	
  	a.insert(x);
  }
  

• 然后当插入一个 \(x\) 的时候应该先找到 \(x\) 的匹配 \(y\) 再把 \(x\) 差进去，因为与 \(y\) 的匹配必然不能是不在数组中的数 \(x\)

• 然后 \(add\) 函数中 \(w\) 的用途是判断是否有 \((y,z)\) 这一匹配，不然 \(z\) 偷偷和别人匹配了 \(y\) 还不知道呢

• 其次就是因为我们先寻找匹配再插入 \(x\)，就会出现是否要求重复这样的不同的需求，\(best\) 函数要处理一下

• int best(int x, int opt){
  	if(x < 0)
  		return -1;
  		
  	auto it = a.lower_bound(mod - x);
  	
  	if(it == a.begin())// 如果没有
  		return -1; 
  	
  	-- it;
  	
  	if(opt && *it == x){// 如果是自身 
  		if(it == a.begin())// 如果前面没有了 
  			return -1;
  		
  		-- it;
  	}
  	
  	return *it;
  }
  

• 做完题之后反思自己寻找 \(trick\) 的思维好像少了很多，不太会总结问题之前做的题都白做了，下次做完题之后应该更仔细的剖析一下而不是单纯记住表面