CSES. Road Reparation

1.Problem

https://cses.fi/problemset/task/1675

2.Idea

Standard MST with UnionFind implementation

3.Source

 int n, m;  
 struct Edge {  
      int u, v, c;  
      bool operator < (const Edge &a)const {  
           return c < a.c;  
      }  
 } Edges[N];  
 struct UF {  
      vector<int> Parent;  
      vector<int> Size;  
      int Count;  
      void init(int n) {  
           Count = n;  
           Parent.resize(n);  
           Size.resize(n);  
           REP(i, n) {  
                make_set(i);  
           }  
      }  
      void make_set(int v) {  
           Parent[v] = v;  
           Size[v] = 1;  
      }  
      int find_set(int v) {  
           if (v == Parent[v])  
                return v;  
           return Parent[v] = find_set(Parent[v]);  
      }  
      void union_sets(int a, int b) {  
           a = find_set(a);  
           b = find_set(b);  
           if (a != b) {  
                if (Size[a] < Size[b])  
                     swap(a, b);  
                Count--;  
                Parent[b] = a;  
                Size[a] += Size[b];  
           }  
      }  
 };  
 void solve()  
 {  
      cin >> n >> m;  
      REP(i, m) {  
           cin >> Edges[i].u >> Edges[i].v >> Edges[i].c;  
           Edges[i].u--;  
           Edges[i].v--;  
      }  
      sort(Edges, Edges + m);  
      UF uf;  
      uf.init(n);  
      Int ret = 0;  
      REP(i, m) {  
           int u = Edges[i].u;  
           int v = Edges[i].v;  
           int c = Edges[i].c;  
           if (uf.find_set(u) != uf.find_set(v)) {  
                ret += c;  
                uf.union_sets(u, v);  
           }  
      }  
      if (uf.Count == 1) cout << ret << endl;  
      else cout << "IMPOSSIBLE" << endl;  
 }  

ARC106 B - Values

Problem:

B - Values (atcoder.jp)

Idea:

Check sum of nodes in the same connected components

Source:

int n, m;
Int a[N], b[N];

struct UF {
	vector<int> Parent;
	vector<int> Size;
	void init(int n) {
		Parent.resize(n);
		Size.resize(n);
		REP(i, n) {
			make_set(i);
		}
	}
	void make_set(int v) {
		Parent[v] = v;
		Size[v] = 1;
	}
	int find_set(int v) {
		if (v == Parent[v])
			return v;
		return Parent[v] = find_set(Parent[v]);
	}
	void union_sets(int a, int b) {
		a = find_set(a);
		b = find_set(b);
		if (a != b) {
			if (Size[a] < Size[b])
				swap(a, b);
			Parent[b] = a;
			Size[a] += Size[b];
		}
	}
};

void solve()
{
	cin >> n >> m;
	REP(i, n) cin >> a[i];
	REP(i, n) cin >> b[i];

	UF uf;
	uf.init(n);
	REP(i, m) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		uf.union_sets(u, v);
	}
	map<int, Int> mp1, mp2;
	REP(i, n) {
		int par = uf.find_set(i);
		mp1[par] += a[i];
		mp2[par] += b[i];
	}

	for (auto x : mp1) {
		int par = x.first;
		if (mp1[par] != mp2[par]) {
			cout << "No" << endl;
			return;
		}
	}
	cout << "Yes" << endl;
}


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(9);
	solve();
	return 0;
}

Codeforces ITMO Academy: pilot course » Segment Tree

<<Point Update/Range Query>>

[PART:1, STEP:1]

 A. Segment Tree for the Sum (Point Set Update/Range Sum Query)

https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/A

B. Segment Tree for the Minimum (Point Set Update/Range Min Query)

https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/B

C. Number of Minimums on a Segment (Point Set Update/Range Min&Count Query)

https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/C

[PART:1, STEP:2]

A. Segment with the Maximum Sum (Point Set Update/Range Max Sum Query)

https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/A

B. K-th one (Point Set Update/Range Sum Query/Binary Search)

https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/B

C. First element at least X (Point Set Update/Range Max Query/Binary Search)

https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/C

D. First element at least X-2 (Point Set Update/Range Max Query/Binary Search)

https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/D

[PART:1, STEP:3]

