Codeforces Round #276

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