P1052 · OFFICIAL SOLUTION

P1052 序列询问官方题解

Gioush OJ · P1052 序列询问

序列询问

【题意简述】

给定一个二进制序列。若当前元素与栈顶相同，则弹出栈顶，否则压入当前元素，由此定义序列的消除结果。

对每次询问 $[l,r]$ ，枚举分割点 $l\leq m<r$ ，分别消除左右两段，再把两个消除结果拼接并继续消除。求所有分割点在拼接以后新消除的元素对数之和。

【数据点 1∼31\sim 31∼3】

【题目描述】

数据范围允许按照定义直接模拟。

【Hint】

对每个分割点分别用栈处理左右两段，再拼接两个栈中的序列。

【解法】

记录拼接后新弹出的元素对数，并对全部分割点求和。时间复杂度为 $\mathcal{O}(qn^2)$ 。

【数据点 4∼94\sim 94∼9】

【题目描述】

需要把单个分割点的计算降至常数时间。

【Hint】

消除结束后的序列中不存在相邻且相同的元素，因此它一定是一个 $0,1$ 交替序列。

【解法】

对每次询问，从左向右维护所有前缀的消除长度，从右向左维护所有后缀的消除长度。加入一个元素时，消除结果的长度只会增加 $1$ 或减少 $1$ 。

预处理完成后，可以在 $\mathcal{O}(1)$ 时间计算一个分割点，单次询问复杂度为 $\mathcal{O}(n)$ ，总时间复杂度为 $\mathcal{O}(qn)$ 。

【数据点 10∼1510\sim 1510∼15】

【题目描述】

需要用一个代数量描述区间消除后的长度。

【Hint】

定义

s_i= \begin{cases} 1,&a_i\equiv i\pmod 2,\\ -1,&a_i\not\equiv i\pmod 2, \end{cases} \qquad P_i=\sum_{j=1}^{i}s_j.

【解法】

先证明下标奇偶性。设当前被消去的两个元素来自原序列中的位置 $x<y$ 。它们在当前序列中相邻，说明原来位于二者之间的 $y-x-1$ 个元素已经全部被成对消去。因此 $y-x-1$ 为偶数， $x,y$ 的奇偶性相反。

被消去的两个元素数值相同、下标奇偶性相反，所以对应的 $s_x,s_y$ 互为相反数。每次消除都不会改变区间内 $s_i$ 的总和。

再考虑最终剩余序列中相邻的两个元素。二者之间的原序列元素同样已经全部被成对消去，所以它们的原下标奇偶性相反；而最终序列不存在相邻且相同的元素，所以它们的数值也相反。数值与下标奇偶性同时改变以后，“二者是否相等”这一关系不变，因此相邻剩余元素对应的 $s_i$ 相同。由此，全部剩余元素对应的 $s_i$ 均同号。

消除前后 $s_i$ 的总和不变，而消除结束后每一项都等于 $1$ 或都等于 $-1$ ，故剩余长度恰好等于这个总和的绝对值：

\left|\operatorname{red}(a_l,\ldots,a_r)\right| = \left|P_r-P_{l-1}\right|.

枚举分割点即可做到 $\mathcal{O}(qn)$ 。

【正解】

【题目描述】

需要对一个询问中的全部分割点同时求和。

【Hint】

对询问 $[l,r]$ ，记

A=P_{l-1},\qquad B=P_r,\qquad X=P_m.

把分割点 $m$ 的贡献写成关于 $A,B,X$ 的绝对值表达式。

【公式】

还需要说明分段消除不会改变最终结果。对任意两个序列 $U,V$ ，先处理 $U$ 后，栈中恰好留下 $\operatorname{red}(U)$ ；继续把 $V$ 依次送入同一个栈，与把 $U\circ V$ 从头送入栈完全相同。因此

\operatorname{red}\left( \operatorname{red}(U)\circ\operatorname{red}(V) \right) = \operatorname{red}(U\circ V).

左右两段消除后的长度分别为 $\lvert X-A\rvert$ 与 $\lvert B-X\rvert$ ，拼接并继续消除后的长度因而等于整个区间的消除长度 $\lvert B-A\rvert$ 。每次新消除恰好删去两个元素，所以

f(m) = \dfrac{ \lvert X-A\rvert+\lvert B-X\rvert-\lvert B-A\rvert }{2}.

定义

G(L,R,x)=\sum_{i=L}^{R}\lvert P_i-x\rvert.

对 $l\leq m<r$ 求和，得到

