Skip to content

2020 牛客国庆集训派对 Day7

Contents

Contest Info

Practice Link

Solved A B C D E F G H I J K
5/11 O O O O - - - - - O -
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • - 没有尝试

Solutions

Problem A. Laminar Family

Solved By Dup4. 04:28(+1)

题意

给出一棵 n 个点的树，以及 m 条简单路径 (a_i, b_i)，问这 m 条简单路径是否两两不相交或者处于包含关系。

思路

  • 按路径长度从大到小排序。
  • 对于第 i 段简单路径，我们在线段树上将这这段路径上的点的权值赋成 i。
  • 然后对于当前路径 (a_i, b_i)，我们在线段树上查询这段路径的点权和，假设为 y，该路径上的点数为 x，那么我们知道如果这段简单路径属于之前的某段路径，而不是拼凑成的，那么肯定属于第 \displaystyle \frac{y}{x} 条路径。
  • 可以额外判断第 \displaystyle \frac{y}{x} 条路径是否包含 第 i 条路径。
Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
int n, m;
vector<vector<int>> G;

struct BIT_2D {
    struct BIT {
        ll a[N];
        void init() {
            memset(a, 0, sizeof a);
        }
        void add(int x, ll v) {
            for (; x < N; a[x] += v, x += x & -x)
                ;
        }
        ll ask(int x) {
            ll res = 0;
            for (; x > 0; res += a[x], x -= x & -x)
                ;
            return res;
        }
    } bit1, bit2;
    void init() {
        bit1.init();
        bit2.init();
    }
    ll ask(int x) {
        return (x + 1) * bit1.ask(x) - bit2.ask(x);
    }
    void add(int x, ll v) {
        bit1.add(x, v);
        bit2.add(x, x * v);
    }
    ll ask(int l, int r) {
        return ask(r) - ask(l - 1);
    }
    void add(int l, int r, ll v) {
        add(l, v);
        add(r + 1, -v);
    }
} bit;

struct HLD {
    int fa[N], deep[N], dis[N], sze[N], son[N], top[N], in[N], fin[N], out[N];
    void dfs(int u) {
        sze[u] = 1;
        son[u] = 0;
        for (auto &v : G[u]) {
            if (v == fa[u])
                continue;
            fa[v] = u;
            deep[v] = deep[u] + 1;
            dis[v] = dis[u] + 1;
            dfs(v);
            sze[u] += sze[v];
            if (!son[u] || sze[v] > sze[son[u]])
                son[u] = v;
        }
    }
    void gettop(int u, int tp) {
        in[u] = ++*in;
        fin[*in] = u;
        top[u] = tp;
        if (son[u])
            gettop(son[u], tp);
        for (auto &v : G[u]) {
            if (v == son[u] || v == fa[u])
                continue;
            gettop(v, v);
        }
        out[u] = *in;
    }
    void init(int rt) {
        fa[rt] = rt;
        dis[rt] = 0;
        *in = 0;
        dfs(rt);
        gettop(rt, rt);
    }
    int querylca(int u, int v) {
        while (top[u] != top[v]) {
            if (deep[top[u]] < deep[top[v]]) {
                swap(u, v);
            }
            u = fa[top[u]];
        }
        if (deep[u] > deep[v])
            swap(u, v);
        return u;
    }
    int querydis(int u, int v) {
        return dis[u] + dis[v] - 2 * dis[querylca(u, v)];
    }
    void updatePath(int u, int v, ll x) {
        while (top[u] != top[v]) {
            if (deep[top[u]] < deep[top[v]])
                swap(u, v);
            bit.add(in[top[u]], in[u], x);
            u = fa[top[u]];
        }
        if (deep[u] > deep[v])
            swap(u, v);
        bit.add(in[u], in[v], x);
    }
    ll queryPath(int u, int v) {
        ll res = 0;
        while (top[u] != top[v]) {
            if (deep[top[u]] < deep[top[v]])
                swap(u, v);
            res += bit.ask(in[top[u]], in[u]);
            u = fa[top[u]];
        }
        if (deep[u] > deep[v])
            swap(u, v);
        res += bit.ask(in[u], in[v]);
        return res;
    }
    bool inSubTree(int u, int v) {
        return in[v] >= in[u] && in[v] <= out[u];
    }
} hld;