A. Inversions (Point Set Update/Range Sum Query/Inversion)

https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/A

B. Inversions 2 (Point Set Update/Range Sum Query/Binary Search/Kth from right)

https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/B

C. Nested Segments (Point Set Update/Range Sum Query/Nested)

https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/C

D. Intersecting Segments  (Point Set Update/Range Sum Query/Intersection)

https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/D

E. Addition to Segment (Point Add Update/Range Sum Query/imos)

https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/E

[PART:1, STEP:4]

A. Sign alternation (Point Set Update/Range Sum Query/Alternate Sign)

https://codeforces.com/edu/course/2/lesson/4/4/practice/contest/274684/problem/A

B. Cryptography (Point Set Update/Range Matrix Multi Query)

https://codeforces.com/edu/course/2/lesson/4/4/practice/contest/274684/problem/B

C. Number of Inversions on Segment (Point Set Update/Range Inverse Number Query)

https://codeforces.com/edu/course/2/lesson/4/4/practice/contest/274684/problem/C

D. Number of Different on Segment (Point Set Update/Range Bitwise OR Query)

https://codeforces.com/edu/course/2/lesson/4/4/practice/contest/274684/problem/D

E. Earthquakes (Point Set Update/Range Min Query with Range Update)

https://codeforces.com/edu/course/2/lesson/4/4/practice/contest/274684/problem/E

<<Range Update/Point Query>>

[PART:2, STEP:1]

A. Addition to Segment (Range Add Update/Point Get Query)

https://codeforces.com/edu/course/2/lesson/5/1/practice/contest/279634/problem/A

B. Applying MAX to Segment (Range Max Update/Point Get Query)

https://codeforces.com/edu/course/2/lesson/5/1/practice/contest/279634/problem/B

C. Assignment to Segment (Range Set Update/Point Get Query)

https://codeforces.com/edu/course/2/lesson/5/1/practice/contest/279634/problem/C

[PART:2, STEP:4]

B. Add Arithmetic Progression On Segment (Range Add-Multi Update/Point Get Query)

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/B

E. Wall (Range MinMax Update/Point Get Query)

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/E

<<Range Update/Range Query>>

[PART:2, STEP:2]

A. Addition and Minimum (Range Add Update/Range Min Query)

https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/A

B. Multiplication and Sum (Range Multi Update/Range Sum Query)

https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/B

C. Bitwise OR and AND (Range OR Update/Range AND Query)

https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/C

D. Addition and Sum (Range Add Update/Range Sum Query)

https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/D

E. Assignment and Minimum (Range Set Update/Range Min Query)

https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/E

F. Assignment and Sum (Range Set Update/Range Sum Query)

https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/F

[PART:2, STEP:3]

A. Assignment and Maximal Segment (Range Set Update/Range MaxSumSeg Query)

https://codeforces.com/edu/course/2/lesson/5/3/practice/contest/280799/problem/A

B. Inverse and K-th one (Range Inverse Update/Range Sum Query/Binary Search)

https://codeforces.com/edu/course/2/lesson/5/3/practice/contest/280799/problem/B

C. Addition and First element at least X (Range Add Update/Range Max Query/Binary Search)

https://codeforces.com/edu/course/2/lesson/5/3/practice/contest/280799/problem/C


[PART:2, STEP:4]

A. Assignment, Addition, and Sum (Range Set Update/Range Add Update/Range Sum Query)

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/A

C. Painter (Range ColorSegment Update/Range CountSegment Query)

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/C

D. Problem About Weighted Sum (Range Add Update/Range Weighted Sum Query)

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/D

F. Mountain (Range Set Update/Range Sum Query/Range Max Query/Binary Search)

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/F

Segment Tree problems in Atcoder

A. Segment Trees

1.Range Add Update/Point Get Query
D - ぴょんぴょんトレーニング (atcoder.jp)
typhoon - 台風 (Typhoon) (atcoder.jp)

2.Range Min Query/Point Update
D - 括弧列 (atcoder.jp)

3.

4.

5.

6.

B. Segment Tree with Lazy Propagation

1.Range Add/Range Min Query
B - ドキドキデート大作戦高橋君 (atcoder.jp)

2.Range Set/Range Max Query
029 - Long Bricks（★5） (atcoder.jp)

