chuka231's blog

 const int N = 100005;  
 //////////////////////////////  
 int V;  
 vector<int> G[N];  
 vector<int> rG[N];  
 vector<int> vs;  
 bool used[N];  
 int cmp[N];  
 void add_edge(int from, int to)  
 {  
      G[from].push_back(to);  
      rG[to].push_back(from);  
 }  
 void dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           if (!used[G[v][i]]) dfs(G[v][i]);  
      }  
      vs.push_back(v);  
 }  
 void rdfs(int v, int k)  
 {  
      used[v] = true;  
      cmp[v] = k;  
      for (int i = 0; i < rG[v].size(); i++) {  
           if (!used[rG[v][i]]) rdfs(rG[v][i], k);  
      }  
 }  
 int scc()  
 {  
      memset(used, 0, sizeof used);  
      vs.clear();  
      for (int v = 0; v < V; v++) {  
           if (!used[v]) dfs(v);  
      }  
      memset(used, 0, sizeof used);  
      int k = 0;  
      for (int i = vs.size() - 1; i >= 0; i--) {  
           if (!used[vs[i]]) rdfs(vs[i], k++);  
      }  
      return k;  
 }  
 int n, m;  
 int a[N], b[N];  
 void solve()  
 {  
      scanf("%d%d", &n, &m);  
      REP(i, m) scanf("%d%d", &a[i], &b[i]);  
      V = n;  
      for (int i = 0; i < m; i++) {  
           add_edge(a[i] - 1, b[i] - 1);  
      }  
      int nn = scc();  
      int u = 0, num = 0;  
      for (int v = 0; v < V; v++) {  
           if (cmp[v] == nn - 1) {  
                u = v;  
                num++;  
           }  
      }  
      memset(used, 0, sizeof(used));  
      rdfs(u, 0);  
      for (int v = 0; v < V; v++) {  
           if (!used[v]) {  
                num = 0;  
                break;  
           }  
      }  
      printf("%d\n", num);  
 }

Atcoder.abc185_f F - Range Xor Query

1.Problem
F - Range Xor Query (atcoder.jp)

2.Idea
XOR segtree

3.Source

 Int seg[1 << 20];  
 void set_value(Int pos, Int val) {  
      pos += 1 << 19;  
      seg[pos] = seg[pos] ^ val;  
      while ((pos /= 2) > 0) {  
           seg[pos] = seg[pos * 2] ^ seg[pos * 2 + 1];  
      }  
 }  
 Int get_xor(int ql, int qr, int sl = 0, int sr = 1 << 19, int pos = 1) {  
      //no overlap  
      if (qr <= sl || sr <= ql) return 0;  
      //fit in the segment  
      if (ql <= sl && sr <= qr) return seg[pos];  
      //partially overlap  
      Int sm = (sl + sr) / 2;  
      Int lxor = get_xor(ql, qr, sl, sm, pos * 2);  
      Int rxor = get_xor(ql, qr, sm, sr, pos * 2 + 1);  
      return lxor ^ rxor;  
 }  
 void solve()  
 {  
      Int n, q, t, x, y;  
      cin >> n >> q;  
      for (int i = 0; i < n; i++) {  
           int x; cin >> x;  
           set_value(i, x);  
      }  
      for (int i = 0; i < q; i++) {  
           cin >> t >> x >> y;  
           if (t == 1) {  
                set_value(x - 1, y);  
           }  
           else {  
                cout << get_xor(x - 1, y) << endl;  
           }  
      }  
 }

Monday, March 1, 2021

LeetCode.699 Falling Squares

1.Problem
Falling Squares - LeetCode

2.Idea
Using range max query on segtree

3.Source

 class Solution {  
 public:  
      map<int, int> mp;  
      int tree[8000];  
      void update(int t, int low, int high, int i, int j, int h) {  
           if (i > j) return;  
           if (low == high) {  
                tree[t] = h;  
                return;  
           }  
           int mid = (low + high) / 2;  
           update(2 * t, low, mid, i, min(mid, j), h);  
           update(2 * t + 1, mid + 1, high, max(mid + 1, i), j, h);  
           tree[t] = max(tree[2 * t], tree[2 * t + 1]);  
      }  
      int query(int t, int low, int high, int i, int j) {  
           if (i > j) return -2e9;  
           if (low == i && high == j) return tree[t];  
           int mid = (low + high) / 2;  
           return max(  
                query(2 * t, low, mid, i, min(mid, j)),  
                query(2 * t + 1, mid + 1, high, max(mid + 1, i), j)  
           );  
      }  
      vector<int> fallingSquares(vector<vector<int>>& positions) {  
           set<int> s;  
           memset(tree, 0, sizeof(tree));  
           for (auto it : positions) {  
                s.insert(it[0]);  
                s.insert(it[0] + it[1] - 1);  
           }  
           int compressed = 1, n = positions.size();  
           vector<int> ans(n);  
           for (auto it : s)  
                mp[it] = compressed++;  
           for(int i=0; i<n; i++){  
       int start=positions[i][0], end=positions[i][1]+start-1, h=positions[i][1];  
       int curr=query(1, 1, 2*n, mp[start], mp[end]), ncurr=curr+h;  
       update(1, 1, 2*n, mp[start], mp[end], ncurr);  
       ans[i]=tree[1];  
     }  
           return ans;  
      }  
 };

Saturday, February 6, 2021

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;  
      }  
 }

