题解：P9068 [Ynoi Easy Round 2022] 超人机械 TEST_95

· · 题解

Part 1 前言

本来看到空间 50M 就以为只能用分块暴力搞，结果花了 3h 过题之后发现题解区一堆 cdq，还我这浪费了的 3h！

不过借这个题短暂复习一下分块+值域分块也是好的，就当时省选前的码力训练吧。

Part 2 解法

本质不同引导我们把序列逆序对问题转化为值域上二维偏序问题，具体来说，定义一种数字 i 首次和最后一次出现分别是在 l_i,r_i，那么答案可以被表示成如下形式：

\sum_{i>j}[l_i<r_j]

如果不带修，BIT 做二维数点直接秒。

现在带上修改，如果直接上 cdq 做三维偏序也是可行的，不过因为空间限制我最后还是想选用分块。

修改操作可以视为修改某一个值的 l_i 和 r_i，每次维护变化量。我们对 l 和 r 分别维护，那么我们现在要解决的问题就是单点修改，查询区间内 \le x 的数字个数或者查询区间内 \ge x 的数字个数。

这个显然是分块的经典例题，我们有 O(n\sqrt {n\log n}) 做法，但是时间复杂度看着就不行。然后考虑你其实是有 O(n) 次单点修改和 n\sqrt n 次查询块内 \le x 的数字个数，这启发我们使用值域分块平衡复杂度，于是就做到严格 n\sqrt n 了。

等等！值域分块空间复杂度 O(n\sqrt n)！cdq 线性空间都未必能过，你这显然没戏了。于是再上经典 trick 离线对于每一个块分别做，这样空间复杂度就被压到严格线性了。

Part 3 代码

具体实现稍微有一点点卡常，但是你只要加上如果修改不改变 l,r 就不修改的剪枝就差不多能过了。

