头像

p_c


访客:9793

离线:2天前


活动打卡代码 AcWing 1128. 信使

p_c
1个月前
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5, M = 2e5 + 5;

struct Edge {
    int a, b, w;
    bool operator <(const Edge &W)const {
        return w < W.w;
    }
}edge[M];
int f[N];

inline int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]); 
}

int main(void) {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edge[i] = {a, b, c};
    }

    for(int i = 1; i <= n; i ++) f[i] = i;
    sort(edge + 1, edge + 1 + m);
    int cnt = 1, res = 0;
    for(int i = 1; i <= m; i ++) {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        int fa = find(a), fb = find(b);
        if(fa != fb) {
            cnt ++;
            res += w;
            f[fa] = fb;
        }
    }

    if(cnt == n) printf("%d\n", res);
    else printf("impossible\n");


    return 0;
}


活动打卡代码 AcWing 1129. 热浪

p_c
1个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue> 

using namespace std;

typedef pair<int, int> PII;

const int N = 2505, M = 6205;

int n, m, s, t;
int h[N], e[M * 2], ne[M * 2], w[M * 2], idx; 
int d[N];
bool vis[N];

inline void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
    e[idx] = a, ne[idx] = h[b], w[idx] = c, h[b] = idx ++;
}

inline int dijkstra(void) {
    memset(vis, false, sizeof vis);
    memset(d, 0x3f, sizeof d);
    priority_queue<PII, vector<PII>, greater<PII> > q;

    d[s] = 0;
    q.push({d[s], s}); vis[s] = true;
    while(q.size()) {
        PII t = q.top(); q.pop();
        int u = t.second, du = t.first;

        vis[u] = false;

        for(int i = h[u]; i + 1; i = ne[i]) {
            int v = e[i];
            if(d[v] > d[u] + w[i]) {
                d[v] = d[u] + w[i];
                if(!vis[v]) {
                    vis[v] = true;
                    q.push({d[v], v});
                }
            }
        }
    }

    return d[t];
}

int main(void) {
//  freopen("in.txt", "r", stdin);
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(h, -1, sizeof h);
    for(int i = 1; i <= m; i ++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    printf("%d\n", dijkstra());

    return 0;
}


活动打卡代码 AcWing 255. 第K小数

p_c
1个月前
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 1e5 + 5;

int cnt;
int a[maxn], v[maxn], root[maxn];
struct Treement{ int l, r, sum; }t[maxn * 20];

inline int find(int l, int r, int x) {
    while(l < r) {
        int mid = l + r >> 1;
        if(v[mid] >= x) r = mid;
        else l = mid + 1;
    }

    return l;
}

inline void init(int& s, int l, int r) {
    s = ++ cnt;
    t[s].sum = 0;
    if(l == r) return;
    int mid = l + r >> 1;
    init(t[s].l, l, mid);
    init(t[s].r, mid + 1, r);
}

inline void modify(int l, int r, int& x, int y, int k) {
    t[++ cnt] = t[y], t[cnt].sum ++, x = cnt;
    if(l == r) return;
    int mid = l + r >> 1;
    if(k <= mid) modify(l, mid, t[x].l, t[y].l, k);
    else modify(mid + 1, r, t[x].r, t[y].r, k);
}

inline int query(int l, int r, int x, int y, int k) {
    if(l == r) return l;
    int mid = l + r >> 1;
    int sum = t[t[y].l].sum - t[t[x].l].sum;
    if(k <= sum) return query(l, mid, t[x].l, t[y].l, k);
    else return query(mid + 1, r, t[x].r, t[y].r, k - sum); 
}

int main(void) {
    int n, m; scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), v[i] = a[i];

    sort(v + 1, v + 1 + n); 
    int num = unique(v + 1, v + 1 + n) - (v + 1);

    init(root[0], 1, num);

    for(int i = 1; i <= n; i ++)
        a[i] = find(1, num, a[i]);

    for(int i = 1; i <= n; i ++) modify(1, num, root[i], root[i - 1], a[i]);
    for(int i = 1; i <= m; i ++) {
        int l, r, tmp;
        scanf("%d%d%d", &l, &r, &tmp);
        printf("%d\n", v[query(1, num, root[l - 1], root[r], tmp)]); 
    }   


    return 0;
} 



p_c
1个月前
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 15;

int n; 
int a[maxn];
bool vis[maxn];

