题解：CF351D Jeff and Removing Periods

· · 题解

这是一个截然不同的，只需要普通线段树的，高贵的 O(n \log n) 做法，n 开到 2 \times 10^6 都没问题。

由题目可知，每次删除后可以重排列这个序列，而每次删除只能删掉颜色相同的一个等差数列。因此我们每次重新排列时只要把相同颜色的全部放到最前面，由于一个前缀一定是一个等差数列，因此我们可以把一种颜色全部删除。

但是问题就在于第一次操作前时不能重排的，所以第一次删除不一定能删完一种颜色。

于是问题就转换成判断是否存在一种颜色可以一次删完，即判断是否有一种颜色在给定区间钟的位置是等差数列。如果存在，答案就是区间的颜色数量；否则就是颜色数量 +1。

那么我们对于每个 i，维护以 i 为结尾，颜色为 b_i 的极长等差数列的开头为 \text{pos}_i，假设 \text{lst}_i 为最大的 j 满足 j<i \land b_i = b_j。那么一个颜色 c 能成为答案，当且仅当：

为什么呢？首先我们取最大的 i 是为了消除后面还有颜色为 c 的数字的影响；\text{lst}_{\text{pos}_i} 的意义就是破坏以 i 为结尾的等差数列的位置，这个位置出现在 l 之前说明无法对 [l,r] 的答案造成影响。

我们知道，区间数颜色问题有广为人知的 O(n \log n) 解法；对于上面的问题，我们可以离线扫描线，用线段树维护 \text{lst}_{\text{pos}_i}。至于如何满足 i 最大的条件，可以在加入 i 后删除 \text{lst}_i，也就是将 \text{lst}_i 位置上的值变成无穷大。

那么这道题就做完了，复杂度为 O(n \log n)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 1000006
using namespace std;
int n,q,a[N],lst[N],t[N],pos[N],ans[N];
vector<pair<int,int> > Q[N];
struct Segtree1{
int tree[N];
void build(int p,int l,int r)
{
    if(l==r)return tree[p]=1,(void)0;
    int mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    tree[p]=tree[p<<1]+tree[p<<1|1];
}
void update(int p,int l,int r,int k)
{
    if(l==r)return tree[p]=0,(void)0;
    int mid=l+r>>1;k<=mid?update(p<<1,l,mid,k):update(p<<1|1,mid+1,r,k);
    tree[p]=tree[p<<1]+tree[p<<1|1];
}
int query(int p,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)return tree[p];
    int mid=l+r>>1,ret=0;
    if(L<=mid)ret+=query(p<<1,l,mid,L,R);
    if(R>mid)ret+=query(p<<1|1,mid+1,r,L,R);
    return ret;
}}T1;
struct Segtree2{
int tree[N];
void build(int p,int l,int r)
{
    if(l==r)return tree[p]=1e15,(void)0;
    int mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
void update(int p,int l,int r,int k,int x)
{
    if(l==r)return tree[p]=x,(void)0;
    int mid=l+r>>1;k<=mid?update(p<<1,l,mid,k,x):update(p<<1|1,mid+1,r,k,x);
    tree[p]=min(tree[p<<1],tree[p<<1|1]);
}
int query(int p,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)return tree[p];
    int mid=l+r>>1,ret=1e15;
    if(L<=mid)ret=min(ret,query(p<<1,l,mid,L,R));
    if(R>mid)ret=min(ret,query(p<<1|1,mid+1,r,L,R));
    return ret;
}}T2;
main()
{
    scanf("%lld",&n),T1.build(1,1,n),T2.build(1,1,n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]),lst[i]=t[a[i]],t[a[i]]=i;
    for(int i=1;i<=n;i++)
    {
        if(!lst[i])pos[i]=i;
        else if(i-lst[i]==lst[i]-lst[lst[i]]||!lst[lst[i]])pos[i]=pos[lst[i]];
        else pos[i]=lst[i];
    }
    scanf("%lld",&q);
    for(int i=1,l,r;i<=q;i++)
        scanf("%lld%lld",&l,&r),Q[r].push_back({l,i});
    for(int i=1;i<=n;i++)
    {
        T2.update(1,1,n,i,lst[pos[i]]);
        if(lst[i])T1.update(1,1,n,lst[i]),T2.update(1,1,n,lst[i],1e15);
        for(auto [l,id]:Q[i])
            ans[id]=T1.query(1,1,n,l,i)+(T2.query(1,1,n,l,i)>=l);
    }
    for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
    return 0;
}