2024 年 8 月做题记录

为了防止版权纠纷，部分内容已修改或匿名化。

0818A

大意是给你一个数组，然后每次查询给区间加上/减去一个固定数值（保证修改后数组严格单调递增），查询是否包含一个下标等于值的数（即 a_i = i）。

然后发现 a_i – i 也是单调的，然后可以打懒标记（我用的线段树）然后二分。

struct Sg {
    struct { int lz, val; } tr[MAXN * 4];
    void build(int l, int r, int p = 1);
    inline void pushdown(int p);
    void upd(int l, int r, int val, int p = 1, int sl = 1, int sr = -1);
    int query(int x, int p = 1, int sl = 1, int sr = -1);
} sg;

vector<int> rd;

struct myLess {
    bool operator()(const int& idx, const int& val) const {
        return sg.query(idx) - idx < val;
    }
};

inline void query()
{
    int res = *lower_bound(rd.begin(), rd.end(), 0, myLess {});
    if (sg.query(res) != res) cout << "NO\n";
    else cout << "YES\n";
}

int main()
{
    ioin();
    cin >> k >> n;
    k--;
    rd.reserve(n);
    for (int i = 1; i <= n; i++) {
        cin >> dat[i];
        rd.push_back(i);
    }
    sg.build(1, n);
    query();
    while (k--) {
        int l, r, df;
        cin >> l >> r >> df;
        sg.upd(l, r, df);
        query();
    }
}

0818B

要求写一个查询区间内出现次数为奇数的数的个数的一个结构。

赛时随便糊了一个 bitset 上去然后发现时限开 2 秒就能冲过去。

int n, q, cnt, tp, l, r;

bitset<100> pf[100001]; // 60pts
map<int, int> mp;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> tp;
        pf[i] = pf[i - 1];
        const int id = mp.count(tp) ? mp[tp] : mp[tp] = cnt++;
        pf[i][id] = pf[i][id] ^ 1;
    }
    cin >> q;
    while (q--) {
        cin >> l >> r;
        cout << (pf[r] ^ pf[l - 1]).count() << '\n';
    }
}

但不幸的是时限只有 1 秒。

然后改题的时候看见题解写得非常简略。看了 std 之后发现是莫队。于是把询问离线下来然后莫队搞一下。

然后顺便把莫队一直没看懂的时间复杂度证明搞懂了。

map<int, int> ls;
int dat[100005], lscnt;

struct Query {
    int l, r, id, ans;
    bool operator<(const Query& rhs) const {
        int ll = l / 400, rr = rhs.l / 400;
        return ll == rr ? r < rhs.r : ll < rr;
    }
} qr[100005];
int res, cnt[100005];
inline void add(int x) { cnt[dat[x]]++; cnt[dat[x]] & 1 ? res++ : res--; }
inline void del(int x) { cnt[dat[x]] & 1 ? res-- : res++; cnt[dat[x]]--; }

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> dat[i];
        dat[i] = ls.count(dat[i]) ? ls[dat[i]] : ls[dat[i]] = lscnt++;
    }

    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> qr[i].l >> qr[i].r;
        qr[i].id = i;
    }
    sort(qr + 1, qr + 1 + q);
    int l = 1, r = 0;
    for (int i = 1; i <= q; i++) {
        while (r < qr[i].r) add(++r);
        while (r > qr[i].r) del(r--);
        while (l > qr[i].l) add(--l);
        while (l < qr[i].l) del(l++);
        qr[i].ans = res;
    }
    sort(qr + 1, qr + q + 1, [](auto l, auto r) {
        return l.id < r.id;
    });
    for (int i = 1; i <= q; i++) cout << qr[i].ans << '\n';
}

[清华集训2012] 序列操作

Luogu

题意：

实现一个数据结构

1. 区间加
2. 区间变成相反数
3. 询问区间中选择 x\space (x \le 20) 个数相乘的所有方案的和对 19940417 取模的值。

n, q \le 50000，值域 1e9。

