【BZOJ 3881】[COCI2015] Divljak

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3881
神犇题解:http://trinkle.is-programmer.com/2015/6/30/bzoj-3881.100056.html

解题报告

考虑把Alice的串建成AC自动机
那么每一次用Bob的串去匹配就是Fail树上一些树链的并
这个用BIT+虚树无脑维护一下就可以了

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 2000009;
const int LOG = 26;
const int SGZ = 26;

int in[N];

inline int read() {
	char c = getchar(); int 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;
}

class Ac_Automaton{
int root, cnt, ch[N][SGZ], fail[N], pos[N], dep[N];
int head[N], to[N], nxt[N], ot[N], fa[N][LOG];
class FenwickTree{
int mx, sum[N];
public:
	inline void init(int nn) {
		mx = nn;
	}
	inline void modify(int p, int d) {
		for (int i = p; i <= mx; i += lowbit(i)) {
			sum[i] += d;
		}
	}
	inline int query(int l, int r) {
		int ret = 0;
		for (int i = l - 1; i > 0; i -= lowbit(i)) {
			ret -= sum[i];
		}
		for (int i = r; i; i -= lowbit(i)) {
			ret += sum[i];
		}
		return ret;
	}
private:
}bit;
public:
	inline void insert(char *s, int nn, int id) {
		int w = root;
		for (int i = 1; i <= nn; i++) {
			int cc = s[i] - 'a';
			if (!ch[w][cc]) {
				ch[w][cc] = ++cnt;
			}
			w = ch[w][cc];
		} 
		pos[id] = w;
	}
	inline void build() {
		static queue<int> que;
		for (int i = 0; i < SGZ; i++) {
			if (ch[root][i]) {
				que.push(ch[root][i]);
			}
		}
		for (; !que.empty(); que.pop()) {
			int w = que.front();
			AddEdge(fail[w], w);
			for (int i = 0; i < SGZ; i++) {
				if (!ch[w][i]) {
					ch[w][i] = ch[fail[w]][i];
				} else {
					que.push(ch[w][i]);
					fail[ch[w][i]] = ch[fail[w]][i];
				}
			}
		}
		DFS(0, 0);
		for (int j = 1; j < LOG; j++) {
			for (int i = 0; i <= cnt; i++) {
				fa[i][j] = fa[fa[i][j - 1]][j - 1];
			}
		}
		bit.init(cnt + 1);
	} 
	inline void match(char *s, int nn) {
		static vector<int> vt[N];
		static int que[N], stk[N], vis[N]; 
		int qtot = 0, stot = 0, vtot = 0;
		que[++qtot] = root;
		for (int i = 1, w = root; i <= nn; i++) {
			w = ch[w][s[i] - 'a'];
			que[++qtot] = w;
		}
		sort(que + 1, que + 1 + qtot);
		qtot = unique(que + 1, que + 1 + qtot) - que - 1;
		sort(que + 1, que + 1 + qtot, cmp);
		for (int i = 1; i <= qtot; i++) {
			if (stot) {
				int lca = LCA(que[i], stk[stot]);
				for (; stot && dep[stk[stot]] > dep[lca]; --stot) {
					if (stot > 1 && dep[stk[stot - 1]] >= dep[lca]) {
						vt[stk[stot - 1]].push_back(stk[stot]);
					} else {
						vt[lca].push_back(stk[stot]);
					}
				}
				if (stot && stk[stot] != lca) {
					stk[++stot] = lca;
					vis[++vtot] = lca;
				}
			} 
			stk[++stot] = que[i];
			vis[++vtot] = que[i];
		}
		for (; stot > 1; --stot) {
			vt[stk[stot - 1]].push_back(stk[stot]);
		}
		update(root, vt);
		for (int i = 1; i <= vtot; i++) {
			vt[vis[i]].clear();
		}
	}
	inline int query(int id) {
		return bit.query(in[pos[id]], ot[pos[id]]);
	}
private:
	inline void update(int w, vector<int> *vt) {
		for (int i = 0; i < (int)vt[w].size(); i++) {
			bit.modify(in[w], -1);
			bit.modify(in[vt[w][i]], 1);
			update(vt[w][i], vt);
		}
	}
	inline int LCA(int a, int b) {
		if (dep[a] < dep[b]) {
			swap(a, b);
		}
		for (int j = SGZ - 1; ~j; j--) {
			if (dep[fa[a][j]] >= dep[b]) {
				a = fa[a][j];
			}
		}
		if (a == b) {
			return a;
		}
		for (int j = SGZ - 1; ~j; j--) {
			if (fa[a][j] != fa[b][j]) {
				a = fa[a][j];
				b = fa[b][j];
			}
		}
		return fa[a][0];
	} 
	static bool cmp(int a, int b) {
		return in[a] < in[b];
	}
	inline void DFS(int w, int f) {
		static int tt = 0;
		in[w] = ++tt;
		dep[w] = dep[fa[w][0] = f] + 1;
		for (int i = head[w]; i; i = nxt[i]) {
			DFS(to[i], w);
		}
		ot[w] = tt;
	}
	inline void AddEdge(int u, int v) {
		static int E = 1;
		to[++E] = v; nxt[E] = head[u]; head[u] = E;
	}
}ac;

