AGC037F Counting of Subarrays

AGC037F

定义一个串$S$为级别$(k,m)$为：

1. $|S|=1$并且$S$中唯一的数为$k$。
2. $S$由大于等于$m$个级别为$k?1$的串拼接而成。

每个串可以同时属于多个级别。
给出数组$a_i$，求连续子序列的数量，满足存在$k$使得这个子序列为级别$(k,m)$。

$m\le n\le 2?10^5$

（这里把题面中的$L$换成了$m$，为了不和下面的题解起冲突）

补题解。

按照值从小往大考虑：找到当前的最小值$min$以及对应的若干个连续的区间，对于某个区间（设其长度为$len$），如果$len=1$则是合法的区间，并将其删除；如果$len<m$则是非法的区间，并将其删除；如果$len\ge m$，将其替换为$?\frac{len}{m}?$个$min+1$，然后继续操作下去。

接下来是如何计算贡献：

假如有某个串长成：$1,1,1,1,1,1,1,1,1,a,b,c$，$m=3$，进行了一次操作之后变成$2,2,2,a,b,c$。那么这个时候的$2,a,b$对应原序列的$1?x,a,b$（$x\in [6,8]$）。

于是对于每个位置，分别记两个值$L,R$。表示：某个位置，作为左（右）端点，它可以对应到原序列中的一段连续区间的长度。

维护这个东西，就可以替换之前计算答案了。

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200010
#define ll long long
int n,m;
int a[N];
struct Node{
    Node *pre,*suc;int v,L,R;ll s;bool f;
} *fir,*lst;
Node *ins(int v,int L,int R,int s,Node *pre,Node *suc){
    Node *nw=new Node;*nw=(Node){
    pre,suc,v,L,R,s,0};if (pre) pre->suc=nw;if (suc) suc->pre=nw;return nw;
}
Node *h[N];
int nh;
bool cmph(Node *son,Node *fa){
    return son->v>fa->v;}
int L[N],R[N],L_[N],R_[N];
ll calc(int L[],int R[],int k){
    ll sL=0,s=0;for (int i=1;i<=k;++i){
    if (i-m+1>0)sL+=L[i-m+1];s+=(sL+L[i])*R[i];}return s;
}
ll ans;
int main(){
    
// freopen("in.txt","r",stdin);scanf("%d%d",&n,&m);for (int i=1;i<=n;++i)scanf("%d",&a[i]);ans=n;fir=lst=ins(a[1],1,1,1,NULL,NULL);h[nh++]=fir,fir->f=1;for (int i=2;i<=n;++i){
    lst=ins(a[i],1,1,1,lst,NULL);if (lst->v!=lst->pre->v)h[nh++]=lst,lst->f=1;}make_heap(h,h+nh,cmph);while (nh){
    Node *fir=h[0];pop_heap(h,h+nh--,cmph);if (fir->f==0 || fir->pre && fir->pre->v==fir->v)continue;int v=fir->v,k=0;Node *p=fir,*lst=p;for (int i=1;p && p->v==v;++i,p=p->suc)L[i]=p->L,R[i]=p->R,++k,lst=p;Node *pre=fir->pre,*suc=lst->suc;if (pre) pre->suc=NULL;if (suc) suc->pre=NULL;fir->f=0;fir->pre=lst->suc=NULL;if (k==1 || k>=m){
    for (Node *p=fir;p && p->v==v;p=p->suc)ans-=p->s;ans+=calc(L,R,k);if (k==1)continue;int d=k/m;memset(L_,0,sizeof(int)*(d+1));memset(R_,0,sizeof(int)*(d+1));for (int i=m;i<=k;++i)R_[i/m]+=R[i];for (int i=k-m+1;i>=1;--i)L_[d-(k-i+1)/m+1]+=L[i];for (int i=d;i>=1;--i)suc=ins(v+1,L_[i],R_[i],0,pre,suc);suc->f=1;suc->s=calc(L_,R_,d);h[nh++]=suc;push_heap(h,h+nh,cmph);continue;}}printf("%lld\n",ans);return 0;
}