inline void dfs(int u) {
    if(u == n) {
        for(int i = 1; i <= n; i ++) 
            if(i == n) printf("%d\n", a[i]);
            else printf("%d ", a[i]);

        return;
    }

    for(int i = 1; i <= n; i ++) {
        if(vis[i]) continue;
        vis[i] = true;
        a[u + 1] = i;
        dfs(u + 1);
        vis[i] = false;
    }

}

int main(void) {
//  freopen("in.txt", "r", stdin);

    scanf("%d", &n);
    dfs(0);

    return 0;
}



p_c
1个月前
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 20;

int n; 
int a[maxn], cnt;
bool vis[maxn];

inline void dfs(int u, int v) {
    if(u > 0) {
        for(int i = 1; i <= cnt; i ++)
            if(i == cnt) printf("%d\n", a[i]);
            else printf("%d ", a[i]);
    }

    if(u == n) return;

    for(int i = 1; i <= n; i ++) {
        if(vis[i]) continue;
        if(i < v) continue;
        a[++ cnt] = i; vis[i] = true;
        dfs(u + 1, i);
        cnt --; vis[i] = false;
    }
}

int main(void) {
//  freopen("in.txt", "r", stdin); 
    scanf("%d", &n);
    puts("");
    dfs(0, 0);

//  fclose(stdin);
    return 0;
}


活动打卡代码 AcWing 1277. 维护序列

p_c
2个月前
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

const int maxn = 1e5 + 5;

int n, m, mod;
int a[maxn];

struct Treement {
    int l, r;
    LL sum;
    LL add, mul;
}tr[maxn * 4];

inline void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].sum %= mod;
}

inline void pushdown(int u) {
    Treement &nodel = tr[u << 1], &noder = tr[u << 1 | 1];
    nodel.add *= tr[u].mul; nodel.mul *= tr[u].mul; nodel.sum *= tr[u].mul;
    noder.add *= tr[u].mul; noder.mul *= tr[u].mul; noder.sum *= tr[u].mul;
    nodel.add += tr[u].add, nodel.sum += tr[u].add * (nodel.r - nodel.l + 1);
    noder.add += tr[u].add, noder.sum += tr[u].add * (noder.r - noder.l + 1);

    nodel.add %= mod; nodel.mul %= mod; nodel.sum %= mod;
    noder.add %= mod; noder.mul %= mod; noder.sum %= mod;

    tr[u].mul = 1, tr[u].add = 0;
}

inline void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0, 1};
    if(l == r) {
        tr[u].sum = a[l];
        return;
    }

    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);  
}

inline void modify_mul(int u, int l, int r, LL x) {
    if(l <= tr[u].l && tr[u].r <= r) {
        tr[u].add *=  x; tr[u].add %= mod;
        tr[u].mul *= x; tr[u].mul %= mod;
        tr[u].sum *= x; tr[u].sum %= mod;
        return;
    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) modify_mul(u << 1, l, r, x);
    if(r > mid) modify_mul(u << 1 | 1, l, r, x);
    pushup(u);
}

inline void modify_add(int u, int l, int r, LL x) {
    if(l <= tr[u].l && tr[u].r <= r) {
        tr[u].add += x; tr[u].add %= mod;
        tr[u].sum += x * (tr[u].r - tr[u].l + 1);
        tr[u].sum %= mod;
        return;
    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) modify_add(u << 1, l, r, x);
    if(r > mid) modify_add(u << 1 | 1, l, r, x);
    pushup(u);
}

inline LL query(int u, int l, int r) {
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum % mod;

    pushdown(u);
    int mid = tr[u].l + tr[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);
    pushup(u);

    return res % mod;   
}

int main(void) {
//  freopen("in.txt", "r", stdin);
    scanf("%d%d", &n, &mod);
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
        a[i] %= mod;
    }

    build(1, 1, n);

    scanf("%d", &m);
    while(m --) {
        int op, t, g;
        LL c;
        scanf("%d%d%d", &op, &t, &g);
        if(op == 1) {
            scanf("%lld", &c);
            c %= mod;
            modify_mul(1, t, g, c);
        } else if(op == 2) {
            scanf("%lld", &c);
            c %= mod;
            modify_add(1, t, g, c);
        } else {
            printf("%lld\n", query(1, t, g));
        }

    }



    return 0;
}


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

p_c
2个月前
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 200005; 

int n;
struct Triangle {
    double x, y1, y2;
    int c;
    bool operator< (const Triangle& t)const {
        return x < t.x;
    }
}triangle[maxn];
struct Treement {
     int l, r;
     int cnt;
     double len;
}tr[4 * maxn];
vector<double> ve;

