营业日志 1.27

博主： admin
发布时间：2021 年 01 月 27 日
400 次浏览
关闭评论
50字数
分类：默认分类

CF1475A

#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
using namespace std;
#define int long long
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);
}

void solve() {
    int n = rd();
    if((n & -n) == n) puts("NO");
    else puts("YES");
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}

CF1475B

#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
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);
}

void solve() {
    int n = rd();
    int u = 0;
    while(u <= n) {
        if((n - u) % 2020 == 0 || (n - u) % 2021 == 0) return puts("YES"), void();
        u += 2020 + 2021;
    }
    puts("NO");
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}

CF1475C

#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
using namespace std;
#define int long long
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);
}

typedef pair<int, int> pi;
map<pi, int> maps;

const int N = 2e5 + 5;
vector<int> le, ri;
vector<pi> opt;

void solve() {
    maps.clear();
    int a = rd(), b = rd(), k = rd();
    le.resize(a + 1); ri.resize(b + 1); 
    std::fill(begin(le), end(le), 0LL);
    std::fill(begin(ri), end(ri), 0LL);
    opt.resize(k + 1);
    std::fill(begin(opt), end(opt), make_pair(0LL, 0LL));
    for(int i = 1; i <= k; i++) {
        opt[i].first = rd();
    }

    for(int j = 1; j <= k; j++) {
        opt[j].second = rd();
    }

    for(int i = 1; i <= k; i++) {
        if(maps.count(opt[i])) continue;
        maps[opt[i]] = 1;
        le[opt[i].first]++, ri[opt[i].second]++;
    }
/*
    for(int i = 1; i <= a; i++) {
        cout << le[i] << " ";
    }
    cout << endl;
    for(int i = 1; i <= b; i++) {
        cout << ri[i] << " ";
    }
    cout << endl;
*/
    int ans = 0;
    for(int i = 1; i <= k; i++) {
        ans += k - (le[opt[i].first] + ri[opt[i].second] - 1);
    }

    printf("%lld\n", ans / 2);
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}

1475E

#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
using namespace std;
#define int long long
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 = 1e4 + 5, mod = 1e9 + 7;

int fac[N];

vector<int> a;

int qpow(int a, int b) {
    int res = 1, base = a;
    while(b) {
        if(b & 1) res = res * base % mod;
        base = base * base % mod; b >>= 1;
    }
    return res;
}

int inv(int x) {
    return qpow(x, mod - 2);
}

int C(int a, int b) {
    return fac[b] * inv(fac[b-a] * fac[a] % mod) % mod;
}

void init() {
    fac[0] = 1;
    for(int i = 1; i <= 1000; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
}

void solve() {
    int n = rd(), k = rd();
    a.resize(n + 1);
    for(int i = 1; i <= n; i++) a[i] = rd();
    sort(a.begin() + 1, a.end());
    int u = n - k + 1, v = n - k + 1;
    while(u > 0 && a[u] == a[n - k + 1]) u--;
    while(v <= n && a[v] == a[n - k + 1]) v++;
    u++; v--;
    printf("%lld\n", C(v - (n - k + 1) + 1, v - u + 1));
}

signed main() {
#ifdef LOCAL
    file();
#endif
    init();
    int T = rd();
    while(T--) solve();
    return 0;
}

CF1475D

值得一记。

有瞎贪心的做法。

#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
using namespace std;
#define int long long
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);
}

typedef pair<int, int> pi;
vector<pi> a;
priority_queue<int, vector<int>, less<int> > Q1, Q2;

int getTwo() {
    int v = Q1.top(); Q1.pop();
    if(Q1.empty()) return Q1.push(v), v; 
    int v2 = Q1.top(); Q1.push(v);
    return v + v2;
}

