LOJ#3085. 「GXOI / GZOI2019」特技飞行

这显然是两道题，求\(C\)是一个曼哈顿转切比雪夫后的线段树扫描线

求\(AB\)，对向交换最大化和擦身而过最大化一定分别为最大值和最小值

对向交换最大化是每个点都对向交换

擦身而过最大化需要对向交换最小化，我们一次对向交换相当于交换任意两个数，所以就是每个置换圈的点数-1累加即可

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 100005

#define ba 47

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 +c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N,K,tot;

int64 A,B,C,xst,xed;

int64 Min,Max;

int64 y[MAXN][2];

struct Point {

    db x,y;

    Point(db _x = 0.0,db _y = 0.0) {

	x = _x;y = _y;

    }

}P[MAXN * 10];

void getinsect(int a,int b) {

    db k1 = 1.0 * (y[a][1] - y[a][0]) / (xed - xst);

    db k2 = 1.0 * (y[b][1] - y[b][0]) / (xed - xst);

    db t1 = y[a][0] - xst * k1;

    db t2 = y[b][0] - xst * k2;

    db X = (t2 - t1) / (k1 - k2);

    db Y = k1 * X + t1;

    P[++tot] = Point(X + Y,X - Y);

}

namespace task1 {

    int id[MAXN],pos[MAXN],fa[MAXN],siz[MAXN];

    int64 all;

    set<pii > S;

    int getfa(int u) {

	return fa[u] == u ? u : fa[u] = getfa(fa[u]);

    }

    void Main() {

	read(N);read(A);read(B);read(C);read(xst);read(xed);

	for(int i = 1 ; i <= N ; ++i) read(y[i][0]);

	for(int i = 1 ; i <= N ; ++i) {read(y[i][1]);id[i] = i;}

	sort(id + 1,id + N + 1,[](int a,int b){return y[a][1] < y[b][1];});

	for(int i = 1 ; i <= N ; ++i) pos[id[i]] = i;

	for(int i = N ; i >= 1 ; --i) {

	    for(auto t : S) {

		if(t.fi < pos[i]) {++all;getinsect(t.se,i);}

		else break;

	    }

	    S.insert(mp(pos[i],i));

	}

	for(int i = 1 ; i <= N ; ++i) fa[i] = i;

	for(int i = 1 ; i <= N ; ++i) {

	    if(getfa(pos[i]) != getfa(i)) fa[getfa(pos[i])] = getfa(i);

	}

	for(int i = 1 ; i <= N ; ++i) {

	    siz[getfa(i)]++;

	}

	int64 t = 0;

	for(int i = 1 ; i <= N ; ++i) {

	    if(getfa(i) == i) {

		t += siz[i] - 1;

	    }

	}

	Min = all * A;

	Max = t * A + (all - t) * B;

	if(Min > Max) swap(Min,Max);

    }

};

namespace task2 {

    struct qry_node {

	int64 l,r;db y;

	int on;

    }qry[MAXN * 30];

    struct node {

	int l,r;

	int cnt;

    }tr[MAXN * 120];

    int d,all;

    int64 ans,val[MAXN * 30];

    void build(int u,int l,int r) {

	tr[u].l = l;tr[u].r = r;

	tr[u].cnt = 0;

	if(l == r) return;

	int mid = (l + r) >> 1;

	build(u << 1,l,mid);

	build(u << 1 | 1,mid + 1,r);

    }

    void Add(int u,int l,int r,int v) {

	if(tr[u].l == l &&tr[u].r == r) {tr[u].cnt += v;return;}

	int mid = (tr[u].l + tr[u].r) >> 1;

	if(r <= mid) Add(u << 1,l,r,v);

	else if(l > mid) Add(u << 1 | 1,l,r,v);

	else {Add(u << 1,l,mid,v);Add( u << 1 | 1,mid + 1,r,v);}

    }

    bool Query(int u,int p) {

	if(tr[u].cnt) return true;

	if(tr[u].l == tr[u].r) return false;

	int mid = (tr[u].l + tr[u].r) >> 1;

	if(p <= mid) return Query(u << 1,p);

	else return Query(u << 1 | 1,p);

    }

    void Main() {

	read(K);

	int64 p,q,r;

	for(int i = 1 ; i <= K ; ++i) {

	    read(p);read(q);read(r);

	    int64 a = p + q,b = p - q;

	    qry[++all] = (qry_node){a - r,a + r,(db)b - r,1};

	    qry[++all] = (qry_node){a - r,a + r,b + r + 1e-12,-1};

	    val[++d] = a + r;val[++d] = a - r;

	}

	sort(val + 1,val + d + 1);

	d = unique(val + 1,val + d + 1) - val - 1;

	build(1,1,d);

	for(int i = 1 ; i <= tot ; ++i) {

	    qry[++all] = (qry_node){0,i,P[i].y,0};

	}

	sort(qry + 1,qry + all + 1,[](qry_node a,qry_node b){return a.y < b.y || (a.y == b.y && a.on > b.on) ;});

	for(int i = 1 ; i <= all ; ++i) {

	    if(qry[i].on == 0) {

		int t = lower_bound(val + 1,val + d + 1,(int64)ceil(P[qry[i].r].x)) - val;

		if(t <= d) ans += Query(1,t);

	    }

	    else {

		int l = lower_bound(val + 1,val + d + 1,qry[i].l) - val;

		int r = lower_bound(val + 1,val + d + 1,qry[i].r) - val;

		++l;

		Add(1,l,r,qry[i].on);

	    }

	}

	Min += ans * C;

	Max += ans * C;

    }

};

void Solve() {

    task1::Main();

    task2::Main();

    out(Min);space;out(Max);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}

巴特西

【LOJ】#3085. 「GXOI / GZOI2019」特技飞行

LOJ#3085. 「GXOI / GZOI2019」特技飞行

最新文章

热门文章