Atcoder.arc068_c Snuke Line

1.Problem
https://atcoder.jp/contests/arc068/tasks/arc068_c

2.Idea
Using BIT like an imos method in order to update intervals.

3.Source

 class BIT { //1 -indexed  
      const int n;  
      vector<Int> bit;  
 public:  
      BIT(int _n = 0) : n(_n), bit(n + 1, 0) {}  
      void add(int i, const Int x = 1) { for (i++; i <= n; i += i&-i) bit[i] += x; }  
      Int sum(int i) { Int x = 0; for (i++; i; i -= i & -i) x += bit[i]; return x; }  
      Int sum(int i, int j) { return sum(j) - sum(i - 1); }  
 };  
 vector<pair<int, int>> range[N];  
 void solve()  
 {  
      int n, m;  
      cin >> n >> m;  
      REP(i, n) {  
           int l, r; cin >> l >> r; 
           // Holding the intervals by the length 
           range[r - l + 1].push_back(make_pair(l, r));  
      }  
      BIT bit(m + 1);  
      int up = n;  
      RREP(d, m) {  
           for (pair<int, int> p : range[d]) {  
                // Here is the imos in interval
                bit.add(p.first, 1);  
                bit.add(p.second + 1, -1);  
                up--;  
           }  
           int cnt = 0;  
           // This takes only log(d)
           for (int i = d; i <= m; i += d) {  
                cnt += bit.sum(i);  
           }  
           cout << cnt + up << endl;  
      }  
 }