「Codeforces 788E」New Task

发表于 | | 阅读次数:
字数统计: 1.2k 字

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%