void solve() {
    int n = rd(), m = rd();
    a.resize(n + 1);
    while(!Q1.empty()) Q1.pop();
    while(!Q2.empty()) Q2.pop();
    for(int i = 1; i <= n; i++) {
        a[i].first = rd();
    }
    for(int i = 1; i <= n; i++) {
        a[i].second = rd();
        if(a[i].second == 1) Q1.push(a[i].first);
        if(a[i].second == 2) Q2.push(a[i].first);
    }

    int u = 0, ans = 0;
    while(!(Q1.empty() && Q2.empty()) && u < m) {
        if(Q1.empty()) u += Q2.top(), Q2.pop(), ans += 2;
        else if(Q1.top() + u >= m) u += Q1.top(), Q1.pop(), ans += 1;
        else if(Q2.empty()) u += Q1.top(), Q1.pop(), ans += 1;
        else {
            int two = getTwo();
            if(two > Q2.top()) {
                u += Q1.top(), Q1.pop(), ans += 1;
            } else {
                u += Q2.top(), Q2.pop(), ans += 2;
            }
        }
    }

    if(u < m) puts("-1");
    else printf("%d\n", ans);
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}

另一种则是「惯用套路」。

#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
using namespace std;
#define int long long
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);
}

vector<int> a, b;
vector<int> t1, t2, sum;

void solve() {
    int n = rd(), m = rd();
    a.resize(n + 1); b.resize(n + 1);
    t1.clear(); t2.clear(); sum.clear();

    for(int i = 1; i <= n; i++) {
        a[i] = rd();
    }

    for(int i = 1; i <= n; i++) {
        b[i] = rd();
        if(b[i] == 1) t1.push_back(a[i]);
        if(b[i] == 2) t2.push_back(a[i]);
    }

    sort(t1.begin(), t1.end(), greater<int> () );
    sort(t2.begin(), t2.end(), greater<int> () );

    if(t2.size() > 0) sum.push_back(t2[0]);
    for(int i = 1; i < (int)t2.size(); i++) {
        sum.push_back(sum[i - 1] + t2[i]);
    }

    int tot = 0, cost = 0, ans = 0x7f7f7f7f7f7f7f;
    for(auto it : t1) {
        tot += it;
        cost++;
        if(tot >= m) { ans = min(ans, cost); continue; }
        auto p = lower_bound(sum.begin(), sum.end(), m - tot);
        if(p == sum.end()) continue;
        ans = min(ans, cost + 2LL * (p - sum.begin() + 1LL));
    }
    auto p = lower_bound(sum.begin(), sum.end(), m);
    if(p != sum.end()) ans = min(ans, 2LL * (p - sum.begin() + 1LL));
    if(ans == 0x7f7f7f7f7f7f7f) puts("-1");
    else cout << ans << endl;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}

P4211 [LNOI2014]LCA

每天一道树剖，保持抑郁。

不错的一道题。XD

考虑如果我们将原式差分 \sum_{i=l}^{r}dep[lca(i, z)]=\sum_{i=1}^{r}dep[lca(i, z)] - \sum_{i=1}^{l-1}dep[lca(i,z)] 。我们只需要求出所有的所需的 \sum_{i=1}^{x}dep[lca(i, z)] 即可。

考虑 \sum_{i=l}^{r}dep[lca(i, z)] 的图形意义。我们发现所有的 LCA 一定在 z 到根的路径上。那么对于 i=x 的贡献，即为将 x 到根的路径上所有数字 +1 。最后查询 z 到根的路径的所有权值和即可。

#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)
#define int long long
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 = 2e5 + 5, M = 2e5 + 5;

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;
    int sum[N << 2], add[N << 2];

    SegmentTree() {
        ms(sum);
        ms(add);
    }

    void build(int l, int r, int x) {
        if(l == r) {
            sum[x] = rd();
            return ;
        }
        MID; 
        build(lson); build(rson);
        sum[x] = sum[x << 1] + sum[x << 1 | 1];
    }

    void modify_add(int l, int r, int x, int p, int q, int v) {
        if(p <= l && r <= q) {
            add[x] += v;
            return ;
        }
        MID;
        sum[x] += (min(r, q) - max(l, p) + 1) * v;
        if(p <= mid) modify_add(lson, p, q, v);
        if(q > mid) modify_add(rson, p, q, v);
    }

    int query(int l, int r, int x, int p, int q) {
        if(p <= l && r <= q) {
            return sum[x] + add[x] * (r - l + 1);
        }
        MID; 
        int res = (min(r, q) - max(l, p) + 1) * add[x];
        if(p <= mid) res += query(lson, p, q);
        if(q > mid) res += query(rson, p, q);
        return res;
    }
} st;

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

