【BZOJ 3672】[NOI2014] 购票

解题报告

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3672
神犇题解:http://blog.csdn.net/lych_cys/article/details/51317809

解题报告

一句话题解:树上CDQ分治

先推一推式子,发现可以斜率优化
于是我们可以用树链剖分做到$O(n \log^3 n)$
或者也可以用KD-Tree配合DFS序做到$O(n^{1.5} \log n)$

我们进一步观察,使单纯的DFS序不能做的地方在于凸包是动态的,查询也是动态的且限制了横坐标的最小值
考虑分治的话,我们按横坐标的限制排序,然后边查询边更新凸包就可以了
总的时间复杂度:$O(n \log^2 n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;
const int M = N << 1;
const LL INF = 6e18;

int n, head[N], nxt[M], to[M], fa[N];
LL q[N], p[N], len[N], dep[N], f[N];

struct Point{
	LL x, y, id, range;
	inline Point() {
	}
	inline Point(LL a, LL b, LL c, LL d):x(a), y(b), id(c), range(d) {
	}
	inline bool operator < (const Point &P) const {
		return x > P.x || (x == P.x && y > P.y);
	}
	inline Point operator - (const Point &P) {
		return Point(x - P.x, y - P.y, 0, 0);
	}
	inline double operator * (const Point &P) {
		return (double)x * P.y - (double)y * P.x;
	}
	inline double slope(const Point &P) {
		return (double)(y - P.y) / (x - P.x);
	}
	static bool update(const Point &P1, const Point &P2) {
		return P1.range > P2.range;
	}
};

inline LL read() {
	char c = getchar(); LL ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; 
	to[++E] = u; nxt[E] = head[v]; head[v] = E; 
}

class DivideAndConquer{
int sz[N], vis[N];
public:	
	inline void solve(int w, int universe) {
		int top = w;
		vis[w = FindRoot(w, universe)] = 1;
		if (fa[w] && !vis[fa[w]]) {
			solve(top, universe - sz[w]);
		}
		vector<Point> cvx;
		for (int nw = fa[w]; dep[nw] >= dep[top]; nw = fa[nw]) {
			cvx.push_back(Point(dep[nw], f[nw], nw, dep[nw] - len[nw]));
		}
		vector<Point> que;
		que.push_back(Point(dep[w], 0, w, dep[w] - len[w]));
		for (int i = head[w]; i; i = nxt[i]) {
			if (dep[to[i]] > dep[w] && !vis[to[i]]) {
				DFS(to[i], w, que);
			}	
		}	
		
		sort(que.begin(), que.end(), Point::update);
		sort(cvx.begin(), cvx.end());
		for (int i = 0, j = 0, tot = 0; i < (int)que.size(); i++) {
			for (; j < (int)cvx.size() && cvx[j].x >= que[i].range; j++) {
				for (; tot > 1 && (cvx[tot - 1] - cvx[tot - 2]) * (cvx[j] - cvx[tot - 2]) >= 0; --tot);
				cvx[tot++] = cvx[j];
			}
			int ret = tot - 1, l = 0, r = tot - 2, mid, k = que[i].id;
			while (l <= r) {
				mid = l + r >> 1;
				if (cvx[mid].slope(cvx[mid + 1]) <= p[k]) {
					ret = mid;
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}
			if (ret >= 0) {
				f[k] = min(f[k], cvx[ret].y + (dep[k] - cvx[ret].x) * p[k] + q[k]);
			}
		}
		for (int i = 0, j; i < (int)que.size(); i++) {
			if (j = que[i].id, que[i].range <= dep[w]) {
				f[j] = min(f[j], f[w] + (dep[j] - dep[w]) * p[j] + q[j]);
			}
		}
		que.clear();
		cvx.clear();
	
		for (int i = head[w]; i; i = nxt[i]) {
			if (dep[to[i]] > dep[w] && !vis[to[i]]) {
				solve(to[i], sz[to[i]]);
			}
		}	
	}	
private:
	inline int FindRoot(int w, int universe) {
		int ret = 0, ans;
		FindRoot(w, w, universe, ret, ans);
		return ret;
	}	
	inline void FindRoot(int w, int f, int universe, int &ret, int &ans) {
		int mx = 1; sz[w] = 1;
		for (int i = head[w]; i; i = nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				FindRoot(to[i], w, universe, ret, ans);
				sz[w] += sz[to[i]];
				mx = max(mx, sz[to[i]]);
			}
		}
		mx = max(mx, universe - sz[w]);
		if (!ret || mx < ans) {
			ans = mx;
			ret = w;
		}
	}
	inline void DFS(int w, int f, vector<Point> &ret) {
		ret.push_back(Point(dep[w], 0, w, dep[w] - len[w]));
		for (int i = head[w]; i; i = nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				DFS(to[i], w, ret);
			}
		}
	}
}DAC;

