Orz 银川真的可惜了

Python可以过的我们纠结了半天
最后省不到一个小时理论AC了四节点的线段树求区间最值
最后还是崩了

铁头娃 铁头娃

不过很开心的是... 我脱单了(可能?)

也算是给两年多的ACM生涯画上了个带点遗憾的句号吧

是时候去搞点自己喜欢的东西了

补题 摸鱼 写博客
半年没怎么做题突然写起来线段树感觉真滴难受 QwQ

传送门:
SPOJ GSS3 - Can you answer these queries III

题意:
给定一组数据, 有多次操作:
  1.查询一段区间内最大的子段和.
  2.修改一个位置上的数据.

题解:
首先读完题可以发现是区间查询+单点更新的问题. 线段树模型, 之后思考要维护什么内容.
对于每一个区间, 我们可以维护区间的最大子段和, 但是当PushUp更新的时候发现合并时不好处理.
考虑以下情况, 当合并两个区间的最大子段和时,分为三种情况:
    1.最大子段和在左区间
    2.最大子段和在右区间
    3.最大子段和在中间部分

对于前两种状况, 我们可以直接取其中较大值即可, 对于第三种情况特殊考虑.
当最大子段和在两区间之间时, 必定会由左侧区间的后缀和右侧区间的前缀组成. 而想要使组成的子段和最大, 则必定是左侧区间的最大后缀和+右区间的最大前缀和.

最大子段和部分解决了, 现在来处理之前维护最大子段和用到的前缀和.
以前缀和举例, 当合并后最大前缀和有两种情况:
    1.最大前缀和都在左侧区间内.
    2.最大前缀和包括右侧区间的一部分.

当第一种情况时直接处理, 第二种情况时最大前缀和等于左侧区间的和+右侧区间的最大前缀和

至此, 我们就已经知道线段树所要维护的所有信息:
    1.区间和
    2.区间最大前缀和
    3.区间最大后缀和
    4.区间最大子段和

根据上文的思考, 我们就可以得出如何维护当前节点的信息:

// 更新区间和
T[cur].sum = T[cur << 1].sum + T[cur << 1 | 1].sum;
// 更新前缀和(左区间前缀 或者 右区间前缀+左区间和)
T[cur].per = max(T[cur << 1].per, T[cur << 1].sum + T[cur << 1 | 1].per);
// 更新后缀和(同理)
T[cur].suf = max(T[cur << 1 | 1].suf, T[cur << 1].suf + T[cur << 1 | 1].sum);
// 更新最大子段和 两种情况
// 1.单独在左右区间内
T[cur].con = max(T[cur << 1].con, T[cur << 1 | 1].con);
// 2.在合并的区间中(左区间后缀+右区间前缀)
T[cur].con = max(T[cur].con, T[cur << 1].suf + T[cur << 1 | 1].per);

单点更新就很好实现了, 和线段树板子就差不多了.

代码如下:

Accept C++14 (clang 4.0) 20ms:

