lyktes

2.0万

RyanMoriarty

Joseph1314

pine_7
15358022392
Sparkle_ZH
zhihaoFu
Justice

13962588881

IEE_
Peter_5

lyktes
1天前

lyktes
16天前

lyktes
21天前

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

using namespace std;

const int N = 5e5 + 5;

#define int long long
struct Node
{
int l, r;
#define l(x) c[x].l
#define r(x) c[x].r
#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];
{
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);
}
}
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;
}


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

using namespace std;

const int N = 1e5 + 5;

#define int long long
struct Node
{
int l, r;
int sum;
#define l(x) c[x].l
#define r(x) c[x].r
#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;
}

{
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 | 1) = (add(p << 1 | 1) * mul(p) + add(p)) % P;
mul(p) = 1;
}

void modify1(int p, int l, int r, int d)
{
if (l <= l(p) && r(p) <= r)
{
sum(p) = (sum(p) * d) % P;
mul(p) = (mul(p) * d) % P;
return;
}
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;
return;
}
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);
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个月前

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


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


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


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