“Inside Information Subtask 2” Code-Antworten

Inside Information Subtask 2

// InsideInformation.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
 
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
 
struct Seg
{
    int l, r, mid;
    Seg* pl, * pr;
    int val = 0;
    Seg(int l, int r) : l(l), r(r), mid((l + r) / 2)
    {
        if(l + 1 < r)
        {
            pl = new Seg(l, mid);
            pr = new Seg(mid, r);
        }
    }
 
    void pull()
    {
        val = pl->val + pr->val;
    }
 
    void update(int i, int x)
    {
        if (l + 1 == r)
        {
            val += x;
            return;
        }
        if (i < mid) pl->update(i, x);
        else pr->update(i, x);
        pull();
    }
 
    int query(int a, int b)
    {
        if (b <= l || a >= r) return 0;
        if (a <= l && r <= b) return val;
        return pl->query(a, b) + pr->query(a, b);
    }
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int N, K; cin >> N >> K;
    //vector<set<int>> servers(N);
    //for (int i = 0; i < N; i++) servers[i].insert(i);
    //vi sz(N, 1);
    Seg* root = new Seg(0, N + K);
    vi so(N, INT32_MAX), go(N, -1);
    so[0] = 0;
    for(int i = 0; i < N + K - 1; i++)
    {
        go[0] = i;
        char type; cin >> type;
        if (type == 'S')
        {
            int a, b; cin >> a >> b; a--; b--;
            if (b == 0) swap(a, b);
            if (so[b] == INT32_MAX) so[b] = i+1;
            if (go[b] > -1) root->update(go[b], -1);
            go[b] = i+1;
            root->update(go[b], 1);
        }
        if (type == 'Q')
        {
            int a, d; cin >> a >> d; a--; d--;
            if (a == 0) {
                if (so[d] != INT32_MAX) cout << "yes" << endl;
                else cout << "no" << endl;
            }
            else
            {
                if (so[d] <= go[a]) cout << "yes" << endl;
                else cout << "no" << endl;
            }
        }
        if (type == 'C')
        {
            int d; cin >> d; d--;
            if (so[d] == INT32_MAX) cout << 1 << endl;
            else
            {
                cout << root->query(so[d], N+K) + 1 << endl;
            }
        }
    }
}