inline int find(double x) {
    return lower_bound(ve.begin(), ve.end(), x) - ve.begin();
}

inline void pushup(int u) {
    if(tr[u].cnt) tr[u].len = ve[tr[u].r + 1] - ve[tr[u].l];
    else if(tr[u].l != tr[u].r) {
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    } else tr[u].len = 0;
} 

inline void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0};
    if(l != r) {
        int mid = l + r >> 1;
        build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); 
    }
}

inline void modify(int u, int l, int r, int c) {
    if(l <= tr[u].l && tr[u].r <= r) {
        tr[u].cnt += c;
        pushup(u);
        return;
    }

    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) modify(u << 1, l, r, c);
    if(r > mid) modify(u << 1 | 1, l, r, c);

    pushup(u);
}

int main(void) {
//  freopen("in.txt", "r", stdin);
    int count = 0;
    while(scanf("%d", &n) != EOF && n) {
        ve.clear();

        for(int i = 1, j = 0; i <= n; i ++) {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            triangle[j ++] = {x1, y1, y2, 1};
            triangle[j ++] = {x2, y1, y2, -1};
            ve.push_back(y1), ve.push_back(y2);
        }
//      puts("33");

        sort(ve.begin(), ve.end());
        ve.erase(unique(ve.begin(), ve.end()), ve.end());       

        build(1, 0, ve.size() - 2);  //由于在这个线段树中,每个节点所代表的是一个线段,而不是一个点,
                                     //所以这里需要在原来的基础上再 减去一个1;即:i:i - i + 1 
        sort(triangle, triangle + 2 * n);

        double fi = 0;
        double x1 = 0, x2 = 0;
        for(int i = 0; i < 2 * n; i ++) {
            //先计算面积 
            if(i > 0) fi += tr[1].len * (triangle[i].x - triangle[i - 1].x);

            //再将这段线段放到线段树上去 
            int l, r;
            l = find(triangle[i].y1);
            r = find(triangle[i].y2) - 1; 
            modify(1, l, r, triangle[i].c); 
        }

        printf("Test case #%d\nTotal explored area: %.2lf\n\n", ++ count, fi);
    }

    return 0;
} 



p_c
2个月前
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 1e5 + 5;

int a[maxn];
struct Treement {
    int l, r; 
    LL sum, add;
}t[maxn * 4];
char str[5];

void pushdown(int u) {
    Treement &root = t[u], &left = t[u << 1], &right = t[u << 1 | 1];
    left.add += root.add; left.sum += (left.r - left.l + 1) * root.add;
    right.add += root.add; right.sum += (right.r - right.l + 1) * root.add;
    root.add = 0;
}

void pushup(int u) {
    t[u].sum = t[u << 1].sum + t[u << 1 | 1].sum;
}

void change(int u, int l, int r, LL d) {
    if(l <= t[u].l && t[u].r <= r) {
        t[u].add += d;
        t[u].sum += (t[u].r - t[u].l + 1) * d;
        return;
    }

    pushdown(u);
    int mid = t[u].l + t[u].r >> 1;
    if(l <= mid) change(u << 1, l, r, d);
    if(r > mid) change(u << 1 | 1, l, r, d);
    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);
    pushup(u);

    return res; 
}

