# 某岛

… : "…アッカリ～ン . .. . " .. .
November 7, 2014

## Problem A. Bits

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

O(nqrtn) 算法：

。。枚举 y。。。然后枚举 q。

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 D. Kindergarten

### Analysis:

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


## Problem E. Sign on Fence

### Brief description:

$$!\max_{l \leq i \leq r-w+1} \min_{i\leq j\leq i+w-1}h_i$$
（[l, r] 之间，长度为 w 的连续段里，最小值的最大值。。。）

### Analysis:

（根据 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{
T[x].upd(T[lx], T[rx]);
}
}
a = x, b = 1;
}
void Del(int x){
a = x, b = 0;
}
};

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