【BZOJ 4817】[SDOI2017] 树点涂色

相关链接

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

解题报告

我们发现涂色可以看作LCT的access操作
然后权值就是到根的虚边数

于是用LCT来维护颜色
用线段树配合DFS序来支持查询
时间复杂度:$O(n \log^2 n)$

Code

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

const int N = 100009;
const int M = N << 1;
const int LOG = 20;

int n, m, head[N], nxt[M], to[M]; 
int in[N], ot[N], dep[N], num[N], ff[N][LOG];

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 int LCA(int u, int v) {
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	for (int j = LOG - 1; ~j; j--) {
		if (dep[ff[u][j]] >= dep[v]) {
			u = ff[u][j];
		}
	}
	if (u == v) {
		return u;
	}
	for (int j = LOG - 1; ~j; j--) {
		if (ff[u][j] != ff[v][j]) {
			u = ff[u][j];
			v = ff[v][j];
		}
	}
	return ff[u][0];
}

class SegmentTree{
	int root, ch[M][2], tag[M], mx[M];
public:
	inline void init() {
		build(root, 1, n);
	}
	inline void modify(int l, int r, int d) {
		modify(root, 1, n, l, r, d);
	}
	inline int query(int l, int r = -1) {
		return query(root, 1, n, l, r >= 0? r: l);
	}
private:
	inline void PushDown(int w) {
		if (tag[w]) {
			int ls = ch[w][0], rs = ch[w][1];
			mx[ls] += tag[w];
			mx[rs] += tag[w];
			tag[ls] += tag[w];
			tag[rs] += tag[w];
			tag[w] = 0;
		}
	}
	inline int query(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return mx[w];
		} else {
			PushDown(w);
			int mid = l + r + 1 >> 1, ret = 0;
			if (L < mid) {
				ret = max(ret, query(ch[w][0], l, mid - 1, L, R));
			}
			if (mid <= R) {
				ret = max(ret, query(ch[w][1], mid, r, L, R));
			}
			return ret;
		}
	}
	inline void modify(int w, int l, int r, int L, int R, int d) {
		if (L <= l && r <= R) {
			tag[w] += d;
			mx[w] += d;
		} else {
			PushDown(w);
			int mid = l + r + 1 >> 1;
			if (L < mid) {
				modify(ch[w][0], l, mid - 1, L, R, d);
			}
			if (mid <= R) {
				modify(ch[w][1], mid, r, L, R, d);
			}
			mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]);
		}
	}
	inline void build(int &w, int l, int r) {
		static int cnt = 0;
		w = ++cnt;
		if (l == r) {
			mx[w] = dep[num[l]];
		} else {
			int mid = l + r + 1 >> 1;
			build(ch[w][0], l, mid - 1);
			build(ch[w][1], mid, r);
			mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]);
		}
	}
}SGT;

class LinkCutTree{
	int ch[N][2], fa[N];
public:
	inline void SetFather(int w, int f) {
		fa[w] = f;
	}
	inline void access(int x) {
		for (int last = 0; x; last = x, x = fa[x]) {
			splay(x);
			if (fa[x]) {
				int p = GetMin(x);
				SGT.modify(in[p], ot[p], -1);
			}
			if (ch[x][1]) {
				int p = GetMin(ch[x][1]);
				SGT.modify(in[p], ot[p], 1);
			}
			ch[x][1] = last;
		}
	}
private:
	inline bool IsRoot(int x) {
		return !fa[x] || (ch[fa[x]][0] != x && ch[fa[x]][1] != x);
	}
	inline int GetMin(int x) {
		return ch[x][0]? GetMin(ch[x][0]): x;
	}
	inline void splay(int x) {
		for (int f, ff; !IsRoot(x); ) {
			f = fa[x], ff = fa[f];
			if (IsRoot(f)) {
				rotate(x);
			} else {
				if ((ch[ff][0] == f) ^ (ch[f][0] == x)) {
					rotate(x);
					rotate(x);
				} else {
					rotate(f);
					rotate(x);
				}
			}
		}
	}
	inline void rotate(int x) {
		int f = fa[x], t = ch[f][1] == x;
		fa[x] = fa[f];
		if (!IsRoot(f)) {
			ch[fa[f]][ch[fa[f]][1] == f] = x;
		}
		ch[f][t] = ch[x][t ^ 1];
		fa[ch[x][t ^ 1]] = f;
		ch[x][t ^ 1] = f;
		fa[f] = x;
	}
}LCT;

inline void DFS(int w, int f) {
	static int ID = 0;
	LCT.SetFather(w, f);
	ff[w][0] = f;
	dep[w] = dep[f] + 1;
	num[in[w] = ++ID] = w;
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
		}
	}
	ot[w] = ID;
}	

int main() {
	n = read(); m = read();
	for (int i = 1; i < n; i++) {
		AddEdge(read(), read());
	}
	DFS(1, 0);
	for (int j = 1; j < LOG; j++) {
		for (int i = 1; i <= n; i++) {
			ff[i][j] = ff[ff[i][j - 1]][j - 1];
		}
	}
	SGT.init();
	for (int i = 1; i <= m; i++) {
		int opt = read();
		if (opt == 1) {
			LCT.access(read());
		} else if (opt == 2) {
			int u = read(), v = read(), lca = LCA(u, v);
			printf("%d\n", SGT.query(in[u]) + SGT.query(in[v]) - 2 * SGT.query(in[lca]) + 1);
		} else {
			int x = read();
			printf("%d\n", SGT.query(in[x], ot[x]));
		}
	}
	return 0;
}