int main() {
	static char ss[N];
	int n = read();
	for (int i = 1; i <= n; i++) {
		scanf("%s", ss + 1);
		int len = strlen(ss + 1);
		ac.insert(ss, len, i);
	}
	ac.build();
	int m = read();
	for (int i = 1; i <= m; i++) {
		if (read() == 1) {
			scanf("%s", ss + 1);
			int len = strlen(ss + 1);
			ac.match(ss, len);
		} else {
			printf("%d\n", ac.query(read()));
		}
	}
	return 0;
}

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

【Latex】分类讨论

之前一直不知道下面这种东西的标准写法:
$$
\begin{equation}
\text{最终得分} =
\begin{cases}
\text{所有操作的分数之和}, & F=0\\
\left \lfloor \frac{\text{所有操作的分数之和}}{2^d} \right \rfloor, & F=1
\end{cases}
\end{equation}
$$

现在知道了:
\begin{equation}
\text{最终得分} =
\begin{cases}
\text{所有操作的分数之和}, & F=0\\\\
\left \lfloor \frac{\text{所有操作的分数之和}}{2^d} \right \rfloor, & F=1
\end{cases}
\end{equation}

参考资料:http://uoj.ac/problem/4

【BZOJ 4198】[NOI2015] 荷马史诗

相关链接

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

解题报告

k叉哈夫曼树
注意最大化儿子不满的那个结点的深度

Code

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

struct Data{
	LL apt, mx;
	inline Data() {
	}
	inline Data(LL a, LL c):apt(a), mx(c) {
	}
	inline Data operator + (const Data &d) {
		return Data(apt + d.apt, max(mx, d.mx + 1));
	}
	inline bool operator < (const Data &d) const {
		return apt > d.apt || (apt == d.apt && mx > d.mx); 
	}
};
priority_queue<Data> que;

inline LL read() {
	char c=getchar(); LL 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;
}

int main() {
	int n = read(), k = read();
	for (int i = 1; i <= n; i++) {
		que.push(Data(read(), 0));
	} 
	LL ans = 0;
	for (bool frt = (n - 1) % (k - 1); (int)que.size() > 1; frt = 0) {
		Data np(0, 0);
		for (int i = frt? 1 + (n - 1) % (k - 1): k; i; --i) {
			np = np + que.top();
			que.pop();
		}
		ans += np.apt;
		que.push(np);
	}
	printf("%lld\n%lld\n", ans, que.top().mx);
	return 0;
}

【BZOJ 3940】[Usaco2015 Feb] Censoring

相关链接

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

解题报告

用栈和AC自动机来模拟即可

Code

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

const int N = 100009;
const int SGZ = 26;

char ctn[N], wrd[N]; 

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 AC_Automaton{
int Root, cnt, ch[N][SGZ], apt[N], dep[N], fail[N];
queue<int> que;
public:
	inline void insert(char *s, int len) {
		int w = Root;
		for (int i = 1; i <= len; i++) {
			int  cc = s[i] - 'a';
			if (!ch[w][cc]) {
				ch[w][cc] = ++cnt;
				dep[cnt] = dep[w] + 1;
			}
			w = ch[w][cc];
		}
		apt[w] = len;
	}
	inline void build() {
		for (int i = 0; i < SGZ; i++) {
			if (ch[Root][i]) {
				que.push(ch[Root][i]);
			}
		}
		for (; !que.empty(); que.pop()) {
			int w = que.front();
			for (int i = 0; i < SGZ; i++) {
				if (ch[w][i]) {
					fail[ch[w][i]] = ch[fail[w]][i];
					apt[ch[w][i]] = max(apt[ch[w][i]], apt[fail[ch[w][i]]]);
					que.push(ch[w][i]);
				} else {
					ch[w][i] = ch[fail[w]][i];
				}
			}
		}
	}
	inline int root() {
		return Root;
	}
	inline int move(int &w, int cc) {
		w = ch[w][cc];
		return apt[w];
	}
}aca;

int main() {
	scanf("%s", ctn + 1);
	int n = read(), m = strlen(ctn + 1);
	for (int i = 1; i <= n; i++) {
		scanf("%s", wrd + 1);
		aca.insert(wrd, strlen(wrd + 1));
	}
	aca.build();
	vector<int> ans, pos;
	for (int i = 1; i <= m; i++) {
		int w = pos.empty()? aca.root(): *--pos.end();
		int len = aca.move(w, ctn[i] - 'a');
		ans.push_back(ctn[i]);
		pos.push_back(w);
		for (int j = 1; j <= len; j++) {
			ans.pop_back();
			pos.pop_back();
		}
	}
	for (int i = 0; i < (int)ans.size(); i++) {
		putchar(char(ans[i]));
	}
	return 0;
}

【BZOJ 4566】[HAOI2016] 找相同字符

相关链接

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

解题报告

我们可以拿一个串建SAM,把另一个串扔到SAM中匹配一遍
也可以直接把两个串拼一起,然后建SAM,最后遍历一下就好

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 800009;
const int SGZ = 27;
 
int n, m;
char s[N];
 
