【BZOJ 4212】神牛的养成计划

相关链接

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

解题报告

这题如果没有强制在线,那么我们可以用$Trie + bitset$在$O(\frac{2000000n}{64})$的时间复杂度过
如果强制在线并且$s1,s2$等长,那么我们可以在$O(2000000 \log 2000000)$的时间复杂度过

现在解决原问题,先考虑一个暴力:
先把前缀能匹配上的串找出来,然后我们在其中找出后缀能匹配的串
考虑一下后缀数组:按字典序排序后,前缀能匹配上的一定是一个区间
于是我们可以先建一个正串的$Trie$,用来找出前缀合法的字符串区间
然后我们将反串建成一个持久化$Trie$,每一次用前缀合法的区间再去查后缀即可

另外还有一点$Trick$就是字符串排序:我们可以先将正串建成$Trie$,然后贪心$DFS$
这样排序的复杂度就可以是线性的,总的时间复杂度也就是线性的了

Code

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

const int N = 2000009;
const int M = 2009;
const int SGZ = 26;

int n,m,tot,beg[M],sz[M],ord[M];
char s1[N];

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 Trie{
	int cnt,ch[N][26],mn[N],mx[N];
	vector<int> id[N];
	public:
		inline void insert(char *s, int len, int ID) {
			int w = 0;
			for (int i=0;i<len;i++) {
				int c = s[i] - 'a';
				if (!ch[w]) ch[w] = ++cnt;
				w = ch[w];
			} 
			id[w].push_back(ID);
		}
		inline void sort(int w, int *arr, int &cur) {
			for (int i=0;i<id[w].size();i++) {
				arr[++cur] = id[w][i];
			}
			for (int i=0;i<SGZ;i++) {
				if (ch[w][i]) {
					sort(ch[w][i], arr, cur);
				}
			}
		}
		inline void mark(int val, char *s, int len) {
			int w = 0;
			for (int i=0;i<len;i++) {
				int c = s[i] - 'a';
				w = ch[w];
				if (!mn[w] || mn[w] > val) mn[w] = val;
				if (!mx[w] || mx[w] < val) mx[w] = val;
			}
		}
		inline void query(char *s, int len, int &l, int &r) {
			int w = 0;
			for (int i=0;i<len;i++) {
				int c = s[i] - 'a';
				if (!ch[w]) {
					l = 1; r = 0;
					return;
				} else {
					w = ch[w];
				}
			}
			l = mn[w]; 
			r = mx[w]; 
		}
	private:
}trie; 

class Persistent_Trie{
	int cnt,root[M],sum[N],ch[N][26];
	public:
		inline void insert(int p, int w, char *s, int len) {
			Insert(root[p], root[w], s, len); 
		}
		inline int query(int l, int r, char *s, int len) {
			if (l > r) return 0;
			int ret = 0, w = root[r]; 
			for (int i=0;i<len;i++) {
				w = ch[w][s[i]-'a']; 
			}
			ret += sum[w];
			w = root[l-1];
			for (int i=0;i<len;i++) {
				w = ch[w][s[i]-'a'];
			}
			ret -= sum[w];
			return ret;
		}
	private:
		void Insert(int p, int &w, char *s, int len) {
			w = ++cnt;
			sum[w] = sum[p] + 1;
			memcpy(ch[w], ch[p], sizeof(ch[w]));
			if (len <= 0) return;
			int c = s[len-1] - 'a'; 
			Insert(ch[p], ch[w], s, len - 1);
		}
}PTE; 

int main() {
	n = read();
	for (int i=1,last=0;i<=n;i++) {
		beg[i] = last;
		scanf("%s", s1+last);
		sz[i] = strlen(s1+last);
		trie.insert(s1+last, sz[i], i);
		last += sz[i];
	}
	tot = 0;
	trie.sort(0, ord, tot);
	for (int i=1;i<=n;i++) {
		trie.mark(i, s1+beg[ord[i]], sz[ord[i]]);
		PTE.insert(i-1, i, s1+beg[ord[i]], sz[ord[i]]);
	}
	m = read(); 
	for (int tt=1,last=0,l,r;tt<=m;tt++) {
		scanf("%s",s1);
		int len = strlen(s1);
		for (int i=0;i<len;i++) {
			s1[i] = (s1[i] - 'a' + last) % SGZ + 'a';
		} 
		trie.query(s1, len, l, r);
		scanf("%s",s1);
		len = strlen(s1);
		for (int i=0,j=len-1;i<j;i++,j--) {
			swap(s1[i], s1[j]);
		}
		for (int i=0;i<len;i++) {
			s1[i] = (s1[i] - 'a' + last) % SGZ + 'a';
		}
		last = PTE.query(l, r, s1, len);
		printf("%d\n",last);
	}
	return 0;
}

