/(O(10 n /log n)/) 能过,居然不卡常,青结了。
感觉是比较套路的一道 Ynoi 了 qwq。
首先看题目,需要找的就是一段长度为 /(1 /dots 10/) 的极长连续的(公差为 1)的等差数列,考虑暴力把一个个数丢进去,会造成怎样的结果,无非这两种情况:
-
无法拓展,单独成段;
-
连接上了在自己左右两边的极长连续段(记为 /(S_1/) 和 /(S_2/)),那么新的极长连续段为 /(|S_1|+|S_2|+1/),同时原来的两个对答案的贡献消失。
把询问离线下来,都丢到右端点上,对于第二种情况,相当于去掉在 /(S_1/) /(S_2/) 上的覆盖,同时加上 /(S_1+mid+S_2/) 的覆盖,对于询问,实际上就是 /(l/) 这个点被某一个长度为 /(x_i/) 的线段覆盖的次数,注意到段长只有 /(10/),直接暴力分成 /(10/) 个线段做事没问题的,区间修改,单点询问肯定用常数小的树状数组啦。
至于怎么在暴力拓展时保留单点询问的正确性,对于一个新数 /(x/),设 /(last_x/) 为上一次出现的次数,则 /(x/) 只对 /((last_x, i]/) 产生贡献(前面的去重后选用 /(last_x/) 的就行了),于是我们从 /(i/) 往左拓展,每次遇到上面的情况就进行区间覆盖操作,注意若 10 能拓展到 11 不算数。
复杂度 /(O(10nk /log n)/),/(k/) 是一个小常数。
Code:
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
using namespace std;
const int N=1e6+1;
inline int read(){
char ch=getchar();int x=0, f=1;
while(!isdigit(ch)) f=(ch=='-'?-1:f), ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0', ch=getchar();
return x*f;
}
typedef pair <int, int> Pii;
int n, m, a[N], las[N+11], Mx;
char ans[N][11];
Pii tmp[25];
vector < Pii > Q[N];
struct BITtree{
int sum[N];
#define lowbit(x) ((x)&(-(x)))
void add(int x, int v){for(; x; x-=lowbit(x)) sum[x]+=v;}
int query(int x){int res=0;for(; x<=n; x+=lowbit(x)) res+=sum[x];return res;}
#undef lowbit
}bit[10];
void chafen(int flg, int l, int r, int v){
if(flg>10||flg<1) return ;
bit[flg-1].add(l, v), bit[flg-1].add(r, -v);
}
signed main(){
n=read(), m=read();
for(int i=1; i<=n; i++) Mx=max(Mx, a[i]=read());
for(int i=1, l, r; i<=m; i++)
l=read(), r=read(), Q[r].push_back(make_pair(l, i));
int pos=1;
for(int i=1; i<=n; i++){
int x=a[i], L=max(1, x-11), R=min(x+11, Mx), top=0;
for(int j=L; j<=R; j++) if(las[j]>las[x]) tmp[++top]=make_pair(-las[j], j);
tmp[++top]=make_pair(-i, x);sort(tmp+1, tmp+top+1);
for(int j=1; j<=top; j++) tmp[j].first*=-1;tmp[top+1].first=las[x], L=R=0;//找到所有的极长区间
for(int j=1; j<=top; j++){
int nxt=tmp[j].second, least=tmp[j].first;
if(nxt<x) while(L<=10&&(x-L-1==nxt||las[x-L-1]>least)) L++;
if(nxt>x) while(R<=10&&(x+R+1==nxt||las[x+R+1]>least)) R++;
//找到匹配的最长段
chafen(L, least, tmp[j+1].first, -1);
chafen(R, least, tmp[j+1].first, -1);
//消掉之前的贡献
chafen(L+R+1, least, tmp[j+1].first, 1);
//加上新的贡献
}
for(int j=0; j<Q[i].size(); j++)
for(int k=1; k<=10; k++)
ans[Q[i][j].second][k]=bit[k-1].query(Q[i][j].first)%10+'0';
las[x]=i;
}
for(int i=1; i<=m; i++) printf("%s/n", ans[i]+1);
return 0;
}
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/281326.html