【BZOJ 4826】[HNOI2017] 影魔

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4826
神犇题解:http://www.cnblogs.com/Enceladus/p/6735887.html

解题报告

这题建出笛卡尔树,之后就是区间加、区间询问
于是将询问离线,用线段树维护一下就好了
总时间复杂度:$O(n \log n)$

至于笛卡尔树那一块,我们可以看作一个分治
而与最大值相关的题,分治是常见解法
所以这题还是很容易想到的吧

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
   
const int N = 200009;
const int NN = N << 1;
const int M = 18;
   
int n,m,p1,p2,val[N];
LL ans[N];
vector<int> q1[N];
vector<pair<int,int> > q2[N],q3[N];
struct Query{int l,r,id;}q[N];
   
inline bool cmp1(const Query &A, const Query &B) {return A.r < B.r;}
inline bool cmp2(const Query &A, const Query &B) {return A.l > B.l;}
   
inline int read() {
    char c=getchar(); int f=1,ret=0;
    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 Sparse_Table{
    int mx[M][N],pos[M][N],lg[N];
    public:
        inline void init(int *arr) {
            for (int i=1;i<=n;i++) {
                mx[0][i] = arr[i];
                pos[0][i] = i;
            }
            for (int l=1,j=1;l*2<=n;j++,l<<=1) {
                for (int i=1;i<=n-l;i++) {
                    if (mx[j-1][i] >= mx[j-1][i+l]) {
                        pos[j][i] = pos[j-1][i];
                        mx[j][i] = mx[j-1][i];
                    } else {
                        pos[j][i] = pos[j-1][i+l];
                        mx[j][i] = mx[j-1][i+l];
                    }
                }
            }
            for (int i=2;i<=n;i++) {
                lg[i] = lg[i>>1] + 1;
            }
        }
        inline int query(int l, int r) {
            int t = lg[r-l+1], j = 1 << t;
            if (mx[t][l] >= mx[t][r-j+1]) return pos[t][l];
            else return pos[t][r-j+1]; 
        }
}ST;
   
void solve(int l, int r) {
    if (l == r - 1) {
        return;
    } else {
        int pos = ST.query(l+1, r-1);
        if (l) q1[pos].push_back(l);
        if (r <= n) q1[r].push_back(pos);
           
        if (r <= n && pos - l > 1) q2[r].push_back(make_pair(l + 1, pos - 1));
        if (l && r - pos > 1) q3[l].push_back(make_pair(pos + 1, r - 1));
           
        solve(l, pos);
        solve(pos, r);
    }
}
   
class Segment_Tree{
    int cnt; LL AnsTmp;
    struct Node{
        Node *ch[2];
        int len;
        LL sum,tag;
    }p[NN],*root; 
    public:
        inline void init() {
            cnt = 0;
            build(root, 1, n);
        }
        inline void modify(int pos, int delta) {
            Node *w = root;
            int  l = 1, r = n, mid;
            while (l <= r) {
                w->sum += delta;
                if (l == r) break;
                mid = l + r + 1 >> 1;
                if (pos < mid) w = w->ch[0], r = mid - 1;
                else w = w->ch[1], l = mid;
            }
        }
        inline void modify(int l, int r, int delta) {
            modify(root, 1, n, l, r, delta);
        }
        inline LL query(int l, int r) {
            AnsTmp = 0;
            query(root, 1, n, l, r);
            return AnsTmp;
        }
    private:
        inline void pushdown(Node *w) {
            w->ch[0]->sum += w->ch[0]->len * w->tag;
            w->ch[1]->sum += w->ch[1]->len * w->tag;
            w->ch[0]->tag += w->tag; w->ch[1]->tag += w->tag;
            w->tag = 0;
        }
        void query(Node *w, int l, int r, int L, int R) {
            if (L <= l && r <= R) {
                AnsTmp += w->sum;
            } else {
                if (w->tag) pushdown(w);
                int mid = l + r + 1 >> 1;
                if (L < mid) query(w->ch[0], l, mid-1, L, R);
                if (mid <= R) query(w->ch[1], mid, r, L, R);
            }
        }
        void modify(Node *w, int l, int r, int L, int R, int delta) {
            if (L <= l && r <= R) {
                w->sum += (LL)delta * w->len;
                w->tag += delta;
            } else {
                if (w->tag) pushdown(w);
                int mid = r + l + 1 >> 1;
                if (L < mid) modify(w->ch[0], l, mid-1, L, R, delta);
                if (mid <= R) modify(w->ch[1], mid, r, L, R, delta);
                w->sum = w->ch[0]->sum + w->ch[1]->sum;
            }
        }
        void build(Node *&w, int l, int r) {
            w = &p[++cnt];
            w->len = r - l + 1;
            w->sum = w->tag = 0; 
            w->ch[0] = w->ch[1] = 0;
            if (l < r) {
                int mid = l + r + 1 >> 1;
                build(w->ch[0], l, mid-1);
                build(w->ch[1], mid, r);
            }
        }
}SEG;
   
int main() {
    n = read(); m = read();
    p1 = read(); p2 = read();
    for (int i=1;i<=n;i++) {
        val[i] = read();
    }
    ST.init(val); 
    solve(0, n+1); 
    for (int i=1;i<=m;i++) {
        q[i].l = read(); 
        q[i].r = read();
        q[i].id = i;
    }
    sort(q+1, q+1+m, cmp1);
    SEG.init();
    for (int i=1,pos=0;i<=m;i++) {
        while (pos < q[i].r) {
            pos++;
            for (int j=0;j<q1[pos].size();j++) {
                SEG.modify(q1[pos][j], p1);
            }
            for (int j=0;j<q2[pos].size();j++) {
                SEG.modify(q2[pos][j].first, q2[pos][j].second, p2);
            }
        }
        ans[q[i].id] += SEG.query(q[i].l, q[i].r);
    }
    sort(q+1, q+1+m, cmp2);
    SEG.init(); 
    for (int i=1,pos=n+1;i<=m;i++) {
        while (pos > q[i].l) {
            pos--;
            for (int j=0;j<q3[pos].size();j++) {
                SEG.modify(q3[pos][j].first, q3[pos][j].second, p2);
            }
        } 
        ans[q[i].id] += SEG.query(q[i].l, q[i].r);
    }
    for (int i=1;i<=m;i++) {
        printf("%lld\n",ans[i]);
    }
    return 0;
}

【BZOJ 3019】[Balkan2012] handsome

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3019
神犇题解:http://www.cnblogs.com/clrs97/p/6371367.html

解题报告

因为字典序大小这个东西实在是没有办法
所以我们根据它给的排列顺序来填数

这在原数列上的填充顺序是离散的
但考虑已经填了$i$个数,现在填第$i+1$个数
这大概是把一个空白的区间分成两份
于是我们预处理$f_{i,l,r}$表示长度为$i$,左右端点的字符分别为$l,r$的合法序列的方案数
这样我们就可以使用线段树在$O(\log n)$的时间复杂度内快速维护答案了

于是我们还是类比传统的数位DP,然后按照排列顺序往里加字符,使用线段树来维护答案
预处理的时间复杂度:$O(n)$,主程序的时间复杂度:$O(n \log n)$

【BZOJ 4785】[ZJOI 2017] 树状数组

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4785
出题人传送门:http://jiruyi910387714.is-programmer.com/posts/209073.html
官方题解:https://pan.baidu.com/s/1dFGHFfr

解题报告

我们发现正常的代码是统计的前缀和
但劼的写法实际是统计后缀和
然后画一画发现,只有$l-1,r$这两个点被改到的时候才会影响答案

我们考虑询问区间是$[l,r]$,一个修改区间是$[a,b]$
那么如果$l,r \in [a,b]$则这个修改区间有$\frac{2}{b-a+1}$的可能影响到答案
如果$l,r$只有一个$\in [a,b]$那么这个修改区间有$\frac{1}{b-a+1}$的可能影响到答案
如果两个都不属于,其显然不会影响到答案

于是我们把修改操作看成二维平面上的点的话
每一个询问操作可以拆成三个矩阵的询问
这个是经典问题,可以用树套树/分治/K-d Tree来解决

至于怎么维护标记,直接做的话,我们可以看成矩阵乘法
因为这个转移矩阵非常特殊,搞一搞发现其不但满足结合律,还满足交换律,所以可以标记永久化
但还有更妙的做法:

我们可以搞一个类似生成函数的东西
设第$i$个操作有$p_i$的可能影响到当前询问,设两个端点被改变偶数次的概率为$a$,奇数次为$b$
那么最后$a-b=\prod\limits_{i}{(1-p_i)-p_i}$
为什么是对的呢?因为只有改变奇数次才会为奇数,而$-1$的奇数次方等于$-1$偶数次方等于$1$,所以刚好对上
又因为我们还知道$a+b=1$,所以$a = \frac{1+\prod\limits_{i}{(1-p_i)-p_i}}{2}$

另外的话,这题有一个坑点:如果$l-1=0$的话,我们需要特判
因为之前我们的推导基于$l-1$那个点记录的是一个后缀
而实际算法中我们我们默认$l-1$那个点的值为$0$,所以需要判断一下总操作次数奇偶
考试的时候就这一点没想到,血wa三小时,最后这题挂零

Code

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

const int N = 100009;
const int M = 30000000;
const int MOD = 998244353;
const int REV = 499122177;

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

int n,m,tot;
class Segment_Tree{
	int cnt,root,AnsTmp,ch[M][2],prod[M][2];
	public:
		inline void modify(int x, int y, int v, bool t) {
			modify(root, 1, n, x, y, v, t);
		}
		inline int query(int x1, int x2, int y1, int y2, bool t) {
			if (x1 > x2 || y1 > y2) return 1;
			AnsTmp = 1;
			query(root, 1, n, x1, x2, y1, y2, t);
			return (AnsTmp+MOD)%MOD;
		}
	private:
		void modify(int &w, int l, int r, int x, int y, int v, bool t) { //X
			if (!w) w = ++cnt; modify(prod[w][0], 1, n, y, v, t);
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (x < mid) modify(ch[w][0], l, mid-1, x, y, v, t);
				else modify(ch[w][1], mid, r, x, y, v, t); 
			}
		}
		void modify(int &w, int l, int r, int p, int v, bool t) { //Y
			if (!w) w = ++cnt, prod[w][0] = prod[w][1] = 1; 
			prod[w][t] = (LL)prod[w][t] * v % MOD;
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (p < mid) modify(ch[w][0], l, mid-1, p, v, t);
				else modify(ch[w][1], mid, r, p, v, t);
			}
		}
		void query(int w, int l, int r, int L, int R, int y1, int y2, bool t) { //X
			if (!w) return;
			if (L <= l && r <= R) query(prod[w][0], 1, n, y1, y2, t);
			else {
				int mid = l + r + 1 >> 1;
				if (L < mid) query(ch[w][0], l, mid-1, L, R, y1, y2, t);
				if (mid <= R) query(ch[w][1], mid, r, L, R, y1, y2, t);
			}
		}
		void query(int w, int l, int r, int L, int R, bool t) { //Y
			if (!w) return;
			if (L <= l && r <= R) AnsTmp = (LL)AnsTmp * prod[w][t] % MOD;
			else {
				int mid = l + r + 1 >> 1;
				if (L < mid) query(ch[w][0], l, mid-1, L, R, t);
				if (mid <= R) query(ch[w][1], mid, r, L, R, t);
			}
		}
}SGT;

