【题意】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+7; 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][2],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=0; 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)>>1,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+1,r,s,x,y,d); update(t); } int main() { int i,op,x; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&e[i]),w[++lw]=e[i]; sort(w+1,w+lw+1),lw=unique(w+1,w+lw+1)-w-1; for(i=1;i<=n;i++) e[i]=lower_bound(w+1,w+lw+1,e[i])-w; memset(tr,0,sizeof(tr)); for(i=1;i<=n;i++) a[i]=query(e[i]),modify(e[i]); memset(tr,0,sizeof(tr)); for(i=n;i>=1;i--) b[i]=query(e[i]),modify(e[i]); len=lw; for(i=1;i<=n;i++){ ans=(ans-BCD[e[i]]+mo)%mo; MOD(e[i],1,n,i,a[i],b[i],1); 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==1) MOD(e[x],1,n,x,0,0,-1); else MOD(e[x],1,n,x,a[x],b[x],1); ans=(ans+BCD[e[x]])%mo; printf("%d ",ans); } return 0; }
更神奇的操作：http://blog.csdn.net/gjghfd/article/details/74897844 留坑