Untitled

 avatar
unknown
c_cpp
2 years ago
3.1 kB
2
Indexable
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
    int value; // This is the value of the subtree, not the ID number
    int token;
    struct node *left;
    struct node *right;
    struct node *parent; // pointing to the parent node
} Node;

Node *ptr_arr[1000001];
char expr[1000005];
int n, m, pos = 0, len, flag = 0;

Node *createNode(int token, int value, Node *parent);
Node *createTree(Node *parent);
void Calculation(Node *root);
void freeNode(Node *root);

int main(void)
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d %d", &n, &m);
        scanf("%s", expr);

        pos = 0;
        len = strlen(expr);

        Node *head = createTree(NULL);
        for (int i = 0; i < m; ++i)
        {
            flag = 0;
            int change;
            scanf("%d", &change);
            ptr_arr[change]->value = !(ptr_arr[change]->value);
            Calculation(ptr_arr[change]);
            printf("%d\n", head->value);
        }
        freeNode(head);
        head = NULL;
    }
}

Node *createNode(int token, int value, Node *parent)
{
    Node *newNode = malloc(sizeof(Node));
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->parent = parent;
    newNode->token = token;
    newNode->value = value;
    return newNode;
}

Node *createTree(Node *parent)
{
    Node *root = NULL;
    int index = 0, _intToken;
    char c;
    char _charToken[100001];
    if (pos < len)
    {
        c = expr[pos++];
        if (c == '|' || c == '&')
        {
            if (c == '|')
                root = createNode(-1, 0, parent);
            if (c == '&')
                root = createNode(-2, 0, parent);
            root->left = createTree(root);
            root->right = createTree(root);
        }
        else if (c == '[')
        {
            while (1)
            {
                c = expr[pos++];
                if (c == ']')
                    break;
                _charToken[index++] = c;
            }
            _charToken[index] = '\0';
            _intToken = atoi(_charToken);

            root = createNode(_intToken, 0, parent);
            ptr_arr[root->token] = root;
        }
    }
    return root;
}

void Calculation(Node *root)
{
    if (flag)
        return;
    if (root)
    {
        Node *parent = root->parent;
        int value = root->value;
        if (parent)
        {
            int origin = parent->value;
            int new = 0;
            if (parent->token == -1) // -1 == OR
            {
                new = ((parent->left)->value + (parent->right)->value);
                if (new > 0)
                    new = 1;
            }
            else if (parent->token == -2) // -2 == AND
                new = ((parent->left)->value) * ((parent->right)->value);

            if (new != origin)
            {
                parent->value = new;
                Calculation(parent);
            }
        }
    }
}

void freeNode(Node *root)
{
    if (root)
    {
        freeNode(root->left);
        freeNode(root->right);
        free(root);
    }
}