首先考虑贡献如何算?

比如1 2 3 4 5 2 3 4,很显然的一个算就是把2 3 4去掉,然后只求1 2 3 4 5的贡献.

考虑i以及相邻的一段的贡献,很显然i的贡献就是相邻一段的长度,比如说1 2 3,1的贡献是1,2的贡献是2,3的贡献是3.

知道贡献怎么算了,下面就分为几步解决这个问题.

第一步:离线

将查询离线,在线不是很好解决这个问题,离线的好处就是我能更新到哪就询问到哪.类似于存版本之类的.具体就是对于每个$rr$查询$[l,r][l,r]$的贡献.

第二步:算贡献

如何算贡献,考虑把现在的下标放到线段树上做下标,那么假如说我连续的一段长度为$44$,现在的位子在$pospos$,那么我对于区间$[pos-4+1,pos][pos-4+1,pos]$的贡献是不是都是1,那么就是一个区间+1,线段树区间+罢了.

第三步:去重

假如我现在是数组,我前面有它的子集例如啥的,对答案有影响吗?有,当然有,那么我怎么去消除它呢,注意！我们每次计算的都是一个点对于前面的值的贡献,那么消除的时候肯定也是出现了下一个相同的点的时候消除.例如:前面存在,假设我前三个已经去重了啊,那么我现在是$44$,我前面有$1,2,31,2,3$也就是我在里面,那么前面那个$44$对于它所在贡献区间的值是不是该全部消除,因为它不可能对后面产生贡献了,因为存在贡献的都可以被比它后面的代替.假如反过来呢?前面是,后面是,很显然的一件事,前面的对于前面的所作的贡献是不能被后面代替的,那么我们要保留前面的区间,但是呢,也要消除$44$对于的贡献,因为我前面的查询都查完了,价值更新在后面一定是没错的.这步在代码里如何实现呢?首先对于每个值对于区间的贡献我们都用一个$vectorvector$存起来,存它前面连续的区间大小,它对于前面的连续区间的贡献都是$11$,然后针对于第一种去重,我们这个去重区间,我不一定是去一个地方的重复对吧?那么我每次都是去掉前面没删除完的区间贡献就好了,对于第二种去重,我们得保留我现在贡献不了的那些值,记录一下,下次再去.

最后

很用心的一篇题解,虽然绝对没人看,最近状态好差...

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e6+5;

int nt[N];//这个位子上上次删除到哪里了.<就是第二种去重,计算保留了多少贡献>
 
struct Seg{
	int l,r;ll lz,sum;
}Tr[N<<2];

void pushup(int u)
{
	Tr[u].sum=Tr[u<<1].sum+Tr[u<<1|1].sum;
}

void pushdown(int u)
{
	if(Tr[u].lz!=0)
	{
		Tr[u<<1].sum+=Tr[u].lz*(Tr[u<<1].r-Tr[u<<1].l+1);
		Tr[u<<1|1].sum+=Tr[u].lz*(Tr[u<<1|1].r-Tr[u<<1|1].l+1);
		Tr[u<<1].lz+=Tr[u].lz;
		Tr[u<<1|1].lz+=Tr[u].lz;
		Tr[u].lz=0;
	}
}

void change(int u,int L,int R,int val)
{
	if(Tr[u].l>R||Tr[u].r<L)	return;
	if(Tr[u].l>=L&&Tr[u].r<=R)
	{
		Tr[u].sum+=1ll*(Tr[u].r-Tr[u].l+1)*val;
		Tr[u].lz+=val;
		return;
	}
	pushdown(u);
	change(u<<1,L,R,val);
	change(u<<1|1,L,R,val);
	pushup(u);
}

void build(int u,int L,int R)
{
	Tr[u].l=L,Tr[u].r=R,Tr[u].sum=0,Tr[u].lz=0;
	if(L==R)	return;
	int mid=(L+R)>>1;
	build(u<<1,L,mid);
	build(u<<1|1,mid+1,R);
}

ll query(int u,int L,int R)
{
	if(Tr[u].l>R||Tr[u].r<L)	return 0;
	if(Tr[u].l>=L&&Tr[u].r<=R)	return Tr[u].sum;
	pushdown(u);
	return query(u<<1,L,R)+query(u<<1|1,L,R);
}

int ql[N],qr[N],pre[N],a[N];
vector<int>id[N],w[N];
ll ans[N];

int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	build(1,1,n);
	a[0]=-2;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]==a[i-1]+1)	pre[i]=pre[i-1];
		else				pre[i]=i;
	}
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&ql[i],&qr[i]);
		id[qr[i]].push_back(i);
	}
	for(int i=1;i<=n;i++)
	{
		change(1,pre[i],i,1);
		while((int)w[a[i]].size())
		{
			int x=w[a[i]].back();
			if(x-pre[x]<=i-pre[i])//第一种去重,我可以全部去掉的情况.
			{
				if(nt[x])	change(1,nt[x],x,1);//把上次删除的补回来.
				change(1,pre[x],x,-1);//这次全删了. 
				w[a[i]].pop_back();
			}
			else//第二种我不能全部去掉. 
			{
				if(nt[x])	change(1,nt[x],x,1);//把上次删除的补回来.
				change(1,x-(i-pre[i]+1)+1,x,-1);
				nt[x]=x-(i-pre[i]+1)+1;
				break;
			} 
		}
		w[a[i]].push_back(i);
		for(int x:id[i])	ans[x]=query(1,ql[x],qr[x]);
	}
	for(int i=1;i<=q;i++)
		printf("%lld\n",ans[i]);
	return 0;
}