inline int Pow(int w, int t) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%MOD)
		if (t&1) ret=(LL)ret*w%MOD;
	return ret;
}

int main() {
	n = read(); m = read();
	for (int i=1,l,r,len,ret;i<=m;i++) {
		if (read() == 1) {
			l = read(); r = read(); 
			len = Pow(r-l+1, MOD-2); ++tot;
			SGT.modify(l, r, (1 - (len * 2ll)) % MOD, 0);
			SGT.modify(l, r, (1 - (len * 4ll)) % MOD, 1);
		} else {
			l = read() - 1; r = read(); ret = 1;
			ret = (LL)ret * SGT.query(1, l, l, r - 1, 0) % MOD;
			ret = (LL)ret * SGT.query(l+1, r, r, n, 0) % MOD;
			ret = (LL)ret * SGT.query(1, l, r, n, 1) % MOD;
			ret = (ret + 1ll) * REV % MOD;
			if (!l&&(tot&1)) ret = (1 - ret) % MOD; 
			printf("%d\n",(ret+MOD)%MOD);
		}
	}
	return 0;
}

【BZOJ 3638】[CF172] k-Maximum Subsequence Sum

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3638
神犇题解Ⅰ:http://blog.csdn.net/werkeytom_ftd/article/details/50950623
神犇题解Ⅱ:http://hzwer.com/6715.html

