头像

mesopotamian


关注数
0
粉丝数
0
阅读量
6502


离线:1小时前



mesopotamian
16小时前
#include <iostream>
#include <cstring>

using namespace std;
const int N = 6e3+10;
int h[N], tot, w[N], d[N];
struct {int to,nxt;}e[N << 1];
int f[N][2];
int n;
void add(int a,int b)
{
    e[tot].to = b, e[tot].nxt = h[a], h[a] = tot ++;
}
void dfs(int u)
{
    f[u][0] = 0; f[u][1] = w[u];
    for(int i = h[u]; ~i; i = e[i].nxt)
    {
        int to = e[i].to;
        dfs(to);
        f[u][0] += max(f[to][0], f[to][1]);
        f[u][1] += max(f[to][0], 0);
    }
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    for(int i = 1; i < n; ++i) 
    {
        int l, k; scanf("%d%d", &l, &k);
        add(k, l); d[l] ++;
    }
    int rt = 1;
    while(d[rt]) rt ++;
    dfs(rt);
    printf("%d", max(f[rt][0], f[rt][1]));
}


活动打卡代码 AcWing 164. 可达性统计

#include <iostream>
#include <bitset>
#include <cstring>
using namespace std;
const int N = 3e4+10;
bitset<N> a[N];
int n, m;
int h[N], tot, vis[N];
struct {int to,nxt; }e[N];
void add(int a,int b)
{
    e[tot].to = b, e[tot].nxt = h[a], h[a] = tot ++;
}
void dfs(int u)
{
    a[u][u] = 1; vis[u] = 1;
    for(int i = h[u]; ~i; i = e[i].nxt)
    {
        int to = e[i].to;
        if(!vis[to]) dfs(to);
        a[u] |= a[to];
    }
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i)
    {
        int a, b; scanf("%d%d", &a, &b);
        add(a, b); 
    }
    for(int i = 1; i <= n; ++i) if(!vis[i]) dfs(i);
    for(int i = 1; i <= n; ++i) printf("%d\n", a[i].count());
}


活动打卡代码 AcWing 165. 小猫爬山

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int n, m, w[N], ans = 1e9;
int v[N];
void dfs(int u,int num)
{
    if(num >= ans) return;
    if(u == n)
    {
        ans = num;
        return;
    }
    for(int i = 0; i < num; ++i)
    {
        if(v[i] + w[u] <= m)
        {
            v[i] += w[u];
            dfs(u + 1, num);
            v[i] -= w[u];
        }
    }
    v[num] = w[u];
    dfs(u + 1, num + 1);
    v[num] = 0;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i) scanf("%d", &w[i]);
    sort(w, w + n); reverse(w, w + n);
    dfs(0, 0);
    cout << ans;
}


活动打卡代码 AcWing 241. 楼兰图腾

#include <iostream>
#include <cstring>
#define LL long long
using namespace std;

const int N = 2e5+10;
int a[N], c[N], m;
LL n[N], v[N];
void add(int p, int k)
{
    for(int i = p; i <= m; i += i & -i) c[i] ++;
}
int sum(int p)
{
    int res = 0;
    while(p)
    {
        res += c[p];
        p -= -p & p;
    }
    return res;
}
int main()
{
    scanf("%d", &m);
    for(int i = 1; i <= m; ++ i) scanf("%d", &a[i]);

    for(int i = 1; i <= m; ++i)
    {
        n[i] += sum(a[i]); 
        v[i] += i - 1 - n[i];
        add(a[i], 1);
    }
    memset(c, 0, sizeof c);
    LL sn = 0, sv = 0;
    for(int i = m; i; i --)
    {
        int t = sum(a[i]);
        add(a[i], 1);
        n[i] *= t;
        v[i] *= (m - i - t);
        sn += n[i]; sv += v[i];
    }
    printf("%lld %lld", sv, sn);
}


活动打卡代码 AcWing 244. 谜一样的牛

#include <iostream>

using namespace std;
const int N = 1e5+10;

int a[N], c[N], n;
void add(int p, int k)
{
    for(int i = p; i <= n; i += -i & i) c[i] += k;
}
int sum(int p)
{
    int res = 0;
    while(p)
    {
        res += c[p];
        p -= -p & p;
    }
    return res;
}
int main()
{
    scanf("%d", &n);
    for(int i = 2; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i) add(i, 1);
    for(int i = n; i; i --)
    {
        int l = 1, r = n;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(sum(mid) >= a[i] + 1) r = mid;
            else l = mid + 1;
        }
        a[i] = r;
        add(r, -1);
    }
    for(int i = 1; i <= n; ++i) printf("%d\n", a[i]);
}