3.Range Set/Range Sum Query + Digit Arrange
E - Replace Digits (atcoder.jp)

4.Range Add/Range Max Query (Inline DP)
W - Intervals (atcoder.jp)

5.Range Multi&Add/Range Sum Query
K - Range Affine Range Sum (atcoder.jp)

6.Range Add/Range Sum Query (2D Rectangles)
N - ビルの建設 (atcoder.jp)

7.Range Min Update/Range Min Query
F - Simplified Reversi (atcoder.jp)

8.Range Inverse Update/Range Inverse Count Query (Binary string)
L - Lazy Segment Tree (atcoder.jp)

9.

10.

11.


C. Some extras

1.Range Set/Range Or Query (Flatten Trees by Euler Tour, Segtee on Tree)
E. New Year Tree: Problem - E - Codeforces

2.

3.

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

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

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

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

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

POJ.3260 The Fewest Coins

1.Problem
3260 -- The Fewest Coins (poj.org)

2.Idea
Knapsack problem. Reference

3.Source

 #include <cstdio>  
 #include <cstring>  
 const int maxn = 101, maxt = 10001, maxv = 121, INF = 0x3f3f3f3f;  
 int n, t, lim, v[maxn], c[maxn], que[maxt + maxv * maxv][2], l, r, f[maxt + maxv * maxv], g[maxv * maxv], ans;  
 int main()  
 {  
      scanf("%d%d", &n, &t);  
      for(int i = 0; i < n; ++i)  
      {  
           scanf("%d", v + i);  
           if(lim < v[i])  
                lim = v[i];  
      }  
      for(int i = 0; i < n; ++i)  
           scanf("%d", c + i);  
      lim *= lim;  
      t += lim;  
      memset(f, 0x3f, sizeof f);  
      memset(g, 0x3f, sizeof g);  
      f[0] = g[0] = 0;  
      for(int i = 0; i < n; ++i)  
           for(int a = 0; a < v[i]; ++a)  
           {  
                l = r = 0;  
                for(int j = 0; j * v[i] + a <= t; ++j)  
                {  
                     int tmp = f[j * v[i] + a] - j;  
                     while(l < r && que[r - 1][1] >= tmp)  
                          --r;  
                     que[r][0] = j;  
                     que[r++][1] = tmp;  
                     f[j * v[i] + a] = que[l][1] + j;  
                     if(que[l][0] == j - c[i])  
                          ++l;  
                }  
           }  
      for(int i = 0; i < n; ++i)  
           for(int j = v[i]; j <= lim; ++j)  
                if(g[j] > g[j - v[i]] + 1)  
                     g[j] = g[j - v[i]] + 1;  
      t -= lim;  
      ans = INF;  
      for(int i = 0; i <= lim; ++i)  
           if(ans > f[t + i] + g[i])  
                ans = f[t + i] + g[i];  
      if(ans != INF)  
           printf("%d\n", ans);  
      else  
           puts("-1");  
      return 0;  
 }  

POJ.2823 Sliding Window

1.Problem
2823 -- Sliding Window (poj.org)

2.Idea
Using Deque

3.Source

 const int N = 1000006;  
 //////////////////////////////  
 int n, k;  
 int a[N];  
 int mn[N], mx[N];  
 int deq[N];  
 void solve()  
 {  
      scanf("%d%d", &n, &k);  
      REP(i, n) scanf("%d", &a[i]);  
      //MIN values  
      int s = 0, t = 0;  
      REP(i, n) {  
           while (s < t && a[deq[t - 1]] >= a[i]) t--;  
           deq[t++] = i;  
           if (i - k + 1 >= 0) {  
                mn[i - k + 1] = a[deq[s]];  
                if (deq[s] == i - k + 1) s++;  
           }  
      }  
      REP(i, n - k + 1) {  
           printf("%d%c", mn[i], i == n - k ? '\n' : ' ');  
      }  
      //MAX Values  
      s = 0, t = 0;  
      REP(i, n) {  
           while (s < t && a[deq[t - 1]] <= a[i]) t--;  
           deq[t++] = i;  
           if (i - k + 1 >= 0) {  
                mx[i - k + 1] = a[deq[s]];  
                if (deq[s] == i - k + 1) s++;  
           }  
      }  
      REP(i, n - k + 1) {  
           printf("%d%c", mx[i], i == n - k ? '\n' : ' ');  
      }  
 }  

