前置知识：STL 或者手打优先队列（堆），`vector`。
这里为了代码方便，后面的代码均使用 STL 优先队列，想看手打堆的话可以看别的巨佬的博客然后去 [模板](https://www.luogu.com.cn/problem/P3378) 或者 Acwing 练手。
该算法可以运用优先队列，维护区间修改操作，并在修改最后进行值的查询。如果区间修改、查询的题目没有要求强制在线，可以使用该算法。
首先来看这种算法的板子：
有一个数列 $a$，长度 $n$，初始时 $a$ 所有元素均为 $0$。
现在要给 $a$ 数列进行 $q$ 次修改操作，每次操作将某一区间所有值均修改为特定的同一值。
最后求 $a$ 数列每个元素的值。
数据范围：$1\leq n,m\leq 10^5$，对于最后的答案 $1\leq a_{\forall i}\leq 10^9$。
样例输入：
```
5 3
1 3 1
2 4 2
3 3 3
```
样例输出：
```
1 2 3 2 0
```
这道题显然可以考虑线段树维护。但是这次我们不用线段树，考虑使用开头博客里优先队列维护每次修改。
既然是板子，肯定要好好讲讲：
**1. 存储区间。**
考虑按照修改区间的左顶点在 `vector` 里存储区间，便于后面线性的遍历。
存储区间代码大致长这样：
```cpp
#define mpr make_pair
inline int read(){//自己手敲的屑快读qwq
int res=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
return res*f;
}
vector<pair<int,pair<int,int> > >a[100005];//r,{color,t}
for (int i=1;i<=q;i++){
int x=read(),y=read(),z=read();
a[x].push_back(mpr(y,mpr(z,i)));//这里的i在后面会讲
}
```
**2. 优先队列维护区间集的排序方式。**
存储区间的时候记录一个优先级。
越后面的操作优先级越大（在上面的代码里取了 $i$）。在后面使用优先队列的处理中，需要根据优先级从小到大排序。
代码见上部分。
**3. 线性遍历所有区间。**
遍历一遍 $1\sim n$，维护优先队列（优先级从小到大），维护这几个操作：
- 弹出队列顶部右端点小于 $i$ 的操作区间（弹出顶部过时操作）。
- 放入所有左端点 $i$ 的区间。
- 选取队列顶部的操作区间对应的值赋值给答案数组对应的下标。
遍历区间的代码大致长这样：
```cpp
#define fr first
#define sc second
int a[100005];
priority_queue<pair<pair<int,int>,pair<int,int> >,vector<pair<pair<int,int>,pair<int,int> > >,less<pair<pair<int,int>,pair<int,int> > > >que;//{t,color},{l,r}
for (int i=1;i<=n;i++){
while (!que.empty()){//弹出过时区间
if (que.top().sc.sc<i) que.pop();
else break;
}
for (auto j:a[i]) que.push(mpr(mpr(j.sc.sc,j.sc.fr),mpr(i,j.fr)));//放入新的区间
if (!que.empty()){//统计该位置答案
const int x=que.top().sc.fr,y=que.top().fr.sc;
ans[i]=y;
}
}
```
**4. 输出答案。**
直接输出 `ans` 数组即可。
代码如下：
```cpp
for (int i=1;i<=n;i++) cout<<ans[i]<<' ';
```
这种做法的正确性就是在每次遍历，弹出过时区间和放入区间之后，队列顶部的一定没有过时，且优先级一定最大。而且在弹出过时区间的时候，可以不考虑队列不在顶部的区间，因为在该区间到顶部的时候会自动弹出，一直没到顶部就更不用管了。
[code](https://www.luogu.com.cn/paste/fpx61x94)
来看一道比较典的题：
有 $n$ 个集合 $a_{1\sim n}$，初始时 $a_{\forall i}$ 为空。
现在要给 $n$ 个集合进行 $q$ 次添加操作，每次操作给出一区间 $[x,y]$，将 $a_{x,x+1,...,y}$ 集合均添加同一个值。
最后求每个集合中最大的那个值。
数据范围：$1\leq n,m\leq 10^5$，对于最后的答案 $1\leq a_{\forall i}\leq 10^9$。
样例输入：
```
5 3
1 4 2
3 5 1
2 3 3
```
样例输出：
```
2 3 3 2 1
```
跟上题思路差不多，考虑将操作的优先级修改为对应的 $z_i$，进行类似的优先队列维护。
[code](https://www.luogu.com.cn/paste/0kxpo5nh)
来一个升级版的典题：
有一个数列 $a$，长度 $n$，初始时 $a$ 所有元素均为 $0$。
现在要给 $a$ 数列进行 $q$ 次修改操作，每次操作将某一区间所有值均修改为特定的同一值（$op=1$），或者将整个数列所有值均加上同一值（$op=2$）。
最后求 $a$ 数列每个元素的值。
数据范围：$1\leq n,m\leq 10^5$，对于最后的答案 $1\leq a_{\forall i}\leq 10^9$，$op\in\{1,2\}$。
样例输入：
```
5 3
1 1 3 1
1 2 4 2
2 1
```
样例输出：
```
2 3 3 3 1
```
可以维护一个 $op=2$ 所有操作对应的前缀和（按优先级排序），然后在每次遍历赋值时二分 $op=2$ 的操作优先级并给值加上前缀和即可。
[code](https://www.luogu.com.cn/paste/vdolc2pf)
练习题：
- [P9715](/problem/P9715)