无可读性，也就图一乐。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int h=330;
int n,q;
int a[N];
set<int> st[N];
int bl[N];
int ans[N];
int o;
namespace work1
{
    struct node{int id,t,k,v;};
    int cnt=0;
    bool cmp(node x,node y){return x.t<y.t;}
    vector<node> qry[N/h+10];
    vector<node> upd[N/h+10];
    void Newquery(int p,int k,int v){qry[p].push_back((node){o,++cnt,k,v});}
    void Newupdate(int p,int k,int v) {upd[p].push_back((node){o,++cnt,k,v});}
    int val[N/h+10],sum[N];
    void add(int x,int v)
    {
        for(int i=1;i<bl[x];i++) val[i]+=v;
        for(int i=x;bl[i]==bl[x];i--) sum[i]+=v;
    }
    int query(int x){return val[bl[x]]+sum[x];}
    void main()
    {
        vector<node> now;//记录现在的询问
        for(int i=bl[n];i;i--)
        {
            memset(val,0,sizeof(val));
            memset(sum,0,sizeof(sum));
            vector<node> tmp;
            tmp.resize(now.size()+qry[i].size());
            merge(now.begin(),now.end(),qry[i].begin(),qry[i].end(),tmp.begin(),cmp);
            now.swap(tmp);
            int p1=0,p2=0;
            while(p1<now.size())
            {
                while(p2<upd[i].size()&&upd[i][p2].t<=now[p1].t) add(upd[i][p2].k,upd[i][p2].v),p2++;
                ans[now[p1].id]+=now[p1].v*query(now[p1].k),p1++;
            }
        }
    }
}
namespace work2
{
    struct node{int id,t,k,v;};
    int cnt=0;
    bool cmp(node x,node y){return x.t<y.t;}
    vector<node> qry[N/h+10];
    vector<node> upd[N/h+10];
    void Newquery(int p,int k,int v){qry[p].push_back((node){o,++cnt,k,v});}
    void Newupdate(int p,int k,int v) {upd[p].push_back((node){o,++cnt,k,v});}
    int val[N/h+10],sum[N];
    void add(int x,int v)
    {
        for(int i=bl[x]+1;i<=bl[n];i++) val[i]+=v;
        for(int i=x;bl[i]==bl[x];i++) sum[i]+=v;
    }
    int query(int x){return val[bl[x]]+sum[x];}
    void main()
    {
        vector<node> now;//记录现在的询问
        for(int i=1;i<=bl[n];i++)
        {
            memset(val,0,sizeof(val));
            memset(sum,0,sizeof(sum));
            vector<node> tmp;
            tmp.resize(now.size()+qry[i].size());
            merge(now.begin(),now.end(),qry[i].begin(),qry[i].end(),tmp.begin(),cmp);
            now.swap(tmp);
            int p1=0,p2=0;
            while(p1<now.size())
            {
                while(p2<upd[i].size()&&upd[i][p2].t<=now[p1].t) add(upd[i][p2].k,upd[i][p2].v),p2++;
                ans[now[p1].id]+=now[p1].v*query(now[p1].k),p1++;
            }
        }
    }
}
int l[N],r[N];
struct BIT
{
    int c[N];
    int lowbit(int x){return x&-x;}
    void add(int x,int v){while(x<=n){c[x]+=v,x+=lowbit(x);}}
    int query(int x){int ans=0;while(x){ans+=c[x],x-=lowbit(x);}return ans;}
}T;
void updl(int p,int v)
{
    int sum=0;
    for(int i=p-1;bl[i]==bl[p];i--) sum+=l[p]<r[i];
    ans[o]+=sum*v;
}
void updr(int p,int v)
{
    int sum=0;
    for(int i=p+1;bl[i]==bl[p];i++) sum+=l[i]<r[p];
    ans[o]+=sum*v;
}
void upd(int x,int v)
{
    int p=a[x];
    bool flag1=v==1&&l[p]>x||v==-1&&l[p]==x; //l是否变化
    bool flag2=v==1&&r[p]<x||v==-1&&r[p]==x; //r是否变化
    if(st[p].size())
    { 
        if(flag1)
        {
            work1::Newquery(bl[p]-1,l[p],-1);
            work2::Newupdate(bl[p],l[p],-1);
            updl(p,-1),l[p]=n+1;
        }
        if(flag2)
        {
            work1::Newupdate(bl[p],r[p],-1);
            work2::Newquery(bl[p]+1,r[p],-1);
            updr(p,-1),r[p]=0;
        }
    }
    if(v==-1) st[p].erase(x);
    else st[p].insert(x);
    if(st[p].size())
    {
        if(flag1)
        {
            l[p]=*st[p].begin(),updl(p,1);
            work1::Newquery(bl[p]-1,l[p],1);
            work2::Newupdate(bl[p],l[p],1);
        }
        if(flag2)
        {
            r[p]=*st[p].rbegin(),updr(p,1);
            work1::Newupdate(bl[p],r[p],1);
            work2::Newquery(bl[p]+1,r[p],1);
        }
    }
}
signed main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],st[a[i]].insert(i);
    for(int i=1;i<=n;i++) bl[i]=(i-1)/h+1;
    long long sum=0;
    for(int i=n;i;i--)
    {
        if(st[i].empty()) l[i]=n+1,r[i]=0;
        else
        {
            l[i]=*st[i].begin(),r[i]=*st[i].rbegin();
            work1::Newupdate(bl[i],r[i],1);
            work2::Newupdate(bl[i],l[i],1);
            sum+=T.query(r[i]),T.add(l[i],1);
        }
    }   
    cin>>q;
    for(o=1;o<=q;o++)
    {
        int x,y;
        cin>>x>>y;
        upd(x,-1),a[x]=y,upd(x,1);
    }
    work1::main();
    work2::main();
    for(int i=0;i<=q;i++) cout<<(sum+=ans[i])<<'\n';
    return 0;
}