某岛

… : "…アッカリ～ン . .. . " .. .
September 3, 2014

BIT

http://codeforces.com/gym/100460/problem/K

//}/* .................................................................................................................................. */

const int N = int(1e5) + 9;

VII A, B;
int a[N],b[N];
int n;

namespace BIT{
int C1[N], C2[N];
void Add(int C[], int x, int d){
for (;x<=n;x+=low_bit(x)) checkMin(C[x], d);
}
int Sum(int C[], int x){
int res = INF; for (;x;x^=low_bit(x)) checkMin(res, C[x]);
return res;
}

} using namespace BIT;

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

FLC(C1, C2, 0x3f);

int m; RD(n); REP(i, n) A.PB(MP(RD(), i));
REP(i, n) B.PB(MP(RD(), i));
SRT(A); SRT(B);
A.PB(MP(INF, INF)); B.PB(MP(INF, INF));

DWN(i, n, 0){
}

RD(m);
REP(i, m) RD(a[i]); REP(i, m) RD(b[i]);

// 1..n

REP(i, m){
int aa = Sum(C1, n-UBD(A, MP(a[i], INF))  );
int bb = Sum(C2, n-UBD(B, MP(b[i], INF))  );
//
//      cout << aa << " " << bb << endl;

if (aa == bb) puts("Draw");
else puts( aa < bb ? "Mike" : "Constantine");
}
}


Sparse Table

int ST[LV][N];

int rmq(int l, int r){
if (l > r) swap(l, r); ++r; int lv = lg2(r-l);
return min(ST[0][lv][l], ST[0][lv][r-(1<<lv)]);
}

for ( int lv = 1 ; (1 << lv) <= n ; lv ++ ){
for ( int i = 1 ; i + (1 << lv)  <= n + 1 ; i ++ ){
ST[lv][i] = min(ST[lv-1][i], ST[lv-1][i + (1<<(lv-1))]);
}
}


HDU 2888 – Check Corners （矩形。。
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1778847

        REP(xx, lg2(n)+1) REP(yy, lg2(m)+1) if (xx+yy){
REP(x, n-_1(xx)+1) REP(y, m-_1(yy)+1){
if (xx){
ST[xx][yy][x][y] = max(ST[xx-1][yy][x][y], ST[xx-1][yy][x+_1(xx-1)][y]);
}
else{
ST[xx][yy][x][y] = max(ST[xx][yy-1][x][y], ST[xx][yy-1][x][y+_1(yy-1)]);
}
}
}


POJ – 2019 Cornfields （正方形。。时空上降一个 log。。
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1778846

ZOJ – 3614 Choir （维护方差。。
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1778842