这个题一开始看上去很没有头绪。试着往数据结构方向去想，但是要维护的东西是完全没思路。

然后发现 x 的范围很小，所以尝试往这方面思考：可以尝试用线段树把所有 0~20 的答案维护下来。那么现在需要解决几个问题。

• 第一：初始状态。很简单，f_0 = 1, f_1 = a_i。
• 第二：如何合并区间。假如说我们要处理 f_i 的答案，就相当于在 i 个数字中间和两边加一个隔板，左右相乘并求和。形式化地，记 fl, fr 分别为左右子树的 f，有
  f_x = \sum_{i=0}^{x} fl_i \times fr_{x – i}
  。可以证明两边区间的贡献是可以被乘起来的。
• 第三：取反操作。因为负负得正，所以只需要将选取奇数个数字乘起来的值取相反数即可。形式化地，f_x = (-1)^xf_x。
• 第四：区间加操作。这个可以找个规律，参见 题解 P4247 【[清华集训2012]序列操作】 by Limit，然后拆一下贡献。

然后就只需要实现了。

const int MODN = 19940417;
const int MAXN = 50006;
int C[MAXN][21];
int arr[MAXN];

struct Sgt;

struct Sgt {    
    struct Data { int len; array<i64, 21> f; Data() { len = -1; } };
    struct Lazy { i64 add; int rev; Lazy() { add = rev = 0; } typedef void(*Updater)(Data&, Lazy&, i64); };
    struct Node { int l, r; Data dat; Lazy lz; } tr[MAXN * 4];
    static inline Data merge(const Data& lhs, const Data& rhs) {
        Data result; fill(result.f.begin(), result.f.end(), 0);
        result.len = lhs.len + rhs.len;
        const int limit = min(result.len, 20);
        for (int i = 0; i <= limit; i++) {
            for (int j = 0; j <= limit; j++) {
                if (i + j <= 20) (result.f[i + j] += lhs.f[i] * rhs.f[j] % MODN) %= MODN;
            }
        }
        return result;
    }
    static inline void updlz_add(Data& dat, Lazy& lz, i64 delta) {
        for (int i = min(dat.len, 20); i > 0; i--) {
            i64 tp = delta;
            for (int j = i - 1; j >= 0; j--) {
                ((dat.f[i] += dat.f[j] * C[dat.len - j][i - j] % MODN * tp % MODN) += MODN) %= MODN;
                (tp *= delta) %= MODN;
            }
        }
        (lz.add += delta) %= MODN;
    }
    static inline void updlz_rev(Data& dat, Lazy& lz, i64 val = 0) {
        for (int i = 0; i <= min(dat.len, 20); i++) { if (i & 1) dat.f[i] = ((-dat.f[i]) % MODN + MODN) % MODN; }
        lz.rev ^= 1; lz.add = (-lz.add % MODN + MODN) % MODN;
    }

    inline void pushdown(int p) {
        if (tr[p].lz.rev) {
            updlz_rev(tr[p << 1].dat, tr[p << 1].lz), updlz_rev(tr[p << 1 | 1].dat, tr[p << 1 | 1].lz);
            tr[p].lz.rev = 0;
        }
        if (tr[p].lz.add) {
            updlz_add(tr[p << 1].dat, tr[p << 1].lz, tr[p].lz.add), updlz_add(tr[p << 1 | 1].dat, tr[p << 1 | 1].lz, tr[p].lz.add);
            tr[p].lz.add = 0;
        }
    }

    template<Lazy::Updater updlz> void update(int l, int r, i64 val, int p = 1) {
        if (tr[p].l > r || tr[p].r < l) return;
        if (l <= tr[p].l && tr[p].r <= r) { updlz(tr[p].dat, tr[p].lz, val); return; }
        pushdown(p);
        update<updlz>(l, r, val, p << 1), update<updlz>(l, r, val, p << 1 | 1);
        tr[p].dat = merge(tr[p << 1].dat, tr[p << 1 | 1].dat);
    }

