IOI2008 鱼

题目:

  据Scheherazade说,在很远的沙漠中有一个湖。湖中起初有N条鱼。
  选择最值钱的K种宝石,对F条鱼的每一条只喂给它一块宝石。注意,因为K可能小于F,两条或更多的鱼可能会吞下同一种宝石。
  随着时间的流逝,有些鱼吃掉了别的鱼。一条鱼能够吃掉另一条鱼,当且仅当它的长度是被吃掉的鱼的两倍(A 能吃掉B 当且仅当LA >= 2 * LB)。
  没有规则说明一条鱼何时会吃掉另一条鱼。有的鱼可能会一条接一条地吃掉几条小鱼,而有的鱼可能不吃别的鱼,即使它们有能力吃。
  当一条鱼吃掉一条小鱼时,它的身长并不改变,但是小鱼腹中的宝石会完好无损地进到大鱼腹中。
  据Scheherazade说,如果你能够找到那个湖,你会被准许捕捉一条鱼,并且得到鱼腹中的宝石。
  你很想试试运气,但是在出发前很想知道捉到一条鱼可能会有多少种不同的宝石组合。
  任务:写一个程序,给定每条鱼的长度以及其最初吞食的宝石的种类,找出鱼腹中宝石不同组合的数量对给定整数M取模的值。
  组合由每种宝石的数量定义,与宝石的排列顺序无关。同一类宝石中任意两块是没有区别的。

思路:

  观察题目中鱼吃鱼的条件,首先可以发现的是,如果存在两条鱼初始宝石相同(为了方便称为颜色),那么短的那只能得到的所有方案长的都能得到。所以对于每一种颜色只需要考虑最长的那条能得到的宝石组合。
  那么现在就剩下了 条不同色的鱼,考虑第 种颜色时,为了保证统计到的方案不在后面的颜色的方案中出现,假设 是一种长度大于 的颜色,那么为了避免被包含就只有两种情况:
  1.选的方案中不存在 这种颜色。
  2. 能吃的 色鱼个数等于 色最长鱼能吃的个数,这时只要 全取就不会被包含。
  发现每次能取得颜色如果按照最长鱼排序都是连续的区间,所以用线段树维护一个区间乘积即可。

代码:

#include <bits/stdc++.h>
#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 N = 5e5 + 5;

struct Fish {
    int len, c;
    void read() {scanf("%d%d", &len, &c);}
    bool operator< (const Fish f) const  {
        return len < f.len;
    }
} fs[N];

int pw[N << 2], m;
#define mid (L + R >> 1)
#define ls (o << 1)
#define rs (o << 1 | 1)
#define lson ls, L, mid
#define rson rs, mid + 1, R
void build(int o, int L, int R) {
    pw[o] = 1;
    if(L == R) return;
    build(lson); build(rson);
}
int qry(int l, int r, int o, int L, int R) {
    if(l > r) return 1;
    if(l == L && r == R) return pw[o];
    if(r <= mid) return qry(l, r, lson);
    else if(l > mid) return qry(l, r, rson);
    else return (ll) qry(l, mid, lson) * qry(mid + 1, r, rson) % m;
}
void upd(int x, int v, int o, int L, int R) {
    if(L == R) {pw[o] += v; return;}
    if(x <= mid) upd(x, v, lson);
    else upd(x, v, rson);
    pw[o] = (ll) pw[ls] * pw[rs] % m;
}
#undef mid

int rk[N], vec[N], cnt[N];
bool mark[N];

vector<int> col[N];
int main() {
    File(fish);
    int n, k, t = 0;
    scanf("%d%d%d", &n, &k, &m);
    rep(i, 1, n) fs[i].read();
    sort(fs + 1, fs + 1 + n);
    rep(i, 1, n) col[fs[i].c].push_back(i);
    drep(i, n, 1) {
        if(mark[fs[i].c]) continue;
        mark[fs[i].c] = true;
        vec[++t] = i;
        rk[fs[i].c] = t;
    }
    rep(i, 1, k / 2) swap(vec[i], vec[k - i + 1]);
    rep(i, 1, k) rk[i] = k - rk[i] + 1;
    build(1, 1, k);
    int p = 1, q, ans = 0;
    rep(i, 1, k) {
        int o = vec[i], c = fs[o].c;
        while(fs[p].len * 2 <= fs[o].len) {
            int c = fs[p++].c;
            cnt[c]++;
            upd(rk[c], 1, 1, 1, t);
        }
        int l = 0, r = col[c].size() - 1, mid, nxt;
        while(l <= r) {
            mid = (l + r >> 1);
            if(fs[col[c][mid]].len * 2 > fs[o].len) nxt = col[c][mid], r = mid - 1;
            else l = mid + 1;
        }
        l = i + 1; r = k; q = k + 1;
        while(l <= r) {
            mid = (l + r >> 1);
            if(fs[nxt].len * 2 <= fs[vec[mid]].len) q = mid, r = mid - 1;
            else l = mid + 1;
        }
        (ans += (ll) qry(1, i - 1, 1, 1, k) * qry(i + 1, q - 1, 1, 1 ,k) % m) %= m;
        (ans += (ll) qry(1, i - 1, 1, 1, k) * cnt[fs[o].c] % m) %= m;
    }
    printf("%d\n", ans);
    return 0;
}