【日常小测】友好城市

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

这题的前置知识是把求$SCC$优化到$O(\frac{n^2}{32})$
具体来说,就是使用$bitset$配合$Kosaraju$算法

有了这个技能以后,我们配合$ST$表来实现提取一个区间的边的操作
这样的话,总的时间复杂度是:$O(\frac{(\sqrt{m} \log m + q) n^2}{32}+q \sqrt{m})$

然后我懒,没有用$ST$表,用的莫队,时间复杂度是$O(\frac{(m + q) n^2}{32}+q \sqrt{m})$
调一调块大小,勉勉强强卡过去了

Code

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

const int N = 159;
const int M = 300009;
const int QQ = 50009;
const int BlockSize = 1200;
const UI ALL = (1ll << 32) - 1;

int n, m, q, U[M], V[M], ans[QQ]; 
struct Query{
	int l, r, blk, id;
	inline bool operator < (const Query &Q) const {
		return blk < Q.blk || (blk == Q.blk && r < Q.r);
	}
}qy[QQ];
struct Bitset{
	UI v[5];
	inline void flip(int x) {
		v[x >> 5] ^= 1 << (x & 31);
	}
	inline void set(int x) {
		v[x >> 5] |= 1 << (x & 31);
	}
	inline void reset() {
		memset(v, 0, sizeof(v));
	}
	inline bool operator [](int x) {
		return v[x >> 5] & (1 << (x & 31));
	}
}g[N], rg[N], PreG[M / BlockSize + 9][N], PreRG[M / BlockSize + 9][N];

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

inline void AddEdge(int u, int v, Bitset *a1, Bitset *a2) {
 	a1[u].set(v);
 	a2[v].set(u);
}

class Kosaraju{
	vector<int> que;
	Bitset vis;
public:
	inline int solve() {
		vis.reset();
		que.clear();
		for (int i = 1; i <= n; ++i) {
			if (!vis[i]) {
				dfs0(i);
			}
		}
		vis.reset();
		int ret = 0;
		for (int j = n - 1; ~j; j--) {
			int i = que[j];
			if (!vis[i]) {
				int cnt = dfs1(i);
				ret += cnt * (cnt - 1) / 2;
			}
		}
		return ret;
	}
private:
	inline void dfs0(int w) {
		vis.flip(w);
		for (int i = 0; i < 5; i++) {
			for (UI j = g[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					dfs0(t);
				}
			}
		}
		que.push_back(w);
	}
	inline int dfs1(int w) {
		vis.flip(w);
		int ret = 1;
		for (int i = 0; i < 5; i++) {
			for (UI j = rg[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					ret += dfs1(t);
				}
			}
		}
		return ret;
	}
}scc;