struct E {
    int u, v, dis;
    E() {}
} e[N];

bool ok(int a1, int b1, int a2, int b2) {
    int t[] = {hld.querylca(a1, a2), hld.querylca(a1, b2), hld.querylca(b1, a2), hld.querylca(b1, b2)};
    sort(t, t + 4, [&](int a, int b) {
        return hld.deep[a] < hld.deep[b];
    });
    int d[] = {hld.querylca(a1, b1), hld.querylca(a2, b2)};
    sort(d, d + 2, [&](int a, int b) {
        return hld.deep[a] < hld.deep[b];
    });
    if (hld.deep[t[3]] >= hld.deep[t[2]] && hld.deep[t[2]] >= hld.deep[d[1]]) {
        int _a = t[2], _b = t[3];
        if (_a > _b)
            swap(_a, _b);
        if (a2 > b2)
            swap(a2, b2);
        //		dbg(_a, _b);
        return _a == a2 && _b == b2;
    } else {
        return false;
    }
}

void run() {
    rd(n, m);
    G.clear();
    G.resize(n + 1);
    for (int i = 1, u, v; i < n; ++i) {
        rd(u, v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bit.init();
    hld.init(1);
    //	ok(1, 4, 2, 3);
    //	dbg("vv");
    //	return;
    for (int i = 1; i <= m; ++i) {
        rd(e[i].u, e[i].v);
        e[i].dis = hld.querydis(e[i].u, e[i].v) + 1;
        //		dbg(e[i].u, e[i].v, e[i].dis);
    }
    sort(e + 1, e + 1 + m, [&](E a, E b) {
        return a.dis > b.dis;
    });
    //	return;
    int _ok = 1;
    for (int i = 1; i <= m; ++i) {
        //	dbg(i);
        int u = e[i].u, v = e[i].v, dis = e[i].dis;
        ll x = hld.queryPath(u, v);
        // dbg(u, v, x, dis);
        if (x == 0) {
            hld.updatePath(u, v, i);
        } else {
            if (x % dis == 0) {
                ll y = x / dis;
                if (!ok(e[y].u, e[y].v, u, v)) {
                    _ok = 0;
                    break;
                } else {
                    hld.updatePath(u, v, -y);
                    hld.updatePath(u, v, i);
                }
            } else {
                _ok = 0;
                break;
            }
        }
    }
    pt(_ok ? "Yes" : "No");
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem B. Abbreviation

Solved By Dup4. 00:49(+)

题意

给出一个字符串，给连续的只被一个空格间隔的并且首字母大写的单词连成的短语加上缩写。

思路

模拟就完了。

Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
using pSI = pair<string, int>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
string s;

bool valid(string s) {
    if (SZ(s) < 2)
        return false;
    if (!isupper(s[0]))
        return false;
    for (int i = 1; i < SZ(s); ++i) {
        if (!islower(s[i]))
            return false;
    }
    return true;
}

int charType(char ch) {
    if (isalpha(ch))
        return 1;
    return 0;
}

string work(string s) {
    string tmp = "";
    for (auto &ch : s) {
        if (isupper(ch))
            tmp += ch;
    }
    if (SZ(tmp) < 2)
        return s;
    string res = tmp;
    tmp += " (";
    tmp += s;
    tmp += ")";
    return tmp;
}

void run() {
    vector<string> vec;
    string t = "";
    for (auto &ch : s) {
        if (t.empty())
            t += ch;
        else {
            if (charType(ch) == charType(t.back()))
                t += ch;
            else {
                vec.push_back(t);
                t.clear();
                t += ch;
            }
        }
    }
    if (!t.empty())
        vec.push_back(t);
    vector<pSI> _vec;
    for (int i = 0; i < SZ(vec); ++i) {
        string ss = vec[i];
        if (_vec.empty())
            _vec.push_back(pSI(ss, valid(ss)));
        else {
            if (_vec.back().se == 1 && SZ(ss) == 1 && ss[0] == ' ' && i + 1 < SZ(vec) && valid(vec[i + 1])) {
                _vec.back().fi += ss;
                _vec.back().fi += vec[i + 1];
                i += 1;
            } else {
                _vec.push_back(pSI(ss, valid(ss)));
            }
        }
    }
    string res = "";
    for (auto &it : _vec) {
        if (it.se == 0)
            res += it.fi;
        else
            res += work(it.fi);
    }
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    while (getline(cin, s)) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem C. Expect to Wait

Solved By Dup4. 02:03(+1)

题意

给出 n 种操作：

  • + t k, 表示在第 t 时刻加入 k 辆车。
  • - t k, 表示在第 t 时刻有 K 个用车需求。

有 q 次询问，每次询问表示假如加入操作 + 0 a, 那么对于每个用车需求总共的等待时间是多少？

思路

  • 将时间拆成 n 段，第 i 段为 t_i - t_{i - 1}。
  • 那么考虑在第 i 个操作种加入一辆车，其实就是在第 [i + 1, n] 的时间段里减一。
  • 在第 i 个操作中有一个用车需求，就是在第 [i + 1, n] 的时间段里加一。
  • 对于 q 次询问，将询问按 a_i 排序，每次剔除时间段内权值小于等于 0 的那些段即可，剩下的没被剔除的总和就是答案。
Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
int n, q, t[N], k[N];
pII qnode[N];
ll ans[N];

struct BIT {
    ll a[N];
    void init() {
        memset(a, 0, sizeof a);
    }
    void update(int x, ll v) {
        for (; x < N; x += x & -x) a[x] += v;
    }
    ll query(int x) {
        ll res = 0;
        for (; x > 0; x -= x & -x) res += a[x];
        return res;
    }
    void update(int l, int r, ll v) {
        if (l > r)
            return;
        update(l, v);
        update(r + 1, -v);
    }
} bit;

void run() {
    rd(n, q);
    t[0] = 0;
    int tot = 0;
    int has = 0;
    char op[5];
    for (int i = 1; i <= n; ++i) {
        cin >> op;
        rd(t[i], k[i]);
        if (*op == '-')
            bit.update(i + 1, n, k[i]), tot += k[i];
        else
            bit.update(i + 1, n, -k[i]), has += k[i];
    }
    for (int i = 1; i <= q; ++i) {
        rd(qnode[i].fi);
        qnode[i].se = i;
    }
    priority_queue<pLL, vector<pLL>, greater<pLL>> pq;
    ll res = 0;
    ll base = 0;
    for (int i = 1; i <= n; ++i) {
        ll _x = bit.query(i);
        ll _t = t[i] - t[i - 1];
        res += _x * _t;
        base += _t;
        pq.push(pLL(_x, _t));
    }
    sort(qnode + 1, qnode + 1 + q);
    int now = 0;
    for (int i = 1; i <= q; ++i) {
        now = qnode[i].fi;
        int id = qnode[i].se;
        if (has + now < tot)
            ans[id] = -1;
        else {
            while (!pq.empty() && pq.top().fi <= now) {
                pLL top = pq.top();
                pq.pop();
                base -= top.se;
                res -= top.fi * top.se;
            }
            ans[id] = res - base * now;
        }
    }
    for (int i = 1; i <= q; ++i) {
        if (ans[i] == -1)
            pt("INFINITY");
        else
            pt(ans[i]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem D. Foreign Postcards

Solved By Dup4. 03:31(+)

题意

给出 n 张扑克牌，C 表示第 i 张扑克牌正面朝上，W 表示反面朝上。现在将 n 张牌入栈，并执行以下流程：

  • 令当前栈的大小为 n，首先在 [1, n] 中随机一个数 k。
  • 然后从栈中取出 k 张牌，如果取出的第一张牌是 W，那么将取出的所有牌都翻一个面。
  • 循环上述流程，直到栈空。

问流程结束后，反面朝上的牌的个数的期望是多少？

思路

  • 令 f_i 表示栈底往上 i 张牌的期望是多少。
  • 然后对于当前 i，我们都要从 f_j(j \leq i) 转移过来。并且根据当前第 i 张牌的状态决定加上的贡献是区间内 W 的牌还是 C 的牌。
Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = long double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e6 + 10;
db f[N], _f[N];
char s[N];
int n, c[N], w[N];

void run() {
    cin >> (s + 1);
    n = strlen(s + 1);
    _f[0] = 0;
    c[0] = w[0] = 0;
    ll _c = 0, _w = 0;
    reverse(s + 1, s + 1 + n);
    for (int i = 1; i <= n; ++i) {
        c[i] = c[i - 1] + (s[i] == 'C');
        w[i] = w[i - 1] + (s[i] == 'W');
        _c += c[i - 1];
        _w += w[i - 1];
        if (s[i] == 'C') {
            f[i] = (1ll * w[i] * i - _w + _f[i - 1]) * 1.0 / i;
        } else {
            f[i] = (1ll * c[i] * i - _c + _f[i - 1]) * 1.0 / i;
        }
        //	f[i] = (1ll * c[i] * num_c + 1ll * w[i] * num_w - _c - _w + _f[i - 1]) * 1.0 / i;
        _f[i] = _f[i - 1] + f[i];
    }
    pt(f[n]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem E. Game on Graph

Upsolved By -.

题意

思路

Problem F. Jenga Boom

Upsolved By -.

题意

思路

Problem G. List of Primes

Upsolved By -.

题意

思路

Problem H. Mole Tunnels

Upsolved By -.

题意

思路

Problem I. Bowlstack

Upsolved By -.

题意

思路

Problem J. Adjustment Office

Solved By Dup4. 00:11(+)

题意

给出一个 n \cdot n 的矩阵，其中 a_{i, j} = i + j，有两种操作：

  • R r，表示输出矩阵中第 r 行的数的和，并且将这行数都变成 0。
  • C c, 表示输出矩阵中第 c 列的数的和，并且将这列数都变成 0。

思路

  • 以行为例，对于当前行我们只需要知道这一行有多少列没被清 0，以及没被清 0 的行的数的和即可。
  • 用数据结构维护行信息以及列信息。
Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e6 + 10;
int n, q, f[2][N];

struct BIT {
    ll a[N];
    void init() {
        memset(a, 0, sizeof a);
    }
    void update(int x, ll v) {
        for (; x < N; x += x & -x) {
            a[x] += v;
        }
    }
    ll query(int x) {
        ll res = 0;
        for (; x > 0; x -= x & -x) res += a[x];
        return res;
    }
    ll query(int l, int r) {
        if (l > r)
            return 0;
        return query(r) - query(l - 1);
    }
} g[2], h[2];

void run() {
    rd(n, q);
    g[0].init();
    g[1].init();
    h[0].init();
    h[1].init();
    memset(f, 0, sizeof f);
    for (int i = 1; i <= n; ++i) {
        g[0].update(i, 1);
        h[0].update(i, i);
        g[1].update(i, 1);
        h[1].update(i, i);
    }
    char op[5];
    for (int i = 1, x; i <= q; ++i) {
        cin >> op;
        rd(x);
        if (*op == 'R') {
            if (f[0][x])
                pt(0);
            else {
                ll res = 1ll * x * g[1].query(1, n) + h[1].query(1, n);
                pt(res);
                g[0].update(x, -1);
                h[0].update(x, -x);
            }
            f[0][x] = 1;
        } else {
            if (f[1][x])
                pt(0);
            else {
                ll res = 1ll * x * g[0].query(1, n) + h[0].query(1, n);
                pt(res);
                g[1].update(x, -1);
                h[1].update(x, -x);
            }
            f[1][x] = 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem K. Binary vs Decimal

Upsolved By -.

题意

思路

Last update: March 24, 2022
Created: March 23, 2022
Back to top