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

void solve() {
    ll h, w, k;
    cin >> h >> w >> k;
    vector<string> ma(h);
    rep(i, 0, h - 1) cin >> ma[i];
    ll ans = 0;
    vl cnt(h * w + 1);
    vl tem3;
    rep(i, 0, h - 1) {
        vl tem(w);
        rep(j, i, h - 1) {
            tem3.clear();
            rep(v, 0, w - 1) tem[v] += ma[j][v] - '0';
            cnt[0]++;
            tem3.push_back(0);
            ll tem2 = 0;
            rep(v, 0, w - 1) {
                tem2 += tem[v];
                if (tem2 >= k) ans += cnt[tem2 - k];
                if (cnt[tem2] == 0) tem3.push_back(tem2);
                cnt[tem2]++;
            }
            for (auto& p : tem3) cnt[p] = 0;
        }
    }
    cout << ans << endl;
    return;
}

 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
91
92
93
94
95

template <typename T = long long>
class Tree {
    vector<T> tree;

public:
    // 构造函数：初始化大小为 n 的树状数组，初始所有元素值为 val（外部表现为 0-based）
    Tree(int n, T val = 0) : tree(n + 1) {
        for (int i = 1; i <= n; i++) {
            tree[i] += val;
            int nxt = i + (i & -i);
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    // 构造函数：使用给定的 vector 在 O(N) 时间内快速初始化建树
    Tree(const vector<T>& data) {
        int n = data.size();
        tree.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            tree[i] += data[i - 1];  // data是 0-based
            int nxt = i + (i & -i);
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    // 单点修改：将 0-based 下标 i 处的元素增加 val
    void add(int i, T val = 1) {
        for (++i; i < tree.size(); i += i & (-i)) {
            tree[i] += val;
        }
    }

    // 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
    T pre(int i) const {
        T res = 0;
        for (++i; i > 0; i &= i - 1) {
            res += tree[i];
        }
        return res;
    }

    // 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
    T query(int l, int r) const {
        if (r < l) {
            return 0;
        }
        return pre(r) - pre(l - 1);  // 当 l=0 时, pre(-1) 会合理地返回 0
    }

    // 树上二分查找：返回满足前缀和 >= val 的最小 0-based 下标
    int lower_bound(T val) const {
        int w = bit_width(tree.size() - 1);
        int res = 0;
        T s = 0;
        for (int i = w - 1; i >= 0; i--) {
            int nxt = res + (1 << i);
            if (nxt < tree.size() && tree[nxt] + s < val) {
                res += (1 << i);
                s += tree[nxt];
            }
        }
        return res;  // 返回 0-based 下标：内部 1-based 下标为 res + 1，因此 0-based 为 res
    }
};
void solve() {
    ll n, q, op, x;
    cin >> n >> q;
    Tree tree1(q + 1), tree2(q + 1);
    vl tem(n + 1), tem2(n + 1);
    ll ans = 0;
    tree1.add(0, n);
    tree2.add(0, n);
    rep(i, 0, q - 1) {
        cin >> op >> x;
        if (op == 1) {
            ll tem3 = tree2.query(0, tem[x] - 1);
            ans += n - tem3;
            tree1.add(tem[x], -1);
            tree1.add(i + 1, 1);
            tem[x] = i + 1;
        } else {
            ll tem3 = tree1.query(tem2[x] + 1, q);
            ans -= tem3;
            tree2.add(tem2[x], -1);
            tree2.add(i + 1, 1);
            tem2[x] = i + 1;
        }
        cout << ans << endl;
    }
    return;
}

 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

using i128 = __int128_t;
const ll MOD = 998244353;
constexpr int MX = 1e5 + 1;
ll F[MX];      // 预处理阶乘
ll INV_F[MX];  // 预处理逆元
ll qpow(ll x, int n) {
    ll res = 1;
    for (; n; n >>= 1) {
        if (n % 2) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}
auto init = [] {
    F[0] = 1;
    for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % MOD;  // 预处理阶乘
    INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
    for (int i = MX - 1; i; i--) {
        INV_F[i - 1] = INV_F[i] * i % MOD;
    }  // 预处理逆元
    return 0;
}();
// 计算C(n,m),即从n个数中取m个数
ll comb(int n, int m) { return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD; }
void solve() {
    ll n;
    cin >> n;
    vector<pll> tem;
    ll nn = n;
    for (ll i = 2; i * i <= n; i++) {
        if (nn % i == 0) {
            ll tem2 = 0;
            while (nn % i == 0) {
                tem2++;
                nn /= i;
            }
            tem.emplace_back(i, tem2);
        }
    }
    if (nn > 1) tem.emplace_back(nn, 1);
    vl tem2;
    tem2.push_back(1);
    for (auto& [x, y] : tem) {
        int tem3 = sz(tem2);
        ll tem4 = 1;
        rep(j, 1, y) {
            tem4 *= x;
            rep(v, 0, tem3 - 1) tem2.push_back(tem2[v] * tem4);
        }
    }
    ranges::sort(tem2);
    int m = sz(tem2);
    map<ll, ll> ma;
    rep(i, 0, m - 1) { ma[tem2[i]] = i; }
    vvl dp(m, vl(100));
    vvl dp2(m, vl(100));
    dp[0][0] = 1;
    rep(i, 1, m - 1) {
        frep(j, m - 1, 0) {
            if ((i128)tem2[j] * tem2[i] > (i128)n) continue;
            if (n % (tem2[j] * tem2[i]) != 0) continue;
            frep(v, 98, 0) {
                if (!dp[j][v]) continue;
                dp[ma[tem2[j] * tem2[i]]][v + 1] = (dp[ma[tem2[j] * tem2[i]]][v + 1] + dp[j][v]) % MOD;
                dp2[ma[tem2[j] * tem2[i]]][v + 1] =
                    (dp2[ma[tem2[j] * tem2[i]]][v + 1] + dp2[j][v] + dp[j][v] * (tem2[i] % MOD) % MOD) % MOD;
            }
        }
    }
    ll ans = 0;
    rep(i, 0, 99) {
        if (!dp[ma[n]][i]) continue;
        ans = (ans + F[i + 1] * (dp[ma[n]][i] + dp2[ma[n]][i]) % MOD) % MOD;
        if (i > 0) ans = (ans + F[i] * dp2[ma[n]][i] % MOD) % MOD;
    }
    cout << ans << endl;
    return;
}