POJ.3709 K-Anonymous Sequence

1.Problem
3709 -- K-Anonymous Sequence (poj.org)

2.Idea
Deque

3.Source

 int n, k;  
 Int a[N];  
 Int dp[N], S[N];  
 int deq[N];  
 Int f(int j, int x)  
 {  
      return -a[j] * x + dp[j] - S[j] + a[j] * j;  
 }  
 bool check(int f1, int f2, int f3)  
 {  
      Int a1 = -a[f1], b1 = dp[f1] - S[f1] + a[f1] * f1;  
      Int a2 = -a[f2], b2 = dp[f2] - S[f2] + a[f2] * f2;  
      Int a3 = -a[f3], b3 = dp[f3] - S[f3] + a[f3] * f3;  
      return (a2 - a1) * (b3 - b2) >= (b2 - b1) * (a3 - a2);  
 }  
 void solve()  
 {  
      int t; cin >> t;  
      while (t--) {  
           scanf("%d%d", &n, &k);  
           for (int i = 0; i < n; i++) {  
                scanf("%d", &a[i]);  
           }  
           for (int i = 0; i < n; i++) {  
                S[i + 1] = S[i] + a[i];  
           }  
           int s = 0, t = 1;  
           deq[0] = 0;  
           dp[0] = 0;  
           for (int i = k; i <= n; i++) {  
                if (i - k >= k) {  
                     while (s + 1 < t && check(deq[t - 2], deq[t - 1], i - k)) t--;  
                     deq[t++] = i - k;  
                }  
                while (s + 1 < t && f(deq[s], i) >= f(deq[s + 1], i)) s++;  
                dp[i] = S[i] + f(deq[s], i);  
           }  
           printf("%lld\n", dp[n]);  
      }  
 }  

POJ.2082 Terrible Sets

1.Problem
2082 -- Terrible Sets (poj.org)

2.Idea
Description is terrible but it was just simple max rectangle in histogram problem.

3.Source

 int n;  
 int h[N];  
 int st[N], L[N], R[N], sum[N];  
 int maxRec() {  
      //L   
      int t = 0;  
      for (int i = 0; i < n; i++) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           L[i] = (t == 0 ? 0 : (st[t - 1] + 1));  
           st[t++] = i;  
      }  
      //R   
      t = 0;  
      for (int i = n - 1; i >= 0; i--) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           R[i] = (t == 0 ? n : st[t - 1]);  
           st[t++] = i;  
      }  
      int res = 0;  
      for (int i = 0; i < n; i++) {  
           res = max(res, h[i] * (sum[R[i]] - sum[L[i]]));  
      }  
      return res;  
 }  
 void solve()  
 {  
      while (cin >> n) {  
           if (n < 0) break;  
           for (int i = 0; i < n; i++) {  
                scanf("%d%d", &sum[i + 1], &h[i]);  
           }  
           for (int i = 0; i < n; i++)   
                sum[i + 1] += sum[i];  
           printf("%d\n", maxRec());  
      }  
 }  

POJ.3250 Bad Hair Day

1.Problem
3250 -- Bad Hair Day (poj.org)

2.Idea
Use monoton stack

3.Source

 int n;  
 Int h[80200];  
 void solve()  
 {       
      int n; cin >> n;  
      for (int i = 0; i < n; i++) {  
           scanf("%d", &h[i]);  
      }  
      h[n] = MOD;  
      Int ans = 0;  
      stack<int> st;//monoton stack  
      for (int i = 0; i <= n; i++) {  
           if (st.empty() || h[st.top()] > h[i])  
                st.push(i);  
           else {  
                while (!st.empty() && h[st.top()] <= h[i]) {  
                     int tmp = st.top(); st.pop();  
                     ans += (Int)(i - tmp - 1);  
                }  
                st.push(i);  
           }  
      }  
      printf("%lld\n", ans);  
 }  

POJ.3494 Largest Submatrix of All 1’s

1.Problem
3494 -- Largest Submatrix of All 1’s (poj.org)

2.Idea
Apply the max rectangle in histogram problem.

