题解--苦涩

· · 题解

如果数据水，敬请谅解，也希望提供强数据。
如果有时间复杂度更优秀的做法，请写题解，我会感激的。
先看部分分吧。

10pts

每个点开一个堆，然后就是常规操作了。

20pts

只有添加，没有删除，相当于区间取 max，区间 max。那就意味着我们可以用线段树维护。

40pts

发现单点删除最大值用线段树不太好操作，也不好进行标记下放和信息。上传我们考虑暴力一点，用分块维护信息，每个块开一个堆代表整块都被插入的东西，每个点也要开一个堆，然后开一个 maxx 数组代表块内最大值。
插入的时候我们边角暴力，中间插入整块的堆，然后更新 maxx。
删除的时候我们比较它自己的堆和它所属的块的堆。如果他自己的堆的堆顶更大，则直接删除，然后更新 maxx。如果它所属的堆更大，则删除掉之后，把它塞入块内其余点的堆里，因为它们还存在这个值，所以不用更新 maxx。
查询的时候我们边角暴力询问单点堆顶和整块堆顶，中间的整块直接查询 maxx，就解决了。
时间复杂度在块长为 \sqrt{n} 时复杂度较优，为 O(n\sqrt{n}logn)。代码如下，比较短。本来这是这个题的标算，但是……

60pts(1)

既然要 polylog，首先堆的一个 log 很难避免，我们剩下的那个 log 就可以往线段树上想。
考虑使用标记永久化，这个永久化的标记形成了一个堆。我们再在线段树里维护一个 maxx，代表这个区间的最大值。这样，插入和查询操作就很好处理了。
现在我们考虑删除，由于是单点，首先我们找到这个最大值，然后在线段树里找到这个标记。我们需要把这个标记移除，并将其加入这个区间的其它点内，你可以再写一个 pushdown，也可以直接跑两遍插入（这样常数要大一点）。
时间复杂度 O(nlog^2n)，代码挺好写的。
我终于知道 lxl 为什么直接拒了。

60pts(2)

如果你的分块可以支持区间修改，则可以通过 60 分的数据。

100pts

我们考虑怎么优化 60 分的线段树，使它支持区间修改。
我们可以想到先找到这一段的最大值是哪一个，然后把标记从这个区间上面移除。这样做看起来时间复杂度是不对的，但我们可以进行剪枝。如果这一个区间的最大值比我们需要删去的小，我们就不去了。
乍一看复杂度还是不对，但我们可以分析一下。我们时间复杂度相当于对于每一个最大值的连续区间，把它在线段树上分成不超过 log 个区间。由于我们插入的时候是整段一起插入同一个值，所以插入均摊下来会产生 mlogn 个线段树区间。
我们每删除一个产生的线段树区间，最多花 logn 时间递归下去删除标记。所以删除的时间复杂度为均摊 O(mlog^2n) （堆的复杂度和向下递归的复杂度是并列的）由于插入和查询的复杂度也是这个量级，所以总复杂度 O((n+m)log^2n)。
代码十分好写，不到 2k。如果哪里没叙述清楚，请向我提出。 

#include <bits/stdc++.h>
#define lc id<<1
#define rc id<<1|1
using namespace std;
const int maxn=2e5+5;
struct tree {
    int l,r,mid,maxx;
    priority_queue<int> q;
} t[maxn*4];
int n,m;
void build(int id,int l,int r) {
    t[id]=(tree) {
        l,r,(l+r)/2,-1
    };
    t[id].q.push(-1);
    if(l==r)return;
    int mid=(l+r)/2;
    build(lc,l,mid);
    build(rc,mid+1,r);
}
void addtag(int id,int v) {
    t[id].q.push(v);
    t[id].maxx=max(t[id].maxx,v);
}
void pushup(int id) {
    t[id].maxx=max(max(t[lc].maxx,t[rc].maxx),t[id].q.top());
}
void pushdown(int id,int l,int r,int k) {//把 k 这个标记往 l,r 之外区间插入
    if(t[id].l>=l&&t[id].r<=r) return;
    if(l>t[id].mid)addtag(lc,k),pushdown(rc,l,r,k);
    else if(r<=t[id].mid)addtag(rc,k),pushdown(lc,l,r,k);
    else pushdown(lc,l,r,k),pushdown(rc,l,r,k);
    pushup(id);
}
void add(int id,int l,int r,int v) {
    if(t[id].l>=l&&t[id].r<=r) {
        addtag(id,v);
        return;
    }
    if(l<=t[id].mid)add(lc,l,r,v);
    if(r>t[id].mid)add(rc,l,r,v);
    pushup(id);
}
void del(int id,int l,int r,int k) {
    if(t[id].l>=l&&t[id].r<=r&&t[id].maxx<k)return;//核心：剪枝
    if(t[id].q.top()==k) {
        t[id].q.pop();
        pushdown(id,l,r,k);
        if(t[id].l==t[id].r)t[id].maxx=t[id].q.top();
        else pushup(id);
        return;//由于只pop一个，这里弄完标记就走了
    }
    if(l<=t[id].mid)del(lc,l,r,k);
    if(r>t[id].mid)del(rc,l,r,k);
    pushup(id);
}
int ask(int id,int l,int r) {
    if(t[id].l>=l&&t[id].r<=r) {
        return t[id].maxx;
    }
    int ans=t[id].q.top();
    if(l<=t[id].mid)ans=max(ans,ask(lc,l,r));
    if(r>t[id].mid)ans=max(ans,ask(rc,l,r));
    return ans;
}
int main() {
    t[0].q.push(-1),t[0].maxx=-1;
    int op,x,y,z;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    for(register int i=1; i<=m; i++) {
        scanf("%d%d%d",&op,&x,&y);
        switch(op) {
            case 1: {
                scanf("%d",&z);
                add(1,x,y,z);
                break;
            }
            case 2: {
                z=ask(1,x,y);
                if(z!=-1)del(1,x,y,z);
                break;
            }
            case 3: {
                printf("%d\n",ask(1,x,y));
                break;
            }
        }
    }
    return 0;
}