184、小蓝的消除游戏.docx

解题思路

题目大意

多组询问，求区间中各个属性值的最大下标减最小下标的差之和。

暴力

考虑直接暴力，可以遍历一遍询问的区间，记录每个出现在该区间中属性值?xx?的最大下标?maxidx?和最小下标?minidx。对区间中出现的各个不同属性值?xx?对答案的贡献?_xmaxidx?minidx?求和即可。时间复杂度)O(nq)，不足以通过此题。

由于是区间询问，很容易想到莫队算法。

莫队

莫队算法是一个经典的处理区间询问问题的算法，对于序列上的区间询问问题，如果从区间?[l,r]?的答案能够?O(1)?扩展到?[l?1,r],[l+1,r],[l,r+1],[l,r?1]（即与?[l,r]?相邻的四个区间）的答案，那么可以在?O(n\sqrt{n})O(nn)?的复杂度内求出所有询问的答案。具体操作时对于所有的询问区间[l,r],以?l?所在块的编号为第一关键字，r?为第二关键字从小到大排序，顺序处理每个询问，暴力从上一个区间的答案转移到下一个区间答案（一步一步移动即可）。

在本题中相邻区间的答案该怎样转移呢？

当区间的某个端点移动了一个位置时，显然只会影响到一种属性值对答案的贡献，即新加入区间（或离开区间）的魔法水晶的属性值?t。

为每一个属性值开一个双端队列。每次区间移动，我们先把属性值?t?原本对答案的贡献减去，然后进行下述操作：

若区间左端点右移，则将双端队列的最左边元素删除。

若区间左端点左移，则将新的左端点下标插入到双端队列最左边。

若区间右端点右移，则将新的右端点下标插入到双端队列最右边。

若区间右端点左移，则将双端队列的最右边元素删除。

则?t?对答案的贡献即双端队列最右边的元素值减最左边的元素值，再加上?t?对答案的新贡献即可。

用上述方法，可以用?O(1)?的时间复杂度转移出相邻区间的答案。所以使用莫队算法可以在?O(nn)?的复杂度内求出所有询问的答案。

算法流程

离线所有询问，按左端点的块号为第一关键字从小到大，右端点值为第二关键字奇块从小到大、偶块从大到小的顺序将所有询问区间进行排序。

初始化莫队，当前区间是[1,1]?时，答案是?0。

枚举排序后的每个询问，暴力移动区间的端点顺序求解各个询问。

输出答案。

AC_Code

C++

#includebits/stdc++.h

usingnamespacestd;

usingLL=longlong;

constintN=4e5+5;

structasdf{

intl,r,bel,id;

booloperator(constasdfa)const

{

if(bel!=a.bel)returnbela.bel;

if(bel1)returnra.r;

returnra.r;

}

}q[N];

intn,m,a[N],blk;

LLans[N];

dequeinte[N];

intmain()

{

cin.tie(0);

cout.tie(0);

ios::sync_with_stdio(0);

cinn;blk=sqrt(n);

for(inti=1;i=n;++i)cina[i];

cinm;

for(inti=1,x,y;i=m;++i)

{

cinxy;

q[i]={x,y,(x-1)/blk+1,i};

}

sort(q+1,q+1+m);

intl=1,r=1;

LLnw=0;

e[a[1]].push_back(1);

for(inti=1;i=m;++i)

{

while(lq[i].l)

{

l--;

if(!e[a[l]].empty())nw=nw+e[a[l]].front()-l;

e[a[l]].push_front(l);

}

while(rq[i].r)

{

r++;

if(!e[a[r]].empty())nw=nw-e[a[r]].back()+r;

e[a[r]].push_back(r);

}

while(lq[i].l)

{

e[a[l]].pop_front();

if(!e[a[l