P9715 题解（2023 激励计划评分 7）

· · 题解

居然是赛场切掉的！

这里提供一个 \text O(n\log n) 的优先队列维护区间修改的考场做法，加卡常数能过。

给每种操作定义一个优先级。显然 t\in\{0,1\} 的操作都分别满足第一、二种性质：

而且第一种操作优先级显然大于第二种，这也是十分显然的。所以这里我设计的优先级是这样的：假设当前是第 i 次操作，则如果 t_i=1，则优先级为 i，反之为 -i。

然后考虑 op\in\{1,2\} 的操作，可以分开处理，最后一起统计。因为格子都是整行或者整列地复制，所以可以将二维的统计单格颜色分开变为两个维护行、列颜色的数组（同时保存优先级）。

保存所有操作的修改之后，可以将二维数组转化，将行、列的所有未被覆盖的操作按照从大到小的优先级排序，依次遍历，覆盖颜色。如果在遍历到某一行的时候，在之前覆盖了 x 列，则因为优先级大的会覆盖优先级小的操作，这次操作只会覆盖该行的 n-x 格。遍历到列的时候处理是类似的。

这样复杂度就是 \text O(n^2)，空间复杂度可以从原来的 \text O(n^2) 优化为 \text O(n)。

接下来考虑优化时间复杂度。分开记录行、列操作。处理行的时候，可以把每次操作的区间和优先级记录到一个 vector 里，维护一个优先队列（优先级从小到大排序），遍历 1\sim n，遍历到 i 的时候，先将队列顶部保存的操作不断弹出，直到顶部操作右区间不小于 i，然后 操作区间左边界为 i 的行操作放入优先队列，取队列顶的操作并将该行设置为对应颜色（后面的操作优先级被覆盖，所以不用管）。列处理与行类似。最后合并行、列处理即可。

时间复杂度 \text O(n\log n)，其中一只 \log n 是优先队列的。

顺带一提，由于使用了较多的 STL 数据结构，所以常数较大。所以遍历 vector 的时候建议使用 auto 遍历，读入输出使用较快方式，可以卡常数时间。

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define mpr make_pair
#define fr first
#define sc second
#define qwq pair<int,pair<pair<int,int>,int> >
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)//快速读取字符
inline const int read(){//基于快读读取字符的超级快读
    int x=0,f=1;register char ch=nc();
    while (ch<48||ch>57) {if (ch=='-') f=-1;ch=nc();}
    while (ch>=48&&ch<=57) x=x*10+ch-48,ch=nc();
    return x*f;
}
const int n=read(),m=read(),k=read(),q=read();
int cnt1,cnt2;
long long sum[500005];
pair<int,int>opt1[2000005],opt2[2000005];
pair<pair<int,int>,int>qq[4000005];//{c,t},type
vector<pair<int,pair<int,int> > >op1[2000005],op2[2000005];//r,{c,t}
inline bool comp(const pair<pair<int,int>,int> &o,const pair<pair<int,int>,int> &p) {return o.fr.sc>p.fr.sc;}
void init1(){
    priority_queue<qwq,vector<qwq >,less<qwq > >que;//t,{{l,r},c}
    for (register int i=1;i<=n;++i){
        while (!que.empty()){
            if (que.top().sc.fr.sc<i) que.pop();
            else break;
        }
        for (auto j:op1[i]) que.push(mpr(j.sc.sc,mpr(mpr(i,j.fr),j.sc.fr)));
        if (!que.empty()){
            const int col=que.top().sc.sc,tt=que.top().fr;
            opt1[i]=mpr(col,tt);
        }
    }
}
void init2(){
    priority_queue<qwq,vector<qwq >,less<qwq > >que;//t,{{l,r},c}
    for (register int i=1;i<=m;++i){
        while (!que.empty()){
            if (que.top().sc.fr.sc<i) que.pop();
            else break;
        }
        for (auto j:op2[i]) que.push(mpr(j.sc.sc,mpr(mpr(i,j.fr),j.sc.fr)));
        if (!que.empty()){
            const int col=que.top().sc.sc,tt=que.top().fr;
            opt2[i]=mpr(col,tt);
        }
    }
}
int main(){
    int op,l,r,c,t,ggg;
    for (register int i=1;i<=q;++i){
        op=read(),l=read(),r=read(),c=read(),t=read(),ggg=(t==1?i:-i);
        if (op==1) op1[l].push_back(mpr(r,mpr(c,ggg)));
        else op2[l].push_back(mpr(r,mpr(c,ggg)));
    }
    init1(),init2();
    for (register int i=1;i<=n;++i) qq[i]=mpr(opt1[i],1);
    for (register int i=1;i<=m;++i) qq[n+i]=mpr(opt2[i],2);
    sort(qq+1,qq+n+m+1,comp);
    for (register int i=1;i<=n+m;++i){
        int col=qq[i].fr.fr,typ=qq[i].sc;
        if (col==0) continue;
        if (typ==1) ++cnt1,sum[col]+=m-cnt2;
        else ++cnt2,sum[col]+=n-cnt1;
    }
    for (register int i=1;i<=k;++i) printf("%lld ",sum[i]);
    return 0;
}