[DS记录]P5070 [Ynoi2015] 即便看不到未来

**题意** ：给出长度为 $n$ 的序列 $A$。 每次查询区间 $[l,r]$ 中长度为 $1\sim k$ 的极长值域连续段个数。 其中，集合 $S$ 的值域连续段定义为 ： 将 $S$ 排序后，存在 $S_l\sim S_r$ 的值是连续的，称 $[S_l,S_r]$ 为一个值域连续段。 允许离线，$n,m,A_i\leq 10^6,k\leq 10$ ，时限$\texttt{3s}$。 ------------ 显然不是根号做法，又允许离线，考虑扫描线。逐步增大右端点 $r$ ，维护每个左端点的答案。 考虑所有右端点恰为 $r$ 的区间的贡献。 记 $A_r$ 上一次出现的位置为 $pre_r$。 对于 $i\leq pre_r$ 的 $A[i,r]$ ，去重后必然也等同于 $A[i,r-1]$ ，所以是无用的。 对于确定的区间 $[i,r]$ ，查询出 $A_r$ 向前连续达到的最小数 $L$ ，向后连续达到的最大数 $R$ ，则原先的两个极长连续段是 $[L,A_r),(A_r,R]$ ，现在合成为 $[L,R]$。 对于每个 $i$ 都处理显然不可承受，考虑利用 $k$ 很小的性质。 我们只需要关心 $[A_r-k-1,A_r+k+1]$ 中的数值。 记 $L_i,R_i$ 表示区间 $[i,r]$ 对应的 $[L,R]$ ，若 $L,R>k$ 则只需记为 $k+1$。 利用 $pre_{[A_r-k,A_r+k]}$ 容易求出各个 $L_i,R_i$ ，分成了 $O(k)$ 段。 对于每一段，贡献模式是确定的，用树状数组维护。 复杂度 $O\big((n+m)k\log n\big)$。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 1005000 using namespace std; namespace io { char buf[8005000],*_p1=buf,*_p2=buf,obuf[4005000],*O=obuf; #define getchar() (_p1==_p2&&(_p2=(_p1=buf)+fread(buf,1,8000000,stdin),_p1==_p2)?EOF:*_p1++) int rd() { int x=0;char ch=getchar(); while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')x=x*10+(ch^48),ch=getchar(); return x; } void putc(char ch){*O++=ch;} void flush(bool op=0){if (O-obuf>4000000||op){fwrite(obuf,O-obuf,1,stdout);O=obuf;}} }using namespace io; int n; #define lbit(p) (p&-p) struct SumDS{ int t[MaxN]; void add(int p,int c) {while(p<=n){t[p]+=c;p+=lbit(p);}} int qry(int p){ int ret=0; while(p){ret+=t[p];p^=lbit(p);} return ret; } }T[11]; void add(int len,int p,int c){ if (len<=0||len>10)return ; T[len].add(p,c); } char ans[MaxN][11]; void qry(int id,int p){ for (int i=1;i<=10;i++) ans[id][i]=T[i].qry(p)%10+'0'; } struct Line{int t,p,nxt;}s[MaxN]; int fir[MaxN],tl; void adl(int u,int t,int p) {s[++tl]=(Line){t,p,fir[u]};fir[u]=tl;} int a[MaxN],m,lim,nxt[MaxN]; bool cmp(int A,int B){return nxt[A]<nxt[B];} bool vis[MaxN]; int main() { n=rd();m=rd(); for (int i=1;i<=n;i++)lim=max(lim,a[i]=rd()); for (int i=1,l,r;i<=m;i++){l=rd();r=rd();adl(l,r,i);} for (int i=1;i<=lim;i++)nxt[i]=n+1; for (int l=n;l;l--){ int kl=max(1,a[l]-11),kr=min(a[l]+11,lim),tn=0,st[25]; for (int i=kl;i<=kr;i++)st[++tn]=i; sort(st+1,st+tn+1,cmp); int L,R;vis[L=R=a[l]]=1; add(1,l,1);add(1,nxt[st[1]],-1); for (int i=1;i<=tn;i++){ if (st[i]==a[l]||st[i]==n+1)break; vis[st[i]]=1; while(vis[L-1])L--;while(vis[R+1])R++; int tl=nxt[st[i]],tr=nxt[st[i+1]]; add(a[l]-L,tl,-1);add(R-a[l],tl,-1);add(R-L+1,tl,1); add(a[l]-L,tr,1);add(R-a[l],tr,1);add(R-L+1,tr,-1); }for (int i=kl;i<=kr;i++)vis[i]=0; nxt[a[l]]=l; for (int i=fir[l];i;i=s[i].nxt)qry(s[i].p,s[i].t); } for (int i=1;i<=m;i++){ for (int k=1;k<=10;k++)putc(ans[i][k]); putc('\n');flush(); }flush(1); return 0; } ```