int head[N], cnt;

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

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

void dfs1(int u, int d, int depth) {
    dep[u] = depth; fa[u] = d; sz[u] = 1; int maxsz = 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(maxsz <= sz[v]) maxsz = 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 == fa[u] || v == hs[u]) continue;
        dfs2(v, v);
    }
}

struct Ques {
    int l, r, z;
} Ques[M];

map<pair<int, int>, int> maps;

struct E {
    int ti, z;
    bool operator<(const E& b) const {
        return ti < b.ti;
    }
} e[M << 1];

int ecnt, n;

void aRange(int x, int v) {
    while(top[x] != 0) {
        st.modify_add(1, n, 1, id[top[x]], id[x], v);
        x = fa[top[x]];
    }
    st.modify_add(1, n, 1, id[0], id[x], v);
}

int qRange(int x) {
    int res = 0;
    while(top[x] != 0) {
        res += st.query(1, n, 1, id[top[x]], id[x]);
        x = fa[top[x]];
    }
    res += st.query(1, n, 1, id[0], id[x]);
    res -= st.query(1, n, 1, id[0], id[0]);
    return res;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    memset(head, -1, sizeof head);
    n = rd(); int q = rd();
    for(int i = 1; i < n; i++) {
        int v = rd();
        addEdge(i, v); addEdge(v, i);
    }

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

    for(int i = 1; i <= q; i++) {
        Ques[i].l = rd();
        Ques[i].r = rd();
        if(Ques[i].l > Ques[i].r) swap(Ques[i].l, Ques[i].r);
        Ques[i].z = rd();
        if(Ques[i].l != 0) {
            e[++ecnt].ti = Ques[i].l - 1;
            e[ecnt].z = Ques[i].z;
        }
        e[++ecnt].ti = Ques[i].r;
        e[ecnt].z = Ques[i].z;
    }

    sort(e + 1, e + ecnt + 1);

    int ti = 0;
    for(int i = 1; i <= ecnt; i++) {
        while(ti <= e[i].ti) {
            aRange(ti, 1);
            ++ti;
        }
        maps[make_pair(e[i].ti, e[i].z)] = qRange(e[i].z);
    }

    for(int i = 1; i <= q; i++) {
        if(Ques[i].l == 0) printf("%lld\n", (maps[make_pair(Ques[i].r, Ques[i].z)] + Ques[i].r - Ques[i].l + 1) % 201314);
        else printf("%lld\n", (maps[make_pair(Ques[i].r, Ques[i].z)] - maps[make_pair(Ques[i].l - 1, Ques[i].z)] + (Ques[i].r - Ques[i].l + 1)) % 201314);
    }

    return 0;
}

最后修改：2021 年 01 月 30 日

如果觉得我的文章对你有用，请随意赞赏

此处评论已关闭

欢迎使用 Typecho
评论数： 1
Hello, World
评论数： 0
离散化
评论数： 0
树状数组
评论数： 0
神秘炼丹术
评论数： 0

Latex 测试
评论数： 0
树状数组
评论数： 0
营业日志 1.29
评论数： 0
营业日志 2.1
评论数： 0
营业日志 3.13
评论数： 0

营业日志 1.27

admin • 2021 年 01 月 27 日

<h1>CF1475A</h1>
<pre><code class="cpp">#include &lt;bits/stdc++.h&gt;
#define d(x) cerr &lt;&lt; #x &lt;&lt; " =&gt; " &lt;&lt; x &lt;&lt; endl
#define dd(x) cerr &lt;&lt; #x &lt;&lt; endl
#define D cerr &lt;&lt; "Passed [" &lt;&lt; __FUNCTION__ "] on line " &lt;&lt; __LINE__ &lt;&lt; endl
using namespace std;
#define int long long
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);
}

