题解：P5070 [Ynoi2015] 即便看不到未来

· · 题解

看着大佬们的题解弄明白了这道题，简单记录一下。

首先看到了 N \le 10^6，就知道可能要带单 \log 了，而且没有强制在线，可以考虑离线搞了。

考虑把询问离线下来，按照右端点排序。因为只需要考虑长度在 10 以内的情况，我们可以考虑对于这十种情况分别记录，设 ans_{i,j} 表示扫描到当前右端点时，左端点为 i，极长子段长为 j 的个数。

考虑新加进来的这个数字 x 对答案的影响。设 las_k 表示 k 上一次出现的位置。因为要求去重，所以它只会对 >las_x 的左端点造成影响。我们不妨考虑数字 [x-10,x+10] （因为极长段长度不超过10），并且按照它们上一次出现的位置从大到小依次考虑。这样能够使得当且数字 x 所在的极长段长度一定是不减的，而且能保证仅处理掉 las_x 以后的位置。

我们设 x 所在的极长值域段为 [l,r]，设 id_j 为对 [x-10,x+10] 的数字排序后第 j 个数上一次出现的位置。首先发现第 j 个数对答案所造成的影响只会在 [id_{j-1}+1,id_{j}] 上，然后考虑具体的影响。新加紧来的数字 x 使得原来的极长值域段 [l,x-1]，[x+1,r] 合并成了一个（若有右端点小于左端点的可视为空区间），那么我们只需要把长度为 x-l ，r-x 的答案减 1，长度为 r-l+1 的答案加 1 即可，我们用十个树状数组维护他。

其实我们在前面要考虑的数字应当加上 x-11 和 x+11，因为要求极长，若我们不考虑一个曾经是长度为十的极长段在加入新数后可能导致它变得更长就寄掉了，所以我们要多枚举这两个数，来避免这种情况。

CODE

#include<bits/stdc++.h>
#define N 1000000
using namespace std;
int n,m;
inline int read(){
    int x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();
    return x;
}int a[N+5],bit[N+5][15],las[N+5],res[N+5][15];//res为最终答案 
bool vis[N+5];//记录是否出现过，后面会说具体用法 

//树状数组的部分 
inline int lowbit(int x){return x&-x;}
inline void add(int x,int k,int id){for(int i=x; i<=n; i+=lowbit(i))bit[i][id]+=k;}
inline int sum(int x,int id){int ans=0;for(int i=x; i; i-=lowbit(i))ans+=bit[i][id];return ans;}
inline void upd(int l,int r,int k,int id){add(l,k,id),add(r+1,-k,id);}

struct node{int pos,val;}t[N+5]; 
inline bool cmp(node a,node b){return a.pos<b.pos;}

struct que{int l,r,id;};
vector<que>q[N+5];//用vector存储询问方便简洁 
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; 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(N,a[i]+11); j++){//把要考虑的数都找到 
            vis[j]=0;//把要用的点清空掉 
            if(las[j])t[++tot]={las[j],j};
        }sort(t+1,t+1+tot,cmp);
        for(int j=tot; j&&t[j].pos>las[a[i]]; j--){//从右往左考虑，如果已经不再是在 a[i] 上一次出现位置的后面就停掉了 
            vis[t[j].val]=1;//记录出现过的数字 

            //扩展[l,r]，如果往后扩展的位置出现过且在合法范围就进行扩展 
            while(l-1>=max(1,a[i]-11)&&vis[l-1])l--;
            while(r+1<=min(N,a[i]+11)&&vis[r+1])r++;

            //更新，不再赘述 
            upd(t[j-1].pos+1,t[j].pos,-1,a[i]-l);
            upd(t[j-1].pos+1,t[j].pos,-1,r-a[i]);
            if(r-l+1<=10)upd(t[j-1].pos+1,t[j].pos,1,r-l+1);
        }las[a[i]]=i;
        for(int j=0; j<q[i].size(); j++)for(int k=1; k<=10; k++)res[q[i][j].id][k]=sum(q[i][j].l,k);
    }for(int i=1; i<=m; i++){
        for(int j=1; j<=10; j++)putchar(res[i][j]%10^48);
        putchar('\n');
    }
    return 0;
}

另一道思维好题（然而黑降紫了，，）