题解：P9596 [JOI Open 2018] 冒泡排序 2

· · 题解

P9596 [JOI Open 2018] 冒泡排序 2

一个序列 A 的扫描次数为 \max_{i=1}^n \sum_{j=1}^i[a_j>a_i]。

证明：

发现一次操作必定将恰好一个 p 前面大于他的数换到他后面(排除没有的)。原式子相当于对于每个位置 p ，把其前面大于他的换到他后面需要的扫描次数取 \max ，即操作后对于每个位置其前面没有大于他的，序列 A 就是拍好序列。

发现同样的值只有最后一个位置 p 有用，一种值的答案为 \sum [A_i>v]-(n-p)，其中可以把 n-p 看作后面比他大的值，因为如果后面有比他小的值 v2 ，他的最后一个位置 p2>p，一定有 \sum [A_i>v2]-(n-p2)>\sum [A_i>v]-(n-p) ，即值 v 一定不优。

开棵权值线段树直接维护这个式子的最值，用 set 维护每种颜色的位置集合即可。

代码如下:

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e6+10,inf=1e9;
int n,q;
int a[N],stk[N],cnt;
int p[N],v[N];
set<int>s[N];
int Max[4*N],tag[4*N];
#define mid (l+r)/2
#define L 2*u
#define R 2*u+1
void change(int u,int l,int r,int lp,int rp,int v)
{
    if(lp>rp)return;
    if(lp<=l&&r<=rp)
    {
        Max[u]+=v;
        tag[u]+=v;
        return;
    }
    if(lp<=mid)change(L,l,mid,lp,rp,v);
    if(rp>mid)change(R,mid+1,r,lp,rp,v);
    Max[u]=max(Max[L],Max[R])+tag[u];
}
void Add(int c,int p){
    change(1,1,cnt,1,c-1,1);
    if(!s[c].size())change(1,1,cnt,c,c,inf-n);
    else change(1,1,cnt,c,c,-*prev(s[c].end()));
    s[c].insert(p);
    change(1,1,cnt,c,c,*prev(s[c].end()));
}
void Del(int c,int p)
{
    change(1,1,cnt,1,c-1,-1);
    change(1,1,cnt,c,c,-*prev(s[c].end()));
    s[c].erase(p);
    if(!s[c].size())change(1,1,cnt,c,c,-(inf-n));
    else change(1,1,cnt,c,c,*prev(s[c].end()));
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),stk[++cnt]=a[i];
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&p[i],&v[i]);p[i]++;
        stk[++cnt]=v[i];
    }
    sort(stk+1,stk+cnt+1);
    cnt=unique(stk+1,stk+cnt+1)-stk-1;
    for(int i=1;i<=cnt;i++)change(1,1,cnt,i,i,-inf);
    for(int i=1;i<=n;i++)a[i]=lower_bound(stk+1,stk+cnt+1,a[i])-stk;
    for(int i=1;i<=q;i++)v[i]=lower_bound(stk+1,stk+cnt+1,v[i])-stk;
    for(int i=1;i<=n;i++)
        Add(a[i],i);
    for(int i=1;i<=q;i++)
    {
        Del(a[p[i]],p[i]);
        a[p[i]]=v[i];
        Add(a[p[i]],p[i]);
        printf("%d\n",Max[1]);
    }
    return 0;
}