void solve() {
    int n = rd();
    if((n &amp; -n) == n) puts("NO");
    else puts("YES");
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}</code></pre>
<h1>CF1475B</h1>
<pre><code class="cpp">#include &lt;bits/stdc++.h&gt;
#define d(x) cerr &lt;&lt; #x &lt;&lt; " =&gt; " &lt;&lt; x &lt;&lt; endl
#define dd(x) cerr &lt;&lt; #x &lt;&lt; endl
#define D cerr &lt;&lt; "Passed [" &lt;&lt; __FUNCTION__ "] on line " &lt;&lt; __LINE__ &lt;&lt; endl
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);
}

void solve() {
    int n = rd();
    int u = 0;
    while(u &lt;= n) {
        if((n - u) % 2020 == 0 || (n - u) % 2021 == 0) return puts("YES"), void();
        u += 2020 + 2021;
    }
    puts("NO");
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}</code></pre>
<h1>CF1475C</h1>
<pre><code class="cpp">#include &lt;bits/stdc++.h&gt;
#define d(x) cerr &lt;&lt; #x &lt;&lt; " =&gt; " &lt;&lt; x &lt;&lt; endl
#define dd(x) cerr &lt;&lt; #x &lt;&lt; endl
#define D cerr &lt;&lt; "Passed [" &lt;&lt; __FUNCTION__ "] on line " &lt;&lt; __LINE__ &lt;&lt; endl
using namespace std;
#define int long long
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);
}

typedef pair&lt;int, int&gt; pi;
map&lt;pi, int&gt; maps;

const int N = 2e5 + 5;
vector&lt;int&gt; le, ri;
vector&lt;pi&gt; opt;

void solve() {
    maps.clear();
    int a = rd(), b = rd(), k = rd();
    le.resize(a + 1); ri.resize(b + 1); 
    std::fill(begin(le), end(le), 0LL);
    std::fill(begin(ri), end(ri), 0LL);
    opt.resize(k + 1);
    std::fill(begin(opt), end(opt), make_pair(0LL, 0LL));
    for(int i = 1; i &lt;= k; i++) {
        opt[i].first = rd();
    }

for(int j = 1; j &lt;= k; j++) {
        opt[j].second = rd();
    }

for(int i = 1; i &lt;= k; i++) {
        if(maps.count(opt[i])) continue;
        maps[opt[i]] = 1;
        le[opt[i].first]++, ri[opt[i].second]++;
    }
/*
    for(int i = 1; i &lt;= a; i++) {
        cout &lt;&lt; le[i] &lt;&lt; " ";
    }
    cout &lt;&lt; endl;
    for(int i = 1; i &lt;= b; i++) {
        cout &lt;&lt; ri[i] &lt;&lt; " ";
    }
    cout &lt;&lt; endl;
*/
    int ans = 0;
    for(int i = 1; i &lt;= k; i++) {
        ans += k - (le[opt[i].first] + ri[opt[i].second] - 1);
    }

printf("%lld\n", ans / 2);
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}</code></pre>
<h1>1475E</h1>
<pre><code class="cpp">#include &lt;bits/stdc++.h&gt;
#define d(x) cerr &lt;&lt; #x &lt;&lt; " =&gt; " &lt;&lt; x &lt;&lt; endl
#define dd(x) cerr &lt;&lt; #x &lt;&lt; endl
#define D cerr &lt;&lt; "Passed [" &lt;&lt; __FUNCTION__ "] on line " &lt;&lt; __LINE__ &lt;&lt; endl
using namespace std;
#define int long long
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 = 1e4 + 5, mod = 1e9 + 7;

int fac[N];

vector&lt;int&gt; a;

