题解 | #密码生成#

1. 本题的思路，首先把所有的线段排序，按左边排序，然后每一次对数组进行修改的时候，都把包含这个点的线段添加到优先队列，然后判断优先队列的top线段是否包含这个点，包含直接修改值，不包含直接弹出队列，如果队列没有满足的，那么不修改默认为0，有满足的直接修改。

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



struct node {
    int l, r, v;
};

bool operator <(node a, node b) {

    return a.v < b.v;//这个是给最大堆用的。（否则最大堆不知道怎么判断，只需要定义同方向）
}

int main() {
    long  N, M;
    cin >> N >> M;
    int  Li, Ri;

    vector<int> pass(N, 0);

    vector<node> tmp;//线段加值放到堆里面
    for (int i = 1; i <= M; i++) {
        cin >> Li >> Ri;

        node now;//准备生成线段

        now.l = Li;
        now.r = Ri;
        now.v = i;

        tmp.push_back(now);
    }

    sort(tmp.begin(), tmp.end(), [](node a, node b) {
        return a.l < b.l;//左端点进行线段的递增序列
        });

    priority_queue<node> q;//构造一个最大堆
    int pos = 0;//线段的下标

    //从第一个角标开始尝试
    for (int i = 0; i < N; i++) {

        while (pos < M && i >= tmp[pos].l ) {//包含这个点的线段都放进去。
            q.push(tmp[pos]);
            pos++;
        }

        //按照堆顶顺序进行赋值（刚好就是那个从下到上的一个尝试）
        while (!q.empty()) {
            node now = q.top();

            if (now.r < i) {//角标超出范围（已经不是那个线断了）（不是这个线段之前已经被处理了）
                q.pop();
            }
            else {
                pass[i] = now.v;//赋值
                break;//因为是最大堆，赋值一次，弹出（剩下的还有可能子啊下一个元素用）
            }

        }


    }


    long long sum = 0;
    for (long i = 0; i < N; i++) {
        sum += i * pass[i];
        sum = sum % 100000009;

    }
    cout << sum<< endl;

    return 0;
}