洛谷 P2367 语文成绩

// P2367 的第二关：同一个差分算法，四种读法差多少
//
// 用法：./p2367Read [n] [csv]      默认 n = 1000000（满数据是 5000000）
//   ★ 它自己造一份 P2367 形状的输入写进临时文件，再 freopen 回 stdin 读四遍 ——
//     不需要喂输入。四遍的**答案必须一模一样**（csv 里的 same 就是钉这件事的）。
//
// 四种读法（第 45 章第 11 步解释过它们的区别，这里量的是**这道题上的**代价）：
//   ① cin（默认，同步开着）    ② cin + sync_with_stdio(false)
//   ③ scanf                    ④ 手写快读（fread 整块读进来自己拼数字）
//
// ⚠ 顺序不能换：关掉同步之后 cin 会自己预读一大块，之后再 freopen 换文件，
//   cin 缓冲里剩的就是上一份文件的残渣 ⇒ 「同步开着」那一趟必须排在最前面
//   （这条坑是第 45 章 read.cpp 里踩过的，照抄它的顺序）。

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;

static char path[64];
static int a[5000005];
static int d[5000006];

static void makeData(int n) {
    snprintf(path, sizeof(path), "/tmp/p2367-bench-%d.txt", (int)getpid());
    FILE* f = fopen(path, "w");
    if (!f) { fprintf(stderr, "写不出临时文件 %s\n", path); exit(1); }
    mt19937 rng(20260826u);
    fprintf(f, "%d %d\n", n, n);
    for (int i = 0; i < n; i++) fprintf(f, "%d%c", (int)(rng() % 101), i + 1 == n ? '\n' : ' ');
    for (int i = 0; i < n; i++) {
        int x = 1 + (int)(rng() % (unsigned)n);
        int y = x + (int)(rng() % (unsigned)(n - x + 1));
        fprintf(f, "%d %d %d\n", x, y, (int)(rng() % 101));
    }
    fclose(f);
}
static void reopen() {
    if (!freopen(path, "r", stdin)) { fprintf(stderr, "读不回临时文件\n"); exit(1); }
}

/* 差分那三行 —— 四趟共用，所以四趟之间的差别只可能来自读入 */
static int finish(int n) {
    int cur = 0, ans = INT_MAX;
    for (int i = 1; i <= n; i++) { cur += d[i]; ans = min(ans, a[i] + cur); }
    return ans;
}
static void reset(int n) { memset(d, 0, sizeof(int) * (size_t)(n + 2)); }

static char ibuf[1 << 22];
static size_t ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return EOF; }
    return ibuf[ipos++];
}
static inline int readIntFast() {
    int c = gc(), x = 0;
    while (c != EOF && (c < '0' || c > '9')) c = gc();
    for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
    return x;
}

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 1000000;
    bool csv = (argc > 2 && string(argv[2]) == "csv");
    makeData(n);
    double ms[4];
    int ans[4];

    /* ① cin（默认，同步开着）—— 必须排第一趟 */
    { reopen(); reset(n);
      auto t0 = steady_clock::now();
      int m, p; cin >> m >> p;
      for (int i = 1; i <= m; i++) cin >> a[i];
      for (int i = 0; i < p; i++) { int x, y, z; cin >> x >> y >> z; d[x] += z; d[y + 1] -= z; }
      ans[0] = finish(m);
      ms[0] = duration<double, milli>(steady_clock::now() - t0).count(); }

    /* ② cin + sync_with_stdio(false) */
    { reopen(); reset(n);
      auto t0 = steady_clock::now();
      ios::sync_with_stdio(false); cin.tie(nullptr);
      int m, p; cin >> m >> p;
      for (int i = 1; i <= m; i++) cin >> a[i];
      for (int i = 0; i < p; i++) { int x, y, z; cin >> x >> y >> z; d[x] += z; d[y + 1] -= z; }
      ans[1] = finish(m);
      ms[1] = duration<double, milli>(steady_clock::now() - t0).count(); }

    /* ③ scanf */
    { reopen(); reset(n);
      auto t0 = steady_clock::now();
      int m, p; if (scanf("%d %d", &m, &p) != 2) { m = p = 0; }
      for (int i = 1; i <= m; i++) { if (scanf("%d", &a[i]) != 1) break; }
      for (int i = 0; i < p; i++) {
          int x, y, z;
          if (scanf("%d %d %d", &x, &y, &z) != 3) break;
          d[x] += z; d[y + 1] -= z;
      }
      ans[2] = finish(m);
      ms[2] = duration<double, milli>(steady_clock::now() - t0).count(); }

    /* ④ 手写快读 */
    { reopen(); reset(n); ipos = ilen = 0;
      auto t0 = steady_clock::now();
      int m = readIntFast(), p = readIntFast();
      for (int i = 1; i <= m; i++) a[i] = readIntFast();
      for (int i = 0; i < p; i++) {
          int x = readIntFast(), y = readIntFast(), z = readIntFast();
          d[x] += z; d[y + 1] -= z;
      }
      ans[3] = finish(m);
      ms[3] = duration<double, milli>(steady_clock::now() - t0).count(); }

    remove(path);
    bool same = (ans[0] == ans[1] && ans[1] == ans[2] && ans[2] == ans[3]);
    if (csv) {
        const char* key[4] = { "cin", "nosync", "scanf", "fast" };
        for (int k = 0; k < 4; k++) printf("%s,%.1f\n", key[k], ms[k]);
        printf("same,%d\nanswer,%d\n", same ? 1 : 0, ans[0]);
        return 0;
    }
    const char* name[4] = { "cin（默认，同步开着）", "cin + sync_with_stdio(false)",
                            "scanf", "手写快读（fread）" };
    /* ⚠ 中文是双宽的，%-30s 按字节数补空格会补歪 —— 照第 45 章 read.cpp 那套按显示宽度补 */
    auto disp = [](const string& t) {
        int w = 0;
        for (unsigned char c : t) { if ((c & 0xC0) == 0x80) continue; w += (c < 0x80) ? 1 : 2; }
        return w;
    };
    auto padR = [&](const string& t, int w) { return t + string(max(0, w - disp(t)), ' '); };
    double best = *min_element(ms, ms + 4);
    printf("n = p = %d（和满数据比是 %.0f%%），四种读法跑同一个差分：\n\n", n, 100.0 * n / 5000000);
    for (int k = 0; k < 4; k++)
        printf("  %s %8.1f 毫秒   慢 %4.1f 倍\n", padR(name[k], 30).c_str(), ms[k], ms[k] / best);
    printf("\n四趟的答案%s（都是 %d）\n", same ? "完全一致" : "居然不一致！", ans[0]);
    return 0;
}