CF1824D LuoTianyi and the Function & 区间历史和模板

LuoTianyi and the Function：

LuoTianyi gives you an array \(a\) of \(n\) integers and the index begins from \(1\) .

Define \(g(i,j)\) as follows:

• When \(i\le j\), \(g(i,j)\) is the largest integer \(x\) that satisfies \(\{a_p:i\le p\le j\}\subseteq\{a_q:x\le q\le j\}\);
• When \(i>j\), \(g(i,j)=0\).

There are \(q\) queries. For each query you are given four integers \(l,r,x,y\) , you need to calculate \(\sum\limits_{i=l}^{r}\sum\limits_{j=x}^{y}g(i,j)\) .

DS 题中算非常简单的。扫描 \(g(i,j)\) 的 \(j\) 那一维，用一个 \(set\) 存每种数最后一次出现的位置，维护一棵线段树，其下标 \(i\) 处维护当前 \(j\) 的 \(g(i,j)\)。插入 \(i\) 和删除 \(las_{a_i}\) 变成简单的区间赋值，而区间赋值可以简单转化为区间加。这样当前 \(j\) 的所有 \(g(\cdot,j)\) 就知道了，将询问差分成 \((l,r,1,x-1)\) 和 \((l,r,1,y)\) 即可离线处理，将线段树改为区间历史和线段树即可。

区间历史和 SNIPPET：

//查询普通和时输出 asks，查询当前的历史和时输出 asks+askhs
struct SGT {
	struct node {ll s,hs,a,d,tim;}t[N<<2];
	void chg(int L,int R,ll v,ll tim,int l,int r,int k){
		if(L>R)return;
		if(L<=l&&r<=R){
			t[k].hs+=(tim-t[k].tim)*t[k].s;
			t[k].s+=v*(r-l+1);
			t[k].a+=v;
			t[k].d+=v*tim;
			t[k].tim=tim;
			return;
		}
		int mid=l+r>>1;
		if(L<=mid)chg(L,R,v,tim,l,mid,k<<1);
		if(R>mid)chg(L,R,v,tim,mid+1,r,k<<1|1);
		t[k].hs+=t[k].s*(tim-t[k].tim);
		t[k].s+=v*(min(r,R)-max(l,L)+1);
		t[k].tim=tim;
	}
	ll asks(int L,int R,ll A,int l,int r,int k){
		if(L<=l&&r<=R)return t[k].s+A*(r-l+1);
		int mid=l+r>>1;ll s=0;
		A+=t[k].a;
		if(L<=mid)s+=asks(L,R,A,l,mid,k<<1);
		if(R>mid)s+=asks(L,R,A,mid+1,r,k<<1|1);
		return s;
	}
	ll askhs(int L,int R,ll A,ll D,ll tim,int l,int r,int k){
		if(L<=l&&r<=R)return t[k].hs+A*(r-l+1)*tim-D*(r-l+1)+t[k].s*(tim-t[k].tim);
		int mid=l+r>>1;ll hs=0;
		A+=t[k].a,D+=t[k].d;
		if(L<=mid)hs+=askhs(L,R,A,D,tim,l,mid,k<<1);
		if(R>mid)hs+=askhs(L,R,A,D,tim,mid+1,r,k<<1|1);
		return hs;
	}
}T;