题解 P5797 【[SEERC2019]Max or Min】

· · 题解

Luogu 题面 & CodeForces 题面

通过手玩，易知只有大于或小于当前数 k 的状态才会对答案有所影响，也就是说当前数的大小不重要，重要的是与 k 的大小关系。

这样原来的序列只有两种：

  1. \{k,>k,>k,>k,>k,\dots\}$ 或 $\{k,<k,<k,<k,<k,\dots\}
  2. \{k,>k,<k,>k,<k,\dots\}

对于第一种，显然，对答案贡献为 \sum_{i=1}^{len} [a_i \neq k] 。

对于第二种，我们每次必须把下一个元素先 copy 成更小或更大后才能转换成 k ，而被 copy 的元素将能被直接转换 k 。

显然有贡献 (\sum_{i=1}^{len} [a_i\neq k])+\lfloor \frac{len}{2} \rfloor 。

这样分类后，显然只要原序列中有数字 k ，对于 k 就有解。

所以现在的问题转化成如何求出 \lfloor \frac{len}{2} \rfloor ，进一步转化成维护一个如第二类的序列，也是线段树的一个经典题目，具体相似于最大子序列问题。

首先当然是断环成链。

考虑每次转换 k 值时，只有值为 k-1 和 k 的元素性质会发生变化，每次只要修改这些节点即可，存储可用 std::vector 或手写链表实现，查询时选取一段合适的长度为 n+1 的区间即可

时间复杂度 \mathcal{O}(n\log n)

Code(C++98):

#include<bits/stdc++.h>
#define forn(i,s,t) for(int i=(s);i<=(t);++i)
using namespace std;
const int N = 2e5+3;
char ch;
template<typename T>inline void redn(T &ret) { // 快读
    ret=0,ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) ret=(ret<<1)+(ret<<3)+ch-48,ch=getchar();
}
vector<int> v[N];
int n,m,a[N<<1],now;
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
struct Node{int l,r,dl,dr,len,lng;}T[N<<4]; //线段树 变量(从左到右)：区间左/右端 以左/右端为端点的最长序列长度 
                                            // 区间长度 该区间序列长度贡献总和
inline Node Mrg(Node L,Node R) {            // 合并区间
    Node M = (Node){0,0,0,0,0,0};
    bool flag = 1ll*(a[L.r]-now)*(a[R.l]-now)<0?1:0;
    M.dl = L.dl+(L.len==L.dl&&flag)*R.dl;
    M.dr = R.dr+(R.len==R.dr&&flag)*L.dr;
    M.l = L.l,M.r = R.r,M.len = L.len+R.len;
    if(flag) M.lng = L.lng+R.lng-(L.dr>>1)-(R.dl>>1)+(L.dr+R.dl>>1);
    else M.lng = L.lng+R.lng;
    return M;
}
void Bld(int p,int l,int r) {      // 建树
    if(l == r) {
        if(now == a[l]) T[p] = (Node){l,r,0,0,r-l+1,0};
        else T[p] = (Node){l,r,1,1,r-l+1,0};
        return ;
    }
    int mid = l+r >> 1;
    Bld(ls(p),l,mid),Bld(rs(p),mid+1,r);
    T[p] = Mrg(T[ls(p)],T[rs(p)]);
}
void Upd(int p,int nl,int nr,int pos) {      // 更新
    if(nl == nr) {
        if(now == a[nl]) T[p] = (Node){nl,nr,0,0,nr-nl+1,0};
        else T[p] = (Node){nl,nr,1,1,nr-nl+1,0};
        return ;
    }
    int mid = nl+nr >> 1;
    if(pos<=mid) Upd(ls(p),nl,mid,pos);
    else Upd(rs(p),mid+1,nr,pos);
    T[p] = Mrg(T[ls(p)],T[rs(p)]);
}
Node Qry(int p,int l,int r,int nl,int nr) { //查询
    if(l==nl&&nr==r) return T[p];
    int mid = nl+nr >> 1;
    if(r<=mid) return Qry(ls(p),l,r,nl,mid);
    else if(l>mid) return Qry(rs(p),l,r,mid+1,nr);
    else return Mrg(Qry(ls(p),l,mid,nl,mid),Qry(rs(p),mid+1,r,mid+1,nr));
}
int main() {
    redn(n),redn(m);
    forn(i,1,n) redn(a[i]),a[i+n]=a[i];
    forn(i,1,n) v[a[i]].push_back(i);
    Bld(1,1,n<<1);
    forn(i,1,m) { now = i; int count = 0;
        if(v[i].size())
        forn(j,0,v[i].size()-1) Upd(1,1,n<<1,v[i][j]),Upd(1,1,n<<1,v[i][j]+n);
        if(v[i-1].size())
        forn(j,0,v[i-1].size()-1) Upd(1,1,n<<1,v[i-1][j]),Upd(1,1,n<<1,v[i-1][j]+n);
        if(!v[i].size()) printf("-1 ");
        else printf("%d ",n-(int)v[i].size()+Qry(1,v[i][0],v[i][0]+n,1,n<<1).lng);
    }
    return 0;
}