「Codeforces 788E」New Task

Description

题目链接:Codeforces 788E

在第 228 届国际 Uzhlyandian 战略比赛中,各队均由 $5$ 名队员组成。

Masha 是新的国防部长,这位部长的主要职责是计算军队的效率。军队由 $n$ 名士兵组成,标号为 $1$ 到 $n$,第 $i$ 个士兵的技能值为 $a_i$。

这个队伍将由 $3$ 名队员和 $2$ 名助手组成,队员的技能值是相同的,助手的技能值不大于队员的技能值。对于 Masha 而言,助手应该分别站在队员的最左侧和最右侧。形式化地说,一个队伍有 $5$ 名士兵,下标为 $i,j,k,l,p$ 满足 $1\le i<j<k<l<p\le n$ 并且 $a_i\le a_j=a_k=a_l\ge a_p$。

军队的效率是 Masha 可以选择的不同队伍的数量。两个队伍是不同的当且仅当有至少一个人不同。

最初,所有的士兵都可以成为队员。由于某些原因,有时一些士兵不能成为队员或可以成为队员;但是所有士兵在任何时候都可以成为助手。Masha 有 $m$ 次操作,每次可以令第 $x$ 个士兵可以成为队员或不能。她需要你求出每次操作后可以选择的队伍数量,答案对 $10^9+7$ 取模。

数据范围:$1\le n,m\le 10^5$,$1\le a_i\le 10^9$


Solution

由于每个士兵都可以成为助手,我们设 $pre_i$ 和 $suf_i$ 分别表示 $i$ 左边和右边比 $a_i​$ 小的数的个数。可以离散化后用树状数组求出。

由于有动态修改,并且区间看起来是可以合并的,我们考虑用线段树维护。

由于第 $1,5$ 个人无关紧要的,我们只关心中间的 $3​$ 个人。又因为每个权值都是独立的,因此对每种权值建立一棵线段树(当然要采用动态开点)。

每个节点维护 $6$ 个值(其中 $p$ 为根节点,$[l,r]$ 为根节点维护的区间,$ls,rs$ 为左右儿子):

变量 含义 单点初值 转移
$A$ 选择第 $1$ 个人的方案数 $pre_l$ $A_p=A_{ls}+A_{rs}$
$B$ 选择第 $2$ 个人的方案数 $1$ $B_p=B_{ls}+B_{rs}$
$C$ 选择第 $3$ 个人的方案数 $suf_r$ $C_p=C_{ls}+C_{rs}$
$AB$ 选择第 $1,2$ 个人的方案数 $0$ $AB_p=AB_{ls}+AB_{rs}+A_{ls}\cdot B_{rs}$
$BC$ 选择第 $2,3$ 个人的方案数 $0$ $BC_p=BC_{ls}+BC_{rs}+B_{ls}\cdot C_{rs}$
$ABC$ 选择第 $1,2,3$ 个人的方案数 $0$ $ABC_p=ABC_{ls}+ABC_{rs}+AB_{ls}\cdot C_{rs}+A_{ls}\cdot BC_{rs}$

具体实现见代码。

时间复杂度:$O((n+m)\log n)$(注意空间复杂度和主席树类似)


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=1e5+5,M=N*20;
const int mod=1e9+7;
int n,m,tot,a[N],b[N],pre[N],suf[N];

void upd(int &x,int y) {
(x+=y)>=mod&&(x-=mod);
}
struct Bit {
int b[N];
void init() {
memset(b,0,sizeof(b));
}
void modify(int x,int v) {
for(;x<=n;x+=x&-x) b[x]+=v;
}
int query(int x) {
int ans=0;
for(;x;x^=x&-x) ans+=b[x];
return ans;
}
} bit;
struct Segment {
int rt[N],ls[M],rs[M],A[M],B[M],C[M],AB[M],BC[M],ABC[M];
int plus(int x,int y) {
int c=x+y;
return c>=mod?c-mod:c;
}
int mul(int x,int y) {
return 1LL*x*y%mod;
}
void pushup(int p) {
int l=ls[p],r=rs[p];
A[p]=plus(A[l],A[r]);
B[p]=plus(B[l],B[r]);
C[p]=plus(C[l],C[r]);
AB[p]=plus(plus(AB[l],AB[r]),mul(A[l],B[r]));
BC[p]=plus(plus(BC[l],BC[r]),mul(B[l],C[r]));
ABC[p]=plus(plus(ABC[l],ABC[r]),plus(mul(A[l],BC[r]),mul(AB[l],C[r])));
}
void modify(int x,int &p,int l,int r,int v) {
if(!p) p=++tot;
if(l==r) {
A[p]=v*pre[x];
B[p]=v;
C[p]=v*suf[x];
return;
}
int mid=(l+r)>>1;
if(x<=mid) modify(x,ls[p],l,mid,v);
else modify(x,rs[p],mid+1,r,v);
pushup(p);
}
} seg;

void init() {
std::sort(b+1,b+n+1);
int sz=std::unique(b+1,b+n+1)-(b+1);
for(int i=1;i<=n;++i) a[i]=std::lower_bound(b+1,b+sz+1,a[i])-b;
bit.init();
for(int i=1;i<=n;++i) pre[i]=bit.query(a[i]),bit.modify(a[i],1);
bit.init();
for(int i=n;i>=1;--i) suf[i]=bit.query(a[i]),bit.modify(a[i],1);
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i];
init();
for(int i=1;i<=n;++i) seg.modify(i,seg.rt[a[i]],1,n,1);
int ans=0;
for(int i=1;i<=n;++i) upd(ans,seg.ABC[seg.rt[i]]);
for(scanf("%d",&m);m--;) {
int opt,x;
scanf("%d%d",&opt,&x);
int &rt=seg.rt[a[x]];
upd(ans,mod-seg.ABC[rt]);
seg.modify(x,rt,1,n,opt-1);
upd(ans,seg.ABC[rt]);
printf("%d\n",ans);
}
return 0;
}
0%