头像

lyktes

哈!




离线:15小时前


最近来访(784)
用户头像
封禁用户
用户头像
RyanMoriarty
用户头像
知不可乎骤得
用户头像
Joseph1314
用户头像
潘潘_the_panda
用户头像
沐星不仙了
用户头像
郫县林俊杰
用户头像
pine_7
用户头像
15358022392
用户头像
Sparkle_ZH
用户头像
zhihaoFu
用户头像
Justice
用户头像
心劫说给影子听
用户头像
13962588881
用户头像
墨染樱飞
用户头像
多财多亿
用户头像
小猪快跑ya
用户头像
焦亚硫酸钠
用户头像
IEE_
用户头像
Peter_5

新鲜事 原文

lyktes
1天前
我 emo 了。 怎么办。


新鲜事 原文

lyktes
16天前
关于学校老师造的数据 dfs 9ms,dp 17ms 这码事……


新鲜事 原文

lyktes
21天前
啊呜啊呜哇 各位觉得 ac saber 哪个段位最好看啊/kel



lyktes
29天前
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

#define int long long
struct Node
{
    int l, r;
    int add, gcd;
#define l(x) c[x].l
#define r(x) c[x].r
#define add(x) c[x].add
#define gcd(x) c[x].gcd
} c[N << 2];
int a[N];
int n, m;

void update(int p)
{
    gcd(p) = __gcd(gcd(p << 1), gcd(p << 1 | 1));
}

void build(int p, int l, int r)
{
    l(p) = l, r(p) = r;
    if (l == r)
    {
        gcd(p) = a[l] - a[l - 1];
        return;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    update(p);
}

void modify(int p, int l, int r, int d)
{
    if (l(p) == r(p))
    {
        gcd(p) += d;
        return;
    }
    if (l <= r(p << 1))
        modify(p << 1, l, r, d);
    if (l(p << 1 | 1) <= r)
        modify(p << 1 | 1, l, r, d);
    update(p);
}

int query(int p, int l, int r)
{
    if (l <= l(p) && r(p) <= r)
        return gcd(p);
    int gcdd = 0;
    if (l <= r(p << 1))
        gcdd = __gcd (gcdd, query(p << 1, l, r));
    if (l(p << 1 | 1) <= r)
        gcdd = __gcd (gcdd, query(p << 1 | 1, l, r));
    return abs(gcdd);
}

namespace BIT
{
    int c[N];
    void Add(int x, int y)
    {
        for (; x < N; x += x & -x)
            c[x] += y;
    }
    int Query(int x)
    {
        int res = 0;
        for (; x; x -= x & -x)
            res += c[x];
        return res;
    }
}

signed main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    build(1, 1, n);
    while (m--)
    {
        char op = getchar();
        while (!isupper(op))
            op = getchar();
        int l, r;
        scanf("%lld%lld", &l, &r);
        if (op == 'Q')
        {
            int A = 0;
            if (l < r)
                A = query(1, l + 1, r);
            int B = a[l] + BIT::Query(l);
            printf("%lld\n", __gcd(A, B));
        }
        else
        {
            int k;
            scanf("%lld", &k);
            modify(1, l, l, k);
            if (r < n)
                modify(1, r + 1, r + 1, -k);
            BIT::Add(l, k);
            BIT::Add(r + 1, -k);
        }
    }
    return 0;
}



lyktes
1个月前
#include <bits/stdc++.h>

const int N = 1e5 + 5;
int n;
bool st[N];

int main()
{
    scanf("%d", &n);
    for (int i = 2; i <= n + 1; i++)
    {
        if (st[i])
            continue;
        for (int j = i << 1; j <= n + 1; j += i)
            st[j] = 1;
    }
    if (n <= 2)
        puts("1");
    else
        puts("2");
    for (int i = 2; i <= n + 1; i++)
        printf("%d ", 1 + st[i] * 1);
    return 0;
}


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

lyktes
1个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

#define int long long
struct Node
{
    int l, r;
    int add, mul;
    int sum;
#define l(x) c[x].l
#define r(x) c[x].r
#define add(x) c[x].add
#define mul(x) c[x].mul
#define sum(x) c[x].sum
} c[N << 2];
int a[N];
int n, m, P;

