【CodeForces】788E New task

【题意】n个数，每个数有附加属性0或1，初始全为1。m个操作，每个操作可以改变一个数字的属性为0或1。对于每次操作后的序列求有多少子序列满足要求：5个数字，中间3个数相等且属性为1，左右两个数小于等于中间三个数且属性任意。n,m<=10^5。

【算法】线段树

【题解】朴素的算法，奇妙的使用>_<！

离散化后，e[i]为i的权值。

用a[i]记录比1~i-1中≤e[i]的数的个数，b[i]表示i+1~n中≤e[i]的数的个数。

a和b可以用树状数组维护，树状数组下标为离散化后的权值，按顺序加入和查询即可。

那么，显然中间3个数是关键。

离散化后对于每个权值(1~p)建线段树(1~n)，根编号为权值，对于线段树x维护下列值：

S[k]表示子树k代表区间内x的数量。

B[k]表示子树k代表区间内只选择第二个点的方案数。

D[k]表示子树k代表区间内只选择第四个点的方案数。

BC[k]表示只选择第二三个点的方案数。

CD[k]表示只选择第三四个点的方案数。

BCD[k]表示选择第二三四个点的方案数。

update的方法见代码。

参考CF用户MemorySlices的代码，非常漂亮，就直接贴了。

#include<bits/stdc++.h>

#define N 100005

#define M 3000005

#define L(__) (son[__][0])

#define R(__) (son[__][1])

#define oo (1<<30)

using namespace std;

const int mo=1e9+;

int n,m,w[N],lw,a[N],b[N],tr[N],e[N],B[M],BC[M],BCD[M],CD[M],D[M],S[M],son[M][],len,ans;

int lowbit(int x){ return x&(-x);}

void modify(int x){ while(x<=n) tr[x]++,x+=lowbit(x);}

int query(int x){ int s=; while(x) s+=tr[x],x-=lowbit(x); return s;}

void update(int t)

{

    S[t]=(S[L(t)]+S[R(t)])%mo;

    B[t]=(B[L(t)]+B[R(t)])%mo;

    D[t]=(D[L(t)]+D[R(t)])%mo;

    BC[t]=(BC[L(t)]+BC[R(t)]+1LL*B[L(t)]*S[R(t)])%mo;

    CD[t]=(CD[L(t)]+CD[R(t)]+1LL*S[L(t)]*D[R(t)])%mo;

    BCD[t]=(BCD[L(t)]+BCD[R(t)]+1LL*BC[L(t)]*D[R(t)]+1LL*B[L(t)]*CD[R(t)])%mo;

}

void MOD(int t,int l,int r,int s,int x,int y,int d)

{

    int mid=(l+r)>>,k=(s>mid);

    if(l==r){ B[t]=x,D[t]=y,S[t]+=d; return ;}

    if(!son[t][k]) son[t][k]=++len;

    if(!k) MOD(L(t),l,mid,s,x,y,d);

    else MOD(R(t),mid+,r,s,x,y,d);

    update(t);

}

int main()

{

    int i,op,x;

    scanf("%d",&n);

    for(i=;i<=n;i++) scanf("%d",&e[i]),w[++lw]=e[i];

    sort(w+,w+lw+),lw=unique(w+,w+lw+)-w-;

    for(i=;i<=n;i++) e[i]=lower_bound(w+,w+lw+,e[i])-w;

    memset(tr,,sizeof(tr));

    for(i=;i<=n;i++) a[i]=query(e[i]),modify(e[i]);

    memset(tr,,sizeof(tr));

    for(i=n;i>=;i--) b[i]=query(e[i]),modify(e[i]);

    len=lw;

    for(i=;i<=n;i++){

        ans=(ans-BCD[e[i]]+mo)%mo;

        MOD(e[i],,n,i,a[i],b[i],);

        ans=(ans+BCD[e[i]])%mo;

      }

    scanf("%d",&m);

    while(m--){

        scanf("%d %d",&op,&x);

        ans=(ans-BCD[e[x]]+mo)%mo;

        if(op==)

            MOD(e[x],,n,x,,,-);

        else

            MOD(e[x],,n,x,a[x],b[x],);

        ans=(ans+BCD[e[x]])%mo;

        printf("%d\n",ans);

      }

    return ;

}

更神奇的操作：http://blog.csdn.net/gjghfd/article/details/74897844 留坑

巴特西

【CodeForces】788E New task

最新文章

热门文章