3.Source

 int m, n;  
 int h[2200];  
 int st[2200], L[2200], R[2200];  
 int maxRec() {  
      //L  
      int t = 0;  
      for (int i = 0; i < n; i++) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           L[i] = (t == 0 ? 0 : (st[t - 1] + 1));  
           st[t++] = i;  
      }  
      //R  
      t = 0;  
      for (int i = n - 1; i >= 0; i--) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           R[i] = (t == 0 ? n : st[t - 1]);  
           st[t++] = i;  
      }  
      int res = 0;  
      for (int i = 0; i < n; i++) {  
           res = max(res, h[i] * (R[i] - L[i]));  
      }  
      return res;  
 }  
 void solve()  
 {       
      while (cin >> m >> n) {  
           memset(h, 0, sizeof h);  
           int ans = 0;  
           for (int i = 0; i < n; i++) {  
                for (int j = 0; j < m; j++) {  
                     int t; scanf("%d", &t);  
                     h[j] = t ? h[j] + 1 : 0;  
                }  
                ans = max(ans, maxRec());  
           }  
           printf("%d\n", ans);  
      }  
 }  

POJ.2559 Largest Rectangle in a Histogram

1.Problem
2559 -- Largest Rectangle in a Histogram (poj.org)

2.Idea
Using stack

3.Source

 int n;  
 int h[N];  
 int L[N], R[N], st[N];  
 void solve()  
 {       
      while (scanf("%d", &n), n) {  
           REP(i, n) scanf("%d", &h[i]);  
           //L  
           int t = 0;  
           for (int i = 0; i < n; i++) {  
                while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
                L[i] = (t == 0 ? 0 : (st[t - 1] + 1));  
                st[t++] = i;  
           }  
           //R  
           t = 0;  
           for (int i = n - 1; i >= 0; i--) {  
                while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
                R[i] = (t == 0 ? n : st[t - 1]);  
                st[t++] = i;  
           }  
           long long res = 0;  
           for (int i = 0; i < n; i++) {  
                res = max(res, (long long)h[i] * (R[i] - L[i]));  
           }  
           printf("%lld\n", res);  
      }  
 }  

LeetCode.1488 Avoid Flood in The City

1.Problem
https://leetcode.com/contest/weekly-contest-194/problems/avoid-flood-in-the-city/

2.Idea
set lower bound

3.Source

 class Solution {  
 public:  
      vector<int> avoidFlood(vector<int>& rains) {  
           int n = rains.size();  
           vector<int> emt, ans;  
           if (n == 0) return emt;  
           set<int> st;  
           map<int, int> mp;  
           ans.resize(n, -1);  
           for (int i = 0; i < n; i++) {  
                if (rains[i] == 0) {  
                     st.insert(i);  
                }  
                else {  
                     int cur = rains[i];  
                     if (mp.find(cur) == mp.end()) {  
                          mp[cur] = i;  
                     }  
                     else {  
                          if (st.size() == 0) return emt;  
                          set<int>::iterator it = st.lower_bound(mp[cur]);  
                          if (it == st.end()) return emt;  
                          else {  
                               ans[*it] = cur;  
                               st.erase(*it);  
                               mp[cur] = i;  
                          }  
                     }  
                }  
           }  
           for (int i = 0; i < n; i++) {  
                if (rains[i] > 0) ans[i] = -1;  
                else if (ans[i] == -1) ans[i] = 1;  
           }  
           return ans;  
      }  
 };  

POJ.3321 Apple Tree

1.Problme
http://poj.org/problem?id=3321

2.Idea
A good editorail using BIT.