解题报告

这题非常的妙啊!
但我还是点亮手动增广这个技能点 QwQ

考虑单次询问整个区间,我们建一个费用流的图就可以辣!
然后我们发现这个费用流的每次增广相当于区间取反+区间询问最大连续字段和
这个是线段树的经典问题,于是我们用线段树来模拟增广的过程就可以辣!

【BZOJ 3711】[PA2014] Druzyny

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3711
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/4654215.html
神犇题解Ⅱ:http://blog.csdn.net/u010600261/article/details/54917569

解题报告

去膜了题解,好神啊!
本题一个区间要同时受$c_i,d_i$的限制

于是我们先只考虑$d_i$的限制
那么对于某一个区间的右端点$i$来讲,设合法的左端点$\in [g_i,i)$
至于$g_i$怎么求?搞一个队列就可以了?或者二分也是可以的
另外还需要注意一点:$g_i$是单调递增的

现在我们再来考虑$c_i$的限制,我们使用分治来解决
在$solve(l,r)$的时候,我们找出$c_i$最大的那个点$k$,然后递归下去
在合并上来的时候,我们就只需要考虑$[l,k-1]$对于$[k,r]$的贡献了
更进一步:因为$c_k$是$[l,r]$中最大的那个,所以对于此时所有的转移,$c_i$的限制均只需要考虑$c_k$
那么此时对于$i \in [k,r]$来讲,其合法的左端点$j \in [max(l,g_i),min(k-1,i-c_k)]$
因为$g_i$单调递增,所以我们对于$[k,r]$从左到右分四段考虑:

  1. $g_i \le l$且$i-c_k \le k-1$
    我们的首先我们肯定可以使用线段树来更新
    但更进一步,对于这一类点,我们只需要在查询第一个点时使用线段树就可以了
    因为这是一个前缀,之后$i$每向右移一位,合法的$j$也最多增加$1$
    不难发现,总的暴力操作次数不大于左右区间中较小的一段
    时间复杂度:$O(\log + \min(r-k+1,k-l))$
  2. $g_i \le l$且$k-1 < i-c_k$
    对于这些点,我们查询的是整个左区间
    我们整体查一次,然后一起更新就可以了
    时间复杂度:$O(\log n)$
  3. $l < g_i < k$
    对于这些点,我们查询的是左区间的一个后缀,我们直接在线段树上查就好
    考虑所有会影响到$i$的$solve$,它们的左区间一定没有交集
    也就是说只会有一个$solve$的左区间包含$g_i$
    于是对于每一个$i$,在整个算法中只会被查询一次
    所以这部分复杂度是$O(n \log n)$的,且不需要考虑到分治的复杂度中去
  4. $g_i \le k$
    直接不管就好

现在我们来分析分治的复杂度:$T(a+b)=T(a)+T(b)+min(a,b)+\log n$
我们发现这和启发式合并一样,于是复杂度是$O(n \log n)$的
在算上第三类更新的复杂度,总时间复杂度仍然为$O(n \log n)$

值得一提的是,这种与最值相关的问题使用分治来解决已经多次出现
比如HDU 5575,一定要引起重视啊

【BZOJ 4771】七彩树

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4771
数据生成器:http://paste.ubuntu.com/24181811/
神犇题解:https://blog.sengxian.com/solutions/bzoj-4771

解题报告

这题sengxian又写了题解了,我又不想写了…..
不过,还是XJB说一说吧!题还是很好的

就是搞两类线段树,两类线段树都支持合并
其中一类线段树,下标是颜色的编号,叶子结点记录的是该种颜色的最浅深度,这个是用来更新第二类线段树的
另一类线段树的下标是深度,结点记录的是区间和,这个是用来回答询问的
我们先把第二类线段树给Merge起来,不过我们发现同一种颜色可能会算重
不过我们也可以发现,再Merge第一类线段树的时候,如果叶子结点重了
那么在第一类线段树里减掉深度较深的那个点之后,答案就没有问题了

