题解 P6749 【『MdOI R3』Yoshino】

BFqwq · 2020-08-12 00:10:52 · 题解

放一下本题的官方题解吧。

其实这个题写正解代码难度相当的高。为了防止空间不够用的现象，我把本题空间改成了 500MB（不过由于我使用了一些优化，所以我的空间其实小。

对于有一些暴力能够跑过本题的情况，其实出题人根本就没有想到有这样的暴力，不过还是在这里向大家道歉。

以下是本题的官方题解。

Subtask 1

考虑暴力修改，暴力查询逆序对，复杂度 \operatorname O(n^3)。

Subtask 2

将逆序对改用归并排序或权值树查询，复杂度 \operatorname O(n^2\log n)。

Subtask 3

由于修改长度是 1，直接考虑使用树套树维护动态逆序对。在修改时查询 [1,l-1] 区间大于原数的和 [r+1,n] 区间小于原数的数的个数并减去，然后对新数做类似的查询并加上。在查询逆序对时，可直接输出。复杂度 \operatorname O(n\log^2 n )

Subtask 4

显而易见，在值域缩小的同时，修改区间也随之缩小。

于是我们可以考虑对每个值建一个树状数组，如果对应位置有这个值，则树状数组该位置的值就是 1，否则是 0。

在修改时，对 [1,l-1] 区间的每个值分别做一个查询并做一个后缀和，对 [r+1,n] 区间的每个值也做一个查询并做一个前缀和，然后对每个值，我们就可以用 \operatorname O(1) 的复杂度修改并维护了。

注意不要忘了清楚修改区间内部对逆序对的贡献，这部分可以暴力。

由于值域可以认为是 \operatorname O(\log n)，故此处的复杂度为 \operatorname O(n\log^2 n)。

Subtask 5

由于第两次操作一就会重置一次，我们可以考虑直接用数学方法计算出修改的贡献。

对于奇数次操作，直接重置，逆序对清零。

对于偶数次操作，分为 l<x 和 l>x 两种。

如果 l<x，则我们修改完后的该区间的值为 [x,x+r-l]，易知 [l,r] 与 [x,x+r-l] 的交集为 [x,l-1]。

则对于值在 [x,l-1] 区间的数，对逆序对的贡献显然是一个公差为 -1 的等差数列，我们可以直接对此进行求和。

而对于值在 [l,x-r+l] 区间的数，显然对逆序对没有贡献，直接忽略。

如果 l>r 则类似讨论。

于是，我们就可以 \operatorname O(1) 完成对逆序对个数的计数（注意此时我们并不需要直接修改这个数列），复杂度 \operatorname O(n)。

Subtask 6

考虑颜色段均摊。

这是一种类似于珂朵莉树的 trick（事实上这就是珂朵莉树的推平操作），复杂度为均摊 \operatorname O(n\times k)，其中 k 为单次修改的复杂度。

对于一个区间染色的操作，我们可以直接将一个区间维护为一个点，并且将他装入在 set 或其他容器中。

在修改时，我们在 set 中找到我们需要清除的所有区间（如果边界被包含则将边界所在的区间断开变成两个区间），并暴力将它们逐个清除，再插入新的区间。

为什么这样做的复杂度是正确的呢？我们可以来证明一下。

最初的时候，每个数单独构成一个区间，所以一共有 n 个区间。

而每次操作的时候，我们增加的区间包括断开左右边界区间时增加的两个区间，以及插入的新区间。

这样一来，整个操作过程中区间的总个数就是 n+3m 个。

而显然一个区间最多被插入一次，删除一次，且 nm 同级，所以复杂度为均摊 \operatorname O(n\times k)。

本题中的操作一并不是颜色段均摊，但显然可以用类似的方法，均摊 \operatorname O(n\times k) 完成修改。

但我们在修改的同时，还需要再维护一个动态逆序对，于是考虑令 k=\log^2n，使用树套树修改