3.Source

 const int MAX_N = 100009;  
 int table[MAX_N+1];  
 int BIT[MAX_N+1];  
 int tos[MAX_N+1];  
 int idx[MAX_N+1];  
 bool noApple[MAX_N+1];  
 vector<int> G[MAX_N+1];  
 int N, counter;  
 inline int readint(){  
   int ret = 0, x;  
   while(x=getchar(), !('0'<=x&&x<='9'));  
   ret = (x&15);  
   while(x=getchar(), '0'<=x&&x<='9') ret = (ret<<3) + (ret<<1) + (x&15);  
   return ret;  
 }  
 inline int sum(int n){int _R=0;for(;n;n-=n&-n)_R+=BIT[n];return _R;}  
 inline int sum(int from, int to){return sum(to-1)-sum(from-1);}  
 inline void add(int n, int x){for(;n<=N;n+=n&-n)BIT[n]+=x;}  
 inline void dfs(int v){  
      int gv = G[v].size();  
      table[v] = counter++;  
      for(int i=0; i<gv; i++){  
           if(!table[G[v][i]]) dfs(G[v][i]);  
      }  
      tos[table[v]] = counter;  
 }  
 int main(){  
      N = readint();  
      for(int i=0, x, y; i<N-1; i++){  
           x = readint(), y = readint();  
           G[x].push_back(y); G[y].push_back(x);  
      }  
      counter = 1;  
      dfs(1);  
      int M = readint();  
      for(int i=0, x; i<M; i++){  
           char op;  
           scanf(" %c ",&op);  
           x = table[readint()];  
           if(op=='Q'){  
                printf("%d\n", tos[x]-x-sum(x,tos[x]));  
           }  
           else{  
                noApple[x] = !noApple[x];  
                add(x,noApple[x]?1:-1);  
           }  
      }  
      return 0;  
 }  

LeetCode.1438 Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1.Problem
https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

2.Idea
MaxMinQueue + 2 Pointers method

3.Source

 class MaxMinQueue {  
 public:  
      MaxMinQueue() {}  
      bool empty() { return elements.empty(); }  
      int size() { return elements.size(); }  
      void push(int val) {  
           elements.push(val);  
           while (!maxElements.empty() && val > maxElements.back()) maxElements.pop_back();  
           maxElements.push_back(val);  
           while (!minElements.empty() && val < minElements.back()) minElements.pop_back();  
           minElements.push_back(val);  
      }  
      int pop() {  
           int val = elements.front();  
           elements.pop();  
           if (val == maxElements.front()) maxElements.pop_front();  
           if (val == minElements.front()) minElements.pop_front();  
           return val;  
      }  
      int peekMax() {  
           return maxElements.front();  
      }  
      int peekMin() {  
           return minElements.front();  
      }  
 private:  
      queue<int> elements;  
      deque<int> maxElements;  
      deque<int> minElements;  
 };  
 class Solution {  
 public:  
      MaxMinQueue q;  
      int longestSubarray(vector<int>& nums, int limit) {  
           int n = nums.size();  
           int ans = 0;  
           int p1 = 0;  
           while (p1 < n) {  
                q.push(nums[p1]);  
                while(q.size() > 0 && (q.peekMax() - q.peekMin() > limit)) {  
                     q.pop();  
                }  
                ans = max(ans, q.size());  
                p1++;  
           }  
           return ans;  
      }  
 };  
 int main()  
 {  
      Solution obj;  
      vector<int> in = { 8,2,4,7 };  
      obj.longestSubarray(in, 4);  
      return 0;  
 }  

LeetCode.5180 Constrained Subset Sum

1.Problem
https://leetcode.com/contest/weekly-contest-186/problems/constrained-subset-sum/

2.Idea
DP + maxQueue

3.Source

 class MaxQueue {  
 public:  
      MaxQueue() {}  
      bool empty() { return elements.empty(); }  
      int size() { return elements.size(); }  
      void push(int val) {  
           elements.push(val);  
           while (!maxElements.empty() && val > maxElements.back()) maxElements.pop_back();  
           maxElements.push_back(val);  
      }  
      int pop() {  
           int val = elements.front();  
           elements.pop();  
           if (val == maxElements.front()) maxElements.pop_front();  
           return val;  
      }  
      int peekMax() {  
           return maxElements.front();  
      }  
 private:  
      queue<int> elements;  
      deque<int> maxElements;  
 };  
 class Solution {  
 public:  
      int dp[100005];  
      int constrainedSubsetSum(vector<int>& nums, int k) {  
           int n = nums.size();  
           int ans = -1000000007;  
           MaxQueue mq;  
           memset(dp, 0, sizeof dp);  
           dp[0] = nums[0];  
           mq.push(nums[0]);  
           for (int i = 1; i<n; i++) {  
                dp[i] = max(nums[i], mq.peekMax() + nums[i]);  
                ans = max(ans, dp[i]);  
                mq.push(nums[i]);  
                if (mq.size() > k) mq.pop();  
           }  
           return ans;  
      }  
 };