class Suffix_Automaton{
int cnt, tail, ch[N][SGZ], fail[N], sz[N][2], len[N], head[N], nxt[N], to[N];
public:
    inline void init() {
		cnt = tail = 1;
        for (int i = 1; i <= n; i++) {
            append(s[i] - 'a', 0);
        }
        append(SGZ - 1, -1);
        for (int i = n + 2; i <= n + m + 1; i++) {
            append(s[i] - 'a', 1);
        }
        for (int i = 1; i <= cnt; i++) {
            AddEdge(fail[i], i);
        }
        DFS(0, 0);
    }
    inline LL query() {
        LL ret = 0;
        for (int i = 1; i <= cnt; i++) {
            ret += (LL)(len[i] - len[fail[i]]) * sz[i][0] * sz[i][1];
        }
        return ret;
    } 
private:
    inline void DFS(int w, int f) {
        for (int i = head[w]; i; i = nxt[i]) {
            if (to[i] != f) {
                DFS(to[i], w);
                sz[w][0] += sz[to[i]][0];
                sz[w][1] += sz[to[i]][1];
            }
        }
    }
    inline void AddEdge(int u, int v) {
        static int E = 1;
        to[++E] = v; nxt[E] = head[u]; head[u] = E;
    }
    inline void append(char cc, int t) {
        int w = tail, cur = ++cnt;
        if (t != -1) {
            sz[cur][t] += 1;
        }
        len[cur] = len[tail] + 1;
        for (tail = cur; w && !ch[w][cc]; ch[w][cc] = cur, w = fail[w]);
        if (w) {
            if (len[ch[w][cc]] == len[w] + 1) {
                fail[cur] = ch[w][cc];
            } else {
                int nt = ++cnt, pt = ch[w][cc]; 
                memcpy(ch[nt], ch[pt], sizeof(ch[nt]));
                len[nt] = len[w] + 1;
                fail[nt] = fail[pt];
                fail[cur] = fail[pt] = nt;
                for (; w && ch[w][cc] == pt; ch[w][cc] = nt, w = fail[w]);
            }
        } else {
			fail[cur] = 1;
		}
    } 
}sam;
 
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    s[n + 1] = 'z' + 1;
    scanf("%s", s + n + 2);
    m = strlen(s + n + 2);
    sam.init();
    printf("%lld\n", sam.query());
    return 0;
}

【BZOJ 4195】[NOI2015] 程序自动分析

相关链接

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

解题报告

用并查集将相同的变量缩起来
然后判有没有两个不等的变量在一个连通分量即可

Code

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

const int N = 200009;
const int M = 300009;

int n, fa[N], cet[M], val[N], dif[N];

