1 Тема від aassii Востаннє редагувалося aassii (16.02.2019 13:23:53)

  • aassii
  • Користувач
  • Поза форумом
  • Дата реєстрації: 09.01.2019
  • Повідомлень: 27
    • Репутація: 8

Тема: Розмістити учнів в готелі

В готель приїхали учні на літню школу. Кожен для себе заздалегідь вибрав, в яку кімнату він хоче заселитися. Якщо обрана кімната виявляється вільна, то учень займає її, в іншому випадку він займає першу вільну кімнату з великим номером. Крім того, деякі учні їдуть в середині школи. Відразу після від'їзду учня його кімната стає доступна для заселення наступного. Так само, іноді адміністрація готелю бажає знати, скільки всього сумарно учнів проживає у цій кімнаті і у всіх кімнатах з номерами менше заданого.

Формат вхідних даних
Перший рядок містить натуральне число n - кількість запитів до готелю, що відбуваються протягом всієї школи (n ? 2*10^5). Наступні n рядків містять інформацію про запити. Запити бувають 3 типів:
+ x, це означає, що приїхав учень, який бажає зайняти кімнату номер x(x ? 2*10^5):
– x, це означає, що з кімнати номер x поїхав учень . (Гарантується, що ця кімната не була порожня).
? x, це означає, що адміністрація хоче дізнатися скільки всього сумарно проживає учнів з номерами кімнат не перевищують x.

Формат вихідних даних
Для кожного приїжджого учня виведіть номер кімнати, в яку він оселиться, або для запиту адміністрації виведіть кількість проживаючих.

▼Прихований текст

Ввід
12
+ 5
? 5
+ 5
? 5
+ 5
? 7
- 6
? 6
+ 5
? 25
+ 5
? 7

Вивід
5
1
6
1
7
3
1
6
3
8
3

▼Прихований текст
//Завдання на дерево відрізків
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX 200002
using namespace std;
//int SegTree[4*MAX];
int a[MAX];
vector<vector<int> > SegTree;
void build(int Vertex, int LeftPos, int RightPos)
{
    if (LeftPos == RightPos) SegTree[Vertex].push_back(a[LeftPos]);
    else
    {
    long long Middle = (LeftPos + RightPos) / 2;
    build (2*Vertex, LeftPos, Middle);
    build (2*Vertex+1, Middle+1, RightPos);
    SegTree[Vertex].resize(RightPos - LeftPos + 1);
    merge(SegTree[2*Vertex].begin(),SegTree[2*Vertex].end(),
          SegTree[2*Vertex+1].begin(),SegTree[2*Vertex+1].end(),
          SegTree[Vertex].begin());
  }
}
void update(int Vertex, int LeftPos, int RightPos, int Position, int NewValue)
{
    if (LeftPos == RightPos)
        //SegTree[Vertex] = NewValue;
        SegTree[Vertex].push_back(NewValue);
    else
    {
    int Middle = (LeftPos + RightPos) / 2;
    if (Position <= Middle) update (2*Vertex, LeftPos, Middle, Position, NewValue);
    else update (2*Vertex+1, Middle+1, RightPos, Position, NewValue);
    //SegTree[Vertex] = SegTree[2*Vertex] + SegTree[2*Vertex+1];
    merge(SegTree[2*Vertex].begin(),SegTree[2*Vertex].end(),
          SegTree[2*Vertex+1].begin(),SegTree[2*Vertex+1].end(),
          SegTree[Vertex].begin());
  }
}
int Query(int Vertex, int LeftPos, int RightPos, int Left, int Right, int x)
{
    if (Left > Right) return 0;
    if ((LeftPos == Left) && (RightPos == Right))
    return lower_bound(SegTree[Vertex].begin(),
                       SegTree[Vertex].end(),x) - SegTree[Vertex].begin();
    int Middle = (LeftPos + RightPos) / 2;
    return Query(2*Vertex, LeftPos, Middle, Left, min(Middle,Right), x) +
    Query(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right, x);
}

/*
int Summa(int Vertex, int LeftPos, int RightPos, int Left, int Right)
{
    if (Left > Right) return 0;
    if ((Left == LeftPos) && (Right == RightPos)) return SegTree[Vertex];
    int Middle = (LeftPos + RightPos) / 2;
    return Summa(2*Vertex, LeftPos, Middle, Left, min(Right,Middle)) +
         Summa(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right);
}
*/

int i, l, r, x, n;
char cmd;
int main ()
{
    //memset(SegTree,0,sizeof(SegTree));
    cin >> n;
    SegTree.resize(4*n);
    build(1,1,n);
    for(i = 1; i <= n; i++)
    {
        cin>>cmd;
        if (cmd == '+') {cin >> x; update(1,1,n,x,1);}
        else if (cmd == '?') {cin >> x; cout << Query(1,1,n,1,n,x) << endl;}
        else if (cmd == '-') {cin >> x; update(1,1,n,x,0);}
    }
  return 0;
}