由于本菜雞很笨，并沒有想到什麼簡單的思路，是以有幸在時間内用權值線段樹水過，u1s1我的思維确實垃圾
思路：
利用權值線段樹求區間第k小，首先我們隻需要知道三個變量（最大相同數量，次大相同數量，次次大)，那麼就可以寫了，顯然這題你用排序肯定不行了，那樣最壞時間複雜度是，顯然會TLE，那麼權值線段樹可以幫你實作，具體思路請看下圖：
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
typedef long long ll;
//#define ll long long
const ll N = 1e3 + 5;
const ll maxn = 1e5 + 20;
const ll mod = 1000000007;
int inv[maxn], vis[maxn], dis[maxn];
int fac[maxn], a[maxn], q[maxn], b[N], c[N];
vector<ll> vec;
//typedef pair<ll, ll> p;
//priority_queue<p, vector<p>, greater<p> > m;
// ll sum[maxn], a[maxn];
ll max(ll a, ll b) { return a > b ? a : b; }
ll min(ll a, ll b) { return a < b ? a : b; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
map<ll, ll> mp;
ll ksm(ll a, ll b)
{
a %= mod;
ll ans = 1ll;
while (b)
{
if (b & 1)
ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1ll;
}
return ans;
}
// ll dp[105][16005];
// string p = "abacaba";
// queue<ll> qk, q;
//vector<ll> vec;
// ll sumx[maxn], sumy[maxn], sumk[maxn];
int cnt;
map<int, int> p;
struct node
{
int ls, rs, sum;
} tr[maxn * 32];
void inser(int &k, int L, int R, int pos, int w)
{
if (!k)
k = ++cnt;
tr[k].sum += w;
if (L == R)
return;
int mid = L + R >> 1;
if (mid >= pos)
inser(tr[k].ls, L, mid, pos, w);
else
inser(tr[k].rs, mid + 1, R, pos, w);
}
int query(int k, int L, int R, int ik)
{
if (L == R)
return L;
int sk = tr[tr[k].ls].sum;
int mid = L + R >> 1;
if (sk >= ik)
return query(tr[k].ls, L, mid, ik);
else
return query(tr[k].rs, mid + 1, R, ik - sk);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
//ll t, n, ans;
// scanf("%lld", &t);
// cin >> t;
// while (t--)
// {
p.clear();
int n, k = 0, Q, x, res = 0;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], p[a[i]]++;
for (int i = 1; i <= n; i++)
{
if (!vis[a[i]])
inser(k, -maxn, maxn, p[a[i]], 1), vis[a[i]] = 1, res++;
}
cin >> Q;
while (Q--)
{
char c;
cin >> c >> x;
if (c == '-')
{
inser(k, -maxn, maxn, p[x], -1), p[x]--;
if (p[x] == 0)
vis[x] = 0, res--;
else
inser(k, -maxn, maxn, p[x], 1);
}
else
{
if (!vis[x])
{
p[x]++, res++, vis[x] = 1;
inser(k, -maxn, maxn, p[x], 1);
}
else
{
inser(k, -maxn, maxn, p[x], -1), p[x]++;
inser(k, -maxn, maxn, p[x], 1);
}
}
//cout << "***" << n << "***" << endl;
int dm = query(k, -maxn, maxn, res);
int ds = query(k, -maxn, maxn, res - 1);
int dk = query(k, -maxn, maxn, res - 2);
//cout << dm << ' ' << ds << ' ' << dk << endl;
if (dm >= 8)
{
cout << "YES" << endl;
continue;
}
if (dm >= 4 && ds >= 4)
{
cout << "YES" << endl;
continue;
}
if (dm >= 4 && ((ds >= 2 && (dm - 4) >= 2) || dk >= 2))
{
cout << "YES" << endl;
continue;
}
cout << "NO" << endl;
}
// }
}