头像

gjh

青岛理工大学


访客:6544

离线:15小时前



gjh
2天前
#include <iostream>

using namespace std;

const int N = 5e5 + 10;

struct node{
    int l, r, tmax, lmax, rmax, sum;
}tr[N * 4];

int n, m, a[N];

node merge(node &l,node &r)
{
    node p;
    p.l = l.l, p.r = l.r;
    p.sum = l.sum + r.sum;
    p.tmax = max(l.rmax + r.lmax, max(l.tmax, r.tmax));
    p.lmax = max(l.lmax, l.sum + r.lmax);
    p.rmax = max(r.rmax, r.sum + l.rmax);
    return p;
}

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].tmax = max(tr[u << 1].rmax + tr[u << 1 | 1].lmax,max(tr[u << 1].tmax, tr[u << 1 | 1].tmax));
    tr[u].lmax = max(tr[u << 1].lmax, tr[u << 1].sum + tr[u << 1 | 1].lmax);
    tr[u].rmax = max(tr[u << 1 | 1].rmax, tr[u << 1].rmax + tr[u << 1 | 1].sum);

    // printf("从%d到%d 区间和是%d 最大前缀和为%d 最大后缀和为%d 最大区间和为 %d\n", tr[u].l, tr[u].r, tr[u].sum,tr[u].lmax,tr[u].rmax,tr[u].tmax);
}

void build(int u,int l,int r)
{
    tr[u] = {l, r};
    if (l == r) {
        tr[u] = {l, r, a[l], a[l], a[l], a[l]};
    }
    else {   
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

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

    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid) return query(u << 1, l, r);
    else if (l > mid) return query(u << 1 | 1, l, r);
    else {
        auto left = query(u << 1, l, r);
        auto right = query(u << 1 | 1, l, r);
        return merge(left, right);
    }
}

void modify(int u,int x,int v)
{
    if (tr[u].l == tr[u].r) {
        tr[u].lmax = tr[u].rmax = tr[u].sum = tr[u].tmax = v;
    }
    else {
        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);
    }
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    build(1, 1, n);
    // cout << endl;
    for (int i = 1; i <= m; i ++ ){
        int op;
        int x, y;
        cin >> op >> x >> y;
        if (op == 1 && x > y) swap(x, y);
        if (op == 1) cout << query(1, x, y).tmax << endl;
        else modify(1, x, y);
    } 
}

int main()
{
    solve();
}



gjh
2天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

#define int long long

const int N = 1e5 + 10;

int tr1[N], tr2[N];
int n, m, a[N];

int lowbite(int x) {return x & -x;}

void add(int tr[],int x,int d)
{
    for(int i = x; i <= n; i += lowbite(i) )  tr[i] += d;
}

int sum(int tr[],int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbite(i)) res += tr[i];
    return res;
}

int print(int x)
{
    return (x + 1) * sum(tr1,x) - sum(tr2,x);
}

signed main()
{
    cin >> n >> m;
    for (int i = 1; i<= n ; i++  ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) add(tr1,i, a[i] - a[i - 1]);
    for (int i = 1; i <= n; i ++ ) add(tr2,i, i * (a[i] - a[i - 1]));
    int x = 2;
    cout << (x + 1)  * sum(tr1,x) << endl;
    cout << sum(tr2,x) << endl;
    for (int i = 1; i <= m; i ++ )
    {
        string op;
        int l ,r, d;
        cin >> op >> l >> r;
        if (op == "C")
        {
            cin >> d;
            add(tr1, l, d), add(tr2, l, l * d);
            add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
        }
        else
        {
            cout << print(r) - print(l - 1) << endl;
        }
    }
}


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

gjh
2天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = N * 2, INT = 0x3f3f3f3f, mod = 1e9 + 7;

#define pi 3.1415926
#define x first
#define y second
typedef long long ll;
typedef pair<int,int> pii;
 //ios::sync_with_stdio(false);
ll gcd(ll a,ll b) {return b ? gcd(b, a % b) : a;}
ll qmi(ll a,ll b) {ll res = 1 % b;while (b){if (b & 1) res = (res * a) % mod;a = a * a % mod;b >>= 1;}return res;}

int t, n, m, tr[N], a[N], s[N];

int lowbite(int x) {return x & -x;}

void add(int x,int c)
{
    for (int i = x; i <= n; i += lowbite(i)) tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbite(i)) res += tr[i];
    return res;
}