另外的话,因为这题强制在线
于是我们还需要把第一类线段树给可持久化
总的时间复杂度:$O(n \log n)$

Code

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

const int N = 200009;
const int M = 1e7;

int n,m,head[N],to[N],nxt[N],dep[N],col[N],fa[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 Segment_Tree_Sum{
	int cnt,AnsTmp,root[N],ch[M][2],sum[M]; 
	public:
		inline void modify(int w, int p, int delta) {
			modify(root[w], 1, n, p, delta); 
		}
		inline void merge(int a, int b) {
			root[a] = Merge(root[a], root[b]); 
		}
		inline int query(int w, int d) {
			AnsTmp = 0;
			query(root[w], 1, n, 1, d);
			return AnsTmp;
		}
		inline void init() {
			memset(root,0,sizeof(int)*(n+5));
			memset(ch,0,sizeof(int)*(cnt+5)*2);
			memset(sum,0,sizeof(int)*(cnt+5));
			cnt = 0;
		}
	private:
		void modify(int &w, int l, int r, int p, int delta) {
			w = cpy(w); sum[w] += delta;
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (p < mid) modify(ch[w][0], l, mid-1, p, delta);
				else modify(ch[w][1], mid, r, p, delta);
			}
		}
		int Merge(int a, int b) {
			a = a? cpy(a): 0; b = b? cpy(b): 0; 
			if (!b || !a) return a + b;
			else {
				if (ch[a][0] || ch[a][1]) {
					ch[a][0] = Merge(ch[a][0], ch[b][0]);
					ch[a][1] = Merge(ch[a][1], ch[b][1]);
				}
				return sum[a] += sum[b], a;
			}
		}
		void query(int w, int l, int r, int L, int R) {
			if (L <= l && r <= R) AnsTmp += sum[w];
			else {
				int mid = l + r + 1 >> 1;
				if (L < mid) query(ch[w][0], l, mid-1, L, R);
				if (mid <= R) query(ch[w][1], mid, r, L, R);
			}
		}
		inline int cpy(int b) {
			memcpy(ch[++cnt], ch[b], 8);
			sum[cnt] = sum[b]; return cnt;
		}	
}STS;

class Segment_Tree_Col{
	int cnt,root[N],ch[M][2],mn[M];
	public:
		inline void insert(int w, int c) {
			insert(root[w], 1, n, c, dep[w]);
			STS.modify(w, dep[w], 1);
		}
		inline void merge(int a, int b) {
			STS.merge(a, b);
			root[a] = merge(root[a], root[b], a);
		}
		inline void init() {
			memset(root,0,sizeof(int)*(n+5));
			memset(ch,0,sizeof(int)*(cnt+5)*2);
			memset(mn,0,sizeof(int)*(cnt+5));
			cnt = 0;
		}
	private:
		void insert(int &w, int l, int r, int p, int v) {
			if (!w) w = ++cnt; if (l == r) mn[w] = v;
			else {
				int mid = l + r + 1 >> 1;
				if (p < mid) insert(ch[w][0], l, mid-1, p, v);
				else insert(ch[w][1], mid, r, p, v);
			}	
		}
		int merge(int a, int b, int w) {
			if (!a || !b) return a + b;
			else if (ch[a][0] || ch[a][1]) {
				ch[a][0] = merge(ch[a][0], ch[b][0], w);
				ch[a][1] = merge(ch[a][1], ch[b][1], w);
			} else {
				STS.modify(w, max(mn[a], mn[b]), -1);
				mn[a] = min(mn[a], mn[b]);
			} return a;
		}
}STC;

int main() {
	for (int T=read();T;T--) {
		n = read(); m = read();
		STS.init(); STC.init(); dep[1] = 1;
		for (int i=1;i<=n;i++) col[i] = read();
		for (int i=2;i<=n;i++) dep[i] = dep[fa[i]=read()] + 1;
		for (int i=1;i<=n;i++) STC.insert(i, col[i]); 
		for (int i=n;i>1;i--) STC.merge(fa[i], i);
		for (int i=1,x,d,last=0;i<=m;i++) {
			x = read() ^ last; d = read() ^ last;
			printf("%d\n",last=STS.query(x, dep[x]+d));
		} 
	}
	return 0;
}

—————————— UPD 2017.4.11 ——————————
似乎Clairs之前出过这个题了…….
http://www.cnblogs.com/clrs97/p/5538804.html

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

【日常小测】最大值

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/03/5894746723453.png

解题报告

最开始题意看错了,花了一个小时写了一个虚树+主席树,写完之后发现过不了样例 QwQ
正解的话,我们搞一发线段树合就可以了
算是一个比较好玩的线段树合并的模板题吧!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100009;
const int M = N * 30;
 