int main() {
	n = read(); read();
	for (int i = 2; i <= n; i++) {
		fa[i] = read();
		LL c = read(); AddEdge(fa[i], i);
		p[i] = read(); q[i] = read();
		len[i] = read();
		dep[i] = dep[fa[i]] + c;
	}
	fill(f, f + N, INF);
	f[1] = 0; dep[0] = -1;
	DAC.solve(1, n);
	for (int i = 2; i <= n; i++) {
		printf("%lld\n", f[i]);
	}
	return 0;
}

【BZOJ 4700】适者

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4700
神犇题解:http://blog.csdn.net/werkeytom_ftd/article/details/54565251

解题报告

设第$i$个机器人打$t_i$次就会$GG$,攻击力是$v_i$
那么推推式子发现$i$比$j$先死更优,当且仅当$t_iv_j < t_jv_i$
于是我们先排个序,贪一贪心

现在考虑如何一开始就$GG$掉的两个,因为删除之后不会影响决策
所以我们相当于在贪心后的删除序列上再删掉两个点
考虑删掉的第一个点对于第二个点的贡献,形如$av_i+b$
这是一个直线的表达式,于是相当于让你维护一个数据结构,支持插入直线、查询单点最值
这个是一个经典的数据结构问题,可以用李超树来解决
总时间复杂度:$O(n \log n)$

另外,这题还有CDQ分治的做法,时间复杂度仍然为$O(n \log n)$
再另外,我居然暂时是$Rank \ 1$!第一次$Rank \ 1$啊! ★,°:.☆( ̄▽ ̄)/$:.°★

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300009;
const int INF = 10000;
const double EPS = 1e-6;

int n,ATK; LL sum[N],pre[N],vout,ans;
struct ROB{int t,v;}r[N];
inline bool cmp(const ROB &A, const ROB &B) {return (LL)A.t * B.v < (LL)B.t * A.v;} 

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

class Segment_Tree{
	int root,cnt; LL AnsTmp;
	struct Node{int ch[2],a; LL b,pl,pr;double pm;}p[N<<1];
	public:
		inline void insert(int a, LL b) {
			insert(root, 1, INF, a, b);
		}
		inline LL query(int x) {
			AnsTmp = 0;
			query(root, 1, INF, x);
			return AnsTmp;
		}
	private:
		void insert(int &w, int l, int r, int a, LL b) {
			if (!w) w = ++cnt;
			if (!p[w].a) {p[w].a = a, p[w].b = b; return;}
			LL nl = (LL)a*l+b, nr = (LL)a*r+b; 
			double nm=(l+r)*0.5*a+b; int mid=l+r+1>>1;
			if (nl <= p[w].pl && nr <= p[w].pr) return;
			if (nm > p[w].pm) {
				if (nl < p[w].pl || nr < p[w].pr) {
					if (nl < p[w].pl && l < r) insert(p[w].ch[0], l, mid-1, p[w].a, p[w].b);
					if (nr < p[w].pr && l < r) insert(p[w].ch[1], mid, r, p[w].a, p[w].b);
				} p[w].a = a; p[w].b = b; p[w].pl = nl; p[w].pr = nr; p[w].pm = nm;
			} else {
				if (nl > p[w].pl && l < r) insert(p[w].ch[0], l, mid-1, a, b);
				if (nr > p[w].pr && l < r) insert(p[w].ch[1], mid, r, a, b);
			}
 		}
		void query(int w, int l, int r, int pos) {
			if (!w) return;
			if (p[w].a) AnsTmp = max(AnsTmp, (LL)p[w].a * pos + p[w].b);
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (pos < mid) query(p[w].ch[0], l, mid-1, pos);
				else query(p[w].ch[1], mid, r, pos);
			}
		}
}SGT;