int get(int x)
{
    int l = 1, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (sum(mid) >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

void solve()
{
    cin >> n;
    for (int i = 2; i <= n; i ++ ) cin >> a[i];

    for (int i = 1; i <= n; i ++ ) add(i, 1);

    for (int i = n; i; i -- ) 
    {
        s[i] = get(a[i] + 1);
        add(s[i], -1);
    }
    for (int i = 1; i <= n; i ++ ) cout << s[i] << endl;
}

int main()
{
    solve();
}



gjh
4天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = N * 2, INT = 0x3f3f3f3f, mod = 1e9 + 7;

#define pi 3.1415926
#define x first
#define y second
typedef long long ll;
typedef pair<int,int> pii;
 //ios::sync_with_stdio(false);
ll gcd(ll a,ll b) {return b ? gcd(b, a % b) : a;}
ll qmi(ll a,ll b) {ll res = 1 % b;while (b){if (b & 1) res = (res * a) % mod;a = a * a % mod;b >>= 1;}return res;}

int t, n, m, a[N], tr[N];

int lowbite(int x) {return x & -x;}

void add(int x,int c)
{
    for (int i = x; i <= n; i += lowbite(i)) tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbite(i)) res += tr[i];
    return res;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n ; i ++ ) cin >> a[i], add(i,a[i] - a[i - 1]);
    for (int i = 1; i <= m; i ++ )
    {
        string op;
        int x, l, r;
        cin >> op;
        if (op == "Q") {
            cin >> x;
            cout << sum(x) << endl;
        } else {
            cin >> l >> r >> x;
            add(l, x), add(r + 1, -x);
        }
    }
}

int main()
{
    solve();
}


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

gjh
5天前

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

define x first

define y second

typedef long long ll;
const int N = 2e5 + 10;

int tr[N], n, x, s[N], greator[N], lower[N];

int lowbite(int x) {return x & -x;}

void add(int x,int c)
{
for (int i = x; i <= n; i += lowbite(i)) tr[i] += c;
}

int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbite(i)) res += tr[i];
return res;
}

void solve()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> s[i];

for (int i = 0; i < n; i ++ ) 
{
    greator[i] = sum(n) - sum(s[i]);
    lower[i] = sum(s[i] - 1);
    add(s[i], 1);
}
memset(tr,0,sizeof tr);
ll res1 = 0, res2 = 0;
for(int i = n - 1; i >= 0; i --)
{

    res1 += (ll) (sum(n) - sum(s[i])) * greator[i];
    res2 += (ll) sum(s[i] - 1) * lower[i];
    add(s[i], 1);
}

cout << res1 << ' ' << res2 << endl;

}

int main()
{
solve();
}



活动打卡代码 AcWing 1250. 格子游戏

gjh
9天前
#include <iostream>

using namespace std;

const int N = 210;

int g[N][N], p[N * N];
int n, m;

int get(int a,int b) 
{
    return (a - 1) * n + b;
}

void init(int x)
{
    for (int i = 1; i <= x;i ++ ) p[i] = i;
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

bool merge(int a,int b)
{
    a = find(a), b = find(b);
    if (a != b) p[a] = b;
    else return true;
    return false;
}

int main()
{
    cin >> n >> m;
    init(n * n);
    for (int i = 1; i <= m; i ++ )
    {
        int x, y, s, t;
        char op;
        cin >> x >> y >> op;
        if (op == 'R') t = get(x, y + 1);
        else t = get(x + 1, y);

        s = get(x, y);

        if (merge(s, t)) {
            cout << i << endl;
            break;
        } else {
            if (i == m) cout << "draw" << endl;
        }
    }
}


活动打卡代码 AcWing 1252. 搭配购买

gjh
9天前
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

int n, m, w;
int f[N];
int c[N], d[N], p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int a, int b)
{
    a = find(a), b = find(b);

    if (a != b) 
    {
        p[a] = b;
        c[b] += c[a], d[b] += d[a];
    }
}

int main()
{
    cin >> n >> m >> w;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    for (int i = 1; i <= n ; i++ )  cin >> c[i] >> d[i];

    for (int i = 1; i <= m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        merge(a, b);
    }

    vector<int> q;
    q.push_back(0);
    for (int i = 1; i <= n; i ++ ) if (p[i] == i) q.push_back(i);

    int k = q.size();

    for (int i = 1; i < k; i ++ )
    {
        int j = q[i];
        for (int o = w; o >= 0; o -- )
            if (c[j] <= o) f[o] = max(f[o], f[o - c[j]] + d[j]);
    }
    cout << f[w] << endl;
}


活动打卡代码 AcWing 237. 程序自动分析