Thursday, February 4, 2021

Atcoder.abc127_f Absolute Minima

1.Problem
https://atcoder.jp/contests/abc127/submissions/5607909

2.Idea
Using BIT to find and calc the median value.
Credit

3.Source

 const int N = 200005;  
 //////////////////////////////  
 template<typename T>  
 struct BIT {  
      int n;  
      vector<T> dat;  
      BIT(int n = 0) {  
           initialize(n);  
      }  
      void initialize(int nin) {  
           n = nin;  
           dat.resize(n);  
           for (int i = 0; i<n; i++) dat[i] = 0;  
      }  
      T sum(int i) {  
           T s = 0;  
           while (i >= 0) {  
                s += dat[i];  
                i = (i & (i + 1)) - 1;  
           }  
           return s;  
      }  
      T sum_between(int i, int j) {  
           if (i > j) return 0;  
           return sum(j) - sum(i - 1);  
      }  
      void plus(int i, T x) {  
           while (i < n) {  
                dat[i] += x;  
                i |= i + 1;  
           }  
      }  
      // a[0]+...+a[ret] >= x  
      int lower_bound(T x) {  
           int ret = -1;  
           int k = 1;  
           while (2 * k <= n) k <<= 1;  
           for (; k>0; k >>= 1) {  
                if (ret + k < n && dat[ret + k] < x) {  
                     x -= dat[ret + k];  
                     ret += k;  
                }  
           }  
           return ret + 1;  
      }  
 };  
 Int T[N], A[N], B[N];  
 void solve()  
 {  
      int q;  
      cin >> q;  
      vector<int> as;  
      REP(i, q) {  
           cin >> T[i];  
           if (T[i] == 1) {  
                cin >> A[i] >> B[i];  
                as.push_back(A[i]);  
           }  
      }  
      sort(as.begin(), as.end());  
      as.erase(unique(as.begin(), as.end()), as.end());  
      map<int, int> mp;  
      int sz = as.size();  
      REP(i, sz) mp[as[i]] = i;  
      BIT<Int> bitnum(sz);  
      BIT<Int> bitsum(sz);  
      Int fix = 0;  
      int all = 0;  
      REP(i, q) {  
           if (T[i] == 1) {  
                int a = mp[A[i]];  
                bitsum.plus(a, A[i]);  
                bitnum.plus(a, 1);  
                fix += B[i];  
                all++;  
           }  
           else {  
                Int ans = fix;  
                int idx = bitnum.lower_bound((all + 1) / 2);  
                ans += bitsum.sum_between(idx + 1, sz - 1);  
                ans -= as[idx] * bitnum.sum_between(idx + 1, sz - 1);  
                ans -= bitsum.sum_between(0, idx - 1);  
                ans += as[idx] * bitnum.sum_between(0, idx - 1);  
                cout << as[idx] << " " << ans << endl;  
           }  
      }  
 }

Sunday, January 24, 2021

Atcoder.chokudai_S001_h LIS

1.Problem
https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_h

2.Idea
Using BIT Max Range Query

3.Source

 const int N = 100005;  
 //////////////////////////////  
 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); }  
 };  
 struct FenwickTreeMin {  
      vector<int> bit;  //0 -indexed
      int n;  
      const int INF = (int)1e9;  
      FenwickTreeMin(int n) {  
           this->n = n;  
           bit.assign(n, INF);  
      }  
      FenwickTreeMin(vector<int> a) : FenwickTreeMin(a.size()) {  
           for (size_t i = 0; i < a.size(); i++)  
                update(i, a[i]);  
      }  
      int getmin(int r) {  
           int ret = INF;  
           for (; r >= 0; r = (r & (r + 1)) - 1)  
                ret = min(ret, bit[r]);  
           return ret;  
      }  
      void update(int idx, int val) {  
           for (; idx < n; idx = idx | (idx + 1))  
                bit[idx] = min(bit[idx], val);  
      }  
 };  
 struct FenwickTreeMax {  
      vector<int> bit;  // 0 - indexed
      int n;  
      FenwickTreeMax(int n) {  
           this->n = n;  
           bit.assign(n, -INF);  
      }  
      FenwickTreeMax(vector<int> a) : FenwickTreeMax(a.size()) {  
           for (size_t i = 0; i < a.size(); i++)  
                update(i, a[i]);  
      }  
      int getMax(int r) {  
           int ret = -INF;  
           for (; r >= 0; r = (r & (r + 1)) - 1)  
                ret = max(ret, bit[r]);  
           return ret;  
      }  
      void update(int idx, int val) {  
           for (; idx < n; idx = idx | (idx + 1))  
                bit[idx] = max(bit[idx], val);  
      }  
 };  
 int n;  
 int a[N];  
 void solve()  
 {  
      cin >> n;  
      REP(i, n) cin >> a[i];  
      map<int, int> mp;  
      REP(i, n) mp[a[i]] = 0;  
      int i = 0;  
      for (auto it = mp.begin(); it != mp.end(); it++) {  
           it->second = i;  
           i++;  
      }  
      FenwickTreeMax ftm(n);  
      REP(i, n) {  
           int cur = mp[a[i]];  
           int tmp = ftm.getMax(cur - 1);  
           if(tmp == -INF) ftm.update(cur, 1);  
           else ftm.update(cur, tmp + 1);  
      }  
      cout << ftm.getMax(n - 1) << endl;  
 }