int n,tot,head[N],nxt[N],to[N],cost[N],vout[N];
int fa[N][20],dis[N],dep[N],val[N],HASH[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 Segment_Tree{
    int root[N],cnt;
    struct Node{int ch[2],lca,sz,id; LL ans,sum;}p[M];
    public:
        inline void insert(int v, int w) {
            insert(root[w], 1, n, v, w);
        }
        inline void Merge(int a, int b) {
            root[a] = merge(root[a], root[b]);
        }
        inline int query(int w) {
            return p[root[w]].id;
        }
        inline Segment_Tree() {
            p[0].ans = -1;
        }
    private:
        void insert(int &w, int l, int r, int pos, int lca) {
            if (w=++cnt, l==r) {
                p[w].lca = lca; p[w].sz = 1; 
            } else {
                int mid = l + r + 1 >> 1;
                if (pos < mid) insert(p[w].ch[0], l, mid-1, pos, lca);
                else insert(p[w].ch[1], mid, r, pos, lca);
            } p[w].id = pos; p[w].ans = 0;
        }
        int merge(int a, int b) {
            if (!a || !b) return a + b;
            if (p[a].ch[0] || p[a].ch[1]) {
                p[a].ch[0] = merge(p[a].ch[0], p[b].ch[0]);
                p[a].ch[1] = merge(p[a].ch[1], p[b].ch[1]);
                int ls = p[a].ch[0], rs = p[a].ch[1]; 
                if (p[ls].ans >= p[rs].ans) p[a].ans = p[ls].ans, p[a].id = p[ls].id;
                else p[a].ans = p[rs].ans, p[a].id = p[rs].id;
            } else {
                int lca = LCA(p[a].lca, p[b].lca);
                LL delta = (dis[p[a].lca] + dis[p[b].lca] - dis[lca] * 2ll) * p[a].sz * p[b].sz;
                delta += p[a].sum * p[b].sz + p[b].sum * p[a].sz;
                p[a].ans = p[a].ans + p[b].ans + delta;
                p[a].sum = p[a].sum + ((LL)dis[p[a].lca] - dis[lca]) * p[a].sz ;
                p[a].sum += p[b].sum + ((LL)dis[p[b].lca] - dis[lca]) * p[b].sz;
                p[a].sz += p[b].sz; p[a].lca = lca;
            } return a;
        }
        inline int LCA(int u, int v) {
            if (dep[u] < dep[v]) swap(u, v);
            for (int i=19;~i;i--) if (dep[fa[u][i]]>=dep[v]) u=fa[u][i];
            if (u == v) return u;
            for (int i=19;~i;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
            return fa[u][0];
        }
}SGT;
 
inline void AddEdge(int u, int v, int c) {
    static int E = 1; cost[E+1] = cost[E+2] = c;
    to[++E] = v; nxt[E] = head[u]; head[u] = E; 
    to[++E] = u; nxt[E] = head[v]; head[v] = E; 
}
 
void DFS(int w, int f) {
    dep[w] = dep[f] + 1; fa[w][0] = f;
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            dis[to[i]] = dis[w] + cost[i];
            DFS(to[i], w);
        }
    } 
}
 
void solve(int w, int f) {
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            solve(to[i], w);
            SGT.Merge(w, to[i]);
        }
    } vout[w] = SGT.query(w);
}
 
int main() {
    n = read();
    for (int i=1,u,v;i<n;i++) {
        u = read(); v = read();
        AddEdge(u, v, read());
    }
    for (int i=1;i<=n;i++) HASH[i] = val[i] = read();
    sort(HASH+1, HASH+1+n);
    tot = unique(HASH+1, HASH+1+n) - HASH - 1;
    for (int i=1;i<=n;i++) val[i] = lower_bound(HASH+1, HASH+1+tot, val[i]) - HASH;
    for (int i=1;i<=n;i++) SGT.insert(val[i], i);
    DFS(1, 1);
    for (int j=1;j<=19;j++) for (int i=1;i<=n;i++) 
        fa[i][j] = fa[fa[i][j-1]][j-1];
    solve(1, 1);
    for (int i=1;i<=n;i++) printf("%d\n",HASH[vout[i]]);
    return 0;
}

【BZOJ 3307】雨天的尾巴

相关链接

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

解题报告

这题,搬到序列上大家都会啊
就是先把操作打成tag,扔到序列上
然后用线段树扫一遍,统计答案即可

当然线段树合并也很好写啊
也是先搞成tag,然后合并上去,顺便记录一下答案
时间复杂度:$O(n \log n)$

Code

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

const int N = 100009;
const int M = N << 1;
const int G = 7000000;
const int INF = 1e9;

int n,m,dep[N],ans[N],fa[N][20];
int head[N],to[M],nxt[M];

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

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

void DFS(int w, int f) {
	fa[w][0] = f; dep[w] = dep[f] + 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
		}
	}
}

inline int LCA(int u, int v) {
	if (dep[u]<dep[v]) swap(u, v);
	for (int j=19;~j;j--) if (dep[fa[u][j]]>=dep[v]) u = fa[u][j];
	if (u == v) return u;
	for (int j=19;~j;j--) if (fa[u][j]!=fa[v][j]) u=fa[u][j],v=fa[v][j];
	return fa[u][0];
}

class Segment_Tree{
	int cnt,ch[G][2],mx[G],id[G],root[N];
	public:
		inline void merge(int x, int y) {
			root[x] = Merge(root[x], root[y]);
		}
		inline void insert(int w, int p, int t) {
			insert(root[w], 1, INF, p, t);
		}
		inline int query(int w) {
			return mx[root[w]]? id[root[w]]: 0;
		}
	private:
		int Merge(int x, int y) {
			if (!x || !y) return x + y;
			if (!ch[x][0] && !ch[x][1]) {
				mx[x] += mx[y];
				return x;
			} else {
				ch[x][0] = Merge(ch[x][0], ch[y][0]);
				ch[x][1] = Merge(ch[x][1], ch[y][1]);
				if (mx[ch[x][0]] >= mx[ch[x][1]]) id[x] = id[ch[x][0]], mx[x] = mx[ch[x][0]];
				else id[x] = id[ch[x][1]], mx[x] = mx[ch[x][1]];
				return x;
			}
		}
		void insert(int &w, int l, int r, int p, int delta) {
			if (!w) w = ++cnt; 
			if (l == r) {
				mx[w] += delta; id[w] = l;
			} else {
				int mid = l + r + 1 >> 1;
				if (p < mid) insert(ch[w][0], l, mid-1, p, delta);
				else insert(ch[w][1], mid, r, p, delta);
				if (mx[ch[w][0]] >= mx[ch[w][1]]) id[w] = id[ch[w][0]], mx[w] = mx[ch[w][0]];
				else id[w] = id[ch[w][1]], mx[w] = mx[ch[w][1]];
			}
		}
}ST;