int qpow(int a, int b) {
    int res = 1, base = a;
    while(b) {
        if(b &amp; 1) res = res * base % mod;
        base = base * base % mod; b &gt;&gt;= 1;
    }
    return res;
}

int inv(int x) {
    return qpow(x, mod - 2);
}

int C(int a, int b) {
    return fac[b] * inv(fac[b-a] * fac[a] % mod) % mod;
}

void init() {
    fac[0] = 1;
    for(int i = 1; i &lt;= 1000; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
}

void solve() {
    int n = rd(), k = rd();
    a.resize(n + 1);
    for(int i = 1; i &lt;= n; i++) a[i] = rd();
    sort(a.begin() + 1, a.end());
    int u = n - k + 1, v = n - k + 1;
    while(u &gt; 0 &amp;&amp; a[u] == a[n - k + 1]) u--;
    while(v &lt;= n &amp;&amp; a[v] == a[n - k + 1]) v++;
    u++; v--;
    printf("%lld\n", C(v - (n - k + 1) + 1, v - u + 1));
}

signed main() {
#ifdef LOCAL
    file();
#endif
    init();
    int T = rd();
    while(T--) solve();
    return 0;
}</code></pre>
<h1>CF1475D</h1>
<p>值得一记。</p>
<p>有瞎贪心的做法。</p>
<pre><code class="cpp">#include &lt;bits/stdc++.h&gt;
#define d(x) cerr &lt;&lt; #x &lt;&lt; " =&gt; " &lt;&lt; x &lt;&lt; endl
#define dd(x) cerr &lt;&lt; #x &lt;&lt; endl
#define D cerr &lt;&lt; "Passed [" &lt;&lt; __FUNCTION__ &lt;&lt; "] on line " &lt;&lt; __LINE__ &lt;&lt; endl
using namespace std;
#define int long long
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);
}

typedef pair&lt;int, int&gt; pi;
vector&lt;pi&gt; a;
priority_queue&lt;int, vector&lt;int&gt;, less&lt;int&gt; &gt; Q1, Q2;

int getTwo() {
    int v = Q1.top(); Q1.pop();
    if(Q1.empty()) return Q1.push(v), v; 
    int v2 = Q1.top(); Q1.push(v);
    return v + v2;
}

void solve() {
    int n = rd(), m = rd();
    a.resize(n + 1);
    while(!Q1.empty()) Q1.pop();
    while(!Q2.empty()) Q2.pop();
    for(int i = 1; i &lt;= n; i++) {
        a[i].first = rd();
    }
    for(int i = 1; i &lt;= n; i++) {
        a[i].second = rd();
        if(a[i].second == 1) Q1.push(a[i].first);
        if(a[i].second == 2) Q2.push(a[i].first);
    }

int u = 0, ans = 0;
    while(!(Q1.empty() &amp;&amp; Q2.empty()) &amp;&amp; u &lt; m) {
        if(Q1.empty()) u += Q2.top(), Q2.pop(), ans += 2;
        else if(Q1.top() + u &gt;= m) u += Q1.top(), Q1.pop(), ans += 1;
        else if(Q2.empty()) u += Q1.top(), Q1.pop(), ans += 1;
        else {
            int two = getTwo();
            if(two &gt; Q2.top()) {
                u += Q1.top(), Q1.pop(), ans += 1;
            } else {
                u += Q2.top(), Q2.pop(), ans += 2;
            }
        }
    }

if(u &lt; m) puts("-1");
    else printf("%d\n", ans);
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}</code></pre>
<p>另一种则是「惯用套路」。</p>
<pre><code class="cpp">#include &lt;bits/stdc++.h&gt;
#define d(x) cerr &lt;&lt; #x &lt;&lt; " =&gt; " &lt;&lt; x &lt;&lt; endl
#define dd(x) cerr &lt;&lt; #x &lt;&lt; endl
#define D cerr &lt;&lt; "Passed [" &lt;&lt; __FUNCTION__ "] on line " &lt;&lt; __LINE__ &lt;&lt; endl
using namespace std;
#define int long long
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);
}