    Data query(int l, int r, int p = 1) {
        if (l <= tr[p].l && tr[p].r <= r) return tr[p].dat;
        pushdown(p);
        int mid = (tr[p].l + tr[p].r) >> 1;
        if (r <= mid) return query(l, r, p << 1); // [l, r] ...mid
        if (l >= mid + 1) return query(l, r, p << 1 | 1); // mid... [l, r]
        // l...mid...r
        return merge(query(l, r, p << 1), query(l, r, p << 1 | 1));
    }

    void build(int l, int r, int p = 1) {
        tr[p].l = l, tr[p].r = r;
        if (l == r) {
            tr[p].dat.len = 1; tr[p].dat.f[0] = 1;
            tr[p].dat.f[1] = arr[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, p << 1); build(mid + 1, r, p << 1 | 1);
        tr[p].dat = merge(tr[p << 1].dat, tr[p << 1 | 1].dat);
    }
} sg;

signed main()
{
    C[0][0] = 1;
    for (int i = 1; i <= 50000; i++) {
        for (int j = 0; j <= min(i, 20); j++) {
            C[i][j] += C[i - 1][j];
            if (j - 1 >= 0) C[i][j] += C[i - 1][j - 1];
            C[i][j] %= MODN;
        }
    }
    // 节约篇幅，不贴更多了
}

[SCOI2016] 萌萌哒

Luogu

题意：

告诉你一些限制条件，每个条件表示为四个数，l_1,r_1,l_2,r_2，即两个长度相同的区间，表示子串 S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1} 与 S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2} 完全相同。然后统计长度为 n 且满足这些约束条件的数字有多少个。

题解有人说暴力并查集做法是普及组的水平，但是我想了很久才想到，所以我的水平是普及——-。

30pts 的暴力：

int fa[10005];
int findfa(int x) { return fa[x] == x ? x : fa[x] = findfa(fa[x]); }
inline bool check(int x, int y) { return findfa(x) == findfa(y); }
inline void merge(int x, int y) { check(x, y) || (fa[findfa(x)] = findfa(y)); }
inline void init(int x) { for (int i = 1; i <= x; i++) fa[i] = i; }
char vis[10005];
const int MODN = 1e9 + 7;

int main()
{
    int n, m;
    cin >> n >> m;
    init(n);
    for (int i = 1; i <= m; i++) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        for (int j = l1; j <= r1; j++) {
            merge(j, j - l1 + l2);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[findfa(i)]) ans += vis[fa[i]] = 1;
    }
    cout << 9ll * powmod(10, ans - 1) % MODN << '\n';
}

发现时间瓶颈在 每一个区间都要暴力连边。于是想，如果可以区间连区间就好了！于是注意力惊人的你注意到了 并查集的合并是一个可重复贡献的过程。然后你就想到了 ST 表，真是令人感到惊叹的注意力。

现在需要解决两个问题。

1. 怎样区间连接区间？写一个看上去有点像二进制拆分的东西，但是我好像说不清楚，所以直接看代码。
2. 怎样统计答案？只需要把这个区间的合并的信息传到下一个区间就可以了，可以理解成一个倍增的逆过程。具体见代码。

int main()
{
    int n, m;
    cin >> n >> m;
    init(n);
    const int top = floor(log2(n));
    for (int i = 1; i <= m; i++) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        for (int k = top; k >= 0; k--)
            if (l1 + (1 << k) - 1 <= r1) {
                merge(l1, l2, k);
                l1 += 1 << k;
                l2 += 1 << k;
            }
    }
    for (int k = top; k; k--)
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            int pos = findfa(i, k);
            merge(i, pos, k - 1);
            merge(i + (1 << (k - 1)), pos + (1 << (k - 1)), k - 1);
        }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (fa[i][0] == i) ans++;
    }
    cout << 9ll * powmod(10, ans - 1) % MODN << '\n';
}

08??A

