WA on #14-#19。

即 $1 \le n,m \le 1 \cdot 10 ^ 5$，含有 1,2(#14-#17) 或 1,2,3(#18,#19) 操作的数据。

Hack 数据已经过掉。

特别在于：改变线段树的值域（大于 $1 \times 10 ^ 5$）时候，答案还会变化。

附提交记录：Link

代码：

// Author:zymooll

#include<bits/stdc++.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define int long long
#define y1 y114514
using namespace std;
int read(){
  int s = 0, w = 1;
  char c = getchar();
  while(c < '0' || c > '9'){
    if(c == '-')w = -1;
    c = getchar();
  }
  while(c >= '0' && c <= '9'){
    s = s * 10 + c - '0';
    c = getchar();
  }
  return s * w;
}
void print(int x){
  if(x < 0){
    putchar('-');
    x = -x;
  }
  if(x >= 10)print(x / 10);
  putchar(x % 10 + '0');
  return;
}
const int NMax = 1e5;
int XMax;
int c, n, m, q;
struct Segment{
  int x1, x2, h, v;
  friend bool operator < (Segment aa, Segment bb){
    return aa.h < bb.h;
  }
};
vector<Segment>t1;
vector<tuple<int, int, int, int, int> >t2;
vector<tuple<int, int, int, int> >t3;
int ans;
struct SegmentTree{
  struct Node{
    int n, tot, l, r;
  }t[64 * NMax + 10];
  int ncnt = 1;
  void lzdown(int p, int L, int R, int mid){
    if(!t[p].l)t[p].l = ++ncnt;
    if(!t[p].r)t[p].r = ++ncnt;
    if(!t[p].n)return;
    if(t[t[p].l].n && t[t[p].r].n)return;
    t[t[p].l].n++, t[t[p].r].n++;
    t[t[p].l].tot = mid - L + 1;
    t[t[p].r].tot = R - mid;
    t[p].n--;
  }
  void modify(int p, int L, int R, int l, int r, int k){
    if(l <= L && R <= r && (k == 1 || t[p].n)){
      t[p].n += k;
      t[p].tot = t[p].n ? R - L + 1 : t[t[p].l].tot + t[t[p].r].tot;
      return;
    }
    int mid = (L + R) / 2; lzdown(p, L, R, mid);
    if(l <= mid)modify(t[p].l, L, mid, l, r, k);
    if(r > mid)modify(t[p].r, mid + 1, R, l, r, k);
    t[p].tot = t[t[p].l].tot + t[t[p].r].tot;
  }
}T;
signed main(){
  //freopen(".in","r",stdin);
  //freopen(".out","w",stdout);
  c = read(), n = read(), m = read(), q = read();
  for(int i = 1; i <= q; i++){
    int opt = read(), x1 = read(), y1 = read(), x2 = read(), y2 = read();
    if(opt == 1){
      t1.push_back((Segment){ x1, x2, y1, 1 });
      t1.push_back((Segment){ x1, x2, y2 + 1, -1 });
      t2.push_back(make_tuple(opt, x1, y1, x2, y2));
    }
    else if(opt == 2){
      t1.push_back((Segment){ x1, x2, y1, 1 });
      t1.push_back((Segment){ x1, x2, y2 + 1, -1 });
      t2.push_back(make_tuple(opt, x1, y1, x2, y2));
    }
    else{
      t3.push_back(make_tuple(x1, y1, x2, y2));
    }
  }
  bitset<10>vis;
  for(int i = 0; i < (int)t3.size() - 1; i++){
    int& x1 = get<0>(t3[i]), & y1 = get<1>(t3[i]);
    int& x2 = get<2>(t3[i]), & y2 = get<3>(t3[i]);
    for(int j = i + 1; j < t3.size(); j++){
      if(vis[j])continue;
      int& x3 = get<0>(t3[j]), & y3 = get<1>(t3[j]);
      int& x4 = get<2>(t3[j]), & y4 = get<3>(t3[j]);
      if(y1 - x1 == y3 - x3 && (x2 >= x3 || x4 >= x1)){
        vis[j] = 1;
        x1 = min(x1, x3);
        y1 = min(y1, y3);
        x2 = max(x2, x4);
        y2 = max(y2, y4);
      }
    }
  }
  for(int i = 0; i < t3.size(); i++){
    if(vis[i])continue;
    unordered_map<int, bool>mp;
    int& x1 = get<0>(t3[i]), & y1 = get<1>(t3[i]);
    int& x2 = get<2>(t3[i]), & y2 = get<3>(t3[i]);
    ans += x2 + 1 - x1;
    for(auto& j : t2){
      int& opt = get<0>(j);
      int& x3 = get<1>(j), & y3 = get<2>(j);
      int& x4 = get<3>(j), & y4 = get<4>(j);
      if(opt == 1){
        if(y2 < y3 || y1 > y3)continue;
        int px = x1 + (y3 - y1);
        if(px < x3 || px > x4 || mp[px])continue;
        ans--, mp[px] = 1;
      }
      else{
        if(x2 < x3 || x1 > x3 || mp[x3])continue;
        int py = y1 + (x3 - x1);
        if(py < y3 || py > y4)continue;
        ans--, mp[x3] = 1;
      }
    }
  }
  sort(t1.begin(), t1.end());
  for(int i = 0; i < t1.size() - 1; i++){
    T.modify(1, 0, 1e9, t1[i].x1, t1[i].x2, t1[i].v);
    if(t1[i + 1].h != t1[i].h)ans += T.t[1].tot * (t1[i + 1].h - t1[i].h);
  }
  print(ans);
  return 0;
}

感激不尽！！！