CTSC2008 图腾

题目:

  在完成了古越州圆盘密码的研究之后,考古学家小布来到了南美大陆的西部。相传很久以前在这片土地上生活着两个部落,一个部落崇拜闪电,另一个部落崇拜高山,他们分别用闪电和山峰的形状作为各自部落的图腾。小布的团队在山洞里发现了一幅巨大的壁画,壁画上被标记出了N个点,经测量发现这N个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包含的信息仅与这N个点的相对位置有关,因此不妨设坐标分别为(1, y1) , (2, y2), ..., (n, yn),其中y1~yn是1~N的一个排列。小布的团队打算研究在这幅壁画中包含着多少个图腾,其中闪电图腾的定义图示如下(图腾的形式只与4个纵坐标值的相对大小排列顺序有关):
  
  崇拜高山的部落有两个氏族,因而山峰图腾有如下两种形式,左边为A类,右边为B类(同样,图腾的形式也都只与4个纵坐标值的大小排列顺序有关):
  
  小布的团队希望知道,这N个点中两个部落图腾数目的差值。因此在本题中,你需要帮助小布的团队编写一个程序,计算闪电图腾数目减去山峰图腾数目的值,由于该值可能绝对值较大,本题中只需输出该值对 的余数(注意余数必为正值,例如 的余数为 )。

思路:

  为了方便描述,把一种方案用按 排序后的编号序列表示,如闪电表示为 ,A型高山表示为
  观察发现除了A型高山以外,剩下的两种方案都不能在 的复杂度内求出答案,所以可以考虑把答案表示成 ,满足
  观察数字,可以表示成 ,也就等于 。但是尝试之后发现 并不好求,所以进一步转化成
   都是比较简单的,所以现在的问题就是怎么求 。(以 为例)

  设 左侧小于 的个数, 右侧大于 的个数。
  设前三个位置的下标为 ,那要满足的条件有 ,,
  先考虑一部分条件,满足 , 的方案数为
  再加上 ,那当前方案中不合法的方案数就是
  最后再加上 ,不合法的值就是
  然后再乘上最后一个位置的方案数,也就是

   求解的方式是类似的,只是设下标改为 “设权值第 小的为 ” 这样。也是一步一步增加限制(所以直接参考代码吧)。得到的两个式子都能用树状数组维护,所以复杂度就做到了

代码:

#include <bits/stdc++.h>
#define Debug(x) cerr << "DEBUG: " << #x << " = " << x << endl
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int MOD = 16777216, N = 200005;

int n, a[N];

struct BIT {
    int c[N], a;
    inline int low(int x) {return x & -x;}
    void clr() {mset(c, 0);}
    void upd(int x, int d) {
        for(; x < N; x += low(x)) (c[x] += d) %= MOD;
    }
    int qry(int x) {
        for(a = 0; x; x -= low(x)) (a += c[x]) %= MOD;
        return a;
    }
    int qry(int l, int r) {return (qry(r) - qry(l - 1)) % MOD;}
} b1, b2;

int le[N], ge[N];
int calc1() { // 1.2.
    b1.clr();
    int ans = 0;
    rep(i, 1, n) {
        int tmp = 0;
        (tmp += (ll) (i - 2) * le[i] % MOD) %= MOD;
        (tmp -= b1.qry(1, a[i])) %= MOD;
        (tmp -= (ll) le[i] * (le[i] - 1) / 2 % MOD) %= MOD;
        (ans += (ll) tmp * ge[i] % MOD) %= MOD;
        b1.upd(a[i], i - 1);
    }
    return ans;
}
int calc2() { // 1234
    b1.clr();
    int ans = 0;
    rep(i, 1, n) {
        (ans += (ll) b1.qry(1, a[i]) * ge[i] % MOD) %= MOD;
        b1.upd(a[i], le[i]);
    }
    return ans;
}
int calc3() { // 1...
    int ans = 0;
    rep(i, 1, n) (ans += (ll) ge[i] * (ge[i] - 1) * (ge[i] - 2) / 6 % MOD) %= MOD;
    return ans;
}
int calc4() { // 13..
    b1.clr(); b2.clr();
    int ans = 0;
    rep(i, 1, n) {
        int tmp = 0;
        (tmp += (ll) le[i] * (a[i] - 2) % MOD) %= MOD;
        (tmp -= (ll) le[i] * (le[i] - 1) / 2 % MOD) %= MOD;
        (tmp -= b1.qry(1, a[i])) %= MOD;
        (tmp -= b2.qry(1, a[i])) %= MOD;
        (ans += (ll) tmp * ge[i] % MOD) %= MOD;
        b1.upd(a[i], n - i - ge[i]);
        b2.upd(a[i], le[i]);
    }
    return ans;
}

void init() {
    b1.clr();
    rep(i, 1, n) {
        le[i] = b1.qry(1, a[i]);
        b1.upd(a[i], 1);
    }
    b1.clr();
    drep(i, n, 1) {
        ge[i] = b1.qry(a[i], n);
        b1.upd(a[i], 1);
    }
}

int main() {
    File(totem);
    scanf("%d", &n);
    rep(i, 1, n) scanf("%d", &a[i]);
    init();
    int ans = (((ll) calc1() + calc2() - calc3() + calc4()) % MOD + MOD) % MOD;
    printf("%d\n", ans);
    return 0;
}