C41 线段树+差分 P2184 贪婪大陆

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define ls u << 1
#define rs u << 1 | 1
const int N = 1e6+10;
int n, m;
struct tree
{
  int l, r, sum[2];
} tr[N * 4];
// sum[0]:区间起点数, sum[1]:区间终点数

void pushup(int u, int k)// 上传
{ 
  tr[ u].sum[k] = tr[ls].sum[k] + tr[rs].sum[k];
}
void build(int u, int l, int r)// 建树
{ 
  tr[ u] = {l, r, 0, 0};
  if (l == r)
    return;
  int mid = (l + r) >> 1;
  build(ls, l, mid);
  build(rs, mid + 1, r);
}
void change(int u, int x, int k)// 点修
{ 
  if (tr[ u].l == tr[ u].r)
  {
    tr[ u].sum[k]++;
    return;
  }
  if (x <= tr[ls].r)
    change(ls, x, k);
  else
    change(rs, x, k);
  pushup(u, k);
}
int query(int u, int x, int y, int k)// 区查
{ 
  if (x > tr[ u].r || y < tr[ u].l)
    return 0;
  if (x <= tr[ u].l && tr[ u].r <= y)
    return tr[ u].sum[k];
  return query(ls, x, y, k) + query(rs, x, y, k);
}
int main()
{
  scanf("%d", &n);
  build(1, 1, 1e6);
  for (int i = 1,op, l, r; i <= n; i++)
  {
    scanf("%d%d%d", &op, &l, &r);
    if (op == 1)
      change(1, l, 0), change(1, r, 1);
    else
      printf("%d\n", query(1, 1, r, 0) - query(1, 1, l - 1, 1));
  }
  return 0;
}

C41 线段树+差分 P2184 贪婪大陆

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define ls u << 1 #define rs u << 1 | 1 const int N = 1e6+10; int n, m; struct tree { int l, r, sum[2]; } tr[N * 4]; // sum[0]:区间起点数, sum[1]:区间终点数

void pushup(int u, int k)// 上传 { tr[ u].sum[k] = tr[ls].sum[k] + tr[rs].sum[k]; } void build(int u, int l, int r)// 建树 { tr[ u] = {l, r, 0, 0}; if (l == r) return; int mid = (l + r) >> 1; build(ls, l, mid); build(rs, mid + 1, r); } void change(int u, int x, int k)// 点修 { if (tr[ u].l == tr[ u].r) { tr[ u].sum[k]++; return; } if (x <= tr[ls].r) change(ls, x, k); else change(rs, x, k); pushup(u, k); } int query(int u, int x, int y, int k)// 区查 { if (x > tr[ u].r || y < tr[ u].l) return 0; if (x <= tr[ u].l && tr[ u].r <= y) return tr[ u].sum[k]; return query(ls, x, y, k) + query(rs, x, y, k); } int main() { scanf("%d", &n); build(1, 1, 1e6); for (int i = 1,op, l, r; i <= n; i++) { scanf("%d%d%d", &op, &l, &r); if (op == 1) change(1, l, 0), change(1, r, 1); else printf("%d\n", query(1, 1, r, 0) - query(1, 1, l - 1, 1)); } return 0; }</pre>