【BZOJ 3514】Codechef MARCH14 GERALD07加强版

相关链接

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

解题报告

这是LCT的经典应用,我们把每条边的权值设为它的编号
然后用LCT动态维护最大生成树
同时记录第$i$条边加入时取代的那一条边的编号$a_i$

对于询问,我们发现对于询问$[l,r]$
只有$a_i < l$的边才会使连通块的大小减少$1$
于是问题变为询问一个区间内小于某个数的个数
这是又是函数式线段树的经典应用

于是这题用LCT和函数式线段树就可以解决
时间复杂度:$O(n \log n)$

相关拓展

这题还可以很方便地将问题改为删掉$[l,r]$的边之后连通块的个数
这个我们将序列倍长,然后直接转化为原问题

【BZOJ 3551】[ONTAK2010] Peaks加强版

相关链接

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

解题报告

这题强制在线,所以不能直接上启发式合并
或者强行可持久化也可以?
不过我们有更加优美的东西:Kruskal重构树

就是按照边权排序,然后做Kruskal
如果需要加边,那么我们新建一个结点,权值设为这条边的权值
然后把原来的两个点连到这个点下面当儿子
于是任意两点之间的最大边权就是他们的LCA的权值了

对于原题来讲,我们可以先倍增到最浅的可以到达的祖先
那么这个祖先的子树就是可以到达的所有点了
考虑DFS序,问题变为区间k大,这是主席树的经典应用
于是这题就做完啦!

今天上午考试考了一道类似的题目,然而忘了这个做法
是用的线段树合并+标记永久化,虽然能A但显然不如这个优雅

【日常小测】资源采集

题目大意

给定一棵$n(n \le 52501)$个点的树,初始状态下,每一结点存储的能量为$0$
树上每一个点有两个属性$v_i,l_i$分别表示这个点每单位时间产生的能量,和这个点的存储能量的上限
再给定$q(q\le52501)$个操作,每个操作有三个属性$w_i,d_i,t_i$,表示
在$t_i$的时刻,遍历在$w_i$的子树中且与$w_i$距离不超过$d_i$的点,并收集这些点的能量
一个点的能量被收集后就会清空,询问每次操作能够收集到多少能量

解题报告

先来说一说链上的情况,我们定义$last_i$为$i$号点上一次被收集的时间
我们可以把相邻的且$last_i$相同的点合并在一起,然后询问的时候用函数式线段树来回答
如果还有什么问题的话,我们可以戳这个题:市场

现在考虑树上的情况,我们先搞出DFS序,将其作为一个点的横坐标
然后我们把深度作为这个点的纵坐标,然后把这个点扔到平面上
这样单次操作就是对于一个平面上的矩形进行操作
这个是经典的$Kd-Tree$的应用,可以做到单次操作只影响到$\sqrt{n}$个结点
于是将$Kd-Tree$子树中$last_i$相同的点合在一起,打一个标记
单次操作最多增加$\sqrt n$个标记,而每一次在$Kd-Tree$上走一次就会回收一个标记
于是总的操作次数为$q\sqrt n$的
当然我们也需要用平衡树的启发式合并,或者函数式线段树来支持询问
于是总的时间复杂度为:$O(q \sqrt n \log n)$

不过众所周知,这题的暴力是$O(nq)$的
所以非递归的暴力跑得飞快,两秒的题目暴力可以卡到一秒以内
所以考完改题的时候,所有改了的人都是用的暴力……

【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

【日常小测】String

题目大意

先给定一个长度为$n(n \le 50000)$的字符串$S$
之后给定$m(m \le 50000)$个操作(强制在线),操作分两种

  1. 在字符串$S$末尾加入一个字符
  2. 将$S$的子串$[l,r]$取出来,设为字符串$T$,询问$T$中出现至少两次的字符串的最长长度

解题报告

我们考虑用一棵线段树来支持插入斜率为$-1$的线段,并询问区间最值
这个是用来维护答案的,至于为什么插入的是线段,待会儿再说
至于具体实现,因为斜率相同,所以我们只需要将直线的纵截距插入即可,换言之我们只需要支持区间取$\max$即可

