P5070 即便看不到未来

题面

题解

前言：我写完代码发现读错题了，白花 \(2\mathrm h\)。

先理解一下题目意思，就是把一段区间排序去重后统计各个长度的极长连续段数量。
经典的，考虑移动右端点 \(r\)，处理各个 \(l\) 的答案。
我们发现，新加入 \(a_r\) 时只用统计 \(a_r\) 附近的若干个值，记 \(bst_k\) 为 \(k\) 在 \(a_1,\cdots,a_{r-1}\) 中最后一次出现位置。
我们取出 \(a_r-11,a_r-10,\cdots,a_r+11\) 这 \(23\) 个数的最后出现位置并排序，然后处理合并即可，开 \(10\) 个树状数组不难实现。
复杂度 \(O(nk\log n)\)，其中 \(k=10\)，由于树状数组常数较小，可以通过。

Code

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int n,q;
struct qry{
    int l,r,id;
};
qry s[1000005];
bool cmp1(qry x,qry y){
    return x.r<y.r;
}
int ans[1000005][12];
int bst[1000005];
int h[25],m;
bool cmp2(int u,int v){
    return bst[u]>bst[v];
}
int c[12][1000005];
inline void add(const int k,int u){
    if(k>10||k==0) return;
    // cerr<<"add "<<k<<' '<<u<<'\n';
    while(u<=n){
        c[k][u]++; c[k][u]%=10;
        // cerr<<"c["<<k<<"]["<<u<<"]="<<c[k][u]<<'\n';
        u+=u&-u;
    }
}
inline void del(const int k,int u){
    if(k>10||k==0) return;
    // cerr<<"del "<<k<<' '<<u<<'\n';
    while(u<=n){
        c[k][u]+=9; c[k][u]%=10;
        // cerr<<"c["<<k<<"]["<<u<<"]="<<c[k][u]<<'\n';
        u+=u&-u;
    }
}
inline int sum(const int k,int u){
    int v=u;
    int res=0;
    while(u){
        // cerr<<"c["<<k<<"]["<<u<<"]="<<c[k][u]<<'\n';
        res+=c[k][u]; u&=u-1;
    }
    // cerr<<"qry "<<k<<" "<<v<<'=';
    // cerr<<res%10<<'\n';
    return res%10;
}
int mem[30],*f=mem+15;
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>q; a[0]=a[n+1]=-1;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=q;i++){
        cin>>s[i].l>>s[i].r; s[i].id=i;
    }
    sort(s+1,s+1+q,cmp1);
    int ps=1;
    for(int i=1;i<=n;i++){
        // cerr<<"i="<<i<<'\n';
        m=0;
        for(int j=max(1,a[i]-11);j<=min(1000000,a[i]+11);j++){
            h[++m]=j;
        }
        h[m+1]=0;
        sort(h+1,h+1+m,cmp2);
        memset(mem,0,sizeof(mem));
        add(1,bst[h[1]]+1); del(1,i+1);
        int pos1=0,pos2=0;
        for(int j=1;j<=m;j++){
            if(h[j]==a[i]) break;
            if(bst[h[j]]==0) break;
            f[h[j]-a[i]]=1;
            while(f[-pos1-1]==1) pos1++;
            while(f[pos2+1]==1) pos2++;
            del(pos1,bst[h[j+1]]+1);
            add(pos1,bst[h[j]]+1);

            del(pos2,bst[h[j+1]]+1);
            add(pos2,bst[h[j]]+1);

            add(pos1+pos2+1,bst[h[j+1]]+1);
            del(pos1+pos2+1,bst[h[j]]+1);
            // cerr<<'\n';
        }
        // cerr<<'\n';
        while(s[ps].r==i){
            ans[s[ps].id][1]=sum(1,s[ps].l);
            ans[s[ps].id][2]=sum(2,s[ps].l);
            ans[s[ps].id][3]=sum(3,s[ps].l);
            ans[s[ps].id][4]=sum(4,s[ps].l);
            ans[s[ps].id][5]=sum(5,s[ps].l);
            ans[s[ps].id][6]=sum(6,s[ps].l);
            ans[s[ps].id][7]=sum(7,s[ps].l);
            ans[s[ps].id][8]=sum(8,s[ps].l);
            ans[s[ps].id][9]=sum(9,s[ps].l);
            ans[s[ps].id][10]=sum(10,s[ps].l);
            ps++;
        }
        bst[a[i]]=i;
    }
    for(int i=1;i<=q;i++){
        putchar(48+ans[i][1]);
        putchar(48+ans[i][2]);
        putchar(48+ans[i][3]);
        putchar(48+ans[i][4]);
        putchar(48+ans[i][5]);
        putchar(48+ans[i][6]);
        putchar(48+ans[i][7]);
        putchar(48+ans[i][8]);
        putchar(48+ans[i][9]);
        putchar(48+ans[i][10]);
        putchar(10);
    }
    return 0;
}