【SRM-06 D】五色战队&&【codeforces 788E】 New task

原题链接：788E - New task

Description

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

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

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

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

能组成战队的条件是：

那五人假设是第a,b,c,d,e人( $a<b<c<d<e$ )，需要满足 $A_{a}leq A_{b} =A_{c}=A_{d}geq A_{e}$

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

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

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

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

Input

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

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

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

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

Output

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

Sample Input

8
3 4 4 2 4 5 4 1
3
1 5
2 5
1 2

Sample Output

1
6
2

HINT

对于100%的数据: $1leq n,mleq 10^5 ,1leq A_{i}leq 10^9$

扔在最前面的碎碎念：

一开始真的不知道怎么写……于是盯着别人的代码研究了好久。在这道题上卡了一个上午……最后发现数组开小了（那一刻有种想打死自己的冲动。通过后又发现时间和空间都跟标程差很多……想了想建树的方式好像可以优化？于是改了一波。最后的代码跑得跟标程差不多快>_<敲开心。

子序列要求： $a<b<c<d<e$ 且 $A_{a}leq A_{b} =A_{c}=A_{d}geq A_{e}$ 。

大体思路就是：离散化→树状数组预处理出L、R数组→对每个值建一棵子线段树→在子线段树上进行操作。

在离散化时可以处理的信息：1.num[i]：第i个点离散化后的数值，2.s[i]：值为i的点数，3.p[i]：第i个点在1~s[num[i]]中的位置。

利用树状数组预处理的信息：1.L[i]：在第i个点左边且数值不大于点i的数值的点数，2.R[i]：在第i个点右边且数值不大于点i的数值的点数。

子线段树上的结点需要维护这几个信息：1.l&r：左右儿子，2.sz：区间内点数（即可以作为有头者的点数），3.s[1]：区间内a,b的方案数，4.s[2]：区间内a,b,c的方案数，5.s[3]：区间内a,b,c,d,e的方案数，6.s[4]：区间内c,d,e的方案数，7.s[5]：区间内d,e的方案数。s数组可由左右儿子的信息合并得到。

其余的详见代码=v=（其实只是因为我懒）

  1 #include<cstdio>
  2 #include<algorithm> 
  3 #include<cstring>
  4 #define LL long long
  5 using namespace std;
  6 const int N=1e5+10;
  7 const int mod=1e9+7;
  8 int n,m,cnt,sum,x,y,last;
  9 int num[N],t[N],L[N],R[N],root[N],s[N],p[N],ans;
 10 struct node{int w,pos;}a[N];
 11 struct tree{int l,r,sz,s[6];}tr[N*10];
 12 int read()
 13 {
 14     int x=0,f=1;char c=getchar();
 15     while(c<'0'||c>'9'){if(x=='-')f=-1;c=getchar();}
 16     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 17     return x*f;
 18 }
 19 bool cmp(node a,node b){return a.w==b.w?a.pos<b.pos:a.w<b.w;}
 20 int lowbit(int x){return x&(-x);}
 21 void insert(int x)
 22 {
 23     while(x<=n)
 24     {
 25         t[x]++;
 26         x+=lowbit(x);
 27     }
 28 }
 29 int query(int x)
 30 {
 31     int ans=0;
 32     while(x){ans+=t[x];x-=lowbit(x);}
 33     return ans;
 34 }
 35 void up(int x)
 36 {
 37     int l=tr[x].l,r=tr[x].r;
 38     tr[x].sz=(tr[l].sz+tr[r].sz)%mod;
 39     tr[x].s[1]=(tr[l].s[1]+tr[r].s[1])%mod;
 40     tr[x].s[5]=(tr[l].s[5]+tr[r].s[5])%mod;
 41     tr[x].s[2]=(tr[l].s[2]+tr[r].s[2]+(LL)tr[l].s[1]*tr[r].sz)%mod;
 42     tr[x].s[4]=(tr[l].s[4]+tr[r].s[4]+(LL)tr[l].sz*tr[r].s[5])%mod;
 43     tr[x].s[3]=(tr[l].s[3]+tr[r].s[3]+(LL)tr[l].s[1]*tr[r].s[4]+(LL)tr[l].s[2]*tr[r].s[5])%mod;
 44     //LL!!! 
 45 }
 46 void change(int &x,int l,int r,int pos,int v)
 47 {
 48     if(x==0)x=++sum;
 49     if(l==r)
 50     {
 51         tr[x].sz=v*1;
 52         tr[x].s[1]=v*L[pos];
 53         tr[x].s[5]=v*R[pos];
 54         tr[x].s[2]=tr[x].s[3]=tr[x].s[4]=0;
 55         tr[x].l=tr[x].r=0;
 56         return;
 57     }
 58     else
 59     {
 60         int mid=(l+r)>>1;
 61         if(p[pos]<=mid)change(tr[x].l,l,mid,pos,v);
 62         else change(tr[x].r,mid+1,r,pos,v);
 63         up(x);
 64     }
 65 }
 66 int main()
 67 {
 68     n=read();
 69     for(int i=1;i<=n;i++)
 70         a[i].w=read(),a[i].pos=i;
 71     sort(a+1,a+n+1,cmp);
 72     for(int i=1;i<=n;i++)
 73     {
 74         if(a[i].w!=a[i-1].w)
 75         {
 76             if(cnt)s[cnt]=i-1-last;
 77             last=i-1;
 78             cnt++;
 79         }
 80         num[a[i].pos]=cnt;
 81         p[a[i].pos]=i-last;
 82     }
 83     s[cnt]=n-last;
 84     for(int i=1;i<=n;i++)
 85         L[i]=query(num[i]),insert(num[i]);
 86     memset(t,0,sizeof(t));
 87     for(int i=n;i>=1;i--)
 88         R[i]=query(num[i]),insert(num[i]);
 89     for(int i=1;i<=n;i++)
 90     {
 91         ans=(ans-tr[root[num[i]]].s[3]+mod)%mod;
 92         change(root[num[i]],1,s[num[i]],i,1);
 93         ans=(ans+tr[root[num[i]]].s[3])%mod;
 94     }
 95     m=read();
 96     for(int i=1;i<=m;i++)
 97     {
 98         x=read();y=read();
 99         ans=(ans-tr[root[num[y]]].s[3]+mod)%mod;
100         change(root[num[y]],1,s[num[y]],y,x-1);
101         ans=(ans+tr[root[num[y]]].s[3])%mod;
102         printf("%d
",ans);
103     }
104     return 0;
105 }

View Code