#662 (Div. 2)B. Applejack and Storages

题目描述

This year in Equestria was a year of plenty, so Applejack has decided to build some new apple storages. According to the advice of the farm designers, she chose to build two storages with non-zero area: one in the shape of a square and another one in the shape of a rectangle (which possibly can be a square as well).
Applejack will build the storages using planks, she is going to spend exactly one plank on each side of the storage. She can get planks from her friend’s company. Initially, the company storehouse has n planks, Applejack knows their lengths. The company keeps working so it receives orders and orders the planks itself. Applejack’s friend can provide her with information about each operation. For convenience, he will give her information according to the following format:
+x: the storehouse received a plank with length x
− x: one plank with length x was removed from the storehouse (it is guaranteed that the storehouse had some planks with length x).
Applejack is still unsure about when she is going to order the planks so she wants to know if she can order the planks to build rectangular and square storages out of them after every event at the storehouse. Applejack is busy collecting apples and she has completely no time to do the calculations so she asked you for help!
We remind you that all four sides of a square are equal, and a rectangle has two pairs of equal sides.

Input

The first line contains a single integer n (1≤n≤105): the initial amount of planks at the company’s storehouse, the second line contains n integers a1,a2,…,an (1≤ai≤105): the lengths of the planks.
The third line contains a single integer q (1≤q≤105): the number of events in the company. Each of the next q lines contains a description of the events in a given format: the type of the event (a symbol + or −) is given first, then goes the integer x (1≤x≤105).

Output

After every event in the company, print “YES” if two storages of the required shape can be built from the planks of that company’s set, and print “NO” otherwise. You can print each letter in any case (upper or lower).

Example

input

6
1 1 1 2 1 1
6
+ 2
+ 1
- 1
+ 2
- 1
+ 2
output
NO
YES
NO
NO
NO
YES

Note

After the second event Applejack can build a rectangular storage using planks with lengths 1, 2, 1, 2 and a square storage using planks with lengths 1, 1, 1, 1.
After the sixth event Applejack can build a rectangular storage using planks with lengths 2, 2, 2, 2 and a square storage using planks with lengths 1, 1, 1, 1.

题目大意

给你n块木板，每块木板的长度为a[i]。有m次操作，每次操作你可以加入或者删除一块长度为x的木板。问每次操作之后，你能不能用这些木板搭出一个长方形和正方形。（注：正方形属于长方形）

题目分析4

因为搭长方形需要四个长度相同的木板，而搭长方形则需要两对有两个长度相同的木板或者直接再搭一个正方形，此外对于木板的长度其实并没有任何的限制。因此我们可以统计出所有木板中有多少对木板长度相同，以及有多少四个木板相同的组数。
如果四个相同木板的数量大于2，或者有一个四个相同木板且还有两对别的相同长度的木板，则为YES；否则就是NO。

代码如下

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <iomanip>
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N=1e5+5;
int a[N];
int main()
{
    int n,m,cnt2=0,cnt4=0;	//cnt2统计两个木板相同的数量，cnt4统计四个木板相同的数量
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    	int x;
    	scanf("%d",&x);
    	a[x]++;
    	if(a[x]%2==0) cnt2++;	//如果x能被2整除，说明两个木板相同的组数多了一个
    	if(a[x]%4==0) cnt4++;	//同理
	}
	scanf("%d",&m);
	while(m--) 
	{
		int x;
		char op[2];
		scanf("%s %d",op,&x);
		if(op[0]=='+')			//两种操作
		{
			a[x]++;					//增加木板的情况要先加
			if(a[x]%2==0) cnt2++;
    		if(a[x]%4==0) cnt4++;
		} 
		else
		{							//删除木板的情况要后减
			if(a[x]%2==0) cnt2--;
    		if(a[x]%4==0) cnt4--;
    		a[x]--;
		}	//情况2中cnt2>=4的原因是有一个cnt4就自带了两个cnt2，要把的出来两个cnt2去掉
		if(cnt4>=2||(cnt2>=4&&cnt4==1)) puts("YES");
		else puts("NO");
	}
    return 0;
}