P5070 [Ynoi2015] 即便看不到未来

· · 题解

在 Ynoi 里算是代码比较好写的题了。

把询问离线下来，从左到右处理右端点，设当前处理到右端点 r。则 s_{i,j} 表示区间 [i,r]，长度为 j 的值域连续段个数。
考虑 r 从 r-1 移动过来对 s 数组产生的影响。设 lst_i 表示值 i 上一次出现的位置，那么只有 l>lst_{a_i} 的位置出现的数的集合发生了改变。
又因为我们只关心长度 \le 10 的连续段个数，也就是只关心 [a_i-10,a_i+10] 的数字最后一次出现的位置 pos_j。把它们的 lst 值升序排序，并从右向左处理。记 L,R 分别表示 x 所在的连续段最小值和最大值。那么可以分为三种情况：

发现它们三个的修改本质上一样：减掉 x-L 和 R-x 的贡献，加上 R-L+1 的贡献。设排序后现在处理到下标 j，那么这些修改的影响区间是 [pos_{j-1}+1,pos_j]。
我们需要一个支持区间加单点查询的数据结构，这里使用树状数组。

然后有个细节。虽然我们本不关心 a_i-11 和 a_i+11 这两个数，但按照上述做法实现，如果 x 成为了一个原来长度为 10 的连续段的开头，我们只有在新长度为 11 时才能把原来 10 这个段的贡献撤掉。故这里应当多循环一位。

const int N=1e6+5;
int n,m,a[N],lst[N];
struct node{int pos,x;} t[N];
il bool cmp(node x,node y) {return x.pos<y.pos;}
struct que{int l,r,id;};
vector<que> q[N]; 
struct BIT
{
    int tr[N];
    il void modify(int x,int k) {for(;x<=n;x+=x&(-x)) tr[x]+=k;}
    il void add(int l,int r,int k) {modify(l,k),modify(r+1,-k);}
    il int query(int x) {int res=0;for(;x;x-=x&(-x)) res+=tr[x];return res%10;}
}tr[15];
int ans[N][15],vis[N];
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++)
    {
        int l=read(),r=read();
        q[r].push_back({l,r,i});
    }
    for(int i=1,mx=1e6;i<=n;i++)
    {
        int tot=1,L=a[i],R=a[i]; t[1]={i,a[i]}; 
        for(int j=max(1,a[i]-11);j<=min(mx,a[i]+11);j++)
        {
            vis[j]=0;
            if(lst[j]) t[++tot]={lst[j],j};
        }
        sort(t+1,t+tot+1,cmp);
        for(int j=tot;j&&t[j].pos>lst[a[i]];j--)
        {
            vis[t[j].x]=1;
            while(vis[L-1]&&L-1>=max(1,a[i]-11)) L--;
            while(vis[R+1]&&R+1<=min(mx,a[i]+11)) R++;
            tr[a[i]-L].add(t[j-1].pos+1,t[j].pos,-1);
            tr[R-a[i]].add(t[j-1].pos+1,t[j].pos,-1);
            if(R-L+1<=10) tr[R-L+1].add(t[j-1].pos+1,t[j].pos,1);
        }
        lst[a[i]]=i;
        for(auto x:q[i]) for(int j=1;j<=10;j++) ans[x.id][j]=tr[j].query(x.l);
    }
    for(int i=1;i<=m;i++,printf("\n")) 
        for(int j=1;j<=10;j++) printf("%d",ans[i][j]);
    return 0;
}