p_c

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


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

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

return 0;
}


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


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;
}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 %= 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].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].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;
} else {
printf("%lld\n", query(1, t, g));
}

}

return 0;
}


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;
}t[maxn * 4];
char str[5];

void pushdown(int u) {
Treement &root = t[u], &left = t[u << 1], &right = t[u << 1 | 1];
}

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