int main() {
	freopen("friend.in", "r", stdin);
	freopen("friend.out", "w", stdout);
	n = read(); m = read(); q = read();
	for (int i = 1; i <= m; i++) {
		U[i] = read();
		V[i] = read();
		AddEdge(U[i], V[i], PreG[i / BlockSize], PreRG[i / BlockSize]);
	}
	for (int i = 1; i <= q; i++) {
		qy[i].l = read(); 
		qy[i].r = read();
		qy[i].blk = qy[i].l / BlockSize;
		qy[i].id = i;
	}
	sort(qy + 1, qy + 1 + q);
	Bitset CurG[N], CurRG[N];
	for (int i = 1, L = 1, R = 0; i <= q; i++) {
		if (qy[i].blk != qy[i - 1].blk || i == 1) {
			L = qy[i].blk + 1;
			R = L - 1;	
			for (int j = 1; j <= n; j++) {
				CurG[j].reset();
				CurRG[j].reset();
			}
		}
		if (qy[i].r / BlockSize - 1 > R) {
			for (int j = R + 1, lim = qy[i].r / BlockSize - 1; j <= lim; j++) {
				for (int k = 1; k <= n; k++) {
					for (int h = 0; h < 5; h++) {
						CurG[k].v[h] ^= PreG[j][k].v[h];
						CurRG[k].v[h] ^= PreRG[j][k].v[h];
					}
				}
			}
			R = qy[i].r / BlockSize - 1;
		}
		if (L <= R) {
			for (int i = 1; i <= n; i++) {
				g[i] = CurG[i];
				rg[i] = CurRG[i];
			}
			for (int l = qy[i].l; l < L * BlockSize; l++) {
				AddEdge(U[l], V[l], g, rg);
			}
			for (int r = (R + 1) * BlockSize; r <= qy[i].r; r++) {
				AddEdge(U[r], V[r], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		} else {
			for (int i = 1; i <= n; i++) {
				g[i].reset();
				rg[i].reset();
			}
			for (int j = qy[i].l; j <= qy[i].r; ++j) {
				AddEdge(U[j], V[j], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		}
	}
	for (int i = 1; i <= q; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

【BZOJ 4810】[YNOI2017] 由乃的玉米田

相关链接

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

解题报告

看一看似乎一脸懵逼啊
询问两数相加、相减为特殊值不是只能$FFT$吗?
你这™还带区间限制,那怎么做啊……

但仔细看看值域范围,发现这货只有$10^{10}$
配上$30s$的限制,刚好是$bitset$的数据范围啊!
于是仔细想一想,加法可以直接减法可以直接左移然后$and$起来
至于减法,我们可以记一下负数就可以转化为减法了
至于相乘嘛,我们可以暴力枚举因数!
于是再配上区间的莫队,时间复杂度:$O(n \sqrt{n} + \frac{mc}{64})$

【日常小测】题目2

相关链接

题目传送门:http://paste.ubuntu.com/24087843/
数据生成器:http://paste.ubuntu.com/24087850/
std:http://paste.ubuntu.com/24087841/

题目大意

给定$1 \sim n$的排列$a_i$,再给定$m$个询问、每次给出$l_i,r_i$
求$\sum\limits_{i=l_i}^{r_i}{\sum\limits_{j=l_i}^{i-1}{gcd(a_i,a_j)}}$, $n,m \le 2 \cdot 10^4$

解题报告

一看数据范围就给人一种大暴力的感觉
但用$O(1)$的$GCD$做到$O(nk)$并不能通过此题

std的话非常套路啊!
考虑维护一个集合,支持加入、删除、查询集合中的数两两$GCD$的和
如果可以在$O(\log n)$的时间复杂度完成维护的话,显然可以用莫队做到$O(n^{1.5} \log n)$

现在考虑如何维护,如果分解因数的话,会有算重的部分
但我们列出式子,发现我们计算的实际是:$\sum\limits_{d|gcd(a_i,a_j)}{f(d)}$
如果窝萌把$f(d)$令成$\varphi (d)$,那岂不是刚刚好?
于是我们对于删除和加入,枚举因数$i$,然后在第i个位置加入$\varphi (i)$即可
那么总的复杂度均摊下来是$O(n^{1.5} \log n)$的

另外本题还有一个兄弟版本:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1439
就是要求维护一个集合中两两互质的对数,把$\varphi(i)$换成$\mu(i)$就是一样的做法了
全™是套路啊!

Code

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

const int N = 100009;

LL vout[N],cnt[N],ans;
int n,m,tot,BLK,pri[N],arr[N],phi[N];
vector<int> divs[N]; bool vis[N]; 
struct Query{int l,r,id,blk;}q[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 Modify(int w, int t) {
	for (int j=divs[w].size()-1,c;~j;j--) {
		c = divs[w][j];
		if (~t) ans += cnt, cnt += phi;
		else cnt -= phi, ans -= cnt;
	}
}

int main() {
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
	n = read(); BLK = sqrt(n) + 1; phi[1] = 1;
	for (int i=2;i<=n;i++) {
		if (!vis[i]) phi[i] = i-1, pri[++tot] = i;
		for (int j=1;j<=tot&&pri[j]*i<=n;j++) {
			vis[i*pri[j]] = 1;
			if (i % pri[j]) phi[i*pri[j]] = phi[i] * phi[pri[j]];
			else {phi[i*pri[j]] = phi[i] * pri[j]; break;}
		}
	} 
	for (int i=1;i<=n;i++) {
		arr[i] = read();
		for (int j=i;j<=n;j+=i)
			divs[j].push_back(i);
	} m = read();
	for (int i=1;i<=m;i++) {
		q[i].l = read(); q[i].r = read();
		q[i].id = i; q[i].blk = q[i].l / BLK;
	}	
	sort(q+1, q+1+m, [](const Query &A, const Query &B){return A.blk<B.blk||(A.blk==B.blk&&A.r<B.r);});
	for (int i=1,l=1,r=0;i<=m;i++) {
		while (r > q[i].r) Modify(arr[r--], -1);
		while (r < q[i].r) Modify(arr[++r], 1);
		while (l > q[i].l) Modify(arr[--l], 1);
		while (l < q[i].l) Modify(arr[l++], -1);
		vout[q[i].id] = ans; 
	}
	for (int i=1;i<=m;i++) printf("%lld\n",vout[i]);
	return 0;
}

【BZOJ 4358】permu

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4358
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5049090.html
神犇题解Ⅱ:http://www.cnblogs.com/czllgzmzl/p/5644724.html

解题报告

1. 莫队+并查集

首先我们考虑一个简化版本:搞一个莫队,然后搞一个值域线段树
这样的话,我们的复杂度就是 $O({n^{1.5}}logn)$ 的,虽然可能会T,但很好想
现在考虑怎么把$log$去掉:如果莫队那里只存在插入操作,那么我们就可以使用并查集来维护
于是考虑莫队那里只有左端点的移动那里会有删除操作,于是我们每一次把左端点块内那一部分拿出来暴力重构
这样的话,复杂度就神奇地少了一个$log$!总复杂度: $O(n\sqrt n \alpha (n))$ 感觉可以A地样子!

2. KD-Tree

这里就是本题的高能部分!简直是太神啦!_(:з」∠)_
考虑将询问化为二维上的点,然后我们按照点值的大小,将序列的位置一个一个插入
每一次把所有包含他的询问的计数器加一,其他的询问的计数器置零
于是我们的每个询问对应的点上的计数器的历史最大值就是这个询问的答案啦!
时间复杂度:$O(n \sqrt n)$

【BZOJ 4262】Sum

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4262
神犇题解-1:http://www.cnblogs.com/clrs97/p/4824806.html
神犇题解-2:http://blog.csdn.net/qq_34637390/article/details/51313126

题解

我们不妨将所有询问按照右端点\(r_i\) 排序
假设当前处理的所有询问右端点统一为last
定义\(val_i^{last} = \min (\{ {a_j}|j \in [i,last]\} )\)
定义\(sum_i^{last} = \sum\limits_{j = i}^{last} {val_i^j}\)
不难发现对于左右端点在l-r的所有区间的min和为\(\sum\limits_{i = l}^r {sum_i^r}\)
更进一步,每一个原题中提到的询问可以拆成:\(\sum\limits_{i = {l_1}}^{{r_1}} {sum_i^{{r_2}}} – \sum\limits_{i = {l_1}}^{{r_1}} {sum_i^{{l_2} – 1}}\)

接下来的事情就是用线段树来维护val和sum辣!
考虑last向右移动一个单位,我们首先需要将一些点的val更新
然后我们需要将每一个点当前的val累加到sum里面去

每一个点维护四个变量a,b,c,d来表示标记
定义 new_val = a * val + b * len
定义 new_sum = sum + c * val + d * len
显然更新val需要用到的参数是 {0,val',0,0}
而默认的参数则应该为 {1,0,0,0}
更新sum的参数则应该为 {1,0,1,0}

于是就可以将这两种标记一起下传了
至于为什么可以混在一起?
因为这货是矩阵乘法啊!
ps:矩阵乘法并没有交换律,只有结合律,所以在修改时也得下传标记

Code

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

const int N = 100000+9;
const int M = N << 1;
const int MOD = 1000000000;
const int SEED1 = 1023;
const int SEED2 = 1025;

int n,m,tot,arr[N],stk[N];
LL vout[N];
struct Query{
	int lim,l,r,t,id;
	inline bool operator < (const Query &B) const {
		return lim < B.lim;
	}
}q[M];

namespace Segment_Tree{
	#define SEG Segment_Tree
	int ch[M][2],L,R,cnt,root;
	LL sum[M],val[M],ans_tmp;
	struct Tag{
		LL a,b,c,d;
		inline Tag() {a=1;b=c=d=0;}
		inline Tag(LL a, LL b, LL c, LL d):a(a),b(b),c(c),d(d) {}
		inline Tag operator * (const Tag &B) {
			return (Tag){a*B.a, B.b+b*B.a, a*B.c+c, B.d+d+b*B.c};
		}
	}tag[M],delta;
	
	void Build(int &w, int l, int r) {
		w = ++cnt;
		tag[w] = Tag(1,0,0,0);
		val[w] = sum[w] = 0;
		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() {
		cnt = 0;
		Build(root,1,n);
	}
	
	inline void Add(int w, int l, int r, Tag v) {
		static int len; len = r - l + 1;
		sum[w] += val[w] * v.c + len * v.d;
		val[w] = val[w] * v.a + len * v.b;
		tag[w] = tag[w] * v;
	}
	
	inline void push_down(int w, int l, int mid, int r) {
		Add(ch[w][0],l,mid-1,tag[w]);
		Add(ch[w][1],mid,r,tag[w]);
		tag[w] = Tag(1,0,0,0);
	}
	
	inline void GetSum() {
		Add(root,1,n,Tag(1,0,1,0));
	}
	
	void Modify(int w, int l, int r) {
		if (L <= l && r <= R) {
			Add(w,l,r,delta);
		} else {
			int mid = l + r + 1 >> 1;
			if (tag[w].a != 1 || tag[w].b || tag[w].c || tag[w].d) 
				push_down(w,l,mid,r);
			if (L < mid) Modify(ch[w][0], l, mid-1);
			if (R >= mid) Modify(ch[w][1], mid, r);
			val[w] = val[ch[w][0]] + val[ch[w][1]];
			sum[w] = sum[ch[w][0]] + sum[ch[w][1]];
		}
	}
	
	inline void modify(int l, int r, int v) {
		delta = Tag(0,v,0,0);
		L = l, R = r;
		Modify(root,1,n);
	}
	
	void query(int w, int l, int r) {
		if (L <= l && r <= R) {
			ans_tmp += sum[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (tag[w].a != 1 || tag[w].b || tag[w].c || tag[w].d) 
				push_down(w,l,mid,r);
			if (L < mid) query(ch[w][0], l, mid-1);
			if (R >= mid) query(ch[w][1], mid, r);
		}
	}
	
	inline LL query(int l, int r) {
		ans_tmp = 0;
		L = l; R = r;
		query(root,1,n);
		return ans_tmp;
	}
};

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() {
	m = read();
	for (int i=1,l1,l2,r1,r2;i<=m;i++) {
		l1 = read(); r1 = read();
		l2 = read(); r2 = read();
		if (l2 > 1) q[++tot] = (Query){l2-1,l1,r1,-1,i};	
		q[++tot] = (Query){r2,l1,r1,1,i};
		n = max(n, max(r1, r2));
	}
	sort(q+1, q+1+tot);
	for (int i=1,c1=SEED1,c2=SEED2;i<=n;i++) {
		arr[i] = c1 ^ c2;
		c1 = (LL)SEED1 * c1 % MOD;
		c2 = (LL)SEED2 * c2 % MOD;
	}
	
	SEG::init();
	for (int i=1,top=0,cur=1;i<=n;i++) {
		while (top && arr[stk[top]] > arr[i]) top--;
		SEG::modify(stk[top]+1, i, arr[i]);
		SEG::GetSum(); stk[++top] = i;
		while (cur <= tot && q[cur].lim == i) {
			vout[q[cur].id] -= SEG::query(q[cur].l, q[cur].r) * q[cur].t;
			cur++;
		}
	}
	SEG::init();
	for (int i=1,top=0,cur=1;i<=n;i++) {
		while (top && arr[stk[top]] < arr[i]) top--;
		SEG::modify(stk[top]+1, i, arr[i]);
		SEG::GetSum(); stk[++top] = i;
		while (cur <= tot && q[cur].lim == i) {
			vout[q[cur].id] += SEG::query(q[cur].l, q[cur].r) * q[cur].t;
			cur++;
		}
	}
	
	for (int i=1;i<=m;i++) 
		printf("%lld\n",vout[i]);
	return 0;
}

【BZOJ 4540】[HNOI2016] 序列

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4540
数据生成器:http://paste.ubuntu.com/23631812/
神犇题解-线段树:http://blog.csdn.net/qq_34637390/article/details/51313126
神犇题解-莫队:https://blog.sengxian.com/solutions/bzoj-4540

解题报告

这题好神啊!莫队和线段树的做法都好神啊!

1. 莫队做法

我们只需要考虑如何O(1)进行转移。
因为是转移,所以一端是固定的,不妨设固定的是左端。
现在从左向右考虑右端点,不难发现:最小值不增(如下图所示)

通过观察我们还可以发现:除了第④段,其他几段的长度都是固定的
于是我们先预处理一下相关信息,对于第④段这种进行特殊处理。
因为第④段这货是l~r中的最小值,所以我们搞一个RMQ就可以特殊处理啦!
这样一来,转移就可以做到O(n),于是就可以上O(n^1.5)的莫队辣!

2. 线段树做法

因为此题和BZOJ_4262 一毛一样,所以就不单独写了。
这里有一份很好的题解,强烈推荐:http://blog.csdn.net/qq_34637390/article/details/51313126

Code (莫队version)

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

const int N = 100000+9;
const int INF = 2e9;

struct Query{
	int l,r,blk,num;
	inline bool operator < (const Query &B) const {
		return blk < B.blk || (blk == B.blk && r < B.r);
	}
}q[N];
int n,m,sqr,top,val[N],stk[N],pos[N],lft[N],rit[N];
LL vout[N],sum_right[N],sum_left[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;
}

namespace Sparse_Table{
	#define ST Sparse_Table
	int sur[N*3][20],arr[N*3][20],POW[20],log[N];
	
	inline void init() {
		POW[0] = 1;
		for (int i=1;i<=17;i++) 
			POW[i] = POW[i-1] << 1;
		for (int i=1,w=1;i<=n;w=1,++i) 
			while (w * 2 <= i) w <<= 1, log[i]++;
		
		for (int i=1;i<=n;i++) {
			arr[i][0] = val[i];
			sur[i][0] = i;
		}
		for (int j=1,cur=1;j<=17;j++,cur<<=1) {
			for (int i=1;i<=n;i++) {
				if (arr[i][j-1] < arr[i+cur][j-1]) {
					arr[i][j] = arr[i][j-1];
					sur[i][j] = sur[i][j-1];
				} else {
					arr[i][j] = arr[i+cur][j-1];
					sur[i][j] = sur[i+cur][j-1];
				}
			}
		}
	}
	
	inline int query(int l, int r) {
		int w = log[r-l+1];
		if (arr[l][w] < arr[r-POW[w]+1][w]) return sur[l][w];
		else return sur[r-POW[w]+1][w];
	}
};

inline LL move_right(int l, int r) {
	int p = ST::query(l, r);
	return sum_left[r] - sum_left[p] + (LL)val[p] * (p - l + 1);
}

inline LL move_left(int l, int r) {
	int p = ST::query(l, r); 
	return sum_right[l] - sum_right[p] + (LL)val[p] * (r - p + 1);
}

inline void prework() {
	stk[top = 0] = -INF;
	for (int i=1;i<=n;i++) {
		while (stk[top] > val[i]) top--;
		lft[i] = pos[top];
		sum_left[i] = sum_left[pos[top]] + (LL)(i-pos[top]) * val[i]; 
		stk[++top] = val[i];
		pos[top] = i;
	}
	
	pos[top = 0] = n+1;
	for (int i=n;i;i--) {
		while (stk[top] >= val[i]) top--;
		rit[i] = pos[top];
		sum_right[i] = sum_right[pos[top]] + (LL)(pos[top]-i) * val[i];
		stk[++top] = val[i];
		pos[top] = i;
	}
	
	ST::init();
}

int main(){
	n = read(); m = read();
	sqr = sqrt(n);
	for (int i=1;i<=n;i++)
		val[i] = read();
	prework();
	for (int i=1;i<=m;i++) {
		q[i].num = i;
		q[i].l = read(); 
		q[i].r = read();
		q[i].blk = q[i].l / sqr;
	}
	sort(q+1, q+1+m);
	
	LL cur = val[1];
	for (int k=1,l=1,r=1;k<=m;k++) {
		while (r < q[k].r) cur += move_right(l,r+1), r++;
		while (r > q[k].r) cur -= move_right(l,r), r--;
		while (l < q[k].l) cur -= move_left(l,r), l++;
		while (l > q[k].l) cur += move_left(l-1,r), l--;
		vout[q[k].num] = cur;
	}
	
	for (int i=1;i<=m;i++) 
		printf("%lld\n",vout[i]);
	return 0;
}

ps:这一份代码并不能处理值为负数的情况,至于为什么:我也普吉岛 QwQ

—————————— UPD 2017.2.2 ——————————
这题今天重新想的时候,想到了一个$O(nlog^2n)$的算法
虽然时间复杂度稍高,但思维复杂度和编程复杂度都相对较低

设$l_i$为第i个数离左边第一个比他小的数的距离,$r_i$同理
于是询问整个序列的话,答案就是 $\sum\limits_{i = 1}^n {{a_i} \times {l_i} \times {r_i}} $
然后仍然考虑离线,将询问排序依次做。
对于每一个数,其贡献有三种情况:
1. $l_i$,$r_i$都没有被询问限制
2. 有一个被限制
3. 有两个被限制
于是我们就可以搞一个树套树套树,把这三种情况分别计算即可
复杂度:$O(nlog^3n)$

但我们考虑离线之后,右端点逐渐右移,于是我们搞一个队列什么的维护一下
然后就搞一个树套树维护左端点就好,复杂度$O(nlog^2n)$

【BZOJ 3585】mex

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3585
数据生成器:http://paste.ubuntu.com/15521165/

我写的是莫队的算法,然而多了一个log,不过还是勉强卡过去辣
其实带log的算法,还有一种更优雅的写法:用线段树来维护区间最值
不过真正不带log的算法,还是只能是莫队配合分块吧!

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 200000+9;
 
int arr[N],cnt[N],n,m,block,vout[N];
set<int> ans;
struct Query{
    int l,r,b,id;
    bool operator < (const Query & B) const {
        return b < B.b || (b == B.b && r < B.r);
    }
}q[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;
}
 
inline void update(int ty, bool delta) {
    if (ty > n) return;
    if (delta) {
        cnt[ty]++;
        if (cnt[ty] == 1) {
            ans.erase(ty);
        }
    } else {
        cnt[ty]--;
        if (!cnt[ty]) {
            ans.insert(ty);
        }
    }
}
 
int main(){
    n = read(); m = read(); block = sqrt(n) + 1;
    for (int i=1;i<=n;i++) {
        arr[i] = read();
        ans.insert(i);
    } ans.insert(0);
    for (int i=1;i<=m;i++) {
        q[i].l = read();
        q[i].r = read();
        q[i].b = q[i].l / block;
        q[i].id = i;
    }
    sort(q+1, q+1+m);
     
    for (int i=1,p1=1,p2=0,l,r;i<=m;i++) {
        l = q[i].l; r = q[i].r;
        while (p1 < l) update(arr[p1++], 0);
        while (p2 > r) update(arr[p2--], 0);
        while (p2 < r) update(arr[++p2], 1);
        while (p1 > l) update(arr[--p1], 1);
        vout[q[i].id] = *(ans.begin());
    }
     
    for (int i=1;i<=m;i++) {
        printf("%d\n",vout[i]);
    }
    return 0;
}

【BZOJ 3575】苹果树

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3757
数据传送门:https://oi.qizy.tech/wp-content/uploads/2016/10/3757.rar

树上莫队的模板题!
真的是好板,只要会树分块就可以写辣!

然而树上莫队有几个地方必须要注意:
1.排序的时候必须以一个点的所在树块的编号为第一关键字,然后第二关键字搞成另一点的DFS序
2.最好把每个询问的两个点中DFS较大的作为第二个点
以上这么做为什么会极大的影响速度并不是太清楚 ╮(╯▽╰)╭ 不过效果真的很好
还有不会的同学,出门左拐去找PoPoQQQ吧:http://blog.csdn.net/popoqqq/article/details/41479829

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

const int N = 50000+9;
const int M = 100000+9;

int head[N],to[M],nxt[M],n,m,col[N],stk[M],top,LIM,dfs_num[M];
int fa[N][17],dep[N],cnt[N],ans,num[N],vout[M],sta[N]; 
struct Query{
	int u,v,a,b,id;
	bool operator < (const Query &B) const {
		return num[u] < num[B.u] || (num[u] == num[B.u] && dfs_num[v] < dfs_num[B.v]);
	}
}query[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;
}

void DFS(int w, int f, int bot) {
	static int block_cnt = 0;
	static int dfs_cnt = 0;
	
	dfs_num[w] = ++dfs_cnt;
	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,top);
			if (top - bot >= LIM) {
				block_cnt++;
				while (top > bot) {
					num[stk[top--]] = block_cnt;				
				}
			}
		}
	}
	stk[++top] = w;
	while (!w && top) {
		num[stk[top--]] = block_cnt;
	}
}

inline void update(int id, bool delta) {
	if (cnt[id] == 1 && !delta) ans--;
	else if (!cnt[id] && delta) ans++;
	cnt[id] += delta?1:-1;
}

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

inline void move(int &w, int pur) {
	int lca = LCA(w, pur);
	for (int i=w;i!=lca;i=fa[i][0]) update(col[i], sta[i] ^= 1);
	for (int i=pur;i!=lca;i=fa[i][0]) update(col[i], sta[i] ^= 1);
	w = pur;
}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

int main(){
	int size = 128 << 20; 
	char *p = (char*)malloc(size) + size;  
	__asm__("movl %0, %%esp\n" :: "r"(p)); 
	
	n = read(); m = read(); LIM = sqrt(n) + 1;
	for (int i=1;i<=n;i++) col[i] = read();
	for (int i=1;i<=n;i++) Add_Edge(read(), read());
	DFS(0,0,0);
	for (int i=1;i<=16;i++) {
		for (int j=0;j<=n;j++) {
			fa[j][i] = fa[fa[j][i-1]][i-1];
		}
	}
	for (int i=1;i<=m;i++) {
		query[i].id = i;
		query[i].u = read(); 
		query[i].v = read();
		query[i].a = read();
		query[i].b = read();
		if (dfs_num[query[i].u] > dfs_num[query[i].v]) {
			swap(query[i].u, query[i].v);
		}
	}
	sort(query+1, query+1+m);
	
	for (int i=1,p1=0,p2=0;i<=m;i++) {
		move(p1, query[i].u);
		move(p2, query[i].v);
		
		int lca = LCA(query[i].v, query[i].u);
		update(col[lca], sta[lca] ^= 1);
		vout[query[i].id] = ans;
		if (query[i].a != query[i].b && cnt[query[i].a] && cnt[query[i].b]) vout[query[i].id]--;
		update(col[lca], sta[lca] ^= 1);
	}
	
	for (int i=1;i<=m;i++) {
		printf("%d\n",vout[i]);
	}
	return 0;
}