/**
 * @author  Moe_Sakiya    sakiya@tun.moe
 * @date    2019-07-23 13:19:44
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

#define leftSon left,mid,cur<<1
#define rightSon mid+1,right,cur<<1|1

const int maxN = 50005;

struct Node
{
    int sum;            // 当前节点的区间和
    int per;            // 当前节点的最大前缀和(前子段和)
    int suf;            // 当前节点的最大后缀和(后子段和)
    int con;            // 当前节点的最大子段和
} T[maxN << 2];

int n, q;

// 向上更新
void PushUp(int cur) {
    // 更新区间和
    T[cur].sum = T[cur << 1].sum + T[cur << 1 | 1].sum;
    // 更新前缀和(左区间前缀 或者 右区间前缀+左区间和)
    T[cur].per = max(T[cur << 1].per, T[cur << 1].sum + T[cur << 1 | 1].per);
    // 更新后缀和(同理)
    T[cur].suf = max(T[cur << 1 | 1].suf, T[cur << 1].suf + T[cur << 1 | 1].sum);
    // 更新最大子段和 两种情况
    // 1.单独在左右区间内
    T[cur].con = max(T[cur << 1].con, T[cur << 1 | 1].con);
    // 2.在合并的区间中(左区间后缀+右区间前缀)
    T[cur].con = max(T[cur].con, T[cur << 1].suf + T[cur << 1 | 1].per);
    return;
}

// 建树
void BuildTree(int left, int right, int cur) {
    int mid = (left + right) >> 1;
    if (left == right) {
        scanf("%d", &T[cur].sum);
        T[cur].suf = T[cur].per = T[cur].con = T[cur].sum;
        return;
    }
    BuildTree(leftSon);
    BuildTree(rightSon);
    PushUp(cur);
    return;
}

// 修改
void UpdateNode(int node, int value, int left, int right, int cur) {
    int mid = (left + right) >> 1;
    if (left == right) {
        T[cur].suf = T[cur].per = T[cur].con = T[cur].sum = value;
        return;
    }
    if (node <= mid)
        UpdateNode(node, value, leftSon);
    else
        UpdateNode(node, value, rightSon);
    PushUp(cur);
    return;
}

// 查询
Node QuerySection(int leftSection, int rightSection, int left, int right, int cur) {
    int mid = (left + right) >> 1;
    // 当前节点完全在查询区间内
    if (leftSection <= left && right <= rightSection)
        return T[cur];
    // 当前节点不在查询区间内 向下递归
    if (mid < leftSection)
        return QuerySection(leftSection, rightSection, rightSon);
    else if (rightSection <= mid)
        return QuerySection(leftSection, rightSection, leftSon);
    // 当前节点部分在查询区域内 取左右子树合并求解(类似PushUp操作)
    Node retNode, leftNode, rightNode;
    leftNode = QuerySection(leftSection, rightSection, leftSon);
    rightNode = QuerySection(leftSection, rightSection, rightSon);
    // 合并区间结果
    retNode.sum = leftNode.sum + rightNode.sum;
    retNode.per = max(leftNode.per, leftNode.sum + rightNode.per);
    retNode.suf = max(rightNode.suf, leftNode.suf + rightNode.sum);
    retNode.con = max(leftNode.con, rightNode.con);
    retNode.con = max(retNode.con, leftNode.suf + rightNode.per);
    return retNode;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int cmd, l, r;
    scanf("%d", &n);
    BuildTree(1, n, 1);
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d %d %d", &cmd, &l, &r);
        switch (cmd) {
        case 0:
            UpdateNode(l, r, 1, n, 1);
            break;
        case 1:
            printf("%d\n", QuerySection(l, r, 1, n, 1).con);
            break;
        }
    }
    return 0;
}

补题
一道简单的数论公式题

题意:
给定一个区间, 求在这个区间[L, R]中因子最多的数, 并输出它和它的因子个数.

题解:
初见杀...
这道题用到了 算术基本定理(又称为正整数唯一分解定理) , 即对于一个大于1的自然数, 如果自身不是质数, 那么一定可以写为两个以上质数的积, 且从小到大排列后有唯一写法.
所以对于区间[L, R]中的所有数进行分解, 得到唯一表达式, 之后计算因子个数.
首先对于12, 总共有6个因子(1, 12, 2, 6, 3, 4), 它的唯一表达式是: 12 = 2 ^ 2 * 3 ^ 1.
对于24, 总共有8个因子(1, 24, 2, 12, 3, 8, 4, 6), 它的唯一表达式是: 24 = 2 ^ 3 * 3 ^ 1.
我们可以看出来规律, 将其唯一表达式出现的所有质因子的指数加上1, 之后取积, 就是其因子个数.

因子个数 = 所有质因子的指数 + 1 的积.

通过质数筛来加速运算.

Accept G++ 530ms:

/**
 * @author  Moe_Sakiya    sakiya@tun.moe
 * @date    2018-11-26 18:59:49
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

const int maxN = 50005;

long long int arrPrime[maxN];
bool isPrime[maxN];
int cnt;

void calPrimes() {
    memset(isPrime, 1, sizeof(isPrime));
    cnt = 0;
    isPrime[1] = false;
    for (long long int i = 2; i < maxN; i++) {
        if (isPrime[i] == true)
            arrPrime[cnt++] = i;
        for (int j = 0; j < cnt && i * arrPrime[j] < maxN; j++) {
            isPrime[i * arrPrime[j]] = false;
            if (i % arrPrime[j] == false)
                break;
        }
    }
    return;
}

long long int calNum(int n) {
    long long int ret = 1;
    int num;
    for (int i = 0; i < cnt; i++) {
        if (n % arrPrime[i] == 0) {
            num = 1;
            while (n % arrPrime[i] == 0 && n > 0) {
                num++;
                n /= arrPrime[i];
            }
            ret *= num;
        }
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    long long int maxNum, maxCount;
    int t, l, r;
    calPrimes();
    scanf("%d", &t);
    while (t--) {
        maxNum = 0;
        maxCount = 0;
        scanf("%d %d", &l, &r);
        for (int i = l; i <= r; i++) {
            long long int tmp = calNum(i);
            if (tmp > maxCount) {
                maxCount = tmp;
                maxNum = i;
            }
        }
        printf("Between %d and %d, %lld has a maximum of %lld divisors.\n", l, r, maxNum, maxCount);
    }
    return 0;
}

康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩.
而对于一个序列，其所有排列按照字典序排序的顺序从小到大编号, 康拓展开就是用于计算这种排列在其顺序中的位置.

举个栗子╰(°▽°)╯
对于序列{1,3,2}, 它的顺序位于其所有排列的第2位, 前一位为{1,2,3}.

其公式如下:

其中 T 为其排列的顺序, A_i 为序列中第 i 个元素, n 为序列总长度.

我们可以看到, 其中需要计算n!, 这一步可以通过打表来优化时间复杂度, 而当n!过大的时候, 就需要大整数计算了.

康托展开的逆运算

因为康托展开是一个双射, 那么一个合法的 T 值必定对应一个唯一的序列, 也就是说可以反向计算顺序为 T 的序列.

1.输入n, T
2.计算第i位对应的值(i从1开始):
    a)将T-1，意为前面有T-1个排列
    b)currI = T/(n-i)!, currI即为当前位数
    c)如果currI已经被使用过,那么currI++
    d)currM = T%(n-i)!, currM为剩下的数
    e)T = currM
3.输出所有的currI

那么直接来道题叭:CodeVS 2972 - 选课

但是这道题...数据并不是很强...只有三个监测点

资料参考 Joseph Galante:Generalized Cantor Expansions

啊哈 我Sakiya又回来了
惊不惊喜 意不意外 (/≧▽≦)/

这是一道简单的 DFS序+线段树区间 更新问题...

题意:
对于一个公司内的员工, 每个员工有且只有一个直系上司, 而一个上司可以有许多的员工, 当给这个上司分配任务的时候, 他也会将该任务分配给所有下属(如果再次被分配将会覆盖掉之前的任务), 对于这样的结构进行两种操作

• 给员工分配任务
• 查询该员工正在进行的任务

题解:
首先我们考虑如何去表示子树的状态
通过DFS序, 前序遍历题目给出的树, 并对于每个节点的入栈出栈时间做记录, 便可以得到对于父节点的所有子节点信息的一条线段, 这样的话查询当前父节点(线段的左端点)即可得知该员工执行的任务. 这样就将一个子树问题转换成了区间问题.
之后我们考虑分配任务的情况
通过线段树的区间更新, 来对当前节点(线段)下的所有节点更新赋值, 使用LazyTag思想优化时间复杂度.

Accept G++ 202ms 4992kB:

/**
 * @author  Moe_Sakiya    sakiya@tun.moe
 * @date    2018-11-14 18:46:28
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

#define leftSon left,mid,curr<<1
#define rightSon mid+1,right,curr<<1|1

using namespace std;

const int maxN = 50005;
struct DisNode
{
    int l, r;
} disArr[maxN];
vector<int> vet[maxN];
int segTree[maxN << 2];
int lazyTag[maxN << 2];
int fatherArr[maxN];
int discnt;

inline void DFS(int id) {
    disArr[id].l = discnt++;
    for (int i = 0; i < (int)vet[id].size(); i++)
        DFS(vet[id][i]);
    disArr[id].r = discnt - 1;
    return;
}

void pushDown(int curr) {
    if (lazyTag[curr] != -1) {
        lazyTag[curr << 1] = lazyTag[curr];
        lazyTag[curr << 1 | 1] = lazyTag[curr];
        segTree[curr << 1] = lazyTag[curr];
        segTree[curr << 1 | 1] = lazyTag[curr];
        lazyTag[curr] = -1;
    }
    return;
}

void buildTree(int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (left == right) {
        segTree[curr] = -1;
        return;
    }
    buildTree(leftSon);
    buildTree(rightSon);
    return;
}

void updateSection(int leftSection, int rightSection, int val, int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (leftSection <= left && right <= rightSection) {
        lazyTag[curr] = val;
        return;
    }
    pushDown(curr);
    if (leftSection <= mid)
        updateSection(leftSection, rightSection, val, leftSon);
    if (rightSection > mid)
        updateSection(leftSection, rightSection, val, rightSon);
    return;
}

int queryNode(int node, int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (left == right) {
        if (lazyTag[curr] != -1)
            segTree[curr] = lazyTag[curr];
        return segTree[curr];
    }
    pushDown(curr);
    if (node <= mid)
        return queryNode(node, leftSon);
    else
        return queryNode(node, rightSon);
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t, n, m, arg0, arg1, u, v;
    char ch[10];
    scanf("%d", &t);
    for (int kase = 1; kase <= t; kase++) {
        // INIT
        discnt = 1;
        memset(fatherArr, 0, sizeof(fatherArr));
        memset(vet, 0, sizeof(vet));
        memset(lazyTag, -1, sizeof(lazyTag));
        // DataIn
        printf("Case #%d:\n", kase);
        scanf("%d", &n);
        for (int i = 0; i < n - 1; i++) {
            scanf("%d %d", &u, &v);
            fatherArr[u] = v;
            vet[v].push_back(u);
        }
        // Deal data & Build tree
        for (int i = 1; i <= n; i++)
            if (fatherArr[i] == 0)
                DFS(i);
        buildTree(1, n, 1);
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            // Query
            scanf("%s", ch);
            switch (ch[0]) {
            case 'C':
                scanf("%d", &arg0);
                printf("%d\n", queryNode(disArr[arg0].l, 1, n, 1));
                break;
            case 'T':
                scanf("%d %d", &arg0, &arg1);
                updateSection(disArr[arg0].l, disArr[arg0].r, arg1, 1, n, 1);
                break;
            }
        }
    }
    return 0;
}