문제 링크: https://codeforces.com/contest/1896/problem/D


일단 수열 가지고 놀다가 발견한 점이 4가지 있습니다.

F1. 당연하게도 arr에 있는 1과 2의 총합( = arrSum)보다 큰 수는 절대 만들 수 없다.

F2. arrSum보다 크지 않고 arrSum과 홀짝이 같은 수는 만들 수 있다.

F3. arr의 양쪽 끝 중 하나에라도 1이 있다면 1부터 arrSum까지 모두 만들 수 있다.

F4. arr의 양쪽 끝 모두 2라면 양쪽 끝에서 2가 연속되는 개수가 만들 수 없는 수를 결정한다.

만약 arr이 아래처럼 생겼다면

222.....2222 1 ............&*&*^&^*&&@&*!&@&$*%!............. 1 222....222222

(왼쪽에 연속된 2가 L개, 오른쪽에는 R개)


arrSum - 1, arrSum - 3, arrSum - 5, .... arrSum - 2*min(L, R) + 1: 이렇게 min(L, R)개의 수는 만들 수 없는 수다.



그래서 전략을 이렇게 짰습니다.


위에서 적은 min(L, R)은 arr에서 가장 왼쪽에 있는 1의 index와 가장 오른쪽에 있는 1의 index 둘을 알면 바로 계산할 수 있다.

따라서 arr에 1이 들어간 모든 index들을 Binary Search Tree에 저장하고 관리한다.



그래서 쿼리 알고리즘을 이렇게 짰습니다.


Query 2. "2 i v" 쿼리가 들어오면

Q2-1. 먼저 arrSum을 갱신하고

Q2-2-1. v == 1 이면 1이 하나 추가되는 상황이니 해당 index를 BST에 추가 ( O(log(1의 개수)) )

Q2-2-2. v == 2 일때는 BST에서 해당 index 제거 ( O(log(1의 개수)) )


Query 1. "1 s" 쿼리가 들어오면

Q1. 만약 s > arrSum이면 "NO"

Q2. s % 2 == arrSum % 2이면 "YES"

Q3. BST에서 최솟값과 최댓값 가져와서 arr 양 끝에 연속되는 2의 개수 계산( O(log(1의 개수)) )

계산 결과에 따라 "YES", "NO" 판단


최대 시간복잡도는 테스트케이스 한개에 O(q*logn) 계산됐습니다.


그런데 pretest 9에서 TLE먹었네요.

개선점이 뭐가 있을까요?


#pragma GCC optimize("O3")
#include <cstdlib>
#include <iostream>
typedef struct Node
{
int key;
struct Node *left, *right;
} Node;

int g_NumOf1s;
int g_arr[100010];

Node* CreateNode(int key)
{
Node* newNode = new Node;
newNode->key = key;
newNode->left = newNode->right = 0;

return newNode;
}

Node* Insert(Node* root, int key)
{
if(!root)
return CreateNode(key);

if(key < root->key)
root->left = Insert(root->left, key);
else if(key > root->key)
root->right = Insert(root->right, key);

return root;
}

Node* FindMin(Node* root)
{
while(root->left)
root = root->left;

return root;
}

Node* FindMax(Node* root)
{
while (root->right)
root = root->right;

return root;
}

Node* DeleteNode(Node* root, int key)
{
if(!root)
return root;

if(key < root->key)
root->left = DeleteNode(root->left, key);
else if(key > root->key)
root->right = DeleteNode(root->right, key);
else
{
if(!root->left)
{
Node* temp = root->right;
delete root;

return temp;
}
else if(!root->right)
{
Node* temp = root->left;
delete root;

return temp;
}

Node* temp = FindMin(root->right);

root->key = temp->key;
root->right = DeleteNode(root->right, temp->key);
}

return root;
}

Node* AddToList(Node* root, int toAdd)
{
++g_NumOf1s;
return Insert(root, toAdd);
}

Node* DeleteFromList(Node* root, int toDelete)
{
--g_NumOf1s;
return DeleteNode(root, toDelete);
}

int FindMinThick(Node* root, int N)
{
if(g_NumOf1s > 0)
return std::min(FindMin(root)->key - 1, N - FindMax(root)->key);
else
return N + 1;
}

void FreeTree(Node* root)
{
if(root)
{
FreeTree(root->left);
FreeTree(root->right);
delete root;
}
}

void RunD()
{
g_NumOf1s = 0;
int sumOfArr = 0;
int N, NQ, queryType, s, i, v, minThick;
Node* listOf1 = 0;
std::cin >> N >> NQ;

for(int idx = 0; idx < N; ++idx)
{
std::cin >> g_arr[idx];
sumOfArr += g_arr[idx];

if(g_arr[idx] == 1)
listOf1 = AddToList(listOf1, idx);
}

while(NQ--)
{
std::cin >> queryType;

if(queryType == 1)
{
std::cin >> s;

if(s > sumOfArr)
std::cout << "NO\n";
else
{
minThick = FindMinThick(listOf1, N);

if(s % 2 != sumOfArr % 2 && s > sumOfArr - 1 - 2 * minThick)
std::cout << "NO\n";
else
std::cout << "YES\n";
}
}
if(queryType == 2)
{
std::cin >> i >> v;

if(g_arr[i] != v)
{
sumOfArr += v - g_arr[i];
g_arr[i] = v;

if(v == 1)
listOf1 = AddToList(listOf1, i);
else // if(v == 2)
listOf1 = DeleteFromList(listOf1, i);
}
}
}

FreeTree(listOf1);
}

int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);

int tc;
std::cin >> tc;

while(tc--)
RunD();

return 0;
}