int main() {
	n = read(); ATK = read();
	for (int i=1,a,b;i<=n;i++) {
		a = read(); b = read();
		b = ceil((double)b / ATK) + EPS;
		r[i].v = a; r[i].t = b;
	}
	sort(r+1, r+1+n, cmp);
	for (int i=1;i<=n;i++) pre[i] = pre[i-1] + r[i].t;
	for (int i=n;i;i--) sum[i] = sum[i+1] + r[i].v;
	for (int i=1;i<=n;i++) {
		LL tmp = SGT.query(r[i].v);
		LL nv = sum[i]*r[i].t-r[i].v+pre[i-1]*r[i].v; 
		if (i > 1) vout = max(vout, tmp + nv);
		SGT.insert(-r[i].t, nv);
	}
	for (int i=1;i<=n;i++) ans += (pre[i] - 1) * r[i].v; 
	printf("%lld\n",ans-vout);
	return 0;
}

【BZOJ 1176】[Balkan2007] Mokia

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1176

这货二维BIT上不了
于是上CDQ

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int M = 200000+9;

struct OPT{
	int x,y,id,delta;
	inline OPT() {}
	inline OPT(int X, int Y, int ID, int DEL):x(X),y(Y),id(ID),delta(DEL){}
	inline bool operator < (const OPT &B) const {return x < B.x;}
}opt[M],buf[M];
int n,m,query_cnt,vout[M],hash[M*2],cnt;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int sum[M*2];
	
	inline void modify(int w, int v){
		for (int i=w;i<=cnt;i+=lowbit(i)) sum[i] += v;
	}
	
	inline int query(int w){
		int ret = 0;
		for (int i=w;i;i-=lowbit(i)) ret += sum[i];
		return ret;
	}
};

void solve(int l, int r) {
	if (l >= r) return;
	int mid = l + r + 1 >> 1;
	solve(l,mid-1);	
	solve(mid,r);
	
	int p1 = l, p2 = mid;
	for (;p2<=r;p2++) {
		for (;p1 < mid && opt[p1].x <= opt[p2].x;p1++)
			if (!opt[p1].id) BIT::modify(opt[p1].y,opt[p1].delta);
		if (opt[p2].id) vout[opt[p2].id] += BIT::query(opt[p2].y)*opt[p2].delta;
	}
	
	for (int i=l;i<p1;i++) if (!opt[i].id) BIT::modify(opt[i].y,-opt[i].delta);
	merge(opt+l,opt+mid,opt+mid,opt+r+1,buf+1);
	memcpy(opt+l,buf+1,sizeof(opt[0])*(r-l+1));
}

