萌新0pts求助
查看原帖
萌新0pts求助
363006
wangyibo201026楼主2022/3/28 12:42

代码:

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 4e5 + 5;

int n, m, q;

struct segment_tree{
  int tree[N], tag[N];
  
  void pushup(int node){
    tree[node] = tree[node << 1] + tree[node << 1 | 1];
  }

  void addtag(int node, int lt, int rt, int val){
    tag[node] += val;
    tree[node] += (rt - lt + 1) * val;
  }

  void pushdown(int node, int lt, int rt){
    if(!tag[node]){
      return ;
    }
    int mid = lt + rt >> 1;
    addtag(node << 1, lt, mid, tag[node]);
    addtag(node << 1 | 1, mid + 1, rt, tag[node]);
    tag[node] = 0;
  }

  void update(int node, int lt, int rt, int x, int y, int val){
    if(x > rt || y < lt){
      return ;
    }
    if(x <= lt && rt <= y){
      addtag(node, lt, rt, val);
      return ;
    }
    pushdown(node, lt, rt);
    int mid = lt + rt >> 1;
    update(node << 1, lt, mid, x, y, val);
    update(node << 1 | 1, mid + 1, rt, x, y, val);
    pushup(node);
  }

  int query(int node, int lt, int rt, int x, int y){
    if(x > rt || y < lt){
      return 0;
    }
    if(x <= lt && rt <= y){
      return tree[node];
    }
    pushdown(node, lt, rt);
    int mid = lt + rt >> 1;
    return query(node << 1, lt, mid, x, y) + query(node << 1 | 1, mid + 1, rt, x, y);
  }
}X, Y;

void Solve(){
  cin >> n >> m >> q;
  while(q--){
    int op;
    cin >> op;
    if(op == 1){
      int x, y;
      cin >> x >> y;
      X.update(1, 1, n, x, x, 1);
      Y.update(1, 1, n, y, y, 1);
    }
    else{
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      cout << X.query(1, 1, n, x1, x2) * n + Y.query(1, 1, n, y1, y2) * m - X.query(1, 1, n, x1, x2) * Y.query(1, 1, n, y1, y2) * 2 << '\n';
    }
  }
}

signed main(){
  Solve();
  return 0;
}
2022/3/28 12:42
加载中...