【吉如一线段树】JZOJ6270. 【省赛模拟8.10】序列

Description

ai,n<=2e5

Solution

• 考虑按照答案分类，假如$d$的倍数为$a[1],a[2],..a[k-1],a[k]$,那么区间被1…(a[k-1]-1),(a[2]+1)…n,(a[1]+1)…(a[n]-1)这三个区间包含的区间的答案至少为d，也就是要维护区间取MAX，并求和。
• 最后求所有区间的答案。
• 将操作区间左到右排序，用一个吉如一线段树（裸的）直接维护这个操作就好了。
• 实际上由于每一次对一个前缀取MAX，区间的值实际上是单调不升的，二分一下就好了（用一个set）.

吉如一线段树

• 据说是nlogn~nlog²n的。
• 我们只考虑求最大值（最小值类似），以及区间求和。
• 每一个节点记录一个最小值和严格次小值（初值为inf），区间和以及区间最小值的个数。
• 假设当前修改的是v，v如果小于等于最小值肯定不用考虑。
• v如果大于最小值并严格小于次小值，那么考虑将最小值的那一部分改为v，再计算贡献。
• 否则大于等于次小值就递归下去。
• 根据一些势能分析这样子做事不会T的（雾），也许之后会补这一部分的知识吧。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define maxn 200005
#define maxm 1000005
#define LL long long 
using namespace std;

int n,i,j,k,a[maxn],mx,tot,w;
int p0[maxn],p1[maxn],q0[maxn],q1[maxn];
int u0[maxn],u1[maxn],v0[maxn],v1[maxn];
struct opr{
	int l,r,x;
	opr(int _l=0,int _r=0,int _x=0){l=_l,r=_r,x=_x;}
} p[20*maxn];
int cmp(opr a,opr b){return a.l<b.l;}

LL t[maxm],ans;
int mi0[maxm],mi1[maxm],cnt[maxm],tag[maxm];

void Min(int &x,int y){x=min(x,y);}
void Max(int &x,int y){x=max(x,y);}

void add0(int i,int x){
	if (x<p0[i]) p1[i]=p0[i],p0[i]=x; else 
	if (x<p1[i]) p1[i]=x;
	if (x>q0[i]) q1[i]=q0[i],q0[i]=x; else
	if (x>q1[i]) q1[i]=x;
}

void add1(int i,int x,int t){
	if (t==0){
		if (x<u0[i]) u1[i]=u0[i],u0[i]=x; else 
		if (x<u1[i]) u1[i]=x;		
	}
	if (t==1){
		if (x>v0[i]) v1[i]=v0[i],v0[i]=x; else
		if (x>v1[i]) v1[i]=x;		
	}
}

void add2(int i,int j){
	if (p0[j]!=maxn) add1(i,p0[j],0);
	if (p1[j]!=maxn) add1(i,p1[j],0);
	if (q0[j]) add1(i,q0[j],1);
	if (q1[j]) add1(i,q1[j],1);
}

void insert(int l,int r,int x){
	if (l<=r) tot++,p[tot]=opr(l,r,x);
}

void maketree(int x,int l,int r){
	t[x]=0,mi0[x]=0,mi1[x]=maxn,tag[x]=0,cnt[x]=r-l+1;
	if (l==r) return;
	int mid=(l+r)>>1;
	maketree(x<<1,l,mid),maketree(x<<1|1,mid+1,r);
}

void doit(int x,int v){
	if (v<=mi0[x]) return;
	t[x]+=(v-mi0[x])*cnt[x];
	mi0[x]=v;
}

void downtag(int x,int l,int r){
	doit(x,tag[x]);
	if (l<r){
		Max(tag[x<<1],tag[x]);
		Max(tag[x<<1|1],tag[x]);
	}
	tag[x]=0;
}

void upd(int x){
	int l=x<<1,r=x<<1|1;
	t[x]=t[l]+t[r];
	mi0[x]=min(mi0[l],mi0[r]);
	mi1[x]=min(mi1[l],mi1[r]);
	if (mi0[x]^mi0[l]) Min(mi1[x],mi0[l]);
	if (mi0[x]^mi0[r]) Min(mi1[x],mi0[r]);
	cnt[x]=(mi0[l]==mi0[x])*cnt[l]+(mi0[r]==mi0[x])*cnt[r];
}

void change(int x,int l,int r,int ll,int rr,int v){
	if (tag[x]) downtag(x,l,r);
	if (l>rr||r<ll||mi0[x]>=v) return;
	if (ll<=l&&r<=rr&&mi1[x]>v){
		tag[x]=max(tag[x],v),downtag(x,l,r); 
		return;
	}
	int mid=(l+r)>>1;
	change(x<<1,l,mid,ll,rr,v);
	change(x<<1|1,mid+1,r,ll,rr,v);
	upd(x);
}

LL find(int x,int l,int r,int ll,int rr){
	if (tag[x]) downtag(x,l,r);
	if (l>rr||r<ll) return 0;
	if (ll<=l&&r<=rr) return t[x];
	int mid=(l+r)>>1;
	return find(x<<1,l,mid,ll,rr)+find(x<<1|1,mid+1,r,ll,rr);
}

int main(){
	scanf("%d",&n);
	for(i=1;i<maxn;i++) p0[i]=p1[i]=maxn,q0[i]=q1[i]=0;
	for(i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		add0(a[i],i),mx=max(mx,a[i]);
	}
	for(i=1;i<=mx;i++) {
		u0[i]=u1[i]=maxn,v0[i]=v1[i]=0;
		for(j=i;j<=mx;j+=i) add2(i,j);
		insert(u0[i]+1,v0[i]-1,i);
		insert(1,v1[i]-1,i);
		insert(u1[i]+1,n,i);
	}
	sort(p+1,p+1+tot,cmp);
	maketree(1,1,n); j=1;
	for(i=1;i<=n;i++){
		for(;j<=tot&&p[j].l==i;j++) 
			change(1,1,n,p[j].l,p[j].r,p[j].x);
		ans+=find(1,1,n,i,n);
	}
	printf("%lld
",ans);
}