现在假设我们已经在维护了$[1,r-1]$的答案,并且我们在维护$[1,r]$回答所有右端点为$r$的询问
考虑插入第$r$个字符会影响哪些部分的答案:显然只会影响$fail$链上的答案
我们记录$last_x$表示$SAM$上的结点x代表的串在$S$中出现的最后一次的时间
我们注意到一条$fail$链上$last_x$一定是相等的,所以我们只需要考虑最长长度$l$
于是我们需要在线段树的$[last_x-l+1,last_x]$区间插入$x+y-(last_x+1)=0$的直线
之后我们更新$fail$链上的$last_x$,至于询问我们只需要到线段树上查询区间最值
当然维护$fail$树的话,我们需要使用$LCT$。

注意到$LCT$的一个$splay$里的$last_x$相等,所以单次$access$只会贡献$\log n$次区间取$\max$操作
所以我们已经能在$O(n \log ^2 n)$的时间复杂度内解决离线版本了
现在考虑在线版本,我们将线段树可持久化即可

【BZOJ 4538】[HNOI2016] 网络

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4538
神犇题解:http://krydom.com/bzoj4538/

解题报告

这题我先说一种怪怪的做法 QwQ
考虑使用主席树,第一维是权值(用BIT搞成后缀和),第二维是DFS序
这样的话,对于询问我们可以在第一维的权值上进行二分
对于每一次二分 $ a$ ,我们可以通过判断覆盖该点的区间个数是否等于所有不小于 $ a$ 的区间个数是否相等

这样话,原问题转化为:在主席树上的区间加减问题
这一块的时空复杂度是 $ O(n{\log ^3}n)$ 的
然后考虑上二分的 $ log$ 这样的话,复杂度就是 $ O(n{\log ^4}n)$ 的
这种做法是自己YY的,感觉很有道理的样子
然而懒得写代码了,也不知道对不对

另外的话,再说一说正解吧!
考虑一条路径,说白了就是查询路径上的点的时候不查到该路径
查询非该路径上的点的时候查询到该路径
这时考虑树链剖分的话,该路径对应的 $ {log(n)}$ 个区间应该忽略,其他部分添加上这个路径的信息
因为是一整块区间抠掉 $ {log(n)}$ 个区间,所以剩余部分也只会有 $ {log(n)}$ 个区间
于是树链剖分暴力搞一搞就可以辣!
时空复杂度比之前的做法应该要稍微优越一点

【UOJ 77】A+B Problem

相关链接

题目传送门:http://uoj.ac/problem/77
神犇题解:http://www.cnblogs.com/geng4512/p/5296863.html

解题报告

我们发现如果忽略\(1<j<i\)这个限制,再假设\({l_i} = {r_i}\)
这样的话,直接上最小割就好

现在考虑\({l_i} < {r_i}\)
这样的话,用线段树优化建图就可以啦!

再考虑\(1<j<i\)这个限制
这样的话,用函数式线段树就可以啦!

感觉是VFK强行套数据结构啊!
另外还有BZOJ 3218可以双倍经验!
话说BZOJ上那些\(200ms+\)的神犇都是用的什么算法啊?
怎么这么快啊!

Code

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

const int N = 200000+9;
const int M = 2000000;
const int INF = 1000000000;

int n,m,S,T,vout,head[N],nxt[M],to[M],flow[M];
int tot,_hash[N],A[N],W[N],B[N],LL[N],RR[N],P[N];

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

inline void Add_Edge(int u, int v, int f = INF, int t = 0) {
	static int E = 1; vout += f * t;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

class Network_Flow{
    int cur[N],dis[N];
    queue<int> que;
    public:
        inline int MaxFlow() {
            int ret = 0;
            while (BFS()) {
                memcpy(cur, head, sizeof(head));
                ret += DFS(S, INF);
            }   
            return ret;
        }
    private:
        inline bool BFS() {
            memset(dis,60,sizeof(dis));
            que.push(S); dis[S] = 0;
              
            while (!que.empty()) {
                int w = que.front(); que.pop();
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > INF && flow[i]) {
                        dis[to[i]] = dis[w] + 1;
                        que.push(to[i]);
                    }
                }
            }
            return dis[T] < INF;
        }
        int DFS(int w, int f) {
            if (w == T) return f;
            else {
                int ret = 0;
                for (int tmp,&i=cur[w];i;i=nxt[i]) {
                    if (dis[to[i]] == dis[w] + 1 && flow[i]) {
                        tmp = DFS(to[i], min(f, flow[i])); 
                        flow[i] -= tmp; flow[i^1] += tmp;
                        f -= tmp; ret += tmp;
                        if (!f) break;
                    }
                }
                return ret;
            }
        }
}Dinic;