#include <iostream>
#include <cstring>
#include <cmath>
#define LL long long
#define mid (t[u].l + t[u].r >> 1)
using namespace std;
const int N = 1e5+10, M = 350;
int n, m;
int w[N];
struct SegTree
{
    int l, r;
    LL add, sum;
}t[N << 4];
void pushup(int u)
{
    t[u].sum = t[u << 1].sum + t[u << 1 | 1].sum;
}
void pushdown(int u)
{
    auto &fa = t[u], &l = t[u << 1], &r = t[u << 1 | 1];
    if(fa.add)
    {
        l.add += fa.add; l.sum += fa.add * (l.r - l.l + 1);
        r.add += fa.add; r.sum += fa.add * (r.r - r.l + 1);
        fa.add = 0;
    }
}
void build(int u,int l,int r)
{
    t[u] = {l, r, 0, w[r]};
    if(l == r) return;
    build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void update(int u,int l, int r,int k)
{
    if(t[u].l >= l && t[u].r <= r)
    {
        t[u].add += k;
        t[u].sum += (LL) k * (t[u].r - t[u].l + 1);
        return;
    }
    pushdown(u);
    if(l <= mid) update(u << 1, l, r, k);
    if(r > mid) update(u << 1 | 1, l, r, k);
    pushup(u);
}
LL query(int u, int l,int r)
{
    if(t[u].l >= l && t[u].r <= r) return t[u].sum;
    pushdown(u);
    LL res = 0;
    if(l <= mid) res += query(u << 1, l, r);
    if(r > mid) res += query(u << 1|1, l, r);
    return res;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i) scanf("%d", &w[i]);
    build(1, 0, n - 1);
    char t[2];
    int l, r, d;
    while(m --)
    {
        scanf("%s%d%d", t, &l, &r);
        if(t[0] == 'C')
        {
            scanf("%d", &d);
            update(1, l - 1, r - 1, d);
        }
        else printf("%lld\n", query(1, l - 1, r - 1));
    }
}


活动打卡代码 AcWing 248. 窗内的星星

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

#define mid (t[u].l + t[u].r >> 1) 
using namespace std;
const int N = 1e5+10;
struct Seg
{
    int x, y1, y2, c;
    bool operator<(const Seg &b) const
    {
        if(x != b.x) return x < b.x;
        return c < b.c;
    }
}segs[N];
struct SegTree
{
    int l, r;
    int add, c;
}t[N << 4];
vector<int> ys;
int id(int x)
{
    return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}
void pushup(int u)
{
    t[u].c = max(t[u << 1].c, t[u << 1 | 1].c);
}
void build(int u,int l,int r)
{
    t[u] = {l, r, 0, 0};
    if(l == r) return;
    build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
}
void pushdown(int u)
{
    auto &fa = t[u], &l = t[u << 1], &r = t[u << 1 | 1];
    if(fa.add)
    {
        l.add += fa.add, l.c += fa.add;
        r.add += fa.add, r.c += fa.add;
        fa.add = 0;
    }
}
void update(int u,int l,int r, int k)
{
    if(l <= t[u].l && t[u].r <= r) 
    {
        t[u].add += k; t[u].c += k;
        return;
    }
    pushdown(u);
    if(l <= mid) update(u << 1, l, r, k);
    if(r > mid) update(u << 1 | 1, l, r, k);
    pushup(u);
}
int main()
{
    int n, W, H;
    while(cin >> n >> W >> H)
    {
        ys.clear();
        for(int i = 0; i < n; ++i)
        {
            int x, y, c;
            scanf("%d%d%d", &x, &y, &c);
            segs[i * 2] = {x, y, y + H, c};
            segs[i * 2 + 1] = {x + W, y, y + H, -c};
            ys.push_back(y); ys.push_back(y + H);
        }
        sort(ys.begin(),ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());
        build(1, 0, ys.size() - 2);
        sort(segs, segs + n * 2);
        int ans = 0;
        for(int i = 0; i < n * 2; ++i)
        {
            update(1, id(segs[i].y1), id(segs[i].y2) - 1, segs[i].c);
            ans = max(ans, t[1].c);
        }
        printf("%d\n", ans);
    }
}


活动打卡代码 AcWing 247. 亚特兰蒂斯

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define mid (t[u].l + t[u].r >> 1)
using namespace std;
const int N = 1e5+10;
struct Seg
{
    double x, y1, y2;
    int k;
    bool operator<(const Seg &b)const
    {
        return x < b.x;
    }
}segs[N << 1];
vector<double> ys;
struct SegTree
{
    int l, r;
    int cnt;
    double len;
}t[N << 4];
int id(double x)
{
    return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}