inline int read() {
	char c = getchar(); int 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 int find(int x) {
	return fa[x] == x? x: fa[x] = find(fa[x]);
}

int main() {
	freopen("prog.in", "r", stdin);
	freopen("prog.out", "w", stdout);
	for (int T = read(); T; T--) {
		n = read();
		int tot = 0, cnt = 0, tt = 0;
		for (int i = 1; i <= n; i++) {
			cet[++tot] = val[++cnt] = read();
			cet[++tot] = val[++cnt] = read();
			cet[++tot] = read();
		}
		sort(val + 1, val + 1 + cnt);
		cnt = unique(val + 1, val + 1 + cnt) - val - 1;
		for (int i = 1; i <= cnt; i++) {
			fa[i] = i;
		}
		for (int i = 1; i <= n; i++) {
			int t = cet[tot--];
			int u = cet[tot--], v = cet[tot--];
			u = lower_bound(val + 1, val + 1 + cnt, u) - val;
			v = lower_bound(val + 1, val + 1 + cnt, v) - val;
			if (t == 1) {
				fa[find(u)] = find(v);
			} else {
				dif[++tt] = u;
				dif[++tt] = v;
			}
		}
		bool ok = 1;
		for (int i = 1; i <= tt; i += 2) {
			int u = dif[i], v = dif[i + 1];
			if (find(u) == find(v)) {
				ok = 0;
				break;
			}
		}
		puts(ok? "YES": "NO");
	}
	return 0;
}

【BZOJ 4196】[NOI2015] 软件包管理器

相关链接

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

解题报告

考虑树链剖分
线段树部分只需要支持区间赋值,查询区间中1的个数
总的时间复杂度:$O(n \log ^ 2 n)$

Code

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

const int N = 100009;
const int M = 200009;

int n, m, head[N], nxt[N], to[N], beg[N], ot[N];
int fa[N], top[N], hvy[N], sz[N], dep[N];

inline int read() {
	char c = getchar(); int 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;
}

inline void DFS1(int w, int f) {
	fa[w] = f;
	dep[w] = dep[f] + 1;
	sz[w] = 1;
	for (int i = head[w]; i; i = nxt[i]) {
		DFS1(to[i], w);
		sz[w] += sz[to[i]];
		if (sz[to[i]] > sz[hvy[w]]) {
			hvy[w] = to[i];
		}
	}
}

inline void DFS2(int w, int t) {
	static int dfc = 0;
	beg[w] = ++dfc;
	top[w] = t;
	if (hvy[w]) {
		DFS2(hvy[w], t);
		for (int i = head[w]; i; i = nxt[i]) {
			if (to[i] != hvy[w]) {
				DFS2(to[i], to[i]);
			} 
		}
	}
	ot[w] = dfc;
}

class Segment_Tree{
int cnt, root, ch[M][2], sum[M], tag[M];
public:
	inline void init() {
		init(root, 1, n);
	}
	inline int install(int w) {
		int ret = 0, tmp;
		while (true) {
			int l = beg[top[w]], r = beg[w], len = r - l + 1;
			tmp = len - modify(root, 1, n, beg[top[w]], beg[w], 1);
			ret += tmp;
			if (fa[top[w]] != w && tmp) {
				w = fa[top[w]];
			} else {
				break;
			}
		} 
		return ret;
	}
	inline int uninstall(int w) {
		return modify(root, 1, n, beg[w], ot[w], -1);
	}
private:
	inline void init(int &w, int l, int r) {
		w = ++cnt;
		if (l < r) {
			int mid = l + r + 1 >> 1;
			init(ch[w][0], l, mid - 1);
			init(ch[w][1], mid, r);
		}
	}
	inline void PushDown(int w, int l, int mid, int r) {
		if (tag[w]) {
			int ls = ch[w][0], rs = ch[w][1];
			if (tag[w] == 1) {
				sum[ls] = mid - l;
				sum[rs] = r - mid + 1;
			} else {
				sum[ls] = sum[rs] = 0;
			}
			tag[ls] = tag[rs] = tag[w];
			tag[w] = 0;
		}
	}
	inline int modify(int w, int l, int r, int L, int R, int t) {
		if (L <= l && r <= R) {
			int ret = sum[w];
			sum[w] = t == -1? 0: r - l + 1;
			tag[w] = t;
			return ret;
		} else {
			int mid = l + r + 1 >> 1, ret = 0;
			PushDown(w, l, mid, r);
			if (L < mid) {
				ret += modify(ch[w][0], l, mid - 1, L, R, t);
			}
			if (mid <= R) {
				ret += modify(ch[w][1], mid, r, L, R, t);
			}
			sum[w] = sum[ch[w][1]] + sum[ch[w][0]];
			return ret;
		}
	}
}SGT;

int main() {
	freopen("manager.in", "r", stdin);
	freopen("manager.out", "w", stdout);
	n = read();
	for (int i = 2; i <= n; i++) {
		AddEdge(read() + 1, i);
	}
	DFS1(1, 1);
	DFS2(1, 1);
	SGT.init();
	m = read();
	char cmd[20];
	for (int i = 1; i <= m; i++) {
		scanf("%s", cmd + 1);
		if (cmd[1] == 'i') {
			printf("%d\n", SGT.install(read() + 1));
		} else {
			printf("%d\n", SGT.uninstall(read() + 1));
		}	
	}
	return 0;
}

【BZOJ 4197】[NOI2015] 寿司晚宴

相关链接

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

解题报告

考虑把小于$\sqrt{n}$的因数状压起来
然后将所有数按照大于$\sqrt{n}$的因数分组
最后分组$DP$即可
总时间复杂度:$O(500 \cdot 3^8)$

Code

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

const int N = 509;
const int M = 6561;

int pri[] = {2, 3, 5, 7, 11, 13, 17, 19};
int n, gpri[N], spri[N], sta1[M], sta2[M], tt[M][N][3];
LL MOD, *f, *g, *h, arr1[M], arr2[M], arr3[M], ori[M];
vector<int> sta[N];

inline void relax(LL &a, LL b) {
	a = (a + b) % MOD;
}

inline int num(int x, int t) {
	for (; t; x /= 3, t--);
	return x % 3;
}

inline int SET(int w, int t, int v) {
	static int buf[] = {1, 3, 9, 27, 81, 243, 729, 2187};
	int ret = 0;
	for (int i = 0; i < 8; i++, w /= 3, t >>= 1) {
		if (t & 1) {
			ret += buf[i] * v;
		} else {
			ret += buf[i] * (w % 3);
		}
	}
	return ret;
}

int main() {
	freopen("dinner.in", "r", stdin);
	freopen("dinner.out", "w", stdout);
	cin>>n>>MOD; 
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < 8; j++) {
			int t = num(i, j);
			if (t == 1) {
				sta1[i] |= 1 << j;
			} else if (t == 2) {
				sta2[i] |= 1 << j;
			}
		}
	}
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < (1 << 8); j++) {
			for (int k = 1; k <= 2; k++) {
				tt[i][j][k] = SET(i, j, k);
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		gpri[i] = i;
		for (int j = 0; j < 8; j++) {
			if (gpri[i] % pri[j] == 0) {
				spri[i] |= (1 << j);
				while (gpri[i] % pri[j] == 0) {
					gpri[i] /= pri[j];
				}
			}
		}
	}
	f = arr1, g = arr2, h = arr3;
	g[0] = f[0] = 1;
	for (int i = 2; i <= n; i++) {
		if (gpri[i] == 1) {
			for (int j = M - 1; ~j; j--) {
				if (g[j]) {
					int sta = 0;
					for (int k = 0; k < 8; k++) {
						if (spri[i] >> k & 1) {
							sta |= num(j, k);
						}
					}
					if (sta == 0) {
						relax(f[tt[j][spri[i]][1]], g[j]);
						relax(f[tt[j][spri[i]][2]], g[j]);
					} else if (sta < 3) {
						relax(f[tt[j][spri[i]][sta]], g[j]);
					}
				}
			}
			memcpy(g, f, sizeof(arr1));
			swap(f, g);
		} else {
			sta[gpri[i]].push_back(spri[i]);
		}
	}
	for (int i = 2; i <= n; i++) {
		if (!sta[i].empty()) {
			memcpy(h, g, sizeof(arr1));
			memcpy(ori, g, sizeof(arr1));
			for (int j = 0; j < (int)sta[i].size(); j++) {
				int vv = sta[i][j];
				for (int k = M - 1; ~k; k--) {
					if (g[k]) {
						int s1 = vv & sta1[k];
						if (!s1) {
							relax(f[tt[k][vv][2]], g[k]);
						} 
					}
				}
				memcpy(g, f, sizeof(arr1));
				swap(f, g);
			}
			memcpy(f, h, sizeof(arr1));
			for (int j = 0; j < (int)sta[i].size(); j++) {
				int vv = sta[i][j];
				for (int k = M - 1; ~k; k--) {
					if (h[k]) {
						int s2 = vv & sta2[k];
						if (!s2) {
							relax(f[tt[k][vv][1]], h[k]);
						}
					}
				}
				memcpy(h, f, sizeof(arr1));
				swap(f, h);
			}
			for (int k = 0; k < M; k++) {
				f[k] = g[k] = (f[k] + g[k] - ori[k]) % MOD + MOD;
			}
		}
	}
	LL ans = 0;
	for (int i = 0; i < M; i++) {
		relax(ans, f[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

【BZOJ 4278】[ONTAK2015] Tasowanie

相关链接

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

解题报告

考虑归并排序
唯一麻烦的地方就是两个字符相同时选哪个
我们可以比较后缀的字典序来解决这个问题
具体实现上,我们可以使用SA

Code

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

const int N = 800009;
const int SGZ = 1001;

int n, m, s[N];
class Suffix_Array{
int *rk, *tmp, sa[N], bot[N], arr1[N], arr2[N], que[N];
public:
	inline void build(int *s, int nn) {
		rk = arr1; tmp = arr2; int sgz = SGZ;
		for (int i = 1; i <= nn; i++) bot[s[i]]++;
		for (int i = 1; i <= sgz; i++) bot[i] += bot[i - 1];
		for (int i = 1; i <= nn; i++) que[bot[s[i]]--] = i;
		rk[que[1]] = sgz = 1; 
		for (int i = 2; i <= nn; i++) rk[que[i]] = (sgz += s[que[i]] != s[que[i - 1]]);
		for (int l = 1; l < nn && sgz < nn; l <<= 1) {
			int tt = 0;
			for (int i = nn - l + 1; i <= nn; i++) tmp[++tt] = i;
			for (int i = 1; i <= nn; i++) if (que[i] > l) tmp[++tt] = que[i] - l;
			for (int i = 0; i <= sgz; i++) bot[i] = 0;
			for (int i = 1; i <= nn; i++) bot[rk[i]]++;
			for (int i = 1; i <= sgz; i++) bot[i] += bot[i - 1];
			for (int i = nn; i; i--) que[bot[rk[tmp[i]]]--] = tmp[i];
			swap(rk, tmp); rk[que[1]] = sgz = 1;
			for (int i = 2; i <= nn; i++) {
				rk[que[i]] = (sgz += tmp[que[i]] != tmp[que[i - 1]] || tmp[que[i] + l] != tmp[que[i - 1] + l]);
			}
		}
	}
	inline int rank(int p) {
		return rk[p];		
	}
}sa;

inline int read() {
	char c = getchar(); int 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;
}

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		s[i] = read();
	}
	s[n + 1] = 1001;
	m = read();
	for (int i = 1; i <= m; i++) {
		s[i + n + 1] = read();
	}
	sa.build(s, n + m + 1);
	for (int i = 1, j = 1, k = 1; k <= n + m; k++) {
		if (i <= n && j <= m) {
			if (s[i] < s[j + n + 1] || (s[i] == s[j + n + 1] && sa.rank(i) < sa.rank(j + n + 1))) {
				printf("%d ", s[i++]);
			} else {
				printf("%d ", s[n + 1 + j++]);
			}
		} else if (i <= n) {
			printf("%d ", s[i++]);
		} else {
			printf("%d ", s[n + 1 + j++]);
		}
	}
	return 0;
}

【BZOJ 1137】[POI2009] Wsp 岛屿

相关链接

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

解题报告

不难发现每一个点应尽量向编号大的点连边
所以就只剩下$O(n)$条线段了,直接做半平面交就好

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100009;
const double EPS = 1e-6;
 
int n, m, tot;
vector<int> del[N];
struct Point{
    double x, y;
    inline Point() {
    }
    inline Point(double _x, double _y):x(_x), y(_y) {
    }
    inline Point operator - (const Point &P) const {
        return Point(x - P.x, y - P.y);
    }
    inline Point operator + (const Point &P) {
        return Point(x + P.x, y + P.y);
    }
    inline Point operator * (double d) {
        return Point(x * d, y * d);
    }
    inline double operator * (const Point &P) {
        return x * P.y - y * P.x;
    }
    inline double len() {
        return sqrt(x * x + y * y);
    }
}p[N];
struct Line{
    Point a, b;
    double slope;
    inline Line() {
    }
    inline Line(const Point &_a, const Point &_b):a(_a), b(_b) {
    }
    inline bool operator < (const Line &L) const {
        return slope < L.slope;
    }
    inline Point intersect(const Line &L) {
        double s1 = (L.b - L.a) * (b - L.a);
        double s2 = (a - L.a) * (L.b - L.a);
        return a + (b - a) * (s2 / (s1 + s2));
    }
    inline bool OnLeft(const Point &P) {
        return (b - a) * (P - a) > EPS;
    }
}l[N];
 
inline int read() {
    char c = getchar(); int 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 HalfPlaneIntersection(Line *arr, int &sz) {
    for (int i = 1; i <= sz; i++) {
        Point vec = arr[i].b - arr[i].a;
        arr[i].slope = atan2(vec.y, vec.x);
    }
    sort(arr + 1, arr + 1 + sz);
    int l = 1, r = 0;
    for (int i = 1; i <= sz; i++) {
        for (; l < r && !arr[i].OnLeft(arr[r].intersect(arr[r - 1])); r--); 
        for (; l < r && !arr[i].OnLeft(arr[l].intersect(arr[l + 1])); l++);
        arr[++r] = arr[i];
    }
    for (; l < r - 1 && !arr[l].OnLeft(arr[r].intersect(arr[r - 1])); r--);
    sz = 0;
    for (int i = l; i <= r; i++) {
        arr[++sz] = arr[i];
    }
    arr[0] = arr[sz];
    arr[sz + 1] = arr[1];
}
 
int main() {
    n = read(); m = read();
    for (int i = 1; i <= n; i++) {
        p[i].x = read();
        p[i].y = read();
    }
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read();
        del[min(x, y)].push_back(max(x, y));
    }
    for (int i = 1; i < n; i++) {
        sort(del[i].begin(), del[i].end());
        int to = n;
        while (!del[i].empty() && *--del[i].end() == to) {
            to--;
            del[i].pop_back();
        }
        if (i == 1 && to == n) {
            printf("%.10lf", (p[1] - p[n]).len());
            exit(0);
        }
        if (to > i) {
            l[++tot] = Line(p[to], p[i]);
        }
    }
    l[++tot] = Line(p[1], p[n]); 
    HalfPlaneIntersection(l, tot);
    double ans = -(p[1] - p[n]).len();
    Point last = l[1].intersect(l[0]);
    for (int i = 1; i <= tot; i++) {
        Point cur = l[i].intersect(l[i + 1]);
        ans += (cur - last).len();
        last = cur;
    }
    printf("%.10lf\n", ans);
    return 0;
}

【模板库】线段树合并

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=4530

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

const int N = 200009; 
const int M = N * 21;

int n, m, vis[N], head[N], nxt[N], to[N];
int dep[N], beg[N], out[N], sz[N], fa[N];
struct Data{
	int t, x, y;
	inline Data() {
	}
	inline Data(bool a, int b, int c):t(a), x(b), y(c) {
	} 
}opt[N];

inline int read() {
	char c = getchar(); int 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;
}

inline void DFS(int w, int f) {
	static int D = 0;
	vis[w] = 1;
	beg[w] = ++D;
	dep[w] = dep[f] + 1;
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
		}
	}
	out[w] = D;
}