题意：给定一张无向图和 m\space (3\times 10^5) 次加边（带权边）操作，如果某次操作之后这张图的 1\to n\space (5\times 10^4) 的最短路小于等于 T，则清空所有边。

找到所有删边的操作的时刻。

这道题数据比较水，让我们来看看赛时代码：

赛时代码：可以证明最短路是单调不上升的，所以二分可以拿到很多分。

#define unlikely(cond) (__builtin_expect((cond), 0))
using namespace std;

const int MAXN = 5e4 + 2, MAXM = 3e5 + 5;

int dis[MAXN], T, n;
uint8_t vis[MAXN];

int head[MAXN], edcnt;
int lowerE, upperE;
struct Ed { int v, w, nxt; } edge[MAXM * 2];
vector<int> result, erfe;

// 1, 2 为同一条边 
inline void add_edge(int u, int v, int w) { edge[++edcnt] = { v, w, head[u] }; head[u] = edcnt; }

using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> q;

inline int dij()
{
    fill(vis, vis + n + 1, 0), fill(dis, dis + n + 1, 0x3f3f3f3f);
    dis[1] = 0;
    q.push({ 0, 1 });
    while (!q.empty()) {
        const pii top = q.top(); q.pop();
        const int u = top.second, ow = top.first;
        if (vis[u]) continue;
        vis[u] = 1;
        for (int e = head[u]; e; e = edge[e].nxt) {
            if (lowerE > e) break;
            if (e <= upperE) {
                int v = edge[e].v, w = edge[e].w;
                if (dis[v] > ow + w) {
                    dis[v] = ow + w;
                    q.push({ dis[v], v });
                }
            }
        }
    }
    return dis[n];
}

struct my_greater {
    bool operator()(const int idx, const int val) const {
        upperE = idx * 2;
        return dij() > val;
    }
} gt;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    int u, v, w, q;
    cin >> n >> q >> T;
    erfe.reserve(q);
    for (int i = 1; i <= q; i++) {
        cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w);
        erfe.push_back(i);
    }
    int lowerq = 0;
    do {
        auto pos_iter = lower_bound(erfe.begin() + lowerq, erfe.end(), T, gt);
        if (pos_iter == erfe.end()) break;
        lowerq = *pos_iter;
        result.push_back(lowerq);
        lowerE = 2 * lowerq + 1;
    } while (true);
    cout << result.size() << '\n';
    for (auto x : result) cout << x << ' '; 
}

然后拿到了 60pts 的好分数。但是另一位神仙赛时二分搞过了，所以问了一下加了哪些优化（下面呈现到代码里了）。

只有两个小小的优化。

#define unlikely(cond) (__builtin_expect((cond), 0))
using namespace std;

const int MAXN = 5e4 + 2, MAXM = 3e5 + 5;

int dis[MAXN], T, n;
uint8_t vis[MAXN];

int lowerE, upperE;
vector<int> result, erfe;
struct Edge {
    int v, w, id;
    bool operator<(const Edge &s2) const { return id < s2.id; }
};
vector<Edge> gr[MAXN];

inline void add_edge(int u, int v, int w, int id) { gr[u].push_back({ v, w, id }); }

using pii = pair<int, int>;

inline bool dij()
{
    memset(vis + 1, 0, sizeof(char) * n);
    memset(dis + 2, 0x3f, sizeof(int) * (n - 1));
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({ 0, 1 });
    while (!q.empty()) {
        const pii top = q.top(); q.pop();
        const int u = top.second, ow = top.first;
        if (vis[u]) continue;
        vis[u] = 1;
        // Optimize 1. 二分到序号在现存边的位置
        auto it = lower_bound(
            gr[u].begin(),
            gr[u].end(),
            Edge { 0, 0, lowerE }
        );
        const auto end = gr[u].end();
        for (; it != end; it++) {
            // Optimize 2
            if (upperE < it->id) break;
            int v = it->v, w = it->w;
            if (dis[v] > ow + w) {
                dis[v] = ow + w;
                if (dis[n] <= T) return false;
                q.push({ dis[v], v });
            }
        }
    }
    return dis[n] > T;
}