void build(int u, int l, int r) {
    t[u] = {l, r};
    if(l == r) {
        t[u].sum = a[l];
        return;
    }

    int mid = l + r >> 1;
    build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

int main(void) {
//  freopen("in.txt", "r", stdin);
    int n, m; scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    build(1, 1, n);
    while(m --) {
        int l, r;
        LL d;
        scanf("%s%d%d", str, &l, &r);
        if(str[0] == 'Q') {
            printf("%lld\n", query(1, l, r));
        } else {
            scanf("%lld", &d);
            change(1, l, r, d);
        }
    }


    return 0;
}



p_c
2个月前
/*
(a, b, c) = (a, b - a, c - b);
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 5e5 + 5;

struct Node {
    int l, r;
    LL gcdd, sum;
}t[maxn * 4];
LL a[maxn];
char str[5];

LL gcd(LL x, LL y) { return y ? gcd(y, x % y) : x; }
void pushup(int u) {
    t[u].gcdd = gcd(t[u << 1].gcdd, t[u << 1 | 1].gcdd);
    t[u].sum = t[u << 1].sum + t[u << 1 | 1].sum;
}

void build(int u, int l, int r) {
    t[u].l = l, t[u].r = r;
    if(l == r) {
        t[u].gcdd = a[l];
        t[u].sum = a[l];
        return;
    }

    int mid = l + r >> 1;
    build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void change(int u, int idx, LL x) {
    if(t[u].l == t[u].r && t[u].l == idx) {
        t[u].gcdd += x;
        t[u].sum += x;

        return;
    }

    int mid = t[u].l + t[u].r >> 1;
    if(idx <= mid) change(u << 1, idx, x);
    else change(u << 1 | 1, idx, x);
    pushup(u);
}

LL query_sum(int u, int l, int r) {
    if(l <= t[u].l && t[u].r <= r) return t[u].sum;

    int mid = t[u].l + t[u].r >> 1;
    LL res = 0;
    if(l <= mid) res = query_sum(u << 1, l, r);
    if(mid < r) res += query_sum(u << 1 | 1, l, r); 

    return res;
}

LL query_gcd(int u, int l, int r) {
    if(l <= t[u].l && t[u].r <= r) return t[u].gcdd;

    int mid = t[u].l + t[u].r >> 1;

    LL res;
    if(r <= mid) res = query_gcd(u << 1, l, r);
    else if(l > mid) res = query_gcd(u << 1 | 1, l, r);
    else res = gcd(query_gcd(u << 1, l, r), query_gcd(u << 1 | 1, l, r));

    return res;
}

int main(void) {
//  freopen("in.txt", "r", stdin);
    int n, m; scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
        scanf("%lld", &a[i]);
    for(int i = n; i >= 1; i --)
        a[i] = a[i] - a[i - 1];

    build(1, 1, n);

    while(m --) {
        scanf("%s", str);
        int l, r;
        LL x;
        if(str[0] == 'Q') {
            scanf("%d%d", &l, &r);
            LL tmp1, tmp2;
            tmp1 = query_sum(1, 1, l);
            tmp2 = query_gcd(1, l + 1, r);
            printf("%lld\n", abs(gcd(tmp1, tmp2)));

        } else {
            scanf("%d%d%lld", &l, &r, &x);
            change(1, l, x); 
            if(r + 1 <= n)
                change(1, r + 1, -x);
        }
    }
    return 0;
}



p_c
2个月前
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 5e5 + 5, inf = 1e5;

typedef long long LL;

int n, m; 
struct Node {
    int l, r; 
    int l_max, r_max, sum; 
    int dat;
}tr[maxn * 4];
int a[maxn];

inline void pushup(int u) {
    tr[u].l_max = max(tr[u << 1].l_max, tr[u << 1].sum + tr[u << 1 | 1].l_max);
    tr[u].r_max = max(tr[u << 1 | 1].r_max, tr[u << 1 | 1].sum + tr[u << 1].r_max);
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].dat = max(max(tr[u << 1].dat, tr[u << 1 | 1].dat), tr[u << 1].r_max + tr[u << 1 | 1].l_max);
}

inline void build(int u, int l, int r) {
    tr[u] = {l, r};
    if(l == r) {
        tr[u].l_max = tr[u].r_max = tr[u].sum = tr[u].dat = a[l];
        return; 
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

inline void modify(int u, int x, int v) {
    if(tr[u].l == x && tr[u].r == x) {
        tr[u].l_max = tr[u].r_max = tr[u].sum = tr[u].dat = v;
        return; 
    }

    int mid = tr[u].l + tr[u].r >> 1;
    if(x <= mid) modify(u << 1, x, v);
    else modify(u << 1 | 1, x, v);

    pushup(u);
}

inline Node query(int u, int l, int r) {
    if(l <= tr[u].l && tr[u].r <= r) return tr[u];

    int mid = tr[u].l + tr[u].r >> 1;
    Node x, y, z;

    if(l <= mid) x = query(u << 1, l, r);
    if(r > mid) y = query(u << 1 | 1, l, r); 

    if(r <= mid) return x;
    else if(l >= mid + 1) return y;
    else {
        z.l_max = max(x.l_max, x.sum + y.l_max);
        z.r_max = max(y.r_max, y.sum + x.r_max);
        z.sum = x.sum + y.sum;
        z.dat = max(max(x.dat, y.dat), x.r_max + y.l_max); 
        return z;
    }   
}

int main(void) {
//  freopen("in.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    build(1, 1, n);

    int op, x, y;
    while(m --) {
        scanf("%d%d%d", &op, &x, &y);
        if(op == 1) {
            if(x > y) swap(x, y);
            Node fi = query(1, x, y);
            printf("%d\n", fi.dat);
        } else {
            modify(1, x, y);
        }
    }



    return 0;
}