P2513 [HAOI2009]逆序对数列

黄题也能翻车。。没脸见人。。

这题状态蛮特殊的，记录一下。

设 f[i][j] 表示 i 的全排列中有 j 个逆序对的排列总数。

考虑将 i+1 插入。状态转移方程

f_{i, j} = \sum_{k=1}^{i - 1} f_{i-1, j-k}

后面的东西前缀和优化即可。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 1e3 + 4;
const int mod = 10000;
int n, m;
int dp[N][N], sum[N];

int getSum(int a, int b) {
    if(a == 0) return sum[b];
    return sum[b] - sum[a - 1];
}

int positive(int x) {
    return (x % mod + mod) % mod;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd(), k = rd();
    dp[1][0] = 1;
    for(int i = 2; i <= n; i++) {
        sum[0] = dp[i - 1][0];
        for(int j = 1; j <= k; j++) {
            sum[j] = (sum[j - 1] + dp[i - 1][j]) % mod;
        }

        for(int j = 0; j <= k; j++) {
            dp[i][j] = getSum(max(0, j - i + 1), j) % mod;
        }
    }

    cout << positive(dp[n][k]) << endl;
    return 0;
}

SP375 QTREE - Query on a tree

每天一道树剖，防止抑郁。

对于边的树剖，下放到儿子节点即可。

值得一提的是，更新 \max \delta(u, v) 时，不应更新他们的 LCA，因为最后一步 u, v 在同一条重链上，因此深度小的那个点的 dfs 序 +1 就是这条重链上的下一个点。

另外，题中给出的 (u,v) 关系未必代表 v 是 u 的儿子。用深度判断下即可。

洛谷 Remote Judge c++ 提交有问题，原 OJ 测了一遍，直接祝掉。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n;

class SegmentTree {
#define MID int mid = (l + r) >> 1
#define lson l, mid, x << 1
#define rson mid + 1, r, x << 1 | 1
public :
    static const int N = ::N;
    static const int inf = ::inf;

    SegmentTree() {
        ms(maxx);
    }

    void clear() {
        ms(maxx);
    }

    int maxx[N];
    void push_up(int x) {
        maxx[x] = max(maxx[x << 1], maxx[x << 1 | 1]);
    }

    void modify(int l, int r, int x, int p, int v) {
        if(l == r) {
            maxx[x] = v;
            return ;
        }
        MID;
        if(p <= mid) modify(lson, p, v);
        if(p > mid) modify(rson, p, v);
        push_up(x);
    }

    int query(int l, int r, int x, int p, int q) {
        if(p <= l && r <= q) {
            return maxx[x];
        }
        MID; int res = -inf;
        if(p <= mid) res = max(res, query(lson, p, q));
        if(q > mid) res = max(res, query(rson, p, q));
        return res;
    }
} st;

struct Edge {
    int to, nxt;
} Edge[N << 1];

struct EdgeInfo {
    int u, v, w;
} e[N];

int head[N], cnt;

void addEdge(int u, int v) {
    Edge[++cnt].to = v;
    Edge[cnt].nxt = head[u];
    head[u] = cnt;
}

int id[N], top[N], sz[N], fa[N], dep[N], hs[N], idx;

void dfs1(int u, int d, int depth) {
    sz[u] = 1; fa[u] = d; dep[u] = depth; int mx = 0;
    for(int i = head[u]; i; i = Edge[i].nxt) {
        const int &v = Edge[i].to;
        if(v == d) continue;
        dfs1(v, u, depth + 1);
        sz[u] += sz[v]; 
        if(sz[v] > mx) mx = sz[v], hs[u] = v;
    }
}

void dfs2(int u, int tf) {
    id[u] = ++idx; top[u] = tf;
    if(sz[u] == 1) return ;
    dfs2(hs[u], tf);
    for(int i = head[u]; i; i = Edge[i].nxt) {
        const int v = Edge[i].to;
        if(v == hs[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}

int qRange(int x, int y) {
    int res = -inf;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        res = max(res, st.query(1, n, 1, id[top[x]], id[x])); x = fa[top[x]];
    }
    if(dep[x] < dep[y]) swap(x, y);
    if(x == y) return res;
    return max(res, st.query(1, n, 1, id[y] + 1, id[x]));
}
signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) {
        st.clear();
        idx = 0; cnt = 0; 
        ms(head); ms(Edge); ms(e); ms(id); ms(top); ms(sz); ms(fa); ms(dep); ms(hs);
        n = rd();
        for(int i = 1; i < n; i++) {
            e[i].u = rd(), e[i].v = rd(), e[i].w = rd();
            addEdge(e[i].u, e[i].v); addEdge(e[i].v, e[i].u);
        }

        dfs1(1, 1, 1);
        dfs2(1, 1);

        st.modify(1, n, 1, 1, -inf);
        for(int i = 1; i < n; i++) {
            int pos = dep[e[i].v] > dep[e[i].u] ? e[i].v : e[i].u;
            st.modify(1, n, 1, id[pos], e[i].w);
        }

        char opt[10];
        scanf("%s", opt + 1);
        while(opt[1] != 'D') {
            if(opt[1] == 'Q') {
                int x = rd(), y = rd();
                printf("%d\n", qRange(x, y));
            } else if(opt[1] == 'C') {
                int x = rd(), v = rd();
                int pos = dep[e[x].v] > dep[e[x].u] ? e[x].v : e[x].u;
                st.modify(1, n, 1, id[pos], v);
            }
            scanf("%s", opt + 1);
        }
    }
    return 0;
}

营业日志 1.23