2020-8-7CF反思

打的是真的差，開場正序開題，然後A讀了 $20$ 分鐘/youl，然後才A。

然後就開了B題，B題可謂是雪崩，題目大概是這樣的，給定一些木棒，要求支援動態插入和刪除，每次操作結束後回答是否能擺出一個正方形和一個長方形。

很顯然，最後爲成的木棒顯然最多隻跟 $3$ 種不同長度的木棒有關，所以我們只需求出出現次數第 $1$ 多的木棒、第 $2$ 多的木棒和第 $3$ 多的木棒。

這道題目不需要離散化，題目保證木棒長度 $a_i \leq 10^5$，所以我們直接開個陣列記錄就好了，維護最大值、次大值、次次大值我是用 $\texttt{multiset}$ 維護的。

然而，事情沒有我想的那麼簡單，我 $\text{WA}$ 了。

這是我當時的程式碼

// Problem: B. Applejack and Storages
// Contest: Codeforces - Codeforces Round #662 (Div. 2)
// URL: https://codeforc.es/contest/1393/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
int h[100010];
multiset<int>q;
signed main(){
	memset(h,0,sizeof(h));
	int n;read(n);
	for(int i=1;i<=n;i++){
		int x;read(x);
		h[x]++;
	}
	for(int i=1;i<=100000;i++)
		if(h[i]>=2)q.insert(-h[i]);
	int m;read(m);
	while(m--){
		char ch;int xx;
		cin>>ch>>xx;
		if(ch=='+'){
			if(h[xx]>=2)q.erase(-h[xx]);
			h[xx]++;
			if(h[xx]>=2)q.insert(-h[xx]);
		}else{
			if(h[xx]>=2)q.erase(-h[xx]);
			h[xx]--;
			if(h[xx]>=2)q.insert(-h[xx]);
		}
		int x=0,y=0,z=0,tot=0;
		for(int i:q){
			if(++tot>3)break;
			if(tot==1)x=-i;
			if(tot==2)y=-i;
			if(tot==3)z=-i;
		}
		int a=x/2,b=y/2,c=z/2;
		if(a<2)puts("NO");
		else if(a-2+b+c<2)puts("NO");
			else puts("YES");
	}
	return 0;
}

我自閉了，這個程式碼十分地有道理，但是直到比賽結束我一直沒找到這個程式碼有什麼問題。

直到比賽結束，我才恍然大悟——我看了看我 $\text{WA}$ 的數據，加了幾句偵錯語句，一個大膽的想法從我腦子裏蹦了出來——$\texttt{multiset}$ 的 $erase$ 函數會把所有隻爲 $x$ 的數刪除！

問了一下美國隊長，竟然真的是這樣，哎，我的 $92$ Rating啊，就這樣沒了，淚目……

這也算是 $92$ Rating換來的血的教訓吧……當然，還好我的草名保住了。