int main(){
	read(); n = read();
	for (int t=read(),x1,y1,x2,y2;t!=3;t=read()) {
		if (t == 1) {
			opt[++m].x = read();
			opt[m].y = hash[++cnt] = read(); 
			opt[m].delta = read();
		} else {
			x1 = read(); y1 = hash[++cnt] = read(); hash[++cnt] = y1 - 1;
			x2 = read(); y2 = hash[++cnt] = read(); hash[++cnt] = y2 - 1;
			opt[++m].x = x1-1; opt[m].y = y1-1; opt[m].delta = 1;  opt[m].id = ++query_cnt;
			opt[++m].x = x2;   opt[m].y = y2;   opt[m].delta = 1;  opt[m].id = query_cnt;
			opt[++m].x = x1-1; opt[m].y = y2;   opt[m].delta = -1; opt[m].id = query_cnt;
			opt[++m].x = x2;   opt[m].y = y1-1; opt[m].delta = -1; opt[m].id = query_cnt;
		}
	}
	sort(hash+1,hash+1+cnt);
	cnt = unique(hash+1,hash+1+cnt) - hash - 1;
	for (int i=1;i<=m;i++) opt[i].y = lower_bound(hash+1,hash+1+cnt,opt[i].y) - hash;
	solve(1,m);
	for (int i=1;i<=query_cnt;i++) printf("%d\n",vout[i]);
	return 0;
}

另外,这题如果强制在线的话,貌似可以上主席树?

【NOI六连测】[D1T1] 比赛

题目传送门:http://pan.baidu.com/s/1kVjNeeV
离线版题目:http://paste.ubuntu.com/18236489/
数据传送门:http://pan.baidu.com/s/1kUR6kTL

哎呀,绍兴一中的NOIP模拟题,第一眼拿到都一脸懵逼QAQ
想了一会儿发现,不就是总方案数减掉一个三位偏序吗?这个我会!
于是开开心心写完BIT+动态建点的线段树。然后小数据对拍,欸!居然没错 (~ ̄▽ ̄)→))* ̄▽ ̄*)o
然后一跑大数据,哎呀,空间简直炸的飞起! 然后再接下来的一个半小时里一直想办法压空间。
什么unsign short配合char之类的都用上了,然而还是不行QAQ,再加上时间复杂度也不一定过得去,于是弃疗

测完程序,发现CDQ+归并就可以卡过QAQ,然而不会CDQ,于是下午学了一学,还是比较好学的。
然而这还不是高潮!高潮在:这货可以降到一维,然后O(nlogn)轻松过 QAQ
对于任意一个符合条件的(x,y)只会有一种情况(在把A,B,C看成一样的情况下):

A[x] < A[y] 
B[x] > B[y]
C[x] > C[y]

然后不难发现,如果我们把[A,B]&[A,C]拿出来统计一次逆序对的话,这货相当于每一个符合要求的(x,y)被算了2次
于是,跑三遍一维逆序对就好了QAQ 这个能算简单的容斥吗?

BIT + 线段树:http://paste.ubuntu.com/18236197/
CDQ分治:http://paste.ubuntu.com/18236240/
逆序对虐场代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;

const int MAXN = 200000+9;

int n,a[MAXN],b[MAXN],c[MAXN],ord[MAXN];
LL vout;

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define low(x) (x&(-x))
	int arr[MAXN],sum;
	
	inline void init(){
		memset(arr,0,sizeof(arr));
		sum = 0;}
	
	inline void modify(int pos){
		for (int i=pos;i<=n;i+=low(i))
			arr[i] += 1; sum++;
	} 
	
	inline int query(int pos){
		int ret = 0;
		for (int i=pos;i;i-=low(i))
			ret += arr[i];
		return sum-ret;
	}
};

inline void itv(int *A, int *B){
	BIT::init();
	for (int i=1;i<=n;i++) ord[A[i]] = i;
	for (int j=1,i=ord[j];j<=n;i=ord[++j])
		vout += BIT::query(B[i]),
		BIT::modify(B[i]);
}

int main(){
	freopen("contest.in","r",stdin);
	freopen("contest.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
	itv(a,b); itv(b,c); itv(a,c); 
	printf("%lld\n",vout/2LL);
	return 0;
}

另外,这题做的时候,发现对于小的结构体,貌似直接排序比排指针还要快一点QAQ
可能是因为后期指针寻址也要花时间吧!所以以后CDQ就直接结构体写了吧! 有图有真相:
struct_iterator