A – 漆黑列车载运数个谎言

这道题应该是并查集域的裸题，不讲。

// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200;
int n, m, fa[MAX_N << 2];
int find(int x) { return fa[x] == x ? fa[x] : fa[x] = find(fa[x]); }
void unite(int x, int y) { fa[find(x)] = fa[find(y)]; }
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= 2 * n; i++)
        fa[i] = i;
    while (m--)
    {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0)
            unite(x, y), unite(x + n, y + n);
        else if (opt == 1 || opt == 2)
            unite(x, y + n), unite(x + n, y);
        else if (find(x) == find(y) || find(x + n) == find(y + n))
            puts("1");
        else
            puts("0");
    }
    return 0;
}

B – 神在夏至祭降下了神谕

傻逼都知道这道题的方程为：

\[ f[i] = \sum_{[i,j] \in validSet} f[j] \]

然而这样枚举是\(O(n^2)\)的，非常垃圾的复杂度。我们可以用树状数组来搞定这个转移，这样的话复杂度就是\(O(n log n)\)的。首先，绝对差的表达式是\(|numOfSummer – numOfWinter|\)。我们可以考虑求个前缀和，把每一个夏人的贡献设为\(1\)，冬人的贡献设为\(-1\)，所以方程中要求的\(f[j]\)集其实就是在区间\([-k,k]\)中，然后多加一个人就相当于把整个区间向右\左平移了，所以真正的区间就是\([sum[i]-k,sum[i]+k]\)，然后计算完毕之后直接往树状数组的\(sum[i]\)处把\(f[i]\)塞进去即可。

// B.cpp
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define ll long long
using namespace std;
const int MAX_N = 2e5 + 2000, mod = 1e9 + 7;
ll tree[MAX_N << 2], f[MAX_N], n, prefix[MAX_N], tmpx, k;
// the number domain still exists;
void add(int x, ll d)
{
    x += MAX_N;
    while (x <= 2 * MAX_N)
        tree[x] += d, x += lowbit(x);
}
ll sum(int x)
{
    x += MAX_N;
    ll ans = 0;
    while (x)
        ans += tree[x], x -= lowbit(x);
    return ans;
}
int main()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &tmpx), prefix[i] = prefix[i - 1] + ((tmpx == 1) ? 1 : -1);
    add(0, 1);
    for (int i = 1; i <= n; i++)
        f[i] = (sum(prefix[i] + k) - sum(prefix[i] - k - 1) + mod) % mod, add(prefix[i], f[i]);
    printf("%lld", f[n]);
    return 0;
}

C – 被粉碎的线段树

先有一个结论：

区间定位个数（答案） = 2 * 区间长度 – 完全被该区间包含的节点个数。——题解

所以，我们只需要搞定后面那个被完全包含的节点个数统计即可。从数学上讲，我们要统计区间\([l’,r’],l’\geq l, r’ \leq r\)的个数。明显的，这他妈就是一个二维偏序问题。所以，题目结束。

// C.cpp
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) (x & -x)
#define pr pair<int, int>
using namespace std;
const int MAX_N = 1e5 + 2000;
int n, m, tmpx, tmpy1, tot, tree[MAX_N << 2];
pr nodes[MAX_N << 2];
struct query
{
    int l, r, ans, id;
    bool operator<(const query &q) const { return id < q.id; }
} queries[MAX_N];
bool cmp(pr a, pr b) { return a.second < b.second; }
bool cmp2(query a, query b) { return a.r < b.r; }
void init(int l, int r)
{
    if (l == r)
    {
        nodes[++tot].first = l, nodes[tot].second = r;
        return;
    }
    nodes[++tot].first = l, nodes[tot].second = r;
    int mid;
    scanf("%d", &mid);
    init(l, mid), init(mid + 1, r);
}
void add(int x, int d)
{
    while (x <= n)
        tree[x] += d, x += lowbit(x);
}
ll sum(int x)
{
    ll ans = 0;
    while (x)
        ans += tree[x], x -= lowbit(x);
    return ans;
}
int main()
{
    scanf("%d%d", &n, &m);
    init(1, n);
    sort(nodes + 1, nodes + 1 + tot, cmp);
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &queries[i].l, &queries[i].r), queries[i].id = i;
    sort(queries + 1, queries + 1 + m, cmp2);
    int cur = 1;
    for (int i = 1; i <= m; i++)
    {
        int xlimit = queries[i].r;
        while (nodes[cur].second <= xlimit && cur <= tot)
            add(nodes[cur].first, 1), cur++;
        queries[i].ans = sum(queries[i].r) - sum(queries[i].l - 1);
    }
    sort(queries + 1, queries + 1 + m);
    for (int i = 1; i <= m; i++)
        printf("%lld\n", 2 * (queries[i].r - queries[i].l + 1) - queries[i].ans);
    return 0;
}