\operatorname{Ans}(l,r) = \dfrac{ G(l,r-1,P_{l-1})+G(l,r-1,P_r) -(r-l)\lvert P_r-P_{l-1}\rvert }{2}.

【离线计算】

每个原询问被拆成两个形如 $G(L,R,x)$ 的离线询问。

将位置 $i$ 按照 $P_i$ 从小到大排序，将全部离线询问按照 $x$ 从小到大排序。扫描询问时，把所有满足 $P_i\leq x$ 的位置加入数据结构。使用两棵树状数组，分别维护这些位置的数量与 $P_i$ 之和。

记区间内 $P_i\leq x$ 的数量与和为 $C_{\leq},S_{\leq}$ ，全部元素的数量与和为 $C,S$ ，则

\begin{aligned} G(L,R,x) ={}&xC_{\leq}-S_{\leq}\\ &+(S-S_{\leq})-x(C-C_{\leq}). \end{aligned}

前两项统计不大于 $x$ 的部分，后两项统计大于 $x$ 的部分。全部元素的和 $S$ 可以由 $P_i$ 的普通前缀和求出。

【复杂度分析】

单组测试数据的时间复杂度为 $\mathcal{O}((n+q)\log n)$ ，空间复杂度为 $\mathcal{O}(n+q)$ 。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/244Name:query.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 50001011#define MAXQ 100001012using namespace std;13int n,q,Line[MAXN],Pre[MAXN],Position[MAXN],Left[MAXN],Right[MAXN];14long long IndexSum[MAXN],Cnt[MAXN],Sum[MAXN],Part[MAXQ],Ans[MAXN];15struct ask{16    int Left,Right,Value,Id;17}Ask[MAXQ];18bool cmpa(int x,int y){return Pre[x]<Pre[y];}19bool cmpb(ask x,ask y){return x.Value<y.Value;}20int lowbit(int x){return x&-x;}21void Modify(int x,long long Val,long long C[]){22    for(;x<=n;x+=lowbit(x)) C[x]+=Val;23}24long long Query(int x,long long C[]){25    long long Ret=0;26    for(;x;x-=lowbit(x)) Ret+=C[x];27    return Ret;28}29void Solve(){30    static int LastN=0;31    scanf("%d%d",&n,&q);32    int ClearN=max(n,LastN);33    memset(Cnt,0,sizeof(long long)*(ClearN+1));34    memset(Sum,0,sizeof(long long)*(ClearN+1));35    Pre[0]=IndexSum[0]=0;36    LastN=n;37    for(int i=1;i<=n;i++){38        scanf("%d",&Line[i]);39        Pre[i]=Pre[i-1]+(Line[i]==(i&1)?1:-1);40        IndexSum[i]=IndexSum[i-1]+Pre[i];41        Position[i]=i;42    }43    int Total=0;44    for(int i=1;i<=q;i++){45        scanf("%d%d",&Left[i],&Right[i]);46        Ask[++Total]={Left[i],Right[i]-1,Pre[Left[i]-1],i*2-1};47        Ask[++Total]={Left[i],Right[i]-1,Pre[Right[i]],i*2};48    }49    sort(Position+1,Position+n+1,cmpa);50    sort(Ask+1,Ask+Total+1,cmpb);51    int Now=1;52    for(int i=1;i<=Total;i++){53        while(Now<=n&&Pre[Position[Now]]<=Ask[i].Value){54            Modify(Position[Now],1,Cnt);55            Modify(Position[Now],Pre[Position[Now]],Sum);56            Now++;57        }58        int l=Ask[i].Left,r=Ask[i].Right;59        long long CntLow=Query(r,Cnt)-Query(l-1,Cnt);60        long long SumLow=Query(r,Sum)-Query(l-1,Sum);61        long long Count=r-l+1,SumAll=IndexSum[r]-IndexSum[l-1];62        Part[Ask[i].Id]=1ll*Ask[i].Value*CntLow-SumLow+63                        SumAll-SumLow-1ll*Ask[i].Value*(Count-CntLow);64    }65    for(int i=1;i<=q;i++){66        Ans[i]=(Part[i*2-1]+Part[i*2]-67                1ll*(Right[i]-Left[i])*abs(Pre[Right[i]]-Pre[Left[i]-1]))/2;68        printf("%lld\n",Ans[i]);69    }70}71int main(){72    int c,T;73    scanf("%d%d",&c,&T);74    while(T-->0) Solve();75    return 0;76}