6356

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

using namespace std;

typedef long long LL;

const int N = 100010;

int n, p, m;
int w[N];
struct Node
{
int l, r;
}tr[N * 4];

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

void eval(Node &t, int add, int mul)
{
t.sum = ((LL)t.sum * mul + (LL)(t.r - t.l + 1) * add) % p;
t.mul = (LL)t.mul * mul % p;
}

void pushdown(int u)
{
eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
tr[u].add = 0, tr[u].mul = 1;
}

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

void modify(int u, int l, int r, int add, int mul)
{
if (tr[u].l >= l && tr[u].r <= r) eval(tr[u], add, mul);
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, add, mul);
if (r > mid) modify(u << 1 | 1, l, r, add, mul);
pushup(u);
}
}

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

pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
if (l <= mid) sum = query(u << 1, l, r);
if (r > mid) sum = (sum + query(u << 1 | 1, l, r)) % p;
return sum;
}

int main()
{
scanf("%d%d", &n, &p);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
build(1, 1, n);

scanf("%d", &m);
while (m -- )
{
int t, l, r, d;
scanf("%d%d%d", &t, &l, &r);
if (t == 1)
{
scanf("%d", &d);
modify(1, l, r, 0, d);
}
else if (t == 2)
{
scanf("%d", &d);
modify(1, l, r, d, 1);
}
else printf("%d\n", query(1, l, r));
}

return 0;
}



3天前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int n;
struct Segment
{
double x, y1, y2;
int k;
bool operator< (const Segment &t)const
{
return x < t.x;
}
}seg[N * 2];
struct Node
{
int l, r;
int cnt;
double len;
}tr[N * 8];

vector<double> ys;

int find(double y)
{
return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

void pushup(int u)
{
if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[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;
}

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

void modify(int u, int l, int r, int k)
{
if (tr[u].l >= l && tr[u].r <= r)
{
tr[u].cnt += k;
pushup(u);
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, k);
if (r > mid) modify(u << 1 | 1, l, r, k);
pushup(u);
}
}

int main()
{
int T = 1;
while (scanf("%d", &n), n)
{
ys.clear();
for (int i = 0, j = 0; i < n; i ++ )
{
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
seg[j ++ ] = {x1, y1, y2, 1};
seg[j ++ ] = {x2, y1, y2, -1};
ys.push_back(y1), ys.push_back(y2);
}

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

build(1, 0, ys.size() - 2);

sort(seg, seg + n * 2);

double res = 0;
for (int i = 0; i < n * 2; i ++ )
{
if (i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);
modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
}

printf("Test case #%d\n", T ++ );
printf("Total explored area: %.2lf\n\n", res);
}

return 0;
}



18天前

“分隔”是指S中每个线段都处于直线L的一边，并且直线L不与任何一个线段相交，如下图蓝色直线分隔红色线段集

3个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 40010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][16];
int q[N];

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int root)
{
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[root] = 1;
int hh = 0, tt = 0;
q[0] = root;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (depth[j] > depth[t] + 1)
{
depth[j] = depth[t] + 1;
q[ ++ tt] = j;
fa[j][0] = t;
for (int k = 1; k <= 15; k ++ )
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}

int lca(int a, int b)
{
if (depth[a] < depth[b]) swap(a, b);
for (int k = 15; k >= 0; k -- )
if (depth[fa[a][k]] >= depth[b])
a = fa[a][k];
if (a == b) return a;
for (int k = 15; k >= 0; k -- )
if (fa[a][k] != fa[b][k])
{
a = fa[a][k];
b = fa[b][k];
}
return fa[a][0];
}

int main()
{
scanf("%d", &n);
int root = 0;
memset(h, -1, sizeof h);

for (int i = 0; i < n; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
if (b == -1) root = a;
}

bfs(root);

scanf("%d", &m);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
int p = lca(a, b);
if (p == a) puts("1");
else if (p == b) puts("2");
else puts("0");
}

return 0;
}



3个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 510, M = 10010;

int n, m;
struct Edge
{
int a, b, w;
bool f;
bool operator< (const Edge &t) const
{
return w < t.w;
}
}edge[M];
int p[N];
int dist1[N][N], dist2[N][N];
int h[N], e[N * 2], w[N * 2], ne[N * 2], idx;

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

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

void dfs(int u, int fa, int maxd1, int maxd2, int d1[], int d2[])
{
d1[u] = maxd1, d2[u] = maxd2;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j != fa)
{
int td1 = maxd1, td2 = maxd2;
if (w[i] > td1) td2 = td1, td1 = w[i];
else if (w[i] < td1 && w[i] > td2) td2 = w[i];
dfs(j, u, td1, td2, d1, d2);
}
}
}

int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edge[i] = {a, b, w};
}

sort(edge, edge + m);
for (int i = 1; i <= n; i ++ ) p[i] = i;

LL sum = 0;
for (int i = 0; i < m; i ++ )
{
int a = edge[i].a, b = edge[i].b, w = edge[i].w;
int pa = find(a), pb = find(b);
if (pa != pb)
{
p[pa] = pb;
sum += w;
edge[i].f = true;
}
}

for (int i = 1; i <= n; i ++ ) dfs(i, -1, -1e9, -1e9, dist1[i], dist2[i]);

