## Problem A. Bits

找到 [l, r] 之間 count_bits() 最多的數。。。

首先 ans = l。。。然後迭代。。。每次把最低位的 0 補成 1。。。

後者可以通過 l |= l+1 實現。。

for i in range(int(input())): l,r=map(int,input().split()) while(l|(l+1)<=r): l|=l+1 print(l)

## Problem B. Maximum Value

給定一堆數。

問最大的 x%y 的值。。要求 x>=y。。

O(nqrtn) 演算法：

我們有：x＝qy＋r

。。枚舉 y。。。然後枚舉 q。

然後每次找到小於 qy 的最大的數即可。

const int N = int(2e6) + 9; int a[N]; int n; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif REP_C(i, RD(n)){ int ai; RD(ai); a[ai] = ai; } FOR(i, 1, N) checkMax(a[i], a[i-1]); // x = qy + r int z = 0; FOR(y, 1, N) if (a[y] == y){ for (int qy=y;qy+y-1<N;qy+=y) checkMax(z, a[qy+y-1]-qy); } OT(z); }

O(n) 演算法：

通過類似篩法，得到每個數的最大約數。

用這個可以幹嘛？

const int N = int(1e6) + 9; int a[N]; int n; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif REP_C(i, RD(n)){ int ai; RD(ai); a[ai] = ai; } int z = 0, t = 1; REP(i, N) if (a[i]){ checkMax(t, i); while (t<N && t<i+a[i]){ //cout << t << " "<< i << endl; if (a[t] == t) checkMax(z, t-i); ++t; } if (i+a[i]<N) checkMax(a[i+a[i]], a[i]); } OT(z); }

## Problem C. Strange Sorting

## Problem D. Kindergarten

### Brief description:

給定一個數組 A[]，按順序分成一些連續的組，每組的貢獻是組中最大的數與最小數的絕對值。

求一種分組方案，使得所有組的貢獻的和最大。

### Analysis:

由於最大、最小的數一定是處在組的端點。。。

所以不難寫出如下 DP：

REP_1(i, n){ REP_1(j, i-1){ checkMax(dp[i], dp[j-1] + abs(A[i] - A[j])); } }

然後把絕對值拆開。。

用兩個樹狀數組記錄一下就行了 http://codeforces.com/contest/484/submission/8596652

複雜度 $$O(nlogn)$$。。。

看了官方 題解 才發現應該用 $$O(n)$$ 的做法。。。

因為每組的數一定是單調的。。。

因此潛在的轉移位置只有 3 個。。。（Paying attention to the interesting points in sequence which making local maximums (i. e. ai - 1 < ai > ai + 1), local minimums (ai - 1 > ai < ai + 1), and point adjacent to them。） 記錄一下就行了。。。

## Problem E. Sign on Fence

### Brief description:

給定長度為 n 的數組 $h_i$。。

每次回答詢問：` l, r, w `

。。表示求：

$$!\max_{l \leq i \leq r-w+1} \min_{i\leq j\leq i+w-1}h_i$$

（[l, r] 之間，長度為 w 的連續段里，最小值的最大值。。。）

### Analysis:

先寫一個支持區間求最大測度的線段樹。。。

然後 cdq 分治。。同 BZOJ 2527. [Poi2011]Meteors

（根據 Swistakk 的留言。。原來這種方法更合適的名字是 “parallel binary search”。）

http://codeforces.com/contest/484/submission/8596944

//}/* .................................................................................................................................. */ const int N = int(3e5) + 9; int A[N], ans[N]; int n; VI P; struct rec{ int ll, rr, mx; bool full; void reset(int t){ ll = rr = mx = t; full = t; } void upd(const rec l, const rec r){ full = l.full && r.full; mx = max(l.mx, r.mx, l.rr + r.ll); ll = max(l.ll, l.full ? l.ll + r.ll : 0); rr = max(r.rr, r.full ? r.rr + l.rr : 0); } }; namespace ST{ #define lx (x << 1) #define rx (lx | 1) #define ml (l+r>>1) #define mr (ml+1) #define lc lx,l,ml #define rc rx,mr,r #define rt 1,1,n rec T[4*N]; int a, b; rec Q(int x, int l, int r){ if (b < l || r < a) return rec(); if (a <= l && r <= b){ return T[x]; } else{ rec ll = Q(lc), rr = Q(rc); rec zz; zz.upd(ll, rr); return zz; } } int Q(int _a, int _b){ a = _a, b = _b; return Q(rt).mx; } void Add(int x, int l, int r){ if (l == r){ T[x].reset(b); } else{ if (a < mr) Add(lc); else Add(rc); T[x].upd(T[lx], T[rx]); } } void Add(int x){ a = x, b = 1; Add(rt); } void Del(int x){ a = x, b = 0; Add(rt); } }; struct Query{ int l, r, w; void in(){ RD(l,r,w); } bool ok(){ return ST::Q(l,r) >= w; } } Q[N]; VI op[N]; void cdq(const VI I, int l, int r){ if (l + 1 == r){ ECH(i, I) ans[*i] = l; } else{ int m = l + r >> 1; FOR(i, l, m) ECH(it, op[i]) ST::Add(*it); VI Il, Ir; ECH(i, I){ if (Q[*i].ok()){ Il.PB(*i); } else{ Ir.PB(*i); } } cdq(Ir, m, r); FOR(i, l, m) ECH(it, op[i]) ST::Del(*it); cdq(Il, l, m); } } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif REP_1_C(i, RD(n)) P.PB(RD(A[i])); UNQ(P); REP_1(i, n) op[P.size()-LBD(P, A[i])-1].PB(i); int m; VI I; REP_1_C(i, RD(m)) Q[i].in(), I.PB(i); cdq(I, 0, P.size()); REP_1(i, m) OT(P[P.size()-ans[i]-1]); }