void build(int u,int l,int r)
{
    t[u] = {l, r, 0, 0};
    if(l == r)return;
    build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
}
void pushup(int u)
{
    if(t[u].cnt) t[u].len = ys[t[u].r + 1] - ys[t[u].l];
    else if(t[u].l != t[u].r)
        t[u].len = t[u << 1].len + t[u << 1 | 1].len;
    else t[u].len = 0;
}
void update(int u,int l,int r,int k)
{
    if(l <= t[u].l && t[u].r <= r) 
    {
        t[u].cnt += k;
        pushup(u);
        return;
    }
    if(l <= mid) update(u << 1, l, r, k);
    if(r > mid) update(u << 1 | 1, l, r, k);
    pushup(u);
}
int main()
{
    int T = 1, n;
    while(cin >> n && n)
    {
        ys.clear();
        for(int i = 0; i < n; ++i)
        {
            double x1, x2, y1, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            segs[i * 2] = {x1, y1, y2, 1};
            segs[i * 2 + 1] = {x2, y1, y2, -1};
            ys.push_back(y1); ys.push_back(y2);
        }
        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(),ys.end()), ys.end());
        build(1, 0, ys.size() - 2);
        sort(segs, segs + n * 2);
        double area = 0;
        for(int i = 0; i < n * 2; ++i)
        {
            if(i) area += t[1].len * (segs[i].x - segs[i - 1].x);
            update(1, id(segs[i].y1), id(segs[i].y2) - 1, segs[i].k);
        }
        printf("Test case #%d\nTotal explored area: %.2lf\n\n", T ++, area);
    }
}



活动打卡代码 AcWing 918. 软件包管理器

#include <iostream>
#include <cstring>
#include <algorithm>
#define mid (t[u].l + t[u].r >> 1)
using namespace std;
const int N = 1e5+10;
int n;
int h[N],tot;
struct {int to,nxt;}e[N];
int dep[N], fa[N], son[N], top[N], sz[N];
int id[N], cnt;
struct Node
{
    int l, r;
    int flag, sum;
}t[N << 4];
void add(int a,int b)
{
    e[tot].to = b, e[tot].nxt = h[a], h[a] = tot ++;
}
void dfs1(int u,int depth)
{
    dep[u] = depth, sz[u] = 1;
    for(int i = h[u]; ~i; i = e[i].nxt)
    {
        int to = e[i].to;
        if(to == fa[u]) continue;
        dfs1(to, depth + 1);
        sz[u] += sz[to];
        if(sz[son[u]] < sz[to]) son[u] = to;
    }
}
void dfs2(int u,int t)
{
    id[u] = ++ cnt; top[u] = t;
    if(!son[u]) return;
    dfs2(son[u], t);
    for(int i = h[u]; ~i; i = e[i].nxt)
    {
        int to = e[i].to;
        if(to == son[u] || to == fa[u]) continue;
        dfs2(to, to);
    }
}
void pushup(int u)
{
    t[u].sum = t[u << 1].sum + t[u << 1 | 1].sum;
}
void pushdown(int u)
{
    auto &fa = t[u], &l = t[u << 1], &r = t[u << 1 | 1];
    if(fa.flag != -1)
    {
        l.flag = fa.flag; l.sum = fa.flag * (l.r - l.l + 1);
        r.flag = fa.flag; r.sum = fa.flag * (r.r - r.l + 1);
        fa.flag = -1;
    }
}
void build(int u,int l,int r)
{
    t[u] = {l, r, -1, 0};
    if(l == r) return;
    build(u << 1, l, mid); build(u << 1 | 1,mid + 1, r);
}
void update(int u,int l,int r,int k)
{
    if(l <= t[u].l && t[u].r <= r)
    {
        t[u].flag = k;
        t[u].sum = k * (t[u].r - t[u].l + 1);
        return;
    }
    pushdown(u);
    if(l <= mid) update(u << 1, l, r, k);
    if(r > mid) update(u << 1 | 1, l, r, k);
    pushup(u);
}
int query(int u,int l,int r)
{
    if(l <= t[u].l && t[u].r <= r) return t[u].sum;
    pushdown(u);
    int res = 0;
    if(l <= mid) res += query(u << 1, l, r);
    if(r > mid) res += query(u << 1 | 1, l, r);
    return res;
}
void update_path(int u,int v,int k)
{
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        update(1, id[top[u]], id[u], k);
        u = fa[top[u]];
    }
    if(dep[u] < dep[v]) swap(u, v);
    update(1, id[v], id[u], k);
}
void update_tree(int u,int k)
{
    update(1, id[u], id[u] + sz[u] - 1, k);
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for(int i = 2; i <= n; ++i)
    {
        int p; scanf("%d", &p); p ++;
        add(p, i);
        fa[i] = p;
    }
    dfs1(1, 1);
    dfs2(1, 1);
    build(1, 1, n);
    int m, x; scanf("%d", &m);
    char op[10];
    while(m --)
    {
        scanf("%s%d", op, &x); x ++;
        if(!strcmp(op, "install"))
        {
            int sum = t[1].sum;
            update_path(1, x, 1);
            printf("%d\n", t[1].sum - sum);
        }
        else
        {
            int sum = t[1].sum;
            update_tree(x, 0);
            printf("%d\n", sum - t[1].sum);
        }
    }
}


