P2391

· · 题解

事实上这题可以使用 \text O(n\log m) 复杂度的贪心+优先队列思想做，此处 ? 大小要看数据。

前置知识

先来看本题目弱化版：

有一个数列 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 里存储区间，便于后面线性的遍历。

存储区间代码大致长这样：

#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，维护优先队列（优先级从小到大），维护这几个操作：

遍历区间的代码大致长这样：

#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 数组即可。

代码如下：

for (int i=1;i<=n;i++) cout<<ans[i]<<' ';

这种做法的正确性就是在每次遍历，弹出过时区间和放入区间之后，队列顶部的一定没有过时，且优先级一定最大。而且在弹出过时区间的时候，可以不考虑队列不在顶部的区间，因为在该区间到顶部的时候会自动弹出，一直没到顶部就更不用管了。

code

本题思路

题意其实跟上面是一样的，但是 1\leq n\leq 10^6,1\leq m\leq 10^7。

乍一看不会 TLE，修改数据范围后直接交上面的代码，喜获 85 分。原因是优先队列占用空间过大。

考虑优化做法。发现优先级低的区间被优先级高的完全覆盖时是没有用处的，所以可以不加进优先队列，可以逆序枚举区间然后判断要不要加。

但是区间修改区间查询又很难蚌，这么复杂我不如直接线段树做这题，但是发现 n 的范围很小，所以可以只判断左端点相同的比自己优先级大的最长区间是否完全覆盖了枚举到的区间，如果是就不放 vector 了。

code