vector&lt;int&gt; a, b;
vector&lt;int&gt; t1, t2, sum;

void solve() {
    int n = rd(), m = rd();
    a.resize(n + 1); b.resize(n + 1);
    t1.clear(); t2.clear(); sum.clear();

for(int i = 1; i &lt;= n; i++) {
        a[i] = rd();
    }

for(int i = 1; i &lt;= n; i++) {
        b[i] = rd();
        if(b[i] == 1) t1.push_back(a[i]);
        if(b[i] == 2) t2.push_back(a[i]);
    }

sort(t1.begin(), t1.end(), greater&lt;int&gt; () );
    sort(t2.begin(), t2.end(), greater&lt;int&gt; () );

if(t2.size() &gt; 0) sum.push_back(t2[0]);
    for(int i = 1; i &lt; (int)t2.size(); i++) {
        sum.push_back(sum[i - 1] + t2[i]);
    }

int tot = 0, cost = 0, ans = 0x7f7f7f7f7f7f7f;
    for(auto it : t1) {
        tot += it;
        cost++;
        if(tot &gt;= m) { ans = min(ans, cost); continue; }
        auto p = lower_bound(sum.begin(), sum.end(), m - tot);
        if(p == sum.end()) continue;
        ans = min(ans, cost + 2LL * (p - sum.begin() + 1LL));
    }
    auto p = lower_bound(sum.begin(), sum.end(), m);
    if(p != sum.end()) ans = min(ans, 2LL * (p - sum.begin() + 1LL));
    if(ans == 0x7f7f7f7f7f7f7f) puts("-1");
    else cout &lt;&lt; ans &lt;&lt; endl;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}</code></pre>
<h1>P4211 [LNOI2014]LCA</h1>
<p>每天一道树剖，保持抑郁。</p>
<p>不错的一道题。XD</p>
<p>考虑如果我们将原式差分 <katex-inline>\sum_{i=l}^{r}dep[lca(i, z)]=\sum_{i=1}^{r}dep[lca(i, z)] - \sum_{i=1}^{l-1}dep[lca(i,z)]</katex-inline> 。我们只需要求出所有的所需的 <katex-inline>\sum_{i=1}^{x}dep[lca(i, z)]</katex-inline> 即可。</p>
<p>考虑 <katex-inline>\sum_{i=l}^{r}dep[lca(i, z)]</katex-inline> 的图形意义。 我们发现所有的 <katex-inline>LCA</katex-inline> 一定在 <katex-inline>z</katex-inline> 到根的路径上。那么对于 <katex-inline>i=x</katex-inline> 的贡献，即为将 <katex-inline>x</katex-inline> 到根的路径上所有数字 <katex-inline>+1</katex-inline> 。最后查询 <katex-inline>z</katex-inline> 到根的路径的所有权值和即可。</p>
<pre><code class="cpp">#include &lt;bits/stdc++.h&gt;
#define d(x) cerr &lt;&lt; #x &lt;&lt; " =&gt; " &lt;&lt; x &lt;&lt; endl
#define dd(x) cerr &lt;&lt; #x &lt;&lt; endl
#define D cerr &lt;&lt; "Passed [" &lt;&lt; __FUNCTION__ &lt;&lt; "] on line " &lt;&lt; __LINE__ &lt;&lt; endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
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 = 2e5 + 5, M = 2e5 + 5;

