c/c++语言开发共享洛谷P3120 [USACO15FEB]牛跳房子(动态开节点线段树)

题意

题目链接

sol

(f[i][j])表示前(i)行(j)列的贡献，转移的时候枚举从哪里转移而来，复杂度(o(n^4))

然后考虑每一行的贡献，动态开节点线段树维护一下每种颜色的答案

转移的时候用总的方案减去相同颜色的方案

复杂度(o(n^2 log^2 n))

#include<bits/stdc++.h>  #define ll long long  using namespace std; const int maxn = 1001, inf = 1e9 + 10, mod = 1000000007, ss = maxn * maxn * 10; inline int read() {     char c = getchar(); int x = 0, f = 1;     while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();     return x * f; } int add(int x, int y) {     if(x + y < 0) return x + y + mod;     return x + y >= mod ? x + y - mod : x + y; } int n, m, k, c[maxn][maxn], f[maxn][maxn], tot; int root[ss], ls[ss], rs[ss], sum[ss]; void intadd(int &k, int l, int r, int pos, int val) {     if(!k) k = ++tot;     sum[k] = add(sum[k], val);     if(l == r) return ;     int mid = l + r >> 1;     if(pos <= mid) intadd(ls[k], l, mid, pos, val);     else intadd(rs[k], mid + 1, r, pos, val); } int query(int k, int l, int r, int ll, int rr) {     if(!k) return 0;     if(ll <= l && r <= rr) return sum[k];     int mid = l + r >> 1;     if(ll > mid) return query(rs[k], mid + 1, r, ll, rr);     else if(rr <= mid) return query(ls[k], l, mid, ll, rr);     else return add(query(ls[k], l, mid, ll, rr), query(rs[k], mid + 1, r, ll, rr));  } signed main() {     n = read(); m = read(); k = read();     f[1][1] = 1;     for(int i = 1; i <= n; i++) {         for(int j = 1; j <= m; j++) {             int k = read(); c[i][j] = k;             if(!f[i][j]) f[i][j] = add(query(root[0], 1, m, 1, j - 1), -query(root[k], 1, m, 1, j - 1));                      }         for(int j = 1; j <= m; j++)             intadd(root[0], 1, m, j, f[i][j]),             intadd(root[c[i][j]], 1, m, j, f[i][j]);     }     cout << f[n][m];     return 0; }