莫队算法学习笔记

2017年12月28日

我相信莫队本人应该没有想到他的莫队算法不仅可以做到支持修改而且还可以上树甚至在树上都可以支持修改吧（笑。

传统的莫队是将询问储存为询问的左端点和右端点，然后对序列以 n \sqrt n 为长度分块，以左端点所在块为第一关键字，右端点为第二关键字排序然后暴力，这样的做法的时间复杂度是 O(nn) O(n \sqrt n) 即 O(n32) O(n ^ {\frac 3 2}) 的。

反正就是个排序再暴力有啥子好讲的，复杂度证明这种事管他呢（其实不带修改的莫队我还是可以证一下的。

好啦以上是复习！

如果需要支持单点修改该怎么办呢？

解决方案是，对于每一个询问，不仅记录询问的区间端点，而且记录下在它之前离它最近的修改操作。对于每一个修改操作，记录下它修改的位置，以及修改前后的值。

就像这样。

struct Query {
    int l, r;
    Change *x;
    int *ans;
} querys[N + 1], *queryEnd;
struct Change {
    int pos, newVal, oldVal;
} changes[N + 1], *changeEnd;

以 n23 n ^ {\frac 2 3} 为大小分块，排序时按照左端点所在块为第一关键字，右端点所在块为第二关键字，离它最近的修改操作的位置为第三关键字排序，然后暴力。

处理修改操作时维护一个指针，每次记录此次操作之后修改指针停留的位置，对于某个询问，如果当前修改指针在离它最近的指针之前，就正着改过去，如果在之后，就倒着改回去。正确性显然。记得处理能影响到当前区间的位置就好了。

这样做的时间复杂度被证明是 O(n53) O(n ^ {\frac 5 3}) 的。

这里是带修改莫队的一道例题，Uva12345的代码。（此题同 BZOJ2120，BZOJ2453.

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
const int N = 50000;
const int MAX = 1000000;
struct Query;
struct Change;
struct Query {
    int l, r;
    Change *x;
    int *ans;
} querys[N + 1], *queryEnd;
struct Change {
    int pos, newVal, oldVal;
} changes[N + 1], *changeEnd;
int n, m;
int block[N + 1], last[N + 1];
int res, ans[N + 1];
bool affected[N + 1];
int buc[MAX + 1], a[N + 1];
int l, r;
Change *now;
int blockSize;
inline bool comp(const Query &x, const Query &y) {
    return block[x.l] < block[y.l] ||
           block[x.l] == block[y.l] && block[x.r] < block[y.r] ||
           block[x.l] == block[y.l] && block[x.r] == block[y.r] && x.x < y.x;
}
inline void update(int pos) {
    if (affected[pos]) {
        if (!--buc[a[pos]]) res--;
    } else {
        if (!buc[a[pos]]++) res++;
    }
    affected[pos] ^= 1;
}
inline void modify(int pos, int val) {
    if (affected[pos]) {
        update(pos);
        a[pos] = val;
        update(pos);
    } else a[pos] = val;
}
int main() {
    queryEnd = querys;
    changeEnd = changes;
    scanf("%d %d", &n, &m);
    blockSize = 1500;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        block[i] = i / blockSize;
        last[i] = a[i];
    }
    for (int i = 1; i <= m; i++) {
        char s[10];
        int x, y;
        scanf("%s %d %d", s, &x, &y);
        if (s[0] == 'Q') {
            x++;
            queryEnd++;
            queryEnd->l = x;
            queryEnd->r = y;
            queryEnd->x = changeEnd;
            queryEnd->ans = &ans[queryEnd - querys];
        } else {
            x++;
            changeEnd++;
            changeEnd->pos = x;
            changeEnd->newVal = y;
            changeEnd->oldVal = last[x];
            last[x] = y;
        }
    }
    std::sort(querys + 1, queryEnd + 1, comp);
    l = 1;
    r = 0;
    now = changes;
    for (Query *v = querys + 1; v != queryEnd + 1; v++) {
        if (now == v->x) {}
        else if (now < v->x) {
            for (Change *p = now + 1; p != v->x + 1; p++) modify(p->pos, p->newVal);
        } else {
            for (Change *p = now; p != v->x + 1 - 1; p--) modify(p->pos, p->oldVal);
        }
        if (l == v->l) {}
        if (l < v->l) for (int i = l; i <= v->l - 1; i++) update(i);
        else for (int i = v->l; i <= l - 1; i++) update(i);
        if (r == v->r) {}
        if (r < v->r) for (int i = r + 1; i <= v->r; i++) update(i);
        else for (int i = v->r + 1; i <= r; i++) update(i);
        l = v->l;
        r = v->r;
        now = v->x;
        *v->ans = res;
    }
    for (int i = 1; i <= queryEnd - querys; i++) printf("%d\n", ans[i]);
    return 0;
}

「NOIP2017」宝藏 - 状压

2017年12月12日

参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 nn 个深埋在地下的宝藏屋，也给出了这 nn 个宝藏屋之间可供开发的 mm 条道路和它们的长度。

小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。

小明的决心感动了考古挖掘的赞助商， 赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。

在此基础上， 小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。

新开发一条道路的代价是：

这条道路的长度 ×\times 从赞助商帮你打通的宝藏屋到这条道路起点的宝]藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代价最小，并输出这个最小值。

Read more..

「JSOI2008」生日聚会 - DP

2017年11月6日

现有 n n 个男生 m m 个女生要坐成一排，需要满足对于任意连续的一段，不存在男女数量之差大于 k k 的情况，其中 n,m,k n, m, k 由输入数据给定。

Read more..

「JSOI2007」建筑抢修 - 贪心，堆

2017年7月14日

小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T部落消灭了所有Z部落的入侵者。但是T部落的基地里已经有 N N 个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。

Read more..

「JSOI2007」麻将

2017年7月7日

麻将是中国传统的娱乐工具之一。麻将牌的牌可以分为字牌（共有东、南、西、北、中、发、白七种）和序数牌（分为条子、饼子、万子三种花色，每种花色各有一到九的九种牌），每种牌各四张。在麻将中，通常情况下一组和了的牌（即完成的牌）由十四张牌组成。十四张牌中的两张组成对子（即完全相同的两张牌），剩余的十二张组成三张一组的四组，每一组须为顺子（即同花色且序数相连的序数牌，例如条子的三、四、五）或者是刻子（即完全相同的三张牌）。一组听牌的牌是指一组十三张牌，且再加上某一张牌就可以组成和牌。那一张加上的牌可以称为等待牌。在这里，我们考虑一种特殊的麻将。在这种特殊的麻将里，没有字牌，花色也只有一种。但是，序数不被限制在一到九的范围内，而是在 1 1 到 n n 的范围内。同时，也没有每一种牌四张的限制。一组和了的牌由 3m+2 3m + 2 张牌组成，其中两张组成对子，其余 3m 3m 张组成三张一组的 m m 组，每组须为顺子或刻子。现给出一组 3m+1 3m + 1 张的牌，要求判断该组牌是否为听牌（即还差一张就可以和牌）。如果是的话，输出所有可能的等待牌。

Read more..

「JSOI2007」合金 - 计算几何，Floyd

2017年7月5日

某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。 现在，用户给出了 n n 种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。

Read more..