namespace Persistent_Segment_Tree{
	#define PST Persistent_Segment_Tree
	int ch[N][2],root[N],cnt,pur,sur,L,R;
	
	void insert(int p, int &w, int l, int r, int f = 0) {
		if (w = ++cnt, p) {
			ch[w][0] = ch[p][0];
			ch[w][1] = ch[p][1];
			Add_Edge(p, w);
		} 
		if (f) Add_Edge(w, f);
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (pur < mid) insert(ch[p][0], ch[w][0], l, mid-1, w);
			else insert(ch[p][1], ch[w][1], mid, r, w);
		} else Add_Edge(sur, w);
	}
	
	inline void insert(int p, int v) {
		pur = v; sur = p;
		insert(root[p-1], root[p], 1, tot);
	}
	
	void modify(int w, int l, int r) {
		if (!w) return;
		else if (L <= l && r <= R) Add_Edge(w, pur);
		else {
			int mid = l + r + 1 >> 1;
			if (L < mid) modify(ch[w][0], l, mid-1);
			if (mid <= R) modify(ch[w][1], mid, r);
		}
	}
	
	inline void modify(int p, int node, int l, int r) {
		pur = node; L = l; R = r;
		modify(root[p], 1, tot);
	}
};

int main() {
	n = read(); PST::cnt = n << 1;
	S = 0; T = N - 1;
	for (int i=1;i<=n;i++) {
		_hash[++tot] = A[i] = read(); 
		B[i] = read();
		W[i] = read();
		_hash[++tot] = LL[i] = read();
		_hash[++tot] = RR[i] = read();
		P[i] = read();
	}
	sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=n;i++) {
		A[i] = lower_bound(_hash+1, _hash+1+tot, A[i]) - _hash;
		LL[i] = lower_bound(_hash+1, _hash+1+tot, LL[i]) - _hash;
		RR[i] = lower_bound(_hash+1, _hash+1+tot, RR[i]) - _hash;
	}
	for (int i=1,l,r;i<=n;i++) {
		PST::insert(i, A[i]);
		Add_Edge(i, T, B[i], 1);
		Add_Edge(S, i, W[i], 1);
		PST::modify(i-1, i+n, LL[i], RR[i]);
		Add_Edge(i+n, i, P[i]);
	}
	printf("%d\n",vout-Dinic.MaxFlow());
	return 0;
}

【CodeChef BTREE】Union on Tree

相关链接

题目传送门:https://www.codechef.com/problems/BTREE
数据生成器:http://paste.ubuntu.com/23671176/
中文题面:http://www.codechef.com/download/translated/OCT14/mandarin/BTREE.pdf
官方题解:https://discuss.codechef.com/questions/53273/btree-editorial
神犇题解Ⅰ:http://xllend3.is-programmer.com/posts/64760.html
神犇题解Ⅱ:https://stalker-blog.apphb.com/post/divide-and-conquer-on-trees-based-on-vertexes

WJMZBMR Orz

又是 青年计算机科学家陈立杰 出的神题!
真的是跪烂!_(:з」∠)_

解题报告

看一看数据范围就可以知道这题复杂度一定只跟 ∑士兵数 相关
于是考虑先把虚树建出来,那么剩下的问题就是在利用虚树的边来统计答案了

1)函数式线段树的做法

考虑k=1,这样的话不用处理重复的问题,于是直接点分治就可以做
但现在有很多的点,于是我们可以将树剖成很多块,每块中恰好又一个城市a有卫兵
更进一步,我们规定这个联通块中任意一个点i到a的距离不大于到其他任意有卫兵的城市的距离
于是我们如果能在每一个联通块中单独处理每一个卫兵的话,就可以不用考虑去重的问题了

我们再仔细观察一下建出来的虚树,发现每一个块就是虚树上的一部分
对于a所在联通块深度最小的那个点,统计一下、加到答案里去
对于a所在联通块的其余边缘节点,再统计一下、从答案中减去