struct {
    bool operator()(const int& idx, const int& val) const {
        upperE = idx * 2;
        return dij();
    }
} my_greater;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    int u, v, w, q;
    cin >> n >> q >> T;
    erfe.reserve(q);
    for (int i = 1; i <= q; i++) {
        cin >> u >> v >> w;
        add_edge(u, v, w, 2 * i - 1);
        add_edge(v, u, w, 2 * i);
        erfe.push_back(i);
    }
    int lowerq = 0;
    while (true) {
        auto pos_iter = lower_bound(erfe.begin() + lowerq, erfe.end(), T, my_greater);
        if (pos_iter == erfe.end()) break;
        lowerq = *pos_iter;
        result.push_back(lowerq);
        lowerE = 2 * lowerq + 1;
    }
    cout << result.size() << '\n';
    for (auto x : result) cout << x << ' '; 
}

取得 100 分的好成绩！虽然不是正解，但是懒得写了

[Ynoi2017] 由乃打扑克

Luogu

年轻人的第一道 Ynoi！

给你一个长为 n 的序列 a，需要支持 m 次操作，操作有两种：

1. 查询区间 [l,r] 的第 k 小值。
2. 区间 [l,r] 加上 k。

n, q \le 1\times 10^5

思路：分块之后二分值域。对于每一个整块二分，边界暴力。

感谢 #pragma GCC unroll(8) 帮助我这样我就不需要手动展开了。

Record 有点慢但是过了。

优化：

1. 在二分值域的 check 过程中，如果 需要查找的值 大于 这个块中的最大值 或者 小于 这个块中的最小值，可跳过。
2. 维护区间最大值/最小值，这样可以减少二分的值域。
3. #pragma GCC unroll(8) 激发了计算机的并行性能。
4. 块长 360 的效率对于我这份暴力东西还是是足够的。
5. 懒标记不要下传。
6. 没用 long long。

int n, m;
#ifdef ONLINE_JUDGE
const int bklen = 360;
#else
const int bklen = 3;
#endif
int bkd[1005][bklen + 3], blen[1005], bkl[10005], bkr[10005], dat[100005], bkcnt;
int lz[1005], nk[100005];

template<class T = int>
struct int_iterator
{
public:
    using value_type = const T;
    using difference_type = T;  
    using pointer = const T*;
    using reference = const T;
    using iterator_category = std::random_access_iterator_tag;
    int_iterator(T x) : _val(x) {}
    value_type operator*() const { return _val; }
    int_iterator &operator+=(difference_type n) { _val += n; return *this; }
    int_iterator &operator++() { return *this += 1; }
    int_iterator &operator--() { return *this += -1; }
    difference_type operator-(const int_iterator &iit) const { return _val - iit._val; }
private:
    T _val;
};

inline int query_single(int val, int p) { return upper_bound(bkd[p] + 1, bkd[p] + blen[p] + 1, val - lz[p]) - bkd[p] - 1; }
inline void pushdown(int p) {
    int l = bkl[p], r = bkr[p];
    for (int i = l; i <= r; i++) bkd[p][i - l + 1] = dat[i];
    sort(bkd[p] + 1, bkd[p] + blen[p] + 1);
}

inline pair<int, int> get_range(int l, int r)
{
    int lb = bkl[nk[l]] < l ? nk[l] + 1 : nk[l];
    int rb = bkr[nk[r]] > r ? nk[r] - 1 : nk[r];
    int ll = 2e9, rr = -2e9;
    if (lb > rb) {
        #pragma GCC unroll(8)
        for (int i = l; i <= r; i++) {
            const int val = dat[i] + lz[nk[i]];
            if (ll > val) ll = val;
            if (rr < val) rr = val;
        }
        return { ll, rr };
    }
    int llz = lz[nk[l]], rlz = lz[nk[r]], lc = bkl[lb];
    #pragma GCC unroll(8)
    for (int i = l; i < lc; i++) {
        const int val = dat[i] + llz;
        if (ll > val) ll = val;
        if (rr < val) rr = val;
    }
    #pragma GCC unroll(8)
    for (int i = lb; i <= rb; i++) {
        ll = min(ll, bkd[i][1] + lz[i]);
        rr = max(rr, bkd[i][blen[i]] + lz[i]);
    }
    #pragma GCC unroll(8)
    for (int i = bkr[rb] + 1; i <= r; i++) {
        const int val = dat[i] + rlz;
        if (ll > val) ll = val;
        if (rr < val) rr = val;
    }
    return { ll, rr };
}

