{CodeForces】788E New task && 汕头市队赛SRM06 D 五色战队

D 五色战队 SRM 06

背景&&描述

        游行寺家里人们的发色多种多样，有基佬紫、原谅绿、少女粉、高级黑、相簿白等。

        日向彼方：吾令人观其气，气成五彩，此天子气也。

        琉璃：我们是不是可以组个五人战队了？

        游行寺家的n个人排成一排。第i个人的发色是Ai。

        能组成战队的条件是：

                那五人假设是第a,b,c,d,e人()，需要满足 

                中间的三人称为有头者，最旁边俩人称为学姐。

                根据字面意思，有头者一定要有头，学姐可以无头。
                反正就是b,c,d这三人一定要有头。

        有着恶趣味的琉璃每次操作会把一个人 变成有头或者无头，

        每次操作后琉璃想知道游行寺家可能产生多少种不同的战队。只要有成员不同,俩战队就是不同的。

 

输入格式

第一行一个整数n，第二行n个整数表示人们的发色。

第三行一个整数m，表示操作数。

接下来有m行，每行第一个数表示操作类型，第二个数表示被操作那人的编号。

类型为1就是把他变无头，类型2就是变有头。

输出格式

每次操作后输出答案，答案对10^9+7取模。。。

样例输入

8

3 4 4 2 4 5 4 1

3

1 5

2 5

1 2

样例输出

1

6

2

数据范围与约定

• 对于100%的数据:

样例解释

第一次操作后可能的战队为{1,2,3,7,8}

第二次操作后可能的战队为{1,2,3,5,7}，{1,2,3,5,8}，{1,2,3,7,8}，{1,2,5,7,8}，{1,3,5,7,8}，{2,3,5,7,8}。

第三次操作后可能的战队为{1,3,5,7,8}，{2,3,5,7,8}

这道题和codechef的原题差不多

题目要求的就是

n个数字中，每个数有数字A和属性B，每次操作将某个点x的属性B改变为0或1，求满足这样要求的子序列的个数：

下标a<b<c<d<e，而Aa<=Ab=Ac=Ad>=Ae且Bb=Bc=Bd=1。

那么每个数左边以及右边小于等于他的数 很显然我们可以用树状数组维护 下标就是值

当然为了方便我们需要将值离散化一波

这样之后 重点就是中间那三个数了 我们可以按值来搞 每个值建一棵线段树

需要维护的信息有（我们设五个点分别为 1 2 3 4 5

sz 及点的个数

A 就是 1 2

C 就是 2 3

AB就是 1 2 3

BC 就是 3 4 5

ABC 就是 1 2 3 4 5

具体怎么算看up咯

跟结点只需要算A C 而A C可以由左边比他小和右边比他小的点的数量得到 这样之后就简单多了 2333

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int M=,N=,mod=1e9+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int sum[N],s[N],ans;

struct node{int w,pos;}e[N];

bool cmp(node a,node b){return a.w<b.w;}

int n,m,cnt,sz;

int L[N],R[N],root[N];

void clear(){memset(sum,,sizeof(sum));}

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

void add(int x){

    while(x<=n){

        sum[x]++;

        x+=lowbit(x);

    }

}

int push_sum(int x){

    int ans=;

    while(x){ans+=sum[x]; x-=lowbit(x);}

    return ans;

}

struct note{

    int l,r,sz;

    int A,C,AB,BC,ABC;

}tr[M];

void up(int x){

    int l=tr[x].l,r=tr[x].r;

    tr[x].sz=(tr[l].sz+tr[r].sz)%mod;

    tr[x].A=(tr[l].A+tr[r].A)%mod;

    tr[x].C=(tr[l].C+tr[r].C)%mod;

    tr[x].AB=(tr[l].AB+tr[r].AB+(LL)tr[l].A*tr[r].sz)%mod;

    tr[x].BC=(tr[l].BC+tr[r].BC+(LL)tr[r].C*tr[l].sz)%mod;

    tr[x].ABC=(tr[l].ABC+tr[r].ABC+(LL)tr[l].A*tr[r].BC+(LL)tr[l].AB*tr[r].C)%mod;

}

void mdf(int& x,int l,int r,int k,int v){

    if(!x) x=++sz;

    if(l==r){

        tr[x].sz=*v;

        tr[x].A=L[k]*v;

        tr[x].C=R[k]*v;

        tr[x].AB=tr[x].BC=tr[x].ABC=;

        tr[x].l=tr[x].r=;

        return ;

    }

    int mid=(l+r)>>;

    if(k<=mid) mdf(tr[x].l,l,mid,k,v);

    else mdf(tr[x].r,mid+,r,k,v);

    up(x);

}

int main()

{

    n=read();

    for(int i=;i<=n;i++) e[i].w=read(),e[i].pos=i;

    sort(e+,e++n,cmp);

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

        if(e[i].w!=e[i-].w) cnt++;

        s[e[i].pos]=cnt;

    }

    clear();

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

        L[i]=push_sum(s[i]);

        add(s[i]);

    }

    clear();

    for(int i=n;i>=;i--){

        R[i]=push_sum(s[i]);

        add(s[i]);

    }

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

        ans=(ans-tr[root[s[i]]].ABC+mod)%mod;

        mdf(root[s[i]],,n,i,);

        ans=(ans+tr[root[s[i]]].ABC)%mod;

    }

    int x,y;

    m=read();

    for(int i=;i<=m;i++){

        x=read(); y=read();

        ans=(ans-tr[root[s[y]]].ABC+mod)%mod;

        mdf(root[s[y]],,n,y,x-);

        ans=(ans+tr[root[s[y]]].ABC)%mod;

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

    }

    return ;

}