class SegmentTree {
#define MID int mid = (l + r) &gt;&gt; 1
#define lson l, mid, x &lt;&lt; 1
#define rson mid + 1, r, x &lt;&lt; 1 | 1
public:
    static const int N = ::N;
    int sum[N &lt;&lt; 2], add[N &lt;&lt; 2];

SegmentTree() {
        ms(sum);
        ms(add);
    }

void build(int l, int r, int x) {
        if(l == r) {
            sum[x] = rd();
            return ;
        }
        MID; 
        build(lson); build(rson);
        sum[x] = sum[x &lt;&lt; 1] + sum[x &lt;&lt; 1 | 1];
    }

void modify_add(int l, int r, int x, int p, int q, int v) {
        if(p &lt;= l &amp;&amp; r &lt;= q) {
            add[x] += v;
            return ;
        }
        MID;
        sum[x] += (min(r, q) - max(l, p) + 1) * v;
        if(p &lt;= mid) modify_add(lson, p, q, v);
        if(q &gt; mid) modify_add(rson, p, q, v);
    }

int query(int l, int r, int x, int p, int q) {
        if(p &lt;= l &amp;&amp; r &lt;= q) {
            return sum[x] + add[x] * (r - l + 1);
        }
        MID; 
        int res = (min(r, q) - max(l, p) + 1) * add[x];
        if(p &lt;= mid) res += query(lson, p, q);
        if(q &gt; mid) res += query(rson, p, q);
        return res;
    }
} st;

struct Edge {
    int to, nxt;
} Edge[M &lt;&lt; 1];

int head[N], cnt;

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

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

void dfs1(int u, int d, int depth) {
    dep[u] = depth; fa[u] = d; sz[u] = 1; int maxsz = 0;
    for(int i = head[u]; ~i; i = Edge[i].nxt) {
        const int &amp;v = Edge[i].to;
        if(v == d) continue;
        dfs1(v, u, depth + 1);
        sz[u] += sz[v];
        if(maxsz &lt;= sz[v]) maxsz = 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 == fa[u] || v == hs[u]) continue;
        dfs2(v, v);
    }
}

struct Ques {
    int l, r, z;
} Ques[M];

map&lt;pair&lt;int, int&gt;, int&gt; maps;

struct E {
    int ti, z;
    bool operator&lt;(const E&amp; b) const {
        return ti &lt; b.ti;
    }
} e[M &lt;&lt; 1];

int ecnt, n;

void aRange(int x, int v) {
    while(top[x] != 0) {
        st.modify_add(1, n, 1, id[top[x]], id[x], v);
        x = fa[top[x]];
    }
    st.modify_add(1, n, 1, id[0], id[x], v);
}

int qRange(int x) {
    int res = 0;
    while(top[x] != 0) {
        res += st.query(1, n, 1, id[top[x]], id[x]);
        x = fa[top[x]];
    }
    res += st.query(1, n, 1, id[0], id[x]);
    res -= st.query(1, n, 1, id[0], id[0]);
    return res;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    memset(head, -1, sizeof head);
    n = rd(); int q = rd();
    for(int i = 1; i &lt; n; i++) {
        int v = rd();
        addEdge(i, v); addEdge(v, i);
    }

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

for(int i = 1; i &lt;= q; i++) {
        Ques[i].l = rd();
        Ques[i].r = rd();
        if(Ques[i].l &gt; Ques[i].r) swap(Ques[i].l, Ques[i].r);
        Ques[i].z = rd();
        if(Ques[i].l != 0) {
            e[++ecnt].ti = Ques[i].l - 1;
            e[ecnt].z = Ques[i].z;
        }
        e[++ecnt].ti = Ques[i].r;
        e[ecnt].z = Ques[i].z;
    }

sort(e + 1, e + ecnt + 1);

int ti = 0;
    for(int i = 1; i &lt;= ecnt; i++) {
        while(ti &lt;= e[i].ti) {
            aRange(ti, 1);
            ++ti;
        }
        maps[make_pair(e[i].ti, e[i].z)] = qRange(e[i].z);
    }

for(int i = 1; i &lt;= q; i++) {
        if(Ques[i].l == 0) printf("%lld\n", (maps[make_pair(Ques[i].r, Ques[i].z)] + Ques[i].r - Ques[i].l + 1) % 201314);
        else printf("%lld\n", (maps[make_pair(Ques[i].r, Ques[i].z)] - maps[make_pair(Ques[i].l - 1, Ques[i].z)] + (Ques[i].r - Ques[i].l + 1)) % 201314);
    }

return 0;
}</code></pre>