题解 | #密码生成#

可以考虑将修改倒序操作，这样就将问题转化为了序列中赋值并删数的操作。这个操作就可以拿链表来维护。

可以使用并查集维护的链表做，它特别擅长做仅删除的链表问题，并且复杂度是O(N)而不是传统的带log的，非常优秀。

#include <bits/stdc++.h>
// #define int long long
using namespace std;

#define ll long long

const int N = 1.5e7, M = 2e5;
const ll MOD = 100000009;

int n, m;
int fa[N], val[N];
int l[M], r[M];
int find(int x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}

signed main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &l[i], &r[i]);
    }
    for (int i = 0; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 0; i <= n; i++) {
        val[i] = 0;
    }
    for (int i = m; i >= 1; i--) {
        int j = find(l[i]);
        while (j <= r[i]) {
            int nxt = find(j + 1);
            if (val[j] == 0) {
                val[j] = i;
                fa[j] = nxt;
            }
            j = nxt;
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += ((long long)i * val[i]) % MOD;
        ans %= MOD;
    }
    printf("%lld", ans);
    return 0;
}