gjh
9天前
//
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int N = 2e6 + 10, M = N * 2, INT = 0x3f3f3f3f, mod = 1e9 + 7;

#define pi 3.1415926
#define x first
#define y second
typedef long long ll;
typedef pair<int,int> pii;
 //ios::sync_with_stdio(false);
ll gcd(ll a,ll b) {return b ? gcd(b, a % b) : a;}
ll qmi(ll a,ll b) {ll res = 1 % b;while (b){if (b & 1) res = (res * a) % mod;a = a * a % mod;b >>= 1;}return res;}

int t, n, m;
int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

bool solve()
{
    vector<pii> q;
    map<int,int> book;
    int cnt = 1;
    scanf("%d", &n);
    for (int i = 1; i <= 2 * n; i ++ ) p[i] = i;
    for (int i = 1; i <= n ;i ++ )
    {
        int a, b, e;
        scanf("%d%d%d", &a, &b, &e);

        if (book[a] == 0) book[a] = cnt ++;
        if (book[b] == 0) book[b] = cnt ++;
        a = book[a];
        b = book[b];
        if (e)
        {
            a = find(a), b = find(b);
            if (a != b) p[a] = b;
        }
        else q.push_back({a, b});
    }
    for (auto s : q)
    {
        int a = s.first, b = s.second;
        a = find(a), b = find(b);

        if (a == b) return false;
    }
    return true;
}
#include <iostream>
int main()
{
    int a;
    char b;
    char c[4];
    double d;
    cin >> a >> b >> c >> d;
    cout << a << endl << b << endl << c << endl << d;
}


活动打卡代码 AcWing 239. 奇偶游戏

gjh
9天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int N = 1e5 + 10, M = N * 2, INT = 0x3f3f3f3f, mod = 1e9 + 7;

#define pi 3.1415926
#define x first
#define y second
typedef long long ll;
typedef pair<int,int> pii;
 //ios::sync_with_stdio(false);
ll gcd(ll a,ll b) {return b ? gcd(b, a % b) : a;}
ll qmi(ll a,ll b) {ll res = 1 % b;while (b){if (b & 1) res = (res * a) % mod;a = a * a % mod;b >>= 1;}return res;}

int t, n, m;
int p[N], d[N];

map<int,int> book;

int find(int x)
{
    if (p[x] != x)
    {
        int root = find(p[x]);
        d[x] ^= d[p[x]];
        p[x] = root;
    }
    return p[x];
}

int solve()
{
    int cnt = 1;
    cin >> n >> m;
    for (int i = 1; i <= N; i ++ ) p[i] = i; 
    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        string op;
        cin >> a >> b >> op;
        printf("a = %d b = %d ", a, b);
        a --;
        if (book[a] == 0) book[a] = cnt ++;
        if (book[b] == 0) book[b] = cnt ++;
        a = book[a], b = book[b];
        t = 0;
        if (op == "odd") t = 1;

        int pa = find(a), pb = find(b);
        //printf("pa = %d pb = %d\n", pa, pb);
        if (pa == pb) {
            printf("d[a] = %d d[b] = %d\n", d[a], d[b]);
            if ((d[a] ^ d[b]) != t) return i;
        } else {

            p[pa] = pb;
            d[pa] = d[pa] ^ d[pb] ^ t;
            printf("d[pa] = %d\n", d[pa]);
        }
    }
   return m;
}

int main()
{
    cout << solve();
}


活动打卡代码 AcWing 238. 银河英雄传说

gjh
9天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30010;

int p[N], d[N], l[N];

void init()
{
    for (int i = 1; i < N; i ++ ) p[i] = i, l[i] = i;
}

int find(int x)
{
    if (p[x] != x)
    {
        int root = find(p[x]);
        if (d[x]) d[x] += d[p[x]];
        else d[x] = d[p[x]] + 1;
        p[x] = root;
    }

    return p[x];
}

void merge(int a,int b)
{
    int pa = find(a);
    int pb = find(b);
    if (pa != pb) {
        p[pa] = l[pb];
        l[pb] = l[pa];
    }
}

int query(int a,int b)
{
    int pa = find(a);
    int pb = find(b);
    if (pa != pb) return -1;
    else return abs(d[a] - d[b]) - 1;
}

int main()
{
    int n;
    cin >> n ;
    init();
    for (int i = 1; i <= n; i ++ ) {
        int a, b;
        char op;
        cin >> op >> a >> b;
        if (op == 'M') merge(a, b);
        else cout << query(a, b) << endl;
    }
}