于是剩下的就是如何具体如何统计一条边对于答案的贡献了
我们分两种情况考虑:

  1. v不是u在虚树中的祖先,统计v的子树中、到u的距离为d的点的个数
    这个的话,直接用函数式线段树查就好
  2. v是u的父亲,其余条件相同
    这样的话,似乎与v的距离就不固定了(lca在u ~ v中移动)
    于是先用点分治做出所有点到u的距离为d的点的个数n1
    然后需要减掉v子树外的部分,这样的话,发现到v的距离就固定了
    于是减掉所有点到v的距离为d-dis(u,v)的点数n2
    再加上v子树中到v距离为d-dis(u,v)的点数n3就可以辣!

2)直接用点分治的做法

先用把点分树搞出来,这样就可以O(log^2(n))的时间复杂度内求dis(w,d)
其中dis(w,d)的定义为 到点w距离在d以内的点有多少 (不会的同学可以先去做BZOJ_3730

再考虑把虚树建出来,这样的话唯一的问题就是如何去重了
考虑如果虚树上一条边的两个点的管辖范围没有交集,那么就肯定没有重复
如果有交集,那么设交集的重点为m,交集半径为r'那么直接减掉dis(m,r')就可以辣!

另外还需要预先将完全包含的管辖区间给修改成“相切”的情况,这样才能保证去重完整
还有的话,中点可能落在边上,于是可以在每边的中点加一个点

这样的做法是不是比主席树的做法清真了很多?
然而我还是写了5k+ _ (:з」∠) _
而且如果边带权的话,这题就很难这样做了

Code

最近为什么写啥常数都大到不行啊 QwQ
又是垫底…..

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

const int N = 100000 + 9;
const int M = N << 1;
const int INF = 1e8;

int n,m,T,head[N],to[M],nxt[M],num[N],cost[N];
int anc[N][18],dep[N],val[N],p[N];

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;
}
		
inline void Add_Edge(int u, int v) {
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

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

inline int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=17;~i;i--) 
		if (dep[anc[x][i]] >= dep[y]) 
			x = anc[x][i];
	if (x == y) return x;
	for (int i=17;~i;i--) {
		if (anc[x][i] != anc[y][i]) {
			x = anc[x][i];
			y = anc[y][i];
		}
	} 
	return anc[x][0];
}

inline int dis(int x, int y) {
	int lca = LCA(x, y);
	return dep[x] + dep[y] - dep[lca] * 2;
}

class Point_Based_Divide_and_Conquer{
	int fa[N][18],tot[N],sum[N];
	int ans_tmp,root,block_size;
	vector<int> q[N],mul[N];
	bool vis[N];
	
	public: 	
		inline void init() {
			block_size = n;
			ans_tmp = INF;
			Get_Root(1, 1);
			tot[root] = 1;
			build(root, n);	
		}
		
		inline int query(int w, int rag) {
			int ret = Query(w, rag, q);
			for (int i=1,t;i<tot[w];i++) {
				t = rag - dis(fa[w][i], w);
				if (t >= 0) {
					ret += Query(fa[w][i], t, q);
					ret -= Query(fa[w][i-1], t, mul);
				}
			}
			return ret;
		}
	private:
		void Get_Root(int w, int f) {
			int mx = 0; sum[w] = 1;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && !vis[to[i]]) {
					Get_Root(to[i], w);
					mx = max(mx, sum[to[i]]);
					sum[w] += sum[to[i]];
				}
			}
			mx = max(block_size - sum[w], mx);
			if (mx < ans_tmp) {
				ans_tmp = mx;
				root = w;
			}
		}
		
		void build(int w, int sz) {
			vis[w] = 1; fa[w][0] = w;
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]]) {
					block_size = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
					ans_tmp = INF; Get_Root(to[i], w);
					memcpy(fa[root]+1, fa[w], sizeof(fa[w])-sizeof(int));
					tot[root] = tot[w] + 1;
					build(root, block_size);
				}
			}
			
			if (val[w]) {
				for (int i=0;i<tot[w];i++) 
					q[fa[w][i]].push_back(dis(w, fa[w][i]));
				for (int i=0;i<tot[w]-1;i++)
					mul[fa[w][i]].push_back(dis(w, fa[w][i+1]));	
			}
			sort(q[w].begin(), q[w].end());
			sort(mul[w].begin(), mul[w].end());
		} 
		
		inline int Query(int w, int r, vector<int> *a) {
			return upper_bound(a[w].begin(), a[w].end(), r) - a[w].begin();
		}
}PDC; 

