P10822

· · 题解

思路

考对于所有操作离线，按照右边边界的大小排序。

对于每一个位置 i，记录 f_j 表示如果第 j 个位置到第 i 个位置的序列是否满足条件（1 表示满足；0 表示不满足。规定当 j>i 时 f_j=0）。

显然，对于 [l,r] 中的合法序列个数位 f_l 到 f_r 中所有与的元素在 i 走到 r 时的历史总和。

然后就是历史和线段树的板子了。

可以使用矩阵乘法。

构造 \begin{bmatrix}b&a&len\end{bmatrix} 分别当前节点表示历史和、但前和、总长度。

当要将 a 加到 b 上时将矩阵乘上：

\begin{bmatrix} 1&0&0\\ 1&1&0\\ 0&0&1 \end{bmatrix}

当要将 a 中异或时：

\begin{bmatrix} 1&0&0\\ 0&-1&0\\ 0&1&1 \end{bmatrix}

然后用线段树维护即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500005;
struct M//矩阵
{
    ll a[3][3];
    inline void mem()
    {
        a[0][0]=0;
        a[1][0]=0;a[1][1]=0;
        a[2][0]=0;a[2][1]=0;a[2][2]=0;
    }
    inline void init()
    {
        a[0][0]=1;
        a[1][0]=0;a[1][1]=1;
        a[2][0]=0;a[2][1]=0;a[2][2]=1;
    }
    inline M operator*(M b)
    {
        M ans;
        ans.a[0][0]=1;
        ans.a[1][0]=a[1][0]+a[1][1]*b.a[1][0];
        ans.a[1][1]=a[1][1]*b.a[1][1];
        ans.a[2][0]=a[2][0]+a[2][1]*b.a[1][0]+b.a[2][0];
        ans.a[2][1]=a[2][1]*b.a[1][1]+b.a[2][1];
        ans.a[2][2]=1;
        return ans;
    }
}A;
struct seg//线段树
{
    ll b,a,len;
    M t;//懒标记
}w[8*N];
struct E
{
    int ne,to;
}e[N];
int he[N],idx,a[N],b[N],l[N],r[N];
ll ans[N];
inline void pushup(int u)//跟新节点信息
{
    w[u].b=w[u<<1].b+w[u<<1|1].b;
    w[u].a=w[u<<1].a+w[u<<1|1].a;
    w[u].len=w[u<<1].len+w[u<<1|1].len;
}
inline void pushdown(int u)//懒标记下传
{
    M t=w[u].t;w[u].t.init();
    w[u<<1].t=w[u<<1].t*t;
    w[u<<1|1].t=w[u<<1|1].t*t;
    ll b,a;
    b=w[u<<1].b+t.a[1][0]*w[u<<1].a+t.a[2][0]*w[u<<1].len;
    a=t.a[1][1]*w[u<<1].a+t.a[2][1]*w[u<<1].len;
    w[u<<1].b=b;w[u<<1].a=a;
    b=w[u<<1|1].b+t.a[1][0]*w[u<<1|1].a+t.a[2][0]*w[u<<1|1].len;
    a=t.a[1][1]*w[u<<1|1].a+t.a[2][1]*w[u<<1|1].len;
    w[u<<1|1].b=b;w[u<<1|1].a=a;
}
void build(int u,int l,int r)
{
    w[u].t.init();
    if(l==r)
    {
        w[u].len=1;
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void mul(int u,int l,int r,int x,int y)//对于每一个节点乘上矩阵A
{
    pushdown(u);
    if(l>=x&&r<=y)
    {
        w[u].t=w[u].t*A;
        w[u].b=w[u].b;
        w[u].a=-w[u].a+w[u].len;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=x)mul(u<<1,l,mid,x,y);
    if(mid<y)mul(u<<1|1,mid+1,r,x,y);
    pushup(u);
}
ll get(int u,int l,int r,int x,int y)//得到区间历史和
{
    pushdown(u);
    if(l>=x&&r<=y)return w[u].b;
    int mid=(l+r)>>1;ll sum=0;
    if(mid>=x)sum+=get(u<<1,l,mid,x,y);
    if(mid<y)sum+=get(u<<1|1,mid+1,r,x,y);
    return sum;
}
void add(int x,int y)
{
    e[++idx].ne=he[x];
    e[idx].to=y;
    he[x]=idx;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>l[i]>>r[i];
        add(r[i],i);
    }
    build(1,1,n);
    A.init();
    for(int i=1;i<=n;i++)
    {
        A.a[1][1]=-1;A.a[2][1]=1;
        mul(1,1,n,b[a[i]]+1,i);//异或
        A.a[1][1]=1;A.a[2][1]=0;
        A.a[1][0]=1;
        pushdown(1);
        w[1].t=w[1].t*A;
        w[1].b=w[1].b+w[1].a;
        w[1].a=w[1].a;//可以将全局操作放进主函数
        A.a[1][0]=0;
        b[a[i]]=i;//跟新last
        for(int j=he[i];j;j=e[j].ne)
            ans[e[j].to]=get(1,1,n,l[e[j].to],i);//处理询问
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
    return 0;
}