國慶·牛客day3 H題-千萬别用樹套樹 線段樹的題

https://ac.nowcoder.com/acm/contest/1108/H

這是題目連結，大緻意思就是有兩種操作，1就是把線段[l,r]插入集合S,2,[l,r]查詢有多少線段[x,y]滿足x<=l<=r<=y,這題維護兩個樹狀數組,一個維護左區間，一個維護右區間，最後查詢的時候就直接用suml(l)-sumr(r-1),sum(l)是在左區間的點數,sumr(r-1)就是不滿足條件的區間端點，減去即可。

AC代碼:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int c[N],d[N];
int suml(int x) {
  int ans=0;
  while(x) {
    ans+=c[x];
    x-=(x&-x);
  }
  return ans;
}

int sumr(int x) {
  int ans=0;
  while(x) {
    ans+=d[x];
    x-=(x&-x);
  }
  return ans;
}

void updatel(int x) {
  while(x<=N) {
    c[x]++;
    x+=(x&-x);
  }
}

void updater(int x) {
  while(x<=N) {
    d[x]++;
    x+=(x&-x);
  }
}
int main() {
  int n,q;
  while(scanf("%d%d",&n,&q)!=EOF) {
    memset(c,0,sizeof(c));
    memset(d,0,sizeof(d));
    int num=0;
    while(q--) {
      int op,l,r;
      scanf("%d%d%d",&op,&l,&r);
      if(op==1) {
        num++;
        updatel(l);
        updater(r);
      } else {
        int ans=0;
        //printf("%d %d %d %d\n",askl(l-1),askr(l-1),askl(r),askr(r));
        ans=suml(l)-sumr(r-1);
        printf("%d\n",ans);
      }
    }
  }

  return 0;
}