void solve(int w, int f) {
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			solve(to[i], w);
			ST.merge(w, to[i]);
		}
	}
	ans[w] = ST.query(w);
}

int main() {
	n = read(); m = read();
	for (int i=1;i<n;i++) AddEdge(read(), read());
	DFS(1, 1);
	for (int j=1;j<20;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
		}
	}
	for (int i=1,u,v,lca,c;i<=m;i++) {
		u = read(); v = read(); c = read();
		lca = LCA(u, v);
		ST.insert(u, c, 1);
		ST.insert(v, c, 1);
		ST.insert(lca, c, -1);
		if (lca-1) ST.insert(fa[lca][0], c, -1);		
	}
	solve(1, 1);
	for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}

【日常小测】市场

相关链接

题目传送门:https://ly.men.ci/problem/196

题目大意

搞一个数据结构来维护一个长度为$n(n \le 10^5)$的序列。
并进行$m(m \le 10^5)$个操作,操作分为以下四种:

  1. 区间加$c(-10^4 \le c \le 10^4)$
  2. 区间除$d$。即对于单个元素$a_i$,除以$d$后变为$\lfloor \frac{a_i}{d} \rfloor$
  3. 询问区间和
  4. 询问区间最值

解题报告

考虑将所有的相邻的并且值相同的位置合成一个块
考虑一次修改操作最多增加两个块,于是总的块数不会超过$n+m$
那么对于操作二,我们暴力应用到区间的每一个块上
因为每一个块最多进行$\log val$次的操作二就会消失
所以总的操作次数不会超过$O ((n+m) \log (10^4))$

现在考虑具体实现
不嫌麻烦的话,我们可以使用$Splay$。脑袋里想想还是很好写的
要好写一点的话,我们就用线段树,记录一下一个点的子树中所有的值是否相等

相关拓展

这种将相同值合并到一起来保证复杂度的题目还在雅礼集训的时候见过一次啊
当时是要求将编号$l \to r$的结点的父亲全部设为$x$,然后单点修改权值,查询某个点的子树和
也是将$fa$相同的点搞在一起,然后用$Splay$维护一下

【Codeforces 781E】Andryusha and Nervous Barriers

相关链接

题目传送门:http://codeforces.com/contest/781/problem/E
代码参考:http://codeforces.com/contest/781/submission/25269119

解题报告

这题我们先考虑没有墙会害怕的版本
这样的话,我们想象一下是墙冲向一排点
于是搞一个线段树支持区间赋值,区间查询就可以了!

现在考虑加上害怕的限制
那我们可以用二维线段树!
但好难写QwQ ←这货写到一半就弃坑了

于是就去看别人的代码
然后看到了毛爷爷的代码 (毛爷爷这场暴跌 默哀 _(:з」∠)_
然后发现这题又可以暴力………

我们考虑将每一次分开的点打成一包
算上最开始的,不难发现总共只有$O(w+2n)$个包
那每一个包我们插到线段树中,此时总包数是$O((w+2n) \log (w+2n))$的
那么每一次查询我们就暴力每一个节点,于是均摊的复杂度仍然是$O(\log n)$的
代码好写还跑得飞快!

这种有一点暴力思想的数据结构题,我还真的是一点想不出来啊!
比如BZOJ 4712,真的是一点都没往那边想啊!
我一定要在科技树上点亮这个技能!

Code

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

const int N = 5000000;
const int M = 200009;
const int MOD = 1000000007;

int hit,wid,n,cnt;
struct Pack{int h,sum,del;}p[N];
struct Wall{int h,l,r,s;}wall[M];

class Segment_Tree{
	int ans_tmp,tot,root,ch[M][2];
	stack<int> s[M];
	public:
		inline void insert(int p, int id) {
			insert(root, 1, wid, p, id);
		}
		inline int query(int h, int l, int r) {
			ans_tmp = 0; 
			query(root, 1, wid, l, r, h);
			return ans_tmp;
		}
	private:
		void insert(int &w, int l, int r, int p, int v) {
			if (!w) w = ++tot; s[w].push(v);
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (p < mid) insert(ch[w][0], l, mid-1, p, v);
				else insert(ch[w][1], mid, r, p, v);
			}
		}
		void query(int w, int l, int r, int L, int R, int h) {
			if (L <= l && r <= R) {
				while (!s[w].empty() && p[s[w].top()].h <= h) {
					if (!p[s[w].top()].del) {
						p[s[w].top()].del = 1;
						(ans_tmp += p[s[w].top()].sum) %= MOD;	
					} s[w].pop();
				}
			} else {
				int mid = l + r + 1 >> 1;
				if (L < mid) query(ch[w][0], l, mid-1, L, R, h);
				if (mid <= R) query(ch[w][1], mid, r, L, R, h);
			}
		}
}SGT;

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

