B. Applejack and Storages (662 div2 思维 模拟)

B. Applejack and Storages**

题意： 初始给定n个长度已知的木板，然后q次操作，每次加入或减少一个长度为x的木板（保证减少前存在长度为 x 的木板），每次操作后询问：是否可以利用现在的木板组成一个正方形和一个长方形(可为正方形)。
思路： 显然可以很暴力去做，每次操作后寻找出现次数前三大的数，然后分类讨论是否能组成，但是复杂度太大。
由于四条形同的木板组成一个正方形，两条形同的木板组成一对边，所以，我们只统计 $2\le k \le4$ 和 $k=4$ 的 $k$ 的个数，分别记为 $f_2、f_4$，其中 $k$ 为每个长度的木板出现的次数 (当等于4后，重新计数)，然后在询问时动态维护个数即可，当 $2\le f_4$ 或者 $3\le f_2$并且 $f_4=1$ ，这两种情况时才能组成两个正方形或者一个正方形一个长方形。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;int vis[N];
int n,x,f2,f4;int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&x);vis[x]++;if(vis[x]==2) f2++;	// 多一对边if(vis[x]==4) f4++,vis[x]=0;  //多一个正方形}int q;scanf("%d",&q);char c[2];while(q--){scanf("%s%d",c,&x);if(c[0]=='-'){vis[x]--;if(vis[x]==-1) vis[x]=3,f4--;   //少一个正方形if(vis[x]==1) f2--;   //少一对边}else {vis[x]++;if(vis[x]==4) f4++,vis[x]=0;  //多一个正方形if(vis[x]==2) f2++;   //多一对边}if(f4>=2||(f4==1&&f2>=3)) printf("YES\n");else printf("NO\n");}return 0;
}