考虑插入一个新段对逆序对的贡献（删除就将贡献减去）。

假设这个区间是 [l,r]，这个区间的值的范围是 [x,y](r-l=y-x)。

那么我们大致可以其他的数分为以下几类：

位于 [1,l-1] 区间且值小于 x 的数。这类数没有贡献，直接无视。
位于 [r+1,n] 区间且值大于 y 的数。这类数同样没有贡献，直接无视。
位于 [1,l-1] 区间且值大于 y 的数。这类数对区间内的所有数都有贡献，只需统计个数并乘以 r-l+1。
位于 [r+1,n] 区间且值小于 x 的数。这类数同样对区间内的所有数都有贡献，处理方法同上。
位于 [1,l-1] 区间且值位于 [x,y] 之间的数。注意到，对于值为 t(t\in[x,y]) 的数，它对这个区间的贡献为 t-x，因为这个区间内前 t-x 个数的值会小于 t-x。于是我们可以对权值维护区间内的个数以及区间和，也就是一个范围内值在某个区间的数有几个，以及这几个数加起来是多少。然后用和减去个数乘以 x 就是我们所要的结果。
位于 [r+1,n] 区间且值位于 [x,y] 之间的数。处理方式类似于第五类数。

这样一来，我们就在修改的同时完成了对逆序对的维护，而复杂度没有发生变化。

于是最终的复杂度就是 \operatorname O(n\log^2 n)。

总结

本题的难度并不高，没有涉及到很复杂的维护方法，也没有涉及到很高级的数据结构，主要还是对一些基本技巧的灵活应用。另外，有一个颜色段均摊的操作值得大家掌握。

另外，本题可能出现空间不够用的情况。在本题的 std 代码中，树套树中的内层线段树使用的是标记永久化的线段树，这也大大节省了本题的空间。出题人没有测试过下放的空间，但看到部分其他用户的提交记录，感觉下放的确空间大了好多。