int main() {
	hit = read(); wid = read(); n = read();
	for (int i=1;i<=n;i++) {
		wall[i].h = read();
		wall[i].l = read();
		wall[i].r = read();
		wall[i].s = read();
	}
	for (int i=1;i<=wid;i++) {
		p[++cnt].h = hit + 1;
		p[cnt].sum = 1;
		SGT.insert(i, cnt); 
	} 
	sort(wall+1, wall+1+n, [](const Wall &A, const Wall &B){return A.h > B.h;});
	for (int i=1,h_mx,tmp;i<=n;i++) { 
		tmp = SGT.query(wall[i].h + wall[i].s, wall[i].l, wall[i].r);
		p[++cnt].sum = tmp; p[cnt].h = wall[i].h;
		p[++cnt].sum = tmp; p[cnt].h = wall[i].h;
		if (wall[i].l == 1) SGT.insert(wall[i].r+1, cnt-1);
		else SGT.insert(wall[i].l-1, cnt-1);
		if (wall[i].r == wid) SGT.insert(wall[i].l-1, cnt);
		else SGT.insert(wall[i].r+1, cnt);
	}
	int vout = 0;
	for (int i=1;i<=cnt;i++) 
		(vout += (p[i].del ^ 1) * p[i].sum) %= MOD;
	printf("%d\n",vout);
	return 0;
}

【BZOJ 4373】算术天才⑨与等差数列

相关链接

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

解题报告

首先,假如一个区间满足以下三个条件那么该区间一定合法:

$\%k$后相等
每一个数互不相同
区间和等于某一特定值

后两个条件都可以用线段树维护
问题就是第一个条件非常麻烦

先来考虑一种简单的Hash方式:记录区间的平方和
这样的话,我们可以$O(1)$计算基准值,$O(\log n)$判断是否等于基准值

但众所周知,Hash是不优雅的
于是我们可以先做一个差分序列,然后维护差分序列相邻两项的$\gcd$
考虑如果所有数的差都是$k$的整数倍,那么这些数$ \bmod \ k$之后肯定就相等啦!

另外的话,区间GCD配合差分的题,也不是第一次见了
之前NOI还考过一道:魔幻棋盘
以后和GCD相关的题目要想一想差分行不行啊!

【BZOJ 4345】[POI2016] Korale

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4345
神犇题解:http://sr16.com:8081/【bzoj4345】【poi2016】korale/

解题报告

这题看到$k$这么玄学,那就一定是与$k$相关辣!
想一想可不可以用线段树合并做。或者可持久化Treap?
然而似乎都不好做。

我们考虑暴搜的搜索树,如果我们使用$BFS$加上小根堆,显然没有问题
于是我们定义二元组$(i,j)$表示当前集合的权值为$i$,最大的元素编号为$j$
类比搜索树,则转移为 $(i,j) \Rightarrow (i + a[j + 1],j + 1)\& (i + a[j + 1] – a[j],j + 1)$
于是我们就可以求出第$k$小的值$ans$了!

然后我们再来考虑如何输出方案:我们暴搜方案,将结果$>ans$的直接剪掉就可以啦!
考虑这样复杂度为什么是对的,因为 $ \le ans$ 的方案数不会超过$k$个啊!

—————————— UPD 2017.3.22 ——————————
今天考试考了这个题,然后wuvin说直接那k短路来做也是对的
想一想正确性确实很对,不过似乎会炸内存?

【BZOJ 2877】[NOI2012] 魔幻棋盘

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2877
神犇题解Ⅰ:http://www.cnblogs.com/Randolph87/p/3795729.html
神犇题解Ⅱ:https://blog.sengxian.com/solutions/bzoj-2877

解题报告

首先这货需要有一个结论: $\gcd ({a_1},{a_2}, \cdots ,{a_n}) = \gcd ({a_i}, {a_1} – {a_2},{a_2} – {a_3}, \cdots ,{a_{n – 1}} – {a_n})$
证明的话,想一想辗转相除法就可以啦!
酱紫的话,一维情况我们维护一个差分就可以啦!

现在考虑二维的情况,每一维直接用线段树肯定是不可取的
于是我们考虑答案的表达式: $\gcd (gcd({a_{i,j}},{a_{l,j}} – {a_{l + 1,j}}, \cdots ,{a_{r – 1,j}} – {a_{r,j}}), \cdots ,gcd({a_{i,k}},{a_{l,k}} – {a_{l + 1,k}}, \cdots ,{a_{r – 1,k}} – {a_{r,k}}))$
将每一个 $gcd()$ 的第一项全部提出来,就是 ${\rm{gcd}}({a_{l,j}}, \cdots ,{a_{l,k}})$
这个只有一维,可以用上文提到的情况来解决
剩下的部分每一次修改还是会改到 $O(n)$ 个点
这样是不优雅的,于是考虑在第二维也差分一次的话
那么每一次需要修改的点就只有4个了
于是就可以用二维线段树维护啦!

【BZOJ 4662】Snow

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4662
神犇题解:http://www.cnblogs.com/ccz181078/p/6291464.html

解题报告

想了两个小时没有想出来
一看题解,居然是姿势优雅的暴力

考虑最开始的区间一定是长这样的

删掉正中间的那个区间之后就变成了这样

发现蓝色框住的区间右端点相同了,绿色框住的区间左端点相同了!
于是两个椭圆框住的区间以后就可以进行区间维护了,不用再一个一个改
复杂度的话,因为暴力修改会进行 $ O(n)$ 次,所以单次修改操作的均摊复杂度为 $ O(\log n)$

具体实现上的话,用线段树支持区间操作
再用一个并查集搞一搞,右端点/左端点相同了就并一起
修改就暴力再并查集上爬一爬就好啦!