考场抠123题，4题想了个错解，20分，前三题做的都特低，哭了

回来瞬间秒了第四题，真的全套题最简单的题，算法难度不超过橙

AC代码附上：

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

struct Snake{
  int _index;
  int _num;
};

bool operator < (Snake a, Snake b) {
  if (a._num == b._num) {
    return a._index < b._index;
  }
  return a._num < b._num;
}

bool operator > (Snake a, Snake b) {
  if (a._num == b._num) {
    return a._index > b._index;
  }
  return a._num > b._num;
}

Snake operator -(Snake a, Snake b) {
  a._num-=b._num;
  return a;
}

int _T;
int _n;
int _list[1000010];
Snake _queue[1000010];
int _head;
int _tail;
Snake _queue2[1000010];
int _head2;
int _tail2;

int _eat[1000010];
int _eaten[1000010];

bool _live[1000010];

int _res;

void DisplayList() {
  for (int i = 1; i <= _n; i++) {
    cout << _list[i] << ',';
  }
  cout << endl;
}

void Eat(int total) {
  Snake eat;
  Snake eaten;
  Snake next;
  if (_head2 == _tail2 || _head != _tail && _queue[_tail-1] > _queue2[_head2]) {
    _tail--;
    eat = _queue[_tail];
  }
  else {
    eat = _queue2[_head2];
    _head2++;
  }
  if (_head == _tail || _head2 != _tail2 && _queue2[_tail2-1] < _queue[_head]) {
    _tail2--;
    eaten = _queue2[_tail2];
  }
  else {
    eaten = _queue[_head];
    _head++;
  }
  //cout << eat._index << " eats " << eaten._index << endl;
  _eat[total] = eat._index;
  _eaten[total] = eaten._index;
  next = eat-eaten;
  _queue2[_tail2] = next;
  _tail2++;
}

void GenRes() {
  //DisplayList();
  _head = 1;
  _tail = _n+1;
  _head2 = 0;
  _tail2 = 0;
  for (int i = 1; i <= _n; i++) {
    _queue[i]._index = i;
    _queue[i]._num = _list[i];
  }
  for (int i = _n; i > 1; i--) {
    Eat(i);
  }
  memset(_live, 0, sizeof(_live));
  _live[_queue2[_head2]._index] = true;
  //cout << _queue2[_head2]._index;
  _res = 1;
  for (int i = 2; i <= _n; i++) {
    if (!_live[_eat[i]]) {
      while (_res < i) {
	_res++;
	_live[_eaten[_res]] = true;
      }
    }
  }
}

int main() {
  int k, a, b;
  scanf("%d%d", &_T, &_n);
  _T--;
  for (int i = 1; i <= _n; i++) {
    scanf("%d", _list+i);
  }
  GenRes();
  printf("%d\n", _res);
  while (_T--) {
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
      scanf("%d%d", &a, &b);
      _list[a] = b;
    }
    GenRes();
    printf("%d\n", _res);
  }
}