LL res = 1e18;
for (int i = 0; i < m; i ++ )
if (!edge[i].f)
{
int a = edge[i].a, b = edge[i].b, w = edge[i].w;
LL t;
if (w > dist1[a][b])
t = sum + w - dist1[a][b];
else if (w > dist2[a][b])
t = sum + w - dist2[a][b];
res = min(res, t);
}

printf("%lld\n", res);

return 0;
}



3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 6010;
int n;
struct Edge{
int a,b,w;
bool operator<(const Edge &t)const{
return w<t.w;
}
}e[N];

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

int main(){
int T;
cin>>T;
while(T--){
cin>>n;
for(int i = 0;i<n-1;i++){
int a,b,c;
cin>>a>>b>>c;
e[i] = {a,b,c};
}
sort(e,e+n-1);
for(int i = 1;i<=n;i++)p[i] = i,sizes[i] = 1;
int res = 0;
for(int i = 0;i<n-1;i++){
int a = find(e[i].a);
int b = find(e[i].b);
int w = e[i].w;
if(a!=b){
res += (sizes[a]*sizes[b]-1)*(w+1);
sizes[a] += sizes[b];
p[b] = a;
}
}
cout<<res<<endl;
}

}



3个月前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 510, M = N * N / 2;

int n, k, m;
struct Edge
{
int a, b;
double w;
bool operator< (const Edge &t) const
{
return w < t.w;
}
}e[M];

PII q[M];
int p[N];

double get_dist(PII a,PII b){
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx*dx+dy*dy);
}

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

int main(){
cin>>n>>k;
for(int i = 0;i<n;i++)cin>>q[i].x>>q[i].y;
for(int i = 0;i<n;i++)
for(int j = 0;j<i;j++)
e[m++] = {i,j,get_dist(q[i],q[j])};

sort(e,e+m);
for(int i = 0;i<n;i++)p[i] = i;

int cnt = n;
double res = 0;
for(int i = 0;i<m;i++){
if(cnt<=k)break;
int a = find(e[i].a);
int b = find(e[i].b);
double w = e[i].w;
if(a!=b){
cnt--;
res = w;
p[a] = b;
}
}
printf("%.2lf\n", res);
return 0;
}



3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 310;
int n;
int w[N][N];
int dist[N];
bool st[N];

int prim(){
memset(dist,0x3f,sizeof dist);
dist[0] = 0;
int res = 0;

for(int i = 0;i<n+1;i++){
int t = -1;
for(int j = 0;j<=n;j++)
if(!st[j]&&(t==-1||dist[t]>dist[j]))t = j;
st[t] = true;
res += dist[t];
for(int j = 0;j<=n;j++)dist[j] = min(dist[j],w[t][j]);
}
return res;
}

int main(){
cin>>n;
for(int i = 1;i<=n;i++){
cin>>w[0][i];
w[i][0] = w[0][i];
}

for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
cin>>w[i][j];

cout<<prim()<<endl;

return 0;

}


3个月前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

const int N = 210;

int k, n, m, S, E;
int g[N][N];
int res[N][N];

void mul(int c[][N], int a[][N], int b[][N])
{
static int temp[N][N];
memset(temp, 0x3f, sizeof temp);
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);
memcpy(c, temp, sizeof temp);
}

void qmi()
{
memset(res, 0x3f, sizeof res);
for (int i = 1; i <= n; i ++ ) res[i][i] = 0;

while (k)
{
if (k & 1) mul(res, res, g);    // res = res * g
mul(g, g, g);   // g = g * g
k >>= 1;
}
}

int main()
{
cin >> k >> m >> S >> E;

memset(g, 0x3f, sizeof g);
map<int, int> ids;
if (!ids.count(S)) ids[S] = ++ n;
if (!ids.count(E)) ids[E] = ++ n;
S = ids[S], E = ids[E];

while (m -- )
{
int a, b, c;
cin >> c >> a >> b;
if (!ids.count(a)) ids[a] = ++ n;
if (!ids.count(b)) ids[b] = ++ n;
a = ids[a], b = ids[b];

g[a][b] = g[b][a] = min(g[a][b], c);
}

qmi();

cout << res[S][E] << endl;

return 0;
}


3个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 110,INF = 0x3f3f3f3f;
int n,m;
int d[N][N],g[N][N];
int pos[N][N];
int path[N],cnt;

void get_path(int i,int j){
if(pos[i][j]==0)return;
int k = pos[i][j];
get_path(i,k);
path[cnt++] = k;
get_path(k,j);
}

int main(){
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i = 1;i<=n;i++)g[i][i] = 0;

while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a][b] = g[b][a] = min(g[a][b],c);
}

int res = INF;
memcpy(d,g,sizeof d);
for(int k = 1;k<=n;k++){
for(int i = 1;i<k;i++)
for(int j = i+1;j<k;j++)
if((long long)d[i][j]+g[j][k]+g[k][i]<res){
res = d[i][j] + g[j][k] + g[k][i];
cnt = 0;
path[cnt++] = k;
path[cnt++] = i;
get_path(i,j);
path[cnt++] = j;
}
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
if(d[i][j]>d[i][k]+d[k][j]){
d[i][j] = d[i][k] + d[k][j];
pos[i][j] = k;
}
}

if(res==INF)cout<<"No solution."<<endl;
else{
for(int i = 0;i<cnt;i++)cout<<path[i]<<' ';
cout<<endl;
}
return 0;
}