[BZOJ 1145] [CTSC2008] 图腾totem

Posted on | In , | Views:

题目链接

BZOJ 1145

做法

我们用一个四个数字来表示这个四元组的相对大小关系。
比如说闪电图腾我们就定义为$1342$
山峰图腾表示为$1243$或$1432$
现在我们要求的就是$f(1342)-f(1243)-f(1432)$
以下式子中的$X$表示任意

我们先用树状数组求出两个数组$l[i],r[i]$，分别表示$i$这个点左边比我小的点的个数，右边比我小的点的个数。

对于求$f(1X)$
这个非常方便，对于每个点，贡献为$\binom{n-i-r[i]}{3}$

对于求$f(1234)$
我们在$3$处统计答案，对于每个点，贡献为$(n-i-r[i])*\binom{l[i]}{2}$

对于$f(1X2X)$
我们在$2$处统计答案。
可以发现每个点的贡献就是$f(132)*(n-i-r[i])$
现在我们考虑求$f(132)$,
$f(132)=(f(132)+f(312)+f(123)+f(213))-(f(312)+f(123)+f(213))$
都是在最后一个位置上统计答案。
对于前一个括号，实际上就是从前面找两个数，有一个小于我就行了，答案为$\binom{l[i]}{2}+l[i]*(i-1-l[i])$
而后面一个括号，第二个数小于我，第一个数随便，也就是$\sum\limits_{j=1}^{i-1}(j-1)*[a[j]<a[i]]$，树状数组维护就好了。

对于$f(13XX)$
在$3$处统计答案。
同样可以发现答案等同于$f(132)*(n-i-r[i])$
与上面不同的是，这次统计答案的位置在$3$.
$f(132)=(f(132)+f(312)+f(321))-(f(312)+f(321))$
都是在$3$所在位置统计答案。
对于前一个括号，发现$2$一定在$3$右侧，而$1$的位置则随意，那么答案就是$\sum\limits_{j=i+1}^{n}(a[j]-1)*[a[j]<a[i]]$，同样可以树状数组维护。
而后面一个括号，实际上就是$f(3XX)=\binom{r[i]}{2}$

以上就是每种情况下每个点的答案，我们对于每种情况扫一下所有点就好了。
复杂度$O(n*logn)$

代码

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
86
87
88
89
90
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (200005)
using namespace std;
int n; 
int l[N],r[N],a[N],T[N];
const int P=16777216;
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
inline int Inc(int a,int b){
    return (a+b>=P)?(a+b-P):(a+b);
}
inline void add(int x,int y){
    for (int i=x;i<=n;i+=i&-i) T[i]=Inc(T[i],y);
} 
inline int query(int x){
    int ret=0;
    for (int i=x;i;i-=i&-i) ret=Inc(ret,T[i]);
    return ret;
}
inline int work1(){ //1*2*
    int ans=0,tt=0;
    memset(T,0,sizeof(T));
    for (int i=1;i<=n;i++){
        tt=Inc(1ll*l[i]*(l[i]-1)/2%P,1ll*l[i]*(i-1-l[i])%P);
        tt=Inc(tt,P-query(a[i]));
        ans=Inc(ans,1ll*tt*(n-i-r[i])%P);
        add(a[i],i-1);
    } 
    return ans;
}
inline int work2(){ //1***
    int ans=0;
    memset(T,0,sizeof(T));
    for (int i=1;i<=n;i++){
        int tt=n-i-r[i];
        if (tt>=3){
            ans=Inc(ans,(1ll*tt*(tt-1)*(tt-2)/6)%P);
        }
    }
    return ans;
}
inline int work3(){ //13** 
    int ans=0,tt=0;
    memset(T,0,sizeof(T));
    for (int i=n;i>=1;i--){
        int tt=query(a[i]);
        tt=Inc(tt,P-1ll*r[i]*(r[i]-1)/2%P);
        ans=Inc(ans,1ll*tt*(n-r[i]-i)%P);
        add(a[i],a[i]-1);
    }
    return ans;
}
inline int work4(){ //1234
    int ans=0;
    memset(T,0,sizeof(T));
    for (int i=1;i<=n;i++){
        ans=Inc(ans,1ll*query(a[i])*(n-i-r[i])%P);
        add(a[i],l[i]);
    }    
    return ans;
} 
int main(){
    read(n);
    for (int i=1;i<=n;i++){
        read(a[i]);
        l[i]=query(a[i]);
        r[i]=a[i]-1-l[i];
        add(a[i],1);
    }
    //printf("%d %d %d %d\n",work1(),work2(),work3(),work4());
    printf("%d",(work1()-work2()+work3()+work4()+P)%P);
    return 0;
}