class Virtual_Tree{
	int stk[N],rag[N],top,lca,cnt,root;
	queue<int> que;
	bool inq[N];
	
	public:	
		inline void build(int &tot) {
			cnt = tot; T = 0;
			root = p[1] = read(); 
			newnode(p[1], read());
			for (int i=2;i<=tot;i++) {
				p[i] = read();
				newnode(p[i], read());
				root = LCA(root, p[i]);
			}
			static auto cmp = [](int a, int b) {return num[a] < num[b];};
			sort(p+1, p+1+tot, cmp);
			if (root != p[1]) p[++tot] = root, newnode(root, -1);
			stk[top=1] = root;
			for (int i=1+(p[1]==root);i<=cnt;i++) {
				lca = LCA(p[i], stk[top]);
				for (;dep[stk[top]] > dep[lca];top--) 
					if (dep[stk[top-1]] >= dep[lca]) AddEdge(stk[top-1], stk[top]);
					else newnode(lca, -1), AddEdge(lca, stk[top]);
				if (lca != stk[top]) 
					stk[++top] = p[++tot] = lca;
				if (p[i] != stk[top])
					stk[++top] = p[i];
			}
			for (int i=1;i<top;i++)
				AddEdge(stk[i], stk[i+1]);
		}
		
		inline int solve(int tot) {
			prework(tot);
			int ret = 0;
			for (int i=1,u,v,r,mid,t;i<T;i+=2) {
				u = to[i]; v = to[i+1];
				r = rag[u] + rag[v] - cost[i] >> 1;
				if (r >= 0) {
					mid = move(u, v, r);
					ret -= PDC.query(mid, r);
				}
			} 
			for (int i=1;i<=tot;i++) 
				ret += PDC.query(p[i], rag[p[i]]);
			return ret;
		}
	private:
		inline void newnode(int w, int v) {
			rag[w] = v << 1;
			head[w] = 0;
		}
		
		inline int move(int x, int y, int r) {
			if (dep[x] < dep[y]) swap(x, y);
			r = rag[x] - r;
			for (int i=0;r;i++,r>>=1)
				if (r & 1) x = anc[x][i];
			return x;	 
		}
		
		inline void prework(int tot) {
			for (int i=1;i<=tot;i++) {
				que.push(p[i]);
				inq[p[i]] = 1;
			}
			
			while (!que.empty()) {
				int w = que.front(); 
				que.pop(); inq[w] = 0;
				for (int i=head[w];i;i=nxt[i]) {
					if (rag[w] > rag[to[i]] + cost[i]) {
						rag[to[i]] = rag[w] - cost[i];
						if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
					}
				}
			}
		}
		
		inline void AddEdge(int u, int v) {
			int w = dis(u, v);
			to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
			to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
		}
}VT; 

int main() {
	n = read();
	fill(val+1, val+1+n, 1);
	for (int i=1,lim=n,u,v;i<lim;i++) {
		u = read(); v = read();
		Add_Edge(u, ++n);
		Add_Edge(n, v);
	}
	
	DFS(1, 1);
	for (int j=1;j<=17;j++) {
		for (int i=1;i<=n;i++) {
			anc[i][j] = anc[anc[i][j-1]][j-1];
		}
	}
	PDC.init();
	
	m = read();
	for (int y=1,k;y<=m;y++) {
		VT.build(k = read());
		printf("%d\n",VT.solve(k)); 
	}
	return 0;
}

【BZOJ 2653】middle

链接

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

题解

先来考虑一个子问题:

假如序列左端点在[l1,r1]之间,右端点在[l2,r2]之间
给定中位数x,问能否找出一个区间使得中位数大于等于x

这个问题很简单的样子:将小于x的赋值-1,大于x赋值为1
这样问题就转化为能否找到一个区间使得区间和大于等于0
这个可以用线段树在 log(n) 的时间内处理

如何在可以接受的时间复杂度内搞出每一个中位数对应的那颗线段树
考虑将原序列排序后从小到大来建树
第i棵线段树和第i+1棵线段树就只有第i个位置需要从1变成-1
这个用函数式线段树就好啦!

Code

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

const int N = 25000 + 9;
const int M = 400000;

int n,m,tot,arr[N],_hash[N],last_ans;
vector<int> pos_que[N];