inline int find(int x) {
	return fa[x] == x? x: fa[x] = find(fa[x]);
}

class SegmentTree{
int cnt, ch[M][2], sum[M], root[N];
public:
	inline void insert(int p, int v) {
		insert(root[p], 1, n, v);
	}
	inline void merge(int a, int b) {
		root[a] = Merge(root[a], root[b]);
	}
	inline int query(int p, int l, int r) {
		return query(root[p], 1, n, l, r);
	}
private:
	inline int Merge(int a, int b) {
		if (!a || !b) {
			return a + b;
		} else {
			sum[a] += sum[b];
			ch[a][0] = Merge(ch[a][0], ch[b][0]);
			ch[a][1] = Merge(ch[a][1], ch[b][1]);
			return a;
		}
	}
	inline void insert(int &w, int l, int r, int p) {
		sum[w = ++cnt] = 1;
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (p < mid) {
				insert(ch[w][0], l, mid - 1, p);
			} else {
				insert(ch[w][1], mid, r, p);
			}
		}
	} 
	inline int query(int w, int l, int r, int L, int R) {
		if (!w) {
			return 0;
		} else if (L <= l && r <= R) {
			return sum[w];
		} else {
			int mid = l + r + 1 >> 1, ret = 0;
			ret += L < mid? query(ch[w][0], l, mid - 1, L, R): 0;
			ret += mid <= R? query(ch[w][1], mid, r, L, R): 0;
			return ret;
		}
	}
}SGT;