活动打卡代码 AcWing 2568. 树链剖分

#include <iostream>
#include <algorithm>
#include <cstring>
#define LL long long
using namespace std;
const int N = 1e5+10, M = N << 1;
int w[N], n;
int h[N], tot;
struct {int to,nxt; }e[M];
int id[N], nw[N], cnt;
int fa[N], son[N], dep[N], top[N], sz[N];
struct Node
{
    int l, r;
    LL add, sum;
}t[N << 4];
void add(int a,int b)
{
    e[tot].to = b, e[tot].nxt = h[a], h[a] = tot ++;
}
void dfs1(int u,int father,int depth)
{
    dep[u] = depth; fa[u] = father; sz[u] = 1;
    for(int i = h[u]; ~i; i = e[i].nxt)
    {
        int to = e[i].to;
        if(to == father) continue;
        dfs1(to, u, depth + 1);
        sz[u] += sz[to];
        if(sz[son[u]] < sz[to]) son[u] = to;
    }
}
void dfs2(int u,int t)
{
    id[u] = ++ cnt; nw[cnt] = w[u]; top[u] = t;
    if(!son[u]) return;
    dfs2(son[u], t);
    for(int i = h[u]; ~i; i = e[i].nxt)
    {
        int to = e[i].to;
        if(to == fa[u] || to == son[u]) continue;
        dfs2(to, to);
    }
}
void pushup(int u)
{
    t[u].sum = t[u << 1].sum + t[u << 1 | 1].sum;
}
void pushdown(int u)
{
    auto &fa = t[u], &l = t[u << 1], &r = t[u << 1 | 1];
    if(fa.add)
    {
        l.add += fa.add; l.sum += fa.add * (l.r - l.l + 1);
        r.add += fa.add; r.sum += fa.add * (r.r - r.l + 1);
        fa.add = 0;
    }
}
void build(int u,int l,int r)
{
    t[u] = {l, r, 0, nw[r]};
    if(l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void update(int u,int l,int r,int k)
{
    if(l <= t[u].l && t[u].r <= r) 
    {
        t[u].add += k;
        t[u].sum += k * (t[u].r - t[u].l + 1);
        return;
    }
    pushdown(u);
    int mid = t[u].l + t[u].r >> 1;
    if(l <= mid) update(u << 1, l, r, k);
    if(r > mid) update(u << 1 | 1, l, r, k);
    pushup(u);
}
LL query(int u,int l,int r)
{
    if(l <= t[u].l && t[u].r <= r) return t[u].sum;
    pushdown(u);
    int mid = t[u].l + t[u].r >> 1;
    LL res = 0;
    if(l <= mid) res += query(u << 1, l, r);
    if(r >mid) res += query(u << 1 | 1, l, r);
    return res;
}
void update_tree(int u,int k)
{
    update(1, id[u], id[u] + sz[u] - 1, k);
}
void update_path(int u,int v,int k)
{
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        update(1, id[top[u]], id[u], k);
        u = fa[top[u]];
    }
    if(dep[u] < dep[v]) swap(u, v);
    update(1, id[v], id[u], k);
}
LL query_tree(int u)
{
    return query(1, id[u], id[u] + sz[u] - 1);
}
LL query_path(int u,int v)
{
    LL res = 0;
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        res += query(1, id[top[u]], id[u]);
        u = fa[top[u]];
    }
    if(dep[u] < dep[v]) swap(u, v);
    res += query(1, id[v], id[u]);
    return res;
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    for(int i = 1; i < n; ++i)
    {
        int a, b; scanf("%d%d", &a, &b);
        add(a, b); add(b, a);
    }
    dfs1(1, -1, 1);
    dfs2(1, 1);
    build(1, 1, n);
    int m; scanf("%d", &m);
    int t, u, v, k;
    while(m --)
    {
        scanf("%d%d", &t, &u);
        if(t == 1)
        {
            scanf("%d%d", &v, &k);
            update_path(u, v, k);
        }
        else if(t == 2)
        {
            scanf("%d", &k);
            update_tree(u, k);
        }
        else if(t == 3)
        {
            scanf("%d", &v);
            printf("%lld\n", query_path(u, v));
        }
        else printf("%lld\n", query_tree(u));
    }
}