CF1137E 做题报告

题目链接

紧跟 zyf 的步伐，发现人间高质量好题。

开始看上去像是一道数据结构题，但是发现 /(k/leq 10^9/) 后果断放弃任何数据结构。

先来看操作一，这种操作的答案可以说是非常简单的，就是 /((1,0)/) 这个二元组。
再来看操作二，操作三可以发现并不是非常显然或者是有简单的做法。

这时我们去考虑每一次操作三对于 /(a_i/) 所需要加上的数：

/[s/times(i-1)+b /quad(1 /leq s,b /leq 10^9)
/]

可以发现这是系数和截距都是整数的一次函数，也就是说函数单调上升且所有的都大于一。
既然这样，我们就考虑从几何的角度去考虑这个问题。（其实我是看题解的）

其实这种东西包含了 单调性，最值，直线 等关键的词语，很显然会想到凸包上。
随便蒙一个结论：不在当前凸包上的点永远不会是最小值。
换一句话说就是：不论进行多少次操作三，一开始不在下凸包上的点都不是最小值。

来证明一下这个随便猜的结论：
为了方便起见，我们对于每个点进行一次平移：

/[(x,y)/leftarrow(x-1,y)
/]

这样的话每一次操作三的相加的数就变成了 /(si+b/) 。
我们假设平面上有三个点 /(A(x_1,y_1)/) ，/(B(x_2,y_2)/) 和 /(C(x_3,y_3)/) 。
满足 /(x_1<x_2<x_3/) 且 /(y_1>y_2>y_3/) ，同时还满足 /(B/) 在 /(AC/) 连线的上方。
很显然，此时 /(B/) 不在三个点组成的点集的下凸包上。
初始时很显然，画个图就可以发现 /(B/) 不可能是最小的值。
进行一次操作三之后会得到这样的是哪个点。

/[A(x_1,y_1+x_1k+b)//
B(x_2,y_2+x_2k+b)//
C(x_3,y_3+x_3k+b)//
/]

由之前的 /(A/) ，/(B/) 和 /(C/) 三个点的位置可以知道。

/[/frac{y_3-y_2}{x_3-x_2}</frac{y_2-y_1}{x_2-x_1}//
/frac{y_2-y_3}{x_3-x_2}>/frac{y_1-y_2}{x_2-x_1}
/]

假设此时 /(B/) 可以是最小值，那么 /(B/) 的值一定要小于 /(C/) 的值，也就是说

/[/begin{split}
y_2+x_2k+b&<y_3+x_3k+b//
y_2+x_2k&<y_3+x_3k//
(x_3-x_2)k&>y_2-y_3//
k&>/frac{y_2-y_3}{x_3-x_2}
/end{split}
/]

结合上述等式可以得到

/[k>/frac{y_2-y_3}{x_3-x_2}>/frac{y_1-y_2}{x_2-x_1}
/]

所以此时 /(y_2/) 都已经大于 /(y_1/) 了，也就是说 /(B/) 在 /(A/) 的上面，显然假设不成立。

所以我们只要维护一个凸包就可以了。
对于操作一，没有什么好讲的，直接把单调栈清空就可以了。
对于操作二，从后端不断弹出，直到斜率满足下凸包的要求，然后把最后一个点加入。
对于操作三，可以直接记录全局的 /(K/) 和 /(B/) 方便计算。

注意：对于操作二要考虑 /(K/) 和 /(B/) 的影响

具体的细节可以看代码。

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define quad putchar(' ')
#define Enter putchar('/n')

using std::abs;
using std::pair;
using std::string;
using std::make_pair;

#define int long long

template <class T> void read(T &a);
template <class T> void write(T x);

template <class T, class ...rest> void read(T &a, rest &...x);
template <class T, class ...rest> void write(T x, rest ...a);

const int N = 1000005;

int n, m, top = 0, K, B;
struct Point {
  int x, y;
  Point(int _x = 0, int _y = 0) {x = _x; y = _y;}
  friend Point operator+(const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
  friend Point operator-(const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
  friend double operator*(const Point &p, const Point &q) {return 1.0 * p.x * q.y - 1.0 * p.y * q.x;}
} sta[N];

inline int Num(Point now) {
  return now.y + K * now.x + B;
}

signed main(void) {
  // File("1");
  read(n, m);
  top = 1; sta[top] = Point(0, 0);
  for (int test = 1, op, k, b, s; test <= m; test++) {
    read(op);
    if (op == 1) {
      read(k);
      top = 1; sta[top] = Point(0, 0);
      n += k; K = B = 0;
    } else if (op == 2) {
      Point now = Point(n, -(n * K + B));
      read(k); n += k;
      while (top > 1 && (now - sta[top - 1]) * (sta[top] - sta[top - 1]) > 0.000000001) top --;
      sta[++top] = now;
    } else if (op == 3) {
      read(b, s);
      K += s; B += b;
    }
    while (top > 1 && Num(sta[top]) >= Num(sta[top - 1])) top --;
    write(sta[top].x + 1, Num(sta[top])); Enter;
  }
  return 0;
}

template <class T> void read(T &a) {
  int s = 0, t = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') c = getchar(), t = -1;
  while (isdigit(c)) s = s * 10 + c - '0', c = getchar();
  a = s * t;
}
template <class T> void write(T x) {
  if (x == 0) putchar('0');
  if (x < 0) putchar('-'), x = -x;
  int top = 0, sta[50] = {0};
  while (x) sta[++top] = x % 10, x /= 10;
  while (top) putchar(sta[top] + '0'), top --;;;
  return ;
}

template <class T, class ...rest> void read(T &a, rest &...x) {
  read(a); read(x...);
}
template <class T, class ...rest> void write(T x, rest ...a) {
  write(x); quad; write(a...);
}