int main() {
	n = read(); m = read();
	for (int i = 1; i <= m; i++) {
		char cmd[3]; 
		scanf("%s", cmd);
		int u = read(), v = read();
		if (cmd[0] == 'A') {
			AddEdge(u, v);
		}
		opt[i] = Data(cmd[0] == 'A', u, v);
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			DFS(i, i);
		}
	}
	for (int i = 1; i <= n; i++) {
		sz[i] = 1;
		fa[i] = i;
		SGT.insert(i, beg[i]);
	}
	for (int i = 1; i <= m; i++) {
		int u = opt[i].x, v = opt[i].y;
		if (opt[i].t == 1) {
			SGT.merge(find(u), find(v));
			sz[find(u)] += sz[find(v)];
			fa[find(v)] = find(u);
		} else {
			if (dep[u] < dep[v]) {
				swap(u, v);
			}
			int p1 = SGT.query(find(u), beg[u], out[u]);
			int p2 = sz[find(u)] - p1;
			printf("%lld\n", (LL)p1 * p2);
		}
	}
	return 0;
}

【BZOJ 4530】[BJOI2014] 大融合

相关链接

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

解题报告

这题LCT是可以做的

但因为本题没有要求强制在线
所以我们可以用并查集来维护连通性,再用线段树合并来支持支持DFS序的区间询问
总的时间复杂度:$O(n \log n)$

Code

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

const int N = 200009; 
const int M = N * 21;

