team2012-D3-1B

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 === 0007 === 

rmq
{{{
int m;
scanf("%d", &m);
rmq.e[0] = 0;
rmq.init(n+1);
for (int i = 0; i < m; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    int z = rmq.index(l, r+1);
    if (rmq.e[z] >= l) printf("%d\n", num[z]);
    else printf("OK\n");
}
}}}

 === 0008 === 
 {{{
倒过来考虑：
设上一次在j购买战斗力，目前到达i，(i<j，i+1...j-1都不购买战斗力）
设，到达j时钱和战斗力分别为xj,yj，在购买战斗力并做完任务后
钱变成(xj/aj+yj)*bj，战斗力变成xj/aj+yj
在i时，设钱和战斗力分别为xi,yi，
如果不购买战斗力，到达j时，
yj0 = yi
xj0 = xi+yi*(bi+...+b[j-1])
如果购买战斗力
yj1 = yi+xi/ai
xj1 = (yi+xi/ai)*(bi+...+b[j-1])
如果购买，则要求：
xj1/aj+yj1 > xj0/aj+yj0
整理得bi+...+b[j-1]>ai-aj
}}}

 === 0009 === 

格雷码g(x)的反函数：
 {{{
inline long long rg(long long y) {
    long long x = 0;
    x = (y >> 33) << 33;
    for (int i = 32; i >= 0; --i) {
        long long x1 = (x >> (i+1)) & 0x1;
        long long xi = x1 ^ ((y >> i) & 0x1);
        x += xi << i;
    }
    return x;
}
}}}

枚举m1,s1，求m2,s2
{{{
long long xx = g(h1(m1, s1, f[i].x)), yy = f[i].y;
// yy = h2(xx)
if (xx < yy) {
    // yy = xx + s2
    if (s2 < 0) s2 = yy - xx;
    else if (s2 != yy - xx) { z = false; break; }
}
else {
    // yy = xx + s2 - m2
    if (d < 0) d = xx - yy;
    else if (d != xx - yy) { z = false; break; }
}
}}}

 === 0010 === 

分段处理，每段dp，矩阵乘法
矩阵的构造如下：
{{{
for (int i = 0; i < k; i++) {
    if (a[i] == 0) continue;
    if (a[i] == 1) mat[i][i] = 1;
    else { // a[i] == 2
        for (int j = i-1; j >= 0; j--) {
            if (a[j] == 0) break;
            if (a[j] == 2) {
                mat[i][j] = 1; break;
            }
        }
        for (int j = i+1; j < k; j++) {
            if (a[j] == 0) break;
            if (a[j] == 2) {
                mat[i][j] = 1; break;
            }
        }
    }
}
}}}

然后： matrix_binary_exp(k, mat, t);
    // ans *= mat

 === 0011 === 
 {{{
对每一条线段分别处理：
首先求出每一个矩形和该线段的交（用比例来表示）
    矩形的两条平行于x轴的边和线段有一个相交的部分，两条平行于y轴的边和线段有一个相交的部分
    再求交即可
然后把线段离散化排序，用一个set维护线段操作的顺序
}}}

 === 0012 === 
 {{{
最长上升子序列
dp时f[i]=max(1,f[j]+1), a[j]<a[i]
令t[j]为所有f[i]=k最小的a[k]
于是可以优化至O(nlogn)
}}}

0007

rmq

int m;
scanf("%d", &m);
rmq.e[0] = 0;
rmq.init(n+1);
for (int i = 0; i < m; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    int z = rmq.index(l, r+1);
    if (rmq.e[z] >= l) printf("%d\n", num[z]);
    else printf("OK\n");
}

0008

{{{

倒过来考虑：

设上一次在j购买战斗力，目前到达i，(i

设，到达j时钱和战斗力分别为xj,yj，在购买战斗力并做完任务后

钱变成(xj/aj+yj)*bj，战斗力变成xj/aj+yj

在i时，设钱和战斗力分别为xi,yi，

如果不购买战斗力，到达j时，

yj0 = yi

xj0 = xi+yi*(bi+...+b[j-1])

如果购买战斗力

yj1 = yi+xi/ai

xj1 = (yi+xi/ai)*(bi+...+b[j-1])

如果购买，则要求：

xj1/aj+yj1 > xj0/aj+yj0

整理得bi+...+b[j-1]>ai-aj

}}}

0009

格雷码g(x)的反函数：

{{{

inline long long rg(long long y) {

long long x = 0;

x = (y >> 33) << 33;

for (int i = 32; i >= 0; --i) {

long long x1 = (x >> (i+1)) & 0x1;

long long xi = x1 ^ ((y >> i) & 0x1);

x += xi << i;

}

return x;

}

}}}

枚举m1,s1，求m2,s2

long long xx = g(h1(m1, s1, f[i].x)), yy = f[i].y;
// yy = h2(xx)
if (xx < yy) {
    // yy = xx + s2
    if (s2 < 0) s2 = yy - xx;
    else if (s2 != yy - xx) { z = false; break; }
}
else {
    // yy = xx + s2 - m2
    if (d < 0) d = xx - yy;
    else if (d != xx - yy) { z = false; break; }
}

0010

分段处理，每段dp，矩阵乘法

矩阵的构造如下：

for (int i = 0; i < k; i++) {
    if (a[i] == 0) continue;
    if (a[i] == 1) mat[i][i] = 1;
    else { // a[i] == 2
        for (int j = i-1; j >= 0; j--) {
            if (a[j] == 0) break;
            if (a[j] == 2) {
                mat[i][j] = 1; break;
            }
        }
        for (int j = i+1; j < k; j++) {
            if (a[j] == 0) break;
            if (a[j] == 2) {
                mat[i][j] = 1; break;
            }
        }
    }
}

然后： matrix_binary_exp(k, mat, t);

// ans *= mat

0011

{{{

对每一条线段分别处理：

首先求出每一个矩形和该线段的交（用比例来表示）

矩形的两条平行于x轴的边和线段有一个相交的部分，两条平行于y轴的边和线段有一个相交的部分

再求交即可

然后把线段离散化排序，用一个set维护线段操作的顺序

}}}

0012

{{{

最长上升子序列

dp时f[i]=max(1,f[j]+1), a[j]

令t[j]为所有f[i]=k最小的a[k]

于是可以优化至O(nlogn)

}}}