贴一份代码吧，供大家参考。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
    register int x=0;
    register bool f=0;
    register char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return f?-x:x;
}
char cr[200];int ttt;
inline void print(register int x,register char k='\n') {
    if(!x) putchar('0');
    while(x) cr[++ttt]=x%10+'0',x/=10;
    while(ttt) putchar(cr[ttt--]);
    putchar(k);
}
inline void printl(register ll x,register char k='\n') {
    if(!x) putchar('0');
    while(x) cr[++ttt]=x%10+'0',x/=10;
    while(ttt) putchar(cr[ttt--]);
    putchar(k);
}
const int maxn=52233;
const int len=30000;
struct seg{
    int v,ls,rs,tag;
    ll sum;
}t[maxn*160];
struct ask{
    int v;
    ll sum;
    friend ask operator +(ask a,ask b){
        return (ask){a.v+b.v,a.sum+b.sum};
    }
    friend ask operator -(ask a,ask b){
        return (ask){a.v-b.v,a.sum-b.sum};
    }
};
int rt[maxn],m,n,tot,st[maxn*128],top,tem[maxn][2],cnt[2];
int nnd(){
    if(top) return st[top--];
    return ++tot;
}
int del(int o){
    if(t[o].tag||t[o].sum||t[o].v||t[o].ls||t[o].rs) return o;
    st[++top]=o;
    return 0;
}
inline void change(int &o,register int l,register int r,register int ql,register int qr,register int v){
    if(!o) o=nnd();
    if(ql<=l&&r<=qr){
        t[o].v+=v*(r-l+1);
        t[o].sum+=v*(l+r)*(r-l+1)/2;
        t[o].tag+=v;
        o=del(o);
        return;
    }
    int mid=l+r>>1;
    if(ql<=mid) change(t[o].ls,l,mid,ql,qr,v);
    if(qr>mid) change(t[o].rs,mid+1,r,ql,qr,v);
    t[o].v=t[t[o].ls].v+t[t[o].rs].v+t[o].tag*(r-l+1);
    t[o].sum=t[t[o].ls].sum+t[t[o].rs].sum+(ll)t[o].tag*(l+r)*(r-l+1)/2;
    o=del(o);
}
inline void add(register int x,register int ql,register int qr,register int v){
    for(register int i=x;i<=n;i+=(i&-i)) 
        change(rt[i],1,len,ql,qr,v);
}
inline ask query(register int o,register int l,register int r,register int ql,register int qr,register ll tag){
    if(ql<=l&&r<=qr){
        ask res=(ask){0,0};
        res.v=t[o].v+tag*(r-l+1);
        res.sum=t[o].sum+tag*(r+l)*(r-l+1)/2;
        return res;
    }
    int mid=l+r>>1;ask res=(ask){0,0};
    if(ql<=mid) res=res+query(t[o].ls,l,mid,ql,qr,tag+t[o].tag);
    if(qr>mid) res=res+query(t[o].rs,mid+1,r,ql,qr,tag+t[o].tag);
    return res;
}
ask find(register int l,register int r,register int ql,register int qr){
    if(ql>qr||l>r) return (ask){0,0};
    if(l>r) return (ask){0,0};
    ask res=(ask){0,0};
    for(register int i=r;i;i-=(i&-i)) 
        res=res+query(rt[i],1,len,ql,qr,0);
    for(register int i=l-1;i;i-=(i&-i)) 
        res=res-query(rt[i],1,len,ql,qr,0);
    return res;
}
struct node{
    int l,r,v;
    friend bool operator <(node a,node b){
        return a.l<b.l;
    }
}tmp1,tmp2,tmp;
set<node> s;
set<node>::iterator it,it1,it2;
ll ans;
inline void split(register int x){
    it=s.upper_bound((node){x,0,0});it--;
    if(it->l==x) return;
    tmp1=(node){it->l,x-1,it->v};
    tmp2=(node){x,it->r,it->v+x-it->l};
    add(it->l,it->v+x-it->l,it->v+it->r-it->l,-1);
    add(x,it->v+x-it->l,it->v+it->r-it->l,1);
    s.erase(*it);
    s.insert(tmp1);s.insert(tmp2);
}
inline void update(register int l,register int r,register int x){
    if(l!=1) split(l);
    if(r!=n) split(r+1);
    while(1){
        tmp=*s.lower_bound((node){l,0,0});
        if(tmp.l==r+1) break;
        int tl=tmp.l,tr=tmp.r,vl=tmp.v,vr=tmp.v+tmp.r-tmp.l;
        add(tl,vl,vr,-1);
        ans-=find(1,tl-1,vr+1,len).v*(tr-tl+1)+find(tr+1,n,1,vl-1).v*(tr-tl+1);
        ask res=find(1,tl-1,vl,vr);
        ans-=res.sum-res.v*vl;
        res=find(tr+1,n,vl,vr);
        ans-=res.v*vr-res.sum;
        s.erase(tmp);
    }
    s.insert((node){l,r,x});
    add(l,x,x+r-l,1);
    register int vr=r-l+x,vl=x;
    ans+=find(1,l-1,vr+1,len).v*(r-l+1)+find(r+1,n,1,vl-1).v*(r-l+1);
    ask res=find(1,l-1,vl,vr);
    ans+=res.sum-res.v*vl;
    res=find(r+1,n,vl,vr);
    ans+=res.v*vr-res.sum;
}
signed main(){
    n=read();m=read();
    for(register int i=1;i<=n;i++){
        int x=read();
        s.insert((node){i,i,x});
        add(i,x,x,1);
        ans+=find(1,i-1,x+1,len).v;
    }
    s.insert((node){n+1,0,0});
    for(register int i=1;i<=m;i++){
        int opt=read();
        if(opt==1){
            int l=read(),r=read(),x=read();
            update(l,r,x);
        }
        if(opt==2) printl(ans);
    }
    return 0;
}