int n, m, vis[N], head[N], nxt[N], to[N];
int dep[N], beg[N], out[N], sz[N], fa[N];
struct Data{
	int t, x, y;
	inline Data() {
	}
	inline Data(bool a, int b, int c):t(a), x(b), y(c) {
	} 
}opt[N];

inline int read() {
	char c = getchar(); int 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;
}

inline void DFS(int w, int f) {
	static int D = 0;
	vis[w] = 1;
	beg[w] = ++D;
	dep[w] = dep[f] + 1;
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
		}
	}
	out[w] = D;
}

inline int find(int x) {
	return fa[x] == x? x: fa[x] = find(fa[x]);
}

class SegmentTree{
int cnt, ch[M][2], sum[M], root[N];
public:
	inline void insert(int p, int v) {
		insert(root[p], 1, n, v);
	}
	inline void merge(int a, int b) {
		root[a] = Merge(root[a], root[b]);
	}
	inline int query(int p, int l, int r) {
		return query(root[p], 1, n, l, r);
	}
private:
	inline int Merge(int a, int b) {
		if (!a || !b) {
			return a + b;
		} else {
			sum[a] += sum[b];
			ch[a][0] = Merge(ch[a][0], ch[b][0]);
			ch[a][1] = Merge(ch[a][1], ch[b][1]);
			return a;
		}
	}
	inline void insert(int &w, int l, int r, int p) {
		sum[w = ++cnt] = 1;
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (p < mid) {
				insert(ch[w][0], l, mid - 1, p);
			} else {
				insert(ch[w][1], mid, r, p);
			}
		}
	} 
	inline int query(int w, int l, int r, int L, int R) {
		if (!w) {
			return 0;
		} else if (L <= l && r <= R) {
			return sum[w];
		} else {
			int mid = l + r + 1 >> 1, ret = 0;
			ret += L < mid? query(ch[w][0], l, mid - 1, L, R): 0;
			ret += mid <= R? query(ch[w][1], mid, r, L, R): 0;
			return ret;
		}
	}
}SGT;

int main() {
	n = read(); m = read();
	for (int i = 1; i <= m; i++) {
		char cmd[3]; 
		scanf("%s", cmd);
		int u = read(), v = read();
		if (cmd[0] == 'A') {
			AddEdge(u, v);
		}
		opt[i] = Data(cmd[0] == 'A', u, v);
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			DFS(i, i);
		}
	}
	for (int i = 1; i <= n; i++) {
		sz[i] = 1;
		fa[i] = i;
		SGT.insert(i, beg[i]);
	}
	for (int i = 1; i <= m; i++) {
		int u = opt[i].x, v = opt[i].y;
		if (opt[i].t == 1) {
			SGT.merge(find(u), find(v));
			sz[find(u)] += sz[find(v)];
			fa[find(v)] = find(u);
		} else {
			if (dep[u] < dep[v]) {
				swap(u, v);
			}
			int p1 = SGT.query(find(u), beg[u], out[u]);
			int p2 = sz[find(u)] - p1;
			printf("%lld\n", (LL)p1 * p2);
		}
	}
	return 0;
}

【BZOJ 2402】陶陶的难题II

相关链接

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

解题报告

不难发现这是一个分数规划问题
再化一化式子就可以转换成凸包上选点的问题
至于支持链上的询问我们可以套树链剖分
总的时间复杂度:$O(n \log^3 n)$

Code

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

const int N = 60009;
const double INF = 1e9;
const double EPS = 1e-4;

int n, head[N], nxt[N], to[N];
struct Point{
	double x, y;
	inline Point() {
	}
	inline Point(double a, double b):x(a), y(b) {
	}
	inline bool operator < (const Point &PP) const {
		return x < PP.x || (x == PP.x && y < PP.y);
	}
	inline bool operator == (const Point &PP) const {
		return x == PP.x && y == PP.y;
	}
 	inline Point operator - (const Point &PP) const {
		return Point(x - PP.x, y - PP.y);
	}
	inline double operator * (const Point &PP) {
		return x * PP.y - y * PP.x;
	}
	inline double slope() {
		return y / x;
	}
}d[N][2];