inline int query(int l, int r, int k)
{
    const int lb = bkl[nk[l]] < l ? nk[l] + 1 : nk[l];
    const int rb = bkr[nk[r]] > r ? nk[r] - 1 : nk[r];
    const auto ran = get_range(l, r);
    const int mn = ran.first, mx = ran.second;
    const auto cmp = [lb, rb, l, r, k](int _, int rval) -> bool {
        int cnt = 0;
        if (lb > rb) {
            #pragma GCC unroll(8)
            for (int i = l; i <= r; i++) if (dat[i] + lz[nk[i]] <= rval) cnt++;
        } else {
            int llz = lz[nk[l]], rlz = lz[nk[r]], lc = bkl[lb];
            #pragma GCC unroll(8)
            for (int i = l; i < lc; i++) if (dat[i] + llz <= rval) cnt++;
            #pragma GCC unroll(8)
            for (int i = lb; i <= rb; i++) {
                if (rval <  bkd[i][1]) continue;
                if (rval >= bkd[i][blen[i]] + lz[i]) { cnt += blen[i]; continue; }
                cnt += query_single(rval, i);
            }
            #pragma GCC unroll(8)
            for (int i = bkr[rb] + 1; i <= r; i++) if (dat[i] + rlz <= rval) cnt++;
        }
        return cnt >= k;
    };
    return *upper_bound(int_iterator<int>(mn), int_iterator<int>(mx), k, cmp);
}

inline void add(int l, int r, int k)
{
    int lb = bkl[nk[l]] < l ? nk[l] + 1 : nk[l];
    int rb = bkr[nk[r]] > r ? nk[r] - 1 : nk[r];
    if (lb > rb) {
        #pragma GCC unroll(8)
        for (int i = l; i <= r; i++) dat[i] += k;
        pushdown(nk[l]);
        if (nk[l] != nk[r]) pushdown(nk[r]);
        return;
    }
    #pragma GCC unroll(8)
    for (int i = lb; i <= rb; i++) lz[i] += k;
    if (l < bkl[lb]) {
        int lim = bkl[lb];
        #pragma GCC unroll(8)
        for (int i = l; i < lim; i++) dat[i] += k;
        pushdown(nk[l]);
    }
    if (r > bkr[rb]) {
        #pragma GCC unroll(8)
        for (int i = bkr[rb] + 1; i <= r; i++) dat[i] += k;
        pushdown(nk[r]);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> dat[i];
    }

    for (int i = 1; i <= n; i += bklen) {
        ++bkcnt;
        bkl[bkcnt] = i, bkr[bkcnt] = min(i + bklen - 1, n);
        int len = bkr[bkcnt] - bkl[bkcnt] + 1;
        const int top = bkr[bkcnt];
        #pragma GCC unroll(8)
        for (int j = i; j <= top; j++) {
            bkd[bkcnt][j - i + 1] = dat[j];
            nk[j] = bkcnt;
        }
        blen[bkcnt] = len;
        sort(bkd[bkcnt] + 1, bkd[bkcnt] + len + 1);
    }

    int opt, l, r, k;
    for (int i = 1; i <= m; i++) {
        cin >> opt >> l >> r >> k;
        if (opt == 1) {
            cout << query(l, r, k) << '\n';
        } else {
            add(l, r, k);
        }
    }
}