namespace Chair_Tree{
	#define CT Chair_Tree
	int ch[M][2],ls[M],rs[M],sum[M],root[N],cnt;
	
	void Build(int &w, int l, int r) {
		sum[w=++cnt] = r - l + 1;
		ls[w] = rs[w] = sum[w];
		if (l < r) {
			int mid = l + r + 1 >> 1;
			Build(ch[w][0], l, mid-1);
			Build(ch[w][1], mid, r);
		} 
	}inline void init() {Build(root[1],1,n);}
	
	void insert(int p, int &w, int l, int r, int pur) {
		sum[w=++cnt] = sum[p] - 2;
		memcpy(ch[w],ch[p],sizeof(ch[w]));
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (pur < mid) insert(ch[p][0], ch[w][0], l, mid-1, pur);
			else insert(ch[p][1], ch[w][1], mid, r, pur);
			ls[w] = max(ls[ch[w][0]], sum[ch[w][0]] + ls[ch[w][1]]);
			rs[w] = max(rs[ch[w][1]], sum[ch[w][1]] + rs[ch[w][0]]);
		} else {
			ls[w] = rs[w] = 0;
		}		
	} inline void insert(int p, int w, int val) {
		insert(root[p],root[w],1,n,val);
	}
	
	int Get_sum(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return sum[w];
		} else {
			int mid = l + r + 1 >> 1, ret = 0;
			if (L < mid) ret += Get_sum(ch[w][0], l, mid-1, L, R);
			if (mid <= R) ret += Get_sum(ch[w][1], mid, r, L, R);
			return ret;
		}
	} inline int Get_Sum(int w, int l, int r) {
		return Get_sum(root[w],1,n,l,r);
	}
	
	int query_left(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return ls[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (R < mid) return query_left(ch[w][0], l, mid-1, L, R);
			else if (mid <= L) return query_left(ch[w][1], mid, r, L, R);
			else {
				int t1 = query_left(ch[w][0], l, mid-1, L, mid-1);
				int t2 = query_left(ch[w][1], mid, r, mid, R) + Get_sum(ch[w][0], l, mid-1, L, mid-1);
				return max(t1, t2);
			}	
		}
	} inline int Left_Max(int w, int l, int r) {
		return query_left(root[w],1,n,l,r);
	}
	
	int query_right(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return rs[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (R < mid) return query_right(ch[w][0], l, mid-1, L, R);
			else if (mid <= L) return query_right(ch[w][1], mid, r, L, R);
			else {
				int t1 = query_right(ch[w][1], mid, r, mid, R);
				int t2 = query_right(ch[w][0], l, mid-1, L, mid-1) + Get_sum(ch[w][1], mid, r, mid, R);
				return max(t1, t2);
			}
		}
	} inline int Right_Max(int w, int l, int r) {
		return query_right(root[w], 1, n, l, r);
	}
};

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

inline bool judge(int sta, int *lim) {
	int ret = CT::Get_Sum(sta, lim[2], lim[3]);
	ret += lim[1] < lim[2] ? CT::Right_Max(sta, lim[1], lim[2] - 1) : 0;
	ret += lim[3] < lim[4] ? CT::Left_Max(sta, lim[3] + 1, lim[4]) : 0;
	return ret >= 0;
}

int main() {
	n = read();
	for (int i=1;i<=n;i++) 
		arr[i] = _hash[i] = read();
	sort(_hash+1, _hash+1+n);
	tot = unique(_hash+1, _hash+1+n) - _hash - 1;
	for (int i=1;i<=n;i++) {
		arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash;
		pos_que[arr[i]].push_back(i);
	}
	CT::init();
	for (int i=2;i<=tot;i++) {
		CT::insert(i-1,i,pos_que[i-1][0]);
		for (int j=1,lim=pos_que[i-1].size();j<lim;j++) 
			CT::insert(i,i,pos_que[i-1][j]);
	}
	
	m = read();
	for (int i=1,lim[5],l,r,mid,ret;i<=m;i++) {
		for (int j=1;j<=4;j++)
			lim[j] = (read() + last_ans) % n + 1;
		sort(lim+1, lim+1+4);
		
		l = 1, r = tot;
		while (l <= r) {
			mid = l + r >> 1;
			if (!judge(mid,lim)) r = mid-1;
			else ret = mid, l = mid + 1; 
		}
		printf("%d\n",last_ans = _hash[ret]);
	}
	return 0;
}