inline int read() {
	char c = getchar(); int 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 HeavyLightDecomposition{
int fa[N], sz[N], dep[N], idx[N], hvy[N], top[N];
class SegmentTree{
vector<Point> cvx[N][2];
public:
	int num[N], root, ch[N][2];
	inline void init() {
		build(root, 1, n);	
	}
	inline void update(int l, int r, double a, double *mx) {
		query(root, 1, n, l, r, a, mx);
	}
private:
	inline void query(int w, int l, int r, int L, int R, double a, double *mx) {
		if (L <= l && r <= R) {
			mx[0] = max(mx[0], cal(cvx[w][0], a));
			mx[1] = max(mx[1], cal(cvx[w][1], a));
		} else {
			int mid = l + r + 1 >> 1;
			if (L < mid) {
				query(ch[w][0], l, mid - 1, L, R, a, mx);
			}
			if (R >= mid) {
				query(ch[w][1], mid, r, L, R, a, mx);
			}
		}
	}
	inline double cal(const vector<Point> &que, double a) {
		int l = 0, r = que.size() - 1, mid, ret = 0;
		while (l <= r) {
			mid = l + r >> 1;
			if (mid == 0 || (que[mid] - que[mid - 1]).slope() >= a) {
				ret = mid; 
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		return -a * que[ret].x + que[ret].y;
	}
	inline void build(int &w, int l, int r) {
		static int cnt = 0;
		w = ++cnt;
		if (l == r) {
			cvx[w][0].push_back(d[num[l]][0]);
			cvx[w][1].push_back(d[num[l]][1]);
		} else {
			int mid = l + r + 1 >> 1;
			build(ch[w][0], l, mid - 1);
			build(ch[w][1], mid, r);
			int ls = ch[w][0], rs = ch[w][1];
			cvx[w][0] = Merge(cvx[ls][0], cvx[rs][0]);
			cvx[w][1] = Merge(cvx[ls][1], cvx[rs][1]);
		}
	}
	inline vector<Point> Merge(const vector<Point> &c1, const vector<Point> &c2) {
		vector<Point> cur, ret;
		for (int i = 0; i < (int)c1.size(); i++) {
			cur.push_back(c1[i]);
		}
		for (int i = 0; i < (int)c2.size(); i++) {
			cur.push_back(c2[i]);
		}
		sort(cur.begin(), cur.end());
		cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
		for (int i = 0; i < (int)cur.size(); i++) {
			while ((int)ret.size() > 1) {
				int idx = ret.size() - 1;
				if ((cur[i] - ret[idx - 1]) * (ret[idx] - ret[idx - 1]) <= EPS) {
					ret.pop_back();
				} else {
					break;
				}
			}
			ret.push_back(cur[i]);
		}
		return ret;
	}
}SGT;
public:
	inline void init() {
		DFS1(1, 1);
		DFS2(1, 1);
		SGT.init();
	}	
	inline double query(int u, int v) {
		double l = 0, r = INF, ret = 0, mid;
		while (r - l > EPS) {
			mid = (l + r) * 0.5;
			if (judge(u, v, mid)) {
				ret = mid;
				l = mid;
			} else {
				r = mid;
			}
		}	
		return ret;
	}
private:
	inline bool judge(int u, int v, double a) {
		double mx[] = {-INF, -INF};
		while (top[u] != top[v]) {
			if (dep[top[u]] > dep[top[v]]) {
				SGT.update(idx[top[u]], idx[u], a, mx);
				u = fa[top[u]];
			} else {
				SGT.update(idx[top[v]], idx[v], a, mx);
				v = fa[top[v]];
			}
		}
		if (dep[u] > dep[v]) {
			SGT.update(idx[v], idx[u], a, mx);
		} else {
			SGT.update(idx[u], idx[v], a, mx);
		}
		return mx[0] + mx[1] > 0;
	}
	inline void DFS1(int w, int f) {
		fa[w] = f;
		sz[w] = 1;
		dep[w] = dep[f] + 1;
		for (int i = head[w]; i; i = nxt[i]) {
			if (to[i] != f) {
				DFS1(to[i], w);
				sz[w] += sz[to[i]];
				if (sz[to[i]] > sz[hvy[w]]) {
					hvy[w] = to[i];
				}
			}
		}
	}
	inline void DFS2(int w, int t) {
		static int dcnt = 0;
		SGT.num[idx[w] = ++dcnt] = w;
		top[w] = t;
		if (hvy[w]) {
			DFS2(hvy[w], t);
		}
		for (int i = head[w]; i; i = nxt[i]) {
			if (to[i] != fa[w] && to[i] != hvy[w]) {
				DFS2(to[i], to[i]);
			}
		}
	}
}HLD;

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][0].x);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][0].y);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][1].x);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][1].y);
	}
	for (int i = 1; i < n; i++) {
		AddEdge(read(), read());
	}
	HLD.init();
	for (int i = read(); i; i--) {
		printf("%.10lf\n", HLD.query(read(), read()));
	}
	return 0;
}

【日常小测】route

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/07/20170624_problem.pdf

解题报告

我们往后多看一步:

假设下一步我们需要向左走,那么我们这一步就走到对于现在所在的点极角序最小的点去
否则就走到极角序最大的点去

不难发现这样一定能构造出一组解

Code

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

const int N = 5009;

int n, vis[N];
char cmd[N];
struct Point{
	int x, y;
	inline Point() {
	}
	inline Point(int a, int b):x(a), y(b) {
	}
	inline Point operator - (const Point &P) {
		return Point(x - P.x, y - P.y);
	}
	inline bool operator < (const Point &P) {
		return x < P.x || (x == P.x && y < P.y);
	}
	inline LL operator * (const Point &P) {
		return x * P.y - y * P.x;
	}
}p[N];

inline int read() {
	char c = getchar(); int 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 solve(int w, int stp) {
	vis[w] = 1;
	printf("%d ", w);
	if (stp < n) {
		int nxt = 0;
		for (int i = 1; i <= n; i++) {
			if (!vis[i]) {
				if (!nxt || (cmd[stp] == 'L'? (p[nxt] - p[w]) * (p[i] - p[w]) < 0: (p[nxt] - p[w]) * (p[i] - p[w]) > 0)) {
					nxt = i;
				}
			}
		}
		solve(nxt, stp + 1);
	}
}

int main() {
	freopen("route.in", "r", stdin);
	freopen("route.out", "w", stdout);
	n = read();
	int s = 0;
	for (int i = 1; i <= n; i++) {
		p[i].x = read();
		p[i].y = read();
		if (!s || p[i] < p[s]) {
			s = i;
		}
	}
	scanf("%s", cmd);
	solve(s, 1);
	return 0;
}