void build(int p, int l, int r)
{
    mul(p) = 1;
    l(p) = l, r(p) = r;
    if (l == r)
    {
        sum(p) = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    sum(p) = (sum(p << 1) + sum(p << 1 | 1)) % P;
}

void spread(int p)
{
    sum(p << 1) = (sum(p << 1) * mul(p) + (r(p << 1) - l(p << 1) + 1) * add(p)) % P;
    sum(p << 1 | 1) = (sum(p << 1 | 1) * mul(p) + (r(p << 1 | 1) - l(p << 1 | 1) + 1) * add(p)) % P;
    mul(p << 1) = (mul(p << 1) * mul(p)) % P;
    mul(p << 1 | 1) = (mul(p << 1 | 1) * mul(p)) % P;
    add(p << 1) = (add(p << 1) * mul(p) + add(p)) % P;
    add(p << 1 | 1) = (add(p << 1 | 1) * mul(p) + add(p)) % P;
    mul(p) = 1;
    add(p) = 0;
}

void modify1(int p, int l, int r, int d)
{
    if (l <= l(p) && r(p) <= r)
    {
        sum(p) = (sum(p) * d) % P;
        add(p) = (add(p) * d) % P;
        mul(p) = (mul(p) * d) % P;
        return;
    }
    spread(p);
    if (l <= r(p << 1))
        modify1(p << 1, l, r, d);
    if (l(p << 1 | 1) <= r)
        modify1(p << 1 | 1, l, r, d);
    sum(p) = (sum(p << 1) + sum(p << 1 | 1)) % P;
}

void modify2(int p, int l, int r, int d)
{
    if (l <= l(p) && r(p) <= r)
    {
        sum(p) = (sum(p) + (r(p) - l(p) + 1) * d) % P;
        add(p) = (add(p) + d) % P;
        return;
    }
    spread(p);
    if (l <= r(p << 1))
        modify2(p << 1, l, r, d);
    if (l(p << 1 | 1) <= r)
        modify2(p << 1 | 1, l, r, d);
    sum(p) = (sum(p << 1) + sum(p << 1 | 1)) % P;
}

int query(int p, int l, int r)
{
    if (l <= l(p) && r(p) <= r)
        return sum(p);
    spread(p);
    int res = 0;
    if (l <= r(p << 1))
        res = (res + query(p << 1, l, r)) % P;
    if (l(p << 1 | 1) <= r)
        res = (res + query(p << 1 | 1, l, r)) % P;
    return res;
}

signed main()
{
    scanf("%lld%lld", &n, &P);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    build(1, 1, n);
    scanf("%lld", &m);
    while (m--)
    {
        int op, l, r;
        scanf("%lld%lld%lld", &op, &l, &r);
        if (op == 1)
        {
            int k;
            scanf("%lld", &k);
            modify1(1, l, r, k);
        }
        if (op == 2)
        {
            int k;
            scanf("%lld", &k);
            modify2(1, l, r, k);
        }
        if (op == 3)
            printf("%lld\n", query(1, l, r));
    }
    return 0;
}



lyktes
1个月前

挺短的,没过 100 行(((

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

struct Node
{
    int l, r;
    int sum;
    int tmax, lmax, rmax;

#define tmax(x) c[x].tmax
#define lmax(x) c[x].lmax
#define rmax(x) c[x].rmax
#define sum(x) c[x].sum
#define l(x) c[x].l
#define r(x) c[x].r
} c[N << 2];
int a[N];

void build(int p, int l, int r)
{
    l(p) = l, r(p) = r;
    if (l == r)
    {
        lmax(p) = rmax(p) = tmax(p) = sum(p) = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    sum(p) = sum(p << 1) + sum(p << 1 | 1);
    lmax(p) = max(lmax(p << 1), sum(p << 1) + lmax(p << 1 | 1));
    rmax(p) = max(rmax(p << 1 | 1), sum(p << 1 | 1) + rmax(p << 1));
    tmax(p) = max({tmax(p << 1), tmax(p << 1 | 1), rmax(p << 1) + lmax(p << 1 | 1)});
}

void change(int p, int pt, int x)
{
    if (l(p) == pt && r(p) == pt)
    {
        lmax(p) = rmax(p) = tmax(p) = sum(p) = x;
        return; 
    }
    int mid = l(p) + r(p) >> 1;
    if (pt <= r(p << 1))
        change(p << 1, pt, x);
    if (l(p << 1 | 1) <= pt)
        change(p << 1 | 1, pt, x);
    sum(p) = sum(p << 1) + sum(p << 1 | 1);
    lmax(p) = max(lmax(p << 1), sum(p << 1) + lmax(p << 1 | 1));
    rmax(p) = max(rmax(p << 1 | 1), sum(p << 1 | 1) + rmax(p << 1));
    tmax(p) = max({tmax(p << 1), tmax(p << 1 | 1), rmax(p << 1) + lmax(p << 1 | 1)});
}

Node query(int p, int l, int r)
{
    if (l <= l(p) && r(p) <= r)
        return c[p];
    if (r <= r(p << 1))
        return query(p << 1, l, r);
    if (l(p << 1 | 1) <= l)
        return query(p << 1 | 1, l, r);
    Node x = query(p << 1, l, r), y = query(p << 1 | 1, l, r);
    Node res = {0};
    res.sum = x.sum + y.sum;
    res.lmax = max(x.lmax, x.sum + y.lmax);
    res.rmax = max(y.rmax, y.sum + x.rmax);
    res.tmax = max({x.tmax, y.tmax, x.rmax + y.lmax});
    return res;
}

int main()
{
    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 op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if (op == 2)
            change(1, l, r);
        else
        {
            if (l > r)
                swap(l, r);
            Node x = query(1, l, r);
            printf("%d\n", x.tmax);
        }
    }
    return 0;
}


活动打卡代码 AcWing 3227. 折点计数

lyktes
1个月前
#include <bits/stdc++.h>

int n;
const int N = 1e5 + 5;
int a[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int res = 0;
    for (int i = 2; i < n; i++)
        res += bool (a[i] > a[i - 1] && a[i] > a[i + 1] || a[i] < a[i - 1] && a[i] < a[i + 1]);
    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 3232. 最大波动

lyktes
1个月前
#include <bits/stdc++.h>

int n;
const int N = 1e5 + 5;
int a[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int res = 0;
    for (int i = 2; i <= n; i++)
        res = std::max(res, abs(a[i] - a[i - 1]));
    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 3203. 画图

lyktes
1个月前
#include <bits/stdc++.h>

int n, res;
const int N = 1e3 + 5;
int a[N];
bool mp[N][N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int x, y, xx, yy;
        scanf("%d%d%d%d", &x, &y, &xx, &yy);
        for (int j = x; j < xx; j++)
            for (int k = y; k < yy; k++)
                if (!mp[j][k])
                    res += (mp[j][k] = 1);
    }
    printf("%d\n", res);
    return 0;
}