做题记录 4.0

Yet Another Segments Subset

来源：CF1399F, 2300 

区间 $\mathrm{DP}$，难点在于求 $\mathrm{c[i]}$, 即第 $\mathrm{i}$ 条线段最多包含多少条其他线段.  

然后求这个的话可以把所有线段按照长度从小到大排序，然后每次 $\mathrm{O(n)}$ 拿出 $\mathrm{i}$ 内的线段进行一遍 $\mathrm{DP}$.  

由于内部的线段长度更小，所以 $\mathrm{c[j]}$ 是可以直接拿来用的.  

#include 
#include 
#include 
#include 
#define N  6009 
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
int n, A[N << 1], cnt, dp[N], f[N]; 
struct seg {
	int l, r, len , id ; 
	seg(int l = 0, int r = 0, int len = 0, int id = 0):l(l), r(r), len(len) , id(id) {}     
}a[N], b[N];   
vectorse[N]; 
bool cmp1(seg i, seg j) { return i.len < j.len; }
bool cmp2(seg i, seg j) { return i.r < j.r; }
void calc(int x) {
	// a[x] 这条线段.     
	for(int i = 1; i <= n ; ++ i) {
		if(a[x].id != b[i].id && b[i].l >= a[x].l && b[i].r <= a[x].r) {
			se[b[i].r].pb(b[i]); 
		}
	}                
	for(int i = a[x].l; i <= a[x].r; ++ i) {
		f[i] = max(f[i], f[i - 1]);   
		for(int j = 0; j < se[i].size() ; ++ j) {
			f[i] = max(f[i], dp[se[i][j].id] + f[se[i][j].l - 1]);   
		}
	}  
	dp[a[x].id] = 1 + f[a[x].r];   
	for(int i = a[x].l; i <= a[x].r; ++ i) f[i] = 0;  
	for(int i = a[x].l; i <= a[x].r; ++ i) se[i].clear();  
}           
void solve() {
	scanf("%d", &n); 
	cnt = 0 ; 
	for(int i = 1; i <= n ; ++ i) {
		scanf("%d%d", &a[i].l, &a[i].r);         
		A[++ cnt] = a[i].l; 
		A[++ cnt] = a[i].r;    
		a[i].len = a[i].r - a[i].l + 1; 
		a[i].id = i;      
	}
	++ n ; 
	a[n].l = 1, a[n].r = (int)2e5 + 5; 
	a[n].len = a[n].r - a[n].l + 1;
	a[n].id = n ;     
	A[++ cnt] = a[n].l; 
	A[++ cnt] = a[n].r;   
	sort(A + 1, A + 1 + cnt);  
	cnt = unique(A + 1, A + 1 + cnt) - A - 1;  
	for(int i = 1; i <= n ; ++ i) {
		a[i].l = lower_bound(A + 1, A + 1 + cnt, a[i].l) - A;  
		a[i].r = lower_bound(A + 1, A + 1 + cnt, a[i].r) - A;    
	}     
	// 按照长度依次处理.  
	sort(a + 1, a + 1 + n, cmp1);   
	for(int i = 1; i <= n ; ++ i) 
		b[i] = a[i]; 
	sort(b + 1, b + 1 + n, cmp2);  
	for(int i = 1; i <= n ; ++ i) {
		calc(i);  
	}
	printf("%d\n", dp[a[n].id] - 1);   
	for(int i = 0; i <= n ; ++ i) dp[i] = 0;   
}
int main() {
	// setIO("input");   
	int T; 
	scanf("%d", &T); 
	while(T -- ) solve();  
	return 0; 
}

Isomorphic Strings

来源：CF985F, 2300  

这道题强调字母之间的相对位置，不妨对每种字母开一个哈希表，然后判断一下即可.  

为了防止出题人卡哈希，这里用了两个 $\mathrm{base}$ 和两个模数.  

#include 
#include 
#include 
#include 
#include 
#define N  200009 
#define ll long long
#define pb push_back  
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
char str[N];   
const int mod1 = 998244353;  
const int mod2 = (int)1e9 + 7;  
const int base1 = 233;  
const int base2 = 233233;      
int b1[N], b2[N];                     
struct HASH {   
	int s1[N], s2[N];        
}ha[26];  
void init() {
	b1[0] = b2[0] = 1; 
	for(int i = 1; i < N ; ++ i) {
		b1[i] = (ll)b1[i - 1] * base1 % mod1;  
		b2[i] = (ll)b2[i - 1] * base2 % mod2;   
	}
}   
int ax[2][30], ay[2][30];      
int main() {
	// setIO("input"); 
	int n , m ; 
	scanf("%d%d", &n, &m); 
	init(); 
	scanf("%s", str + 1); 
	// 字符串输入进来.  
	for(int i = 1; i <= n ; ++ i) {
		int c = str[i] - 'a';    
		for(int j = 0; j < 26 ; ++ j) {
			ha[j].s1[i] = ha[j].s1[i - 1];
			ha[j].s2[i] = ha[j].s2[i - 1];   
		}    
		(ha[c].s1[i] += b1[i]) %= mod1; 
		(ha[c].s2[i] += b2[i]) %= mod2;       
	}
	// 加密好了.  
	for(int i = 1; i <= m ; ++ i) {
		int x, y, len ; 
		scanf("%d%d%d", &x, &y, &len);       
		if(x > y) swap(x, y);                
		for(int j = 1; j <= 26; ++ j) {
			ax[0][j] = (ll)(ha[j - 1].s1[x + len - 1] - ha[j - 1].s1[x - 1] + mod1) % mod1 * b1[y - x] % mod1; 
			ax[1][j] = (ll)(ha[j - 1].s2[x + len - 1] - ha[j - 1].s2[x - 1] + mod2) % mod2 * b2[y - x] % mod2;

			ay[0][j] = (ll)(ha[j - 1].s1[y + len - 1] - ha[j - 1].s1[y - 1] + mod1) % mod1;     
			ay[1][j] = (ll)(ha[j - 1].s2[y + len - 1] - ha[j - 1].s2[y - 1] + mod2) % mod2;     
		}

		sort(ax[0] + 1, ax[0] + 1 + 26); 
		sort(ax[1] + 1, ax[1] + 1 + 26); 
		sort(ay[0] + 1, ay[0] + 1 + 26); 
		sort(ay[1] + 1, ay[1] + 1 + 26);  

		int flag = 0; 
		for(int j = 1; j <= 26; ++ j) {
			//  printf("%d %d\n", ax[0][j], ay[0][j]); 
			if((ax[0][j] != ay[0][j]) || (ax[1][j] != ay[1][j])) {
				flag = 1; 
				break; 
			}
		}
		if(flag)  printf("NO\n"); 
		else printf("YES\n"); 
	}
	return 0; 
}

Envy

来源：CF891C, 2300 

对于一个图来说，最小生成树所构成的边的种类数是固定的. 

就是说，对于边权为 $\mathrm{v}$ 的边在一个树中有 $\mathrm{c}$ 个，则任意必有 $\mathrm{c}$ 个. 

然后对于一个生成树中同一权值的边，连通性也同样是必须相同的.  

那么在这道题中就可以对于询问离线，每次讲 $\mathrm{[1, i-1]}$ 的边连出来，然后看 $\mathrm{i}$ 的询问边是否有环即可.  

由于需要连边并撤销，所以直接上可撤销并查集即可.

p.s. 这道题用 $\mathrm{LCT}$ 做也是经典问题，即每次暴力查看一条边是否能加入，能加入则加，不能加则不合法. 

#include 
#include 
#include 
#include 
#include 
#define N  1000009 
#define ll long long
#define pb push_back  
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
struct UFS {
	int p[N], top , size[N];   
	struct OP {
		int x, y;
		// x 连向 y    
		OP(int x = 0, int y = 0):x(x), y(y){} 
	}sta[N]; 
	void init() {
		top = 0; 
		for(int i = 1; i < N ; ++ i) {
			size[i] = 1, p[i] = i; 
		}
	}
	int find(int x) {
		return p[x] == x ? x : find(p[x]); 
	}  
	int merge(int x, int y) {
		x = find(x), y = find(y);
		if(x == y) return 0;    
		if(size[x] > size[y]) swap(x, y); 
		// size[y] > size[x] 
		size[y] += size[x], p[x] = y;  
		sta[++ top] = OP(x, y);  
		return 1;  
	} 
	void undo(int h) {
		// (h, top] 撤销掉.  
		while(top > h) {
			OP cur = sta[top];   
			size[cur.y] -= size[cur.x];  
			p[cur.x] = cur.x;     
			-- top;  
		}
	}
}T; 
int n , m , Q, ans[N]; 
struct Edge {
	int u, v, c; 
	Edge(int u = 0, int v = 0, int c = 0):u(u), v(v), c(c){}  
}e[N];  
bool cmp(Edge i, Edge j) { return i.c < j.c; }  
struct query {
	int u, v, c, id;     
	query(int u = 0, int v = 0, int c = 0, int id = 0):u(u), v(v), c(c), id(id){}  
};  
vectorG[N];
bool cmp2(query i, query j) { return i.id < j.id; }    
int main() {
	// setIO("input");  
	scanf("%d%d", &n, &m);
	int mx = 0;  
	for(int i = 1; i <= m ; ++ i) {
		int x, y, z; 
		scanf("%d%d%d", &x, &y, &z);    
		e[i] = Edge(x, y, z);  
		mx = max(mx, z); 
	}
	scanf("%d", &Q); 
	for(int i = 1, k; i <= Q; ++ i) {
		scanf("%d", &k); 
		for(int j = 1; j <= k ; ++ j) {
			int x; 
			scanf("%d", &x); 
			// printf("%d %d\n", x, e[x].c); 
			G[e[x].c].pb(query(e[x].u, e[x].v, e[x].c, i));   
		}
	}    
	sort(e + 1, e + 1 + m, cmp);
	T.init(); 
	memset(ans, -1, sizeof(ans)); 
	for(int i = 1, j = 1; i <= mx; ++ i) {
		// 先解决
		int o = T.top;     
		sort(G[i].begin(), G[i].end(), cmp2); 
		if(G[i].size()) {
			int d = G[i][0].id;  
			for(int j = 0; j < G[i].size() ; ++ j) {
				if(G[i][j].id != d) {
					T.undo(o);  
				}   // 换询问了. 
				if(!T.merge(G[i][j].u, G[i][j].v)) {
					ans[G[i][j].id] = 0;    
				}
				d = G[i][j].id;   
			}
		}           
		T.undo(o);   
		for( ; j <= m && e[j].c <= i; ++ j) {
			T.merge(e[j].u, e[j].v);  
		}
		// 把新的边加进来.   
	}
	for(int i = 1; i <= Q; ++ i) {
		printf("%s\n", ans[i] == 0 ? "NO" : "YES"); 
	}
	return 0; 
}

Centroids

来源：CF708C, 2300  

对于重心来说，显然合法，然后非重心来说要从最大的子树选择最大的且不超过 $\mathrm{n/2}$ 的子块删下来.  

求最大的 $\mathrm{n/2}$ 的子块用换根 $\mathrm{DP}$ 求解即可，这里开了一个前缀/后缀的最大值数组，会方便很多. 

#include 
#include 
#include 
#include 
#include 
#define N  400009 
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
vectorG[N];
int n , size[N], son[N], f[N], g[N], ans[N], mk[N];    
void dfs(int x, int ff) {
	size[x] = 1;       
	for(int i = 0; i < G[x].size() ; ++ i) {
		int v = G[x][i]; 
		if(v == ff) continue;  
		dfs(v, x); 
		if(size[v] <= n / 2) 
			f[x] = max(f[x], size[v]); 
		else 
			f[x] = max(f[x], f[v]);  
		size[x] += size[v];  
		mk[x] = max(mk[x], size[v]); 
		if(size[v] > size[son[x]]) son[x] = v;  
	}
	mk[x] = max(mk[x], n - size[x]); 
	if(n - size[x] > size[son[x]]) son[x] = ff;              
} 
void dfs2(int x, int ff) {
	vectorpre, suf;  
	for(int i = 0; i < G[x].size() ; ++ i) {
		int v = G[x][i];     
		if(v != ff) {
			if(size[v] <= n / 2) 
				pre.pb(size[v]), suf.pb(size[v]); 
			else 
				pre.pb(f[v]), suf.pb(f[v]);    
		}
	}
	for(int i = 1; i < pre.size() ; ++ i) 
		pre[i] = max(pre[i - 1], pre[i]); 
	for(int i = suf.size() - 2; i >= 0; -- i) 
		suf[i] = max(suf[i], suf[i + 1]);   
	int now = 0; 
	for(int i = 0; i < G[x].size() ; ++ i) {
		int v = G[x][i]; 
		if(v == ff) continue;     
		if(now > 0) 
			g[v] = max(g[v], pre[now - 1]); 
		if(now < suf.size() - 1) 
			g[v] = max(g[v], suf[now + 1]);
		if(n - size[v] <= n / 2) 
			g[v] = max(g[v], n - size[v]); 
		else 
			g[v] = max(g[v], g[x]);         
		dfs2(v, x), ++ now; 
	}
}
int main() {
	// setIO("input");  
	scanf("%d", &n); 
	for(int i = 1; i < n ; ++ i) {
		int x, y; 
		scanf("%d%d", &x, &y); 
		G[x].pb(y); 
		G[y].pb(x); 		
	}
	dfs(1, 0); 
	dfs2(1, 0);        
	for(int i = 1; i <= n ; ++ i) {
		if(mk[i] <= n / 2) printf("1 "); 
		else {   
			if(n - size[i] > n / 2) {
				// 外面是不合法的.   
				if(n - size[i] - g[i] <= n / 2) 
					printf("1 ");
				else printf("0 "); 
			}
			else {
				int v = son[i];   
				if(size[v] - f[v] <= n / 2) 
					printf("1 "); 
				else printf("0 ");  
			}
		}
	}
	return 0; 
}

Count Pairs

来源：CF1188B, 2300 

在等式两侧分别乘上一个差，左边就能凑成平方差的形式. 

然后最后可以把和 $\mathrm{i,j}$ 相关的分别移到两侧，用 $\mathrm{map}$ 来统计即可. 

#include  
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
ll mod, K; 
ll calc(ll x) {
	return (x * x % mod * x % mod * x % mod - K * x % mod + mod) % mod; 
} 
int n; 
mapmp; 
int main() {
	// setIO("input"); 
	scanf("%d%lld%lld", &n, &mod, &K); 
	ll ans = 0; 
	for(int i = 1; i <= n ; ++ i) {
		ll x; 
		scanf("%lld", &x);  
		ll p = calc(x);  
		ans += mp[p];   
		mp[p] = mp[p] + 1;  
	}
	printf("%lld", ans); 
	return 0; 
}

A Simple Task

来源：CF558E, 2300 

对于每一个字母的位置开一个线段树，然后排序的话就是两个区间赋值操作.  

全程都用线段树维护，由于空间十分充裕所以该做法是正确的. 

#include 
#define N  100009 
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin)  
using namespace std; 
int n , Q; 
char str[N]; 
struct Seg {
	#define ls now << 1 
	#define rs now << 1 | 1 
	int sum[N << 2], lazy[N << 2];     
	void mark(int l, int r, int now, int v) {  
		sum[now] = (r - l + 1) * v;  
		lazy[now] = v;    
	}
	void pushdown(int l, int r, int now) {
		if(lazy[now] != -1) {
			int mid = (l + r) >> 1;  
			mark(l, mid, ls, lazy[now]); 
			mark(mid + 1, r, rs, lazy[now]); 
			lazy[now] = -1; 
		}
	}
	void build(int l, int r, int now) {
		sum[now] = 0, lazy[now] = -1; 
		if(l == r) return ; 
		int mid = (l + r) >> 1;  
		build(l, mid, ls), build(mid + 1, r, rs); 
	}
	void pushup(int now) {
		sum[now] = sum[ls] + sum[rs]; 
	}
	void update(int l, int r, int now, int L, int R, int v) {
		if(l >= L && r <= R) {
			mark(l, r, now, v); 
			return ;  
		}
		int mid = (l + r) >> 1; 
		pushdown(l, r, now);  
		if(L <= mid)  update(l, mid, ls, L, R, v); 
		if(R > mid)   update(mid + 1, r, rs, L, R, v);  
		pushup(now); 
	}
	void modify(int l, int r, int now, int p, int v) {
		if(l == r) {
			sum[now] = v;  
			return ; 
		}
		int mid = (l + r) >> 1;  
		if(p <= mid) modify(l, mid, ls, p, v); 
		else modify(mid + 1, r, rs, p, v); 
		pushup(now); 
	}
	int query(int l, int r, int now, int L, int R) {
		if(l >= L && r <= R) {
			return sum[now]; 
		}
		pushdown(l, r, now);  
		int mid = (l + r) >> 1, re = 0; 
		if(L <= mid)  re += query(l, mid, ls, L, R); 
		if(R > mid)   re += query(mid + 1, r, rs, L, R); 
		return re;   
	}
	#undef ls 
	#undef rs
}T[26];  
int main() {
	// setIO("input"); 
	scanf("%d%d", &n, &Q); 
	for(int i = 0; i < 26 ; ++ i) {
		T[i].build(1, n, 1); 
	}
	scanf("%s", str + 1);  
	for(int i = 1; i <= n ; ++ i) {
		int c = str[i] - 'a'; 
		T[c].modify(1, n, 1, i, 1);  
		// 修改为 1.  
	}
	for(int i = 1; i <= Q; ++ i) {
		int l, r, k; 
		scanf("%d%d%d", &l, &r, &k); 
		if(k == 1) {
			// 这个是升序. 
			int pre = 0; 
			for(int j = 0; j < 26; ++ j) {
				int cur = T[j].query(1, n, 1, l, r);   
				if(!cur) continue;    
				T[j].update(1, n, 1, l, r, 0);     
				T[j].update(1, n, 1, l + pre, l + pre + cur - 1, 1);  
				pre += cur;  
			}
		}
		else {
			int pre = 0; 
			for(int j = 25; j >= 0; -- j) {
				int cur = T[j].query(1, n, 1, l, r); 
				if(!cur) continue;  
				T[j].update(1, n, 1, l, r, 0); 
				T[j].update(1, n, 1, l + pre, l + pre + cur - 1, 1); 
				pre += cur;  
			}
		}
	}  
	for(int i = 1; i <= n ; ++ i) {
		for(int j = 0; j < 26; ++ j) {
			if(T[j].query(1, n, 1, i, i)) {
				printf("%c", 'a' + j);  
			}
		}
	}
	return 0; 
}

Another Filling the Grid

来源：CF1228E, 2300  

二项式反演：只要满足钦定的情况把恰好的情况算了组合数次就可以使用.  

这道题中钦定几行/几列不选，然后用二项式反演计算恰好的情况即可.  

#include 
#include 
#include 
#include 
#include 
#define N  303
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
const int mod = (int)1e9 + 7; 
int n , K , fac[N], inv[N]; 
int qpow(int x, int y) {
	int tmp = 1; 
	for( ; y ; y >>= 1, x = (ll)x * x % mod) {
		if(y & 1) tmp = (ll)tmp * x % mod; 
	}
	return tmp ; 
}
int get_inv(int x) {
	return qpow(x, mod - 2); 
}
void init() {
	fac[0] = inv[0] = 1; 
	for(int i = 1; i < N ; ++ i) {
		fac[i] = (ll)fac[i - 1] * i % mod; 
		inv[i] = get_inv(fac[i]); 
	}
} 
int C(int x, int y) {
	return (ll)fac[x] * inv[y] % mod * inv[x - y] % mod;  
}
int F(int x, int y) {
	return (ll)C(n, x) * C(n, y) % mod * qpow(K - 1, n * n - (n - x) * (n - y)) % mod * qpow(K, (n - x) * (n - y)) % mod;   
}
int main() {
	// setIO("input");
	scanf("%d%d", &n, &K); 
	init(); 
	if(K == 1) printf("1"); 
	else {
		int ans = 0; 
		for(int i = 0; i <= n ; ++ i) {
			for(int j = 0; j <= n ; ++ j) {
				int d = (i + j) & 1 ? (mod - 1) : 1;   
				(ans += (ll)d * F(i, j) % mod) %= mod; 
			}
		}
		printf("%d", ans); 
	}
	return 0; 
}

Road Improvement

来源：CF543D, 2300  

这道题是一个换根 $\mathrm{DP}$, 但是无法求逆元.  

当逆元不存在的情况，这种问题的套路就是用前缀/后缀积来替代逆元.  

那么这道题中只需对每个点的所有儿子维护一个前后缀的积，然后转移即可. 

#include 
#include 
#include 
#include 
#include  
#define N  200009 
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
const int mod = (int)1e9 + 7; 
int qpow(int x, int y) {
	int tmp = 1;   
	for( ; y ; y >>= 1, x = (ll)x * x % mod) 
		if(y & 1) tmp = (ll)tmp * x % mod ; 
	return tmp ; 
}
int get_inv(int x) {
	return qpow(x, mod - 2); 
}
vectorF[N]; 
int fa[N], f[N], g[N], n , G[N] ;      
void dfs(int x, int ff) { 
	int tmp = 1;  
	for(int i = 0; i < F[x].size() ; ++ i) {
		int v = F[x][i]; 
		if(v == ff) continue;  
		dfs(v, x);  
		tmp  = (ll)tmp * (ll)(1 + g[v]) % mod;  
	}
	g[x] = tmp ; 
}
int ans[N]; 
void dfs2(int x, int ff) {   
	ans[x] = 1;
	vectorpre, suf;      
	for(int i = 0; i < F[x].size() ; ++ i) {
		int v = F[x][i]; 
		ans[x] = (ll)ans[x] * (g[v] + 1) % mod;    
		if(v != ff) {
			pre.pb(g[v] + 1); 
			suf.pb(g[v] + 1);    	
		}
	}
	for(int i = 1; i < pre.size() ; ++ i) 
		pre[i] = (ll)pre[i - 1] * pre[i] % mod ; 
	for(int i = suf.size() - 2; i >= 0; -- i) 
		suf[i] = (ll)suf[i + 1] * suf[i] % mod ;
	int now = 0;      
	for(int i = 0; i < F[x].size() ; ++ i) {
		int v = F[x][i];
		if(v == ff) continue;    
		// 更新 g[x]  
		g[x] = g[ff] + 1;      
		if(now  > 0) g[x] = (ll)g[x] * pre[now - 1] % mod; 
		if(now < suf.size() - 1) 
			g[x] = (ll)g[x] * suf[now + 1] % mod;  
		dfs2(v, x), ++ now;   
	}    
}
int main() {
	// setIO("input"); 
	scanf("%d", &n); 
	for(int i = 2; i <= n ; ++ i) {
		scanf("%d", &fa[i]); 
		F[fa[i]].pb(i); 
		F[i].pb(fa[i]);   
	}
	dfs(1, 0);    
	dfs2(1, 0);   
	for(int i = 1; i <= n ; ++ i) printf("%d ", ans[i]); 
	return 0; 
}

Pairwise Modulo

来源：CF1553F, 2300 

把式子拆开化成两个部分，然后前半部分可以调和级数在乘上 $\mathrm{O(\log n)} $ 处理.  

后一半部分的话是 $\mathrm{a[k + 1]/a[i] = t}$ 这种形式，不妨考虑每一个 $\mathrm{a[i]}$ 对于后面的贡献：

即枚举那个 $\mathrm{t}$, 然后给 $\mathrm{a[i] \times t}$ 加上 $\mathrm{a[i]}$ 的贡献即可.  

#include 
#define N  400009 
#define ll long long 
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)   
using namespace std;
int n , a[N]; 
ll sum[N]; 
struct BIT {
	ll C[N]; 
	int lowbit(int x) { return x & (-x); }  
	void upd(int x, int v) {
		while(x < N) {
			C[x] += v, x += lowbit(x); 
		}
	}
	ll query(int x) {
		ll tmp = 0; 
		while(x > 0) {
			tmp += C[x], x -= lowbit(x); 
		}
		return tmp; 
	}
	ll calc(int l, int r) {
		if(l > r) return 0ll; 
		return query(r) - query(l - 1); 
	}
}T1, T2; 
int main() {
	// asetIO("input"); 
	scanf("%d", &n);
	int mx = 0 ;  
	for(int i = 1; i <= n ; ++ i) {
		scanf("%d", &a[i]); 
		mx = max(mx, a[i]); 
		sum[i] = sum[i - 1] + a[i]; 
	}
	ll ans = 0; 
	for(int i = 1; i <= n ; ++ i) {
		ll d1 = sum[i - 1];    
		for(int j = 1; j * a[i] <= mx; ++ j) {
			// a[p] is [j * a[i], (j + 1) * a[i])         
			d1 -= 1ll * j * a[i] * T1.calc(j * a[i], min(mx, (j + 1) * a[i] - 1));    
		}
		T1.upd(a[i], 1);    

		ll d2 = 1ll * (i - 1) * a[i];   
		d2 -= T2.calc(1, a[i]);    
		for(int j = 1; a[i] * j <= mx ; ++ j) 
			T2.upd(a[i] * j, a[i]);            
		ans += d1 + d2; 
		printf("%lld ", ans); 
	}
	return 0; 
}

Array GCD

来源：CF623B, 2300  

有一个非常关键的信息：因为删除的是连续段，所以 $\mathrm{a[1]}$ 和 $\mathrm{a[n]}$ 并不可能都删除掉.  

那么就可以枚举每一种可能的质因子然后进行 $\mathrm{DP}$ 了，设计 $\mathrm{DP}$ 状态为 $\mathrm{f[0][x],f[1][x],f[2][x]}$.  

分别表示没有删除，正在删除，删除完毕三个状态，然后转移即可.  

#include 
#include 
#include 
#include 
#define N  1000009 
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
int n , A, B, a[N]; 
vectorg;  
void divide(int x) {
	for(int i = 2; i * i <= x ; ++ i) {
		if(x % i == 0) {
			g.pb(i); 
			while(x % i == 0) x /= i; 
		}
	}
	if(x > 1) g.pb(x); 
}
ll F[3][N];   
ll solve(int prime) {   
	// F[0][x] : 并没有删除  
	// F[1][x] : 正在删除  
	// F[2][x] : 删除完毕了     
	memset(F, 0x3f3f3f, sizeof(F));  
	F[0][0] = 0;             
	for(int i = 1; i <= n ; ++ i) {
		int ty = 0;  
		if(a[i] % prime == 0) ty = 0; 
		else if((a[i] - 1) % prime == 0 || (a[i] + 1) % prime == 0) ty = 1; 
		else ty = 2;    


		if(ty == 0) {
			F[0][i] = F[0][i - 1];        
			F[2][i] = min(F[2][i - 1], F[1][i - 1]);   
		}
		if(ty == 1) {
			// 这个是 + 1 / -1   
			F[0][i] = F[0][i - 1] + 1ll * B;    
			F[2][i] = min(F[2][i - 1], F[1][i - 1]) + 1ll * B;       
		}
		F[1][i] = min(F[0][i - 1], F[1][i - 1]) + 1ll * A;                  
	}
	return min(min(F[0][n], F[1][n]), F[2][n]); 
}
int main() {
	// setIO("input");
	scanf("%d%d%d", &n, &A, &B);  
	for(int i = 1; i <= n ; ++ i) {
		scanf("%d", &a[i]); 
	}     
	divide(a[1]), divide(a[n]);   
	divide(a[1] - 1), divide(a[1] + 1); 
	divide(a[n] - 1), divide(a[n] + 1); 
	ll ans = 100000000000000000ll;  
	for(int i = 0 ; i < g.size() ; ++ i) {    
		ans = min(ans, solve(g[i]));     
	}
	printf("%lld", ans);  
	return 0; 
}

Optimal Insertion

来源：CF1601C, 2300  

考虑 $\mathrm{b}$ 序列只有 1 个数字怎么做：直接贪心塞到 $\mathrm{a}$ 中的最佳位置.  

然后有多个数字时答案的下界就是把每个数字都塞到各自的最优位置.  

但问题是我们无法预知 $\mathrm{b}$ 中内部的数字会产生多少逆序对.  

但是我们发现随着数字递增，最佳位置不可能递减，所以把每个数字独立开来各自求最佳位置即可.  

#include 
#define N  2000009 
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
struct BIT {
	int C[N << 1]; 
	int lowbit(int x) { return x & (-x); }  
	void upd(int x, int v) {
		while(x < N) C[x] += v, x += lowbit(x); 
	}	
	void clr(int x) {
		while(x < N) C[x] = 0, x += lowbit(x); 
	}
	int query(int x) {
		int tmp = 0; 
		while(x > 0) tmp += C[x], x -= lowbit(x); 
		return tmp;  
	}
}T;  
struct Segment_Tree {
	#define ls now << 1 
	#define rs now << 1 | 1
	int minv[N << 2], sum[N << 2]; 
	void build(int l, int r, int now) {
		minv[now] = N, sum[now] = 0; 
		if(l == r) return ; 
		int mid = (l + r) >> 1; 
		build(l, mid, ls), build(mid + 1, r, rs); 
	} 
	void pushup(int now) {
		sum[now] = sum[ls] + sum[rs]; 
		minv[now] = min(minv[ls], sum[ls] + minv[rs]); 
	}
	void update(int l, int r, int now, int p, int v) {
		if(l == r) {
			sum[now] += v;  
			minv[now] = min(0, sum[now]); 
			return ; 
		}
		int mid = (l + r) >> 1;    
		if(p <= mid) update(l, mid, ls, p, v); 
		else update(mid + 1, r, rs, p, v); 
		pushup(now); 
	}    
	#undef ls 
	#undef rs 
}se;  
struct data {
	int p, v; 
	data(int p = 0, int v = 0):p(p), v(v){}  
}q[N];  
bool cmp(data i, data j) {
	return i.v < j.v;  
}
int n , m , a[N], b[N], A[N];    
void solve() {
	scanf("%d%d", &n, &m); 
	ll ans = 0; 
	int tot = 0; 
	for(int i = 1; i <= n ; ++ i) scanf("%d", &a[i]), A[++ tot] = a[i];  
	for(int i = 1; i <= m ; ++ i) scanf("%d", &b[i]), A[++ tot] = b[i]; 
	sort(A + 1, A + 1 + tot); 
	for(int i = 1; i <= n ; ++ i) a[i] = lower_bound(A + 1, A + 1 + tot, a[i]) - A ; 
	for(int i = 1; i <= m ; ++ i) b[i] = lower_bound(A + 1, A + 1 + tot, b[i]) - A ;    
	for(int i = 1; i <= n ; ++ i) {
		ans += 1ll * i - 1ll - 1ll * T.query(a[i]);   
		T.upd(a[i], 1);  
	}
	sort(b + 1, b + 1 + m);      
	for(int i = 1; i <= m ; ++ i) 
		ans += T.query(b[i] - 1);        
	se.build(1, n + 1, 1);        
	for(int i = 1; i <= n ; ++ i) {
		q[i].p = i, q[i].v = a[i]; 
	}  
	sort(q + 1, q + 1 + n, cmp); 
	// 等于的，不变
	// 小于的，- 1
	// 大于的，+ 1           
	for(int i = 1; i <= n + 1; ++ i) 
		se.update(1, n + 1, 1, i, 1);     
	for(int i = 1, j = 1; i <= m ; ++ i) {
		if(b[i] != b[i - 1]) {    
			for(int k = j - 1; k >= 1; -- k) {
				if(q[k].v == b[i - 1])
					se.update(1, n + 1, 1, q[k].p, -1);       
				else break; 
			}
			while(j <= n && q[j].v < b[i]) {
				se.update(1, n + 1, 1, q[j].p, -2);   
				++ j;   
			}
			while(j <= n && q[j].v == b[i]) {
				se.update(1, n + 1, 1, q[j].p, -1);   
				++ j;  
			}
		}
		// -1 和 不变.  
		ans += 1ll * se.minv[1];      
	}
	printf("%lld\n", ans); 
	for(int i = 1; i <= n ; ++ i) T.clr(a[i]); 
}
int main() {
	// setIO("input"); 
	int Q; 
	scanf("%d", &Q); 
	while(Q -- ) solve(); 
	return 0; 
}

Company

来源：CF1062E, 2300 

显然对于一堆点的 $\mathrm{lca}$ 来说只需看 $\mathrm{dfs}$ 序最小和最大的 $\mathrm{lca}$ 就行. 

那么删除的时候也肯定删除最小/最大的点，然后就写两个 $\mathrm{ST}$ 表和倍增求 $\mathrm{lca}$ 即可.  

#include 
#define N  100009
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin)  
using namespace std;
vectorG[N];  
int n , Q, Lg[N], dep[N], fa[N][18], mi[N][18], ma[N][18], dfn[N], scc;          
void dfs(int x) {
	dfn[x] = ++ scc, dep[x] = dep[fa[x][0]] + 1; 
	for(int i = 0; i < G[x].size() ; ++ i) 
		dfs(G[x][i]); 
}
void init() {
	for(int i = 2; i < N ; ++ i) Lg[i] = Lg[i >> 1] + 1; 
	for(int i = 1; i <= n ; ++ i) mi[i][0] = ma[i][0] = i; 
	for(int j = 1; (1 << j) <= n ; ++ j) {
		for(int i = 1; i + ( 1 << j) - 1 <= n ; ++ i) {
			if(dfn[mi[i][j - 1]] < dfn[mi[i + (1 << (j - 1))][j - 1]]) 
				mi[i][j] = mi[i][j - 1]; 
			else mi[i][j] = mi[i + (1 << (j - 1))][j - 1]; 
			if(dfn[ma[i][j - 1]] > dfn[ma[i + (1 << (j - 1))][j - 1]]) 
				ma[i][j] = ma[i][j - 1]; 
			else ma[i][j] = ma[i + (1 << (j - 1))][j - 1]; 

		}
	}
	// printf("%d %d\n", mi[4][1], mi[5][2]); 
}        
int qmin(int l, int r) {
	int p = Lg[r - l + 1]; 
	if(dfn[mi[l][p]] < dfn[mi[r - (1 << p) + 1][p]])      
		return mi[l][p]; 
	else return mi[r - (1 << p) + 1][p]; 
}
int qmax(int l, int r) {
	int p = Lg[r - l + 1]; 
	if(dfn[ma[l][p]] > dfn[ma[r - (1 << p) + 1][p]]) 
		return ma[l][p]; 
	else return ma[r - (1 << p) + 1][p];  
}
int get_lca(int x, int y) {
	if(dep[x] > dep[y]) swap(x, y);
	if(dep[x] != dep[y]) { 
		for(int i = 17; i >= 0; -- i) 
			if(dep[fa[y][i]] >= dep[x]) y = fa[y][i];
	}    
	if(x == y) return x; 
	for(int i = 17; i >= 0; -- i) 
		if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];     
	return fa[x][0];  
}
int calc(int l, int r) {
	// printf("%d %d\n", l, r); 
	int p1 = qmin(l, r); 
	int p2 = qmax(l, r);  
	return get_lca(p1, p2);   
}
int check(int l, int r, int det) {
	// [l, det - 1] and [det + 1, r]   
	if(det > l && det < r) 
		return dep[get_lca(calc(l, det - 1), calc(det + 1, r))]; 
	else if(det == l) return dep[calc(det + 1, r)];  
	else return dep[calc(l, det - 1)]; 
}
int main() {
	// setIO("input");     
	scanf("%d%d", &n, &Q); 
	for(int i = 2; i <= n ; ++ i) {
		scanf("%d", &fa[i][0]); 
		G[fa[i][0]].pb(i); 
	}   
	for(int j = 1; j < 18 ; ++ j) 
		for(int i = 1; i <= n ; ++ i) 
			fa[i][j] = fa[fa[i][j - 1]][j - 1];  
	dfs(1);  
	init();   
	// 预处理完毕了.  
	// 
	for(int i = 1; i <= Q; ++ i) {
		int l, r; 
		scanf("%d%d", &l, &r); 
		int pmin = qmin(l, r); 
		int pmax = qmax(l, r);   
		int p0 = check(l, r, pmin), p1 = check(l, r, pmax); 
		// printf("%d %d\n", pmax, pmin); 
		if(p0 > p1) {
			printf("%d %d\n", pmin, p0 - 1); 
		} 
		else {
			printf("%d %d\n", pmax, p1 - 1); 
		}  
	}
	return 0; 
}

Pursuit For Artifacts

来源：CF652E, 2300  

降智题.  

开始一直在想 $\mathrm{DFS}$ 树和返祖边那一套理论，然后就想不出来了.  

但是直接按照点双的思路思考的话就简单了：因为不能重复经过边，所以显然可以点双缩点.  

那么一个点双内存在 $\mathrm{1}$ 边就把这个团标为 1，然后点双之间的边就正常连.  

最后只需要看点双树上 $\mathrm{a,b}$ 两点之间是否有 1 边/ 1 点即可.  

#include  
#include 
#include 
#include   
#include 

Product Oriented Recurrence

来源：CF1182E, 2300 

直接考虑递推式时是 $\mathrm{\sum f(y) + b}$ 的形式，然后 $\mathrm{b}$ 不好处理. 

但是好在 $\mathrm{b}$ 是关于 $\mathrm{i}$ 线性的，所以在进行矩阵乘法的时候把后面的常数一起维护即可. 

#include 
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin)  
using namespace std; 
const int mod = (int)1e9 + 6;
ll f[5], n, c0;             
struct M {
	int len, C[6][6];   
	M(int t = 0) { 
		len = t; 
		memset(C, 0, sizeof(C)); 
	}
	void I() {   
		for(int i = 1; i <= len ; ++ i) C[i][i] = 1; 
	}   
	M operator*(const M b) const {
		M c(len); 
		for(int k = 1; k <= len ; ++ k) {
			for(int i = 1; i <= len ; ++ i) {
				for(int j = 1; j <= len ; ++ j) { 
					(c.C[i][j] += (ll)C[i][k] * b.C[k][j] % mod) %= mod; 
				}
			}
		}
		return c; 
	}
};   
M operator^(M a, ll b) {
	M tmp(a.len); 
	tmp.I();  
	while(b) {
		if(b & 1) tmp = tmp * a; 
		b >>= 1, a = a * a; 
	}
	return tmp; 
}
ll qpow(ll x, ll y) {
	ll tmp = 1; 
	while(y) {
		if(y & 1) tmp = (ll)tmp * x % (mod + 1); 
		y >>= 1, x = (ll)x * x % (mod + 1); 
	}
	return tmp ; 
}
int main() {        
	// setIO("input"); 
	scanf("%lld%lld%lld%lld%lld", &n, &f[1], &f[2], &f[3], &c0);      
	M c(5);    
	for(int i = 1; i <= 5; ++ i) 
		c.C[i][1] = 1;
	c.C[1][2] = c.C[2][3] = c.C[4][4] = c.C[5][4] = c.C[5][5] = 1;
	c = c ^ (n - 3);            
	M F(3);   
	F.C[1][1] = F.C[2][1] = F.C[3][1] = F.C[1][2] = F.C[2][3] = 1;    
	F = F ^ (n - 3);   
	ll pc = qpow(c0, (ll)2 * c.C[5][1] % mod);              
	ll p1 = qpow(f[1], F.C[3][1]);  
	ll p2 = qpow(f[2], F.C[2][1]);      
	ll p3 = qpow(f[3], F.C[1][1]);     
	printf("%lld", (ll)pc * p1 % (mod + 1) * p2 % (mod + 1) * p3 % (mod + 1));   
	return 0; 
}

Dogeforces

来源：CF1494D, 2300  

写了一个分治算法.  

对于一个叶子节点来说，可以知道这个叶子节点到根的路径.  

然后对于其他的叶子节点，可以知道与选定叶子节点 $\mathrm{lca}$ 处的值.  

那么就根据 $\mathrm{lca}$ 处的值对叶子节点分类，然后进行分治即可.  

有一些细节需要注意一下. 

#include 
#define ll long long 
#define pb push_back 
#define N  504 
#define setIO(s) freopen(s".in","r",stdin)  
using namespace std;
setse; 
set::iterator it;  
int leaf, val[N][N], cnt, fa[N * N], fin[N * N];  
vectortmp; 
void solve(vectorg, int ff) {                            
	int p = g[0], rt = 0, pr = g[0];   
	fin[rt = p] = val[p][p];   
	se.clear(); 
	for(int i = 1; i < g.size() ; ++ i) {
		int q = g[i]; 
		se.insert(val[p][q]);   
	}
	vectorh;          
	for(it = se.begin(); it != se.end() ; it ++ ) { 
		int now = *it;   
		if(now == fin[ff]) {
			fa[pr] = ff, pr = rt = ff; 
		}
		else {
			rt = ++ cnt; 
			fa[pr] = cnt, fin[cnt] = now, pr = cnt; 
		} 
		h.pb(now);       
	}	              
	pr = g[0];     
	for(int i = 0; i < h.size() ; ++ i) { 
		vectortp;  
		tp.clear();     
		for(int j = 1; j < g.size() ; ++ j) { 
			if(val[p][g[j]] == h[i]) {
				tp.pb(g[j]);      
			}
		}      
		solve(tp, fa[pr]), pr = fa[pr];      
	}          
	if(rt != ff)  fa[rt] = ff;         
}
int main() {
	// setIO("input"); 
	scanf("%d", &leaf); 
	for(int i = 1; i <= leaf; ++ i) 
		for(int j = 1; j <= leaf; ++ j) scanf("%d", &val[i][j]); 
	cnt = leaf; 
	for(int i = 1; i <= leaf; ++ i) 
		tmp.pb(i); 
	solve(tmp, 0);
	printf("%d\n", cnt); 
	for(int i = 1; i <= cnt; ++ i) printf("%d ", fin[i]); 
	printf("\n"); 
	for(int i = 1; i <= cnt; ++ i) if(!fa[i]) printf("%d\n", i); 
	for(int i = 1; i <= cnt; ++ i) {
		if(fa[i]) printf("%d %d\n", i, fa[i]); 
	} 
	return 0;
}

Shovels Shop

来源：CF1154F, 2100  

肯定会买最便宜的 $\mathrm{K}$ 个，那么直接令 $\mathrm{f[x]}$ 表示购买 $\mathrm{x}$ 个的花费. 

然后 $\mathrm{O(k^2)}$ 转移即可. 

#include 
#define N  200009 
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin)  
using namespace std; 
ll suf[N], f[N]; 
int n , m, K, a[N],  x[N], y[N]; 
int main() {
	// setIO("input"); 
	scanf("%d%d%d", &n, &m, &K); 
	for(int i = 1; i <= n ; ++ i) {
		scanf("%d", &a[i]); 
	}
	for(int i = 1; i <= m ; ++ i) {
		scanf("%d%d", &x[i], &y[i]); 
		y[i] = x[i] - y[i];         
	}
	sort(a + 1, a + 1 + n);        
	for(int i = 1; i <= K ; ++ i) 
		suf[i] = suf[i - 1] + a[i];  
	f[0] = 0;    
	for(int i = 1; i <= K ; ++ i) {
		f[i] = f[i - 1] + a[i];  
		for(int j = 1; j <= m ; ++ j) {
			if(x[j] <= i) f[i] = min(f[i], f[i - x[j]] + suf[i] - suf[i - y[j]]);    
		}  
	} 
	printf("%lld", f[K]); 
	return 0; 	
}

Increase Sequence

来源：CF466D, 2100  

一道差分题.   

令 $\mathrm{a[i]' = h - a[i]}$ 即与 $\mathrm{h}$ 相差多少，然后我们想通过对这个序列 $\mathrm{-1}$ 使之变成全 0.  

然后这种问题就可以用差分数组来解决了，即每次可以将一个位置 +1， 一个位置 -1 且次数仅为 1 次.   

然后每次 $\mathrm{+1}$ 就是一个与前面 $\mathrm{-1}$ 的匹配问题，求解即可. 

#include 
#define ll long long 
#define N  2003 
#define pb push_back  
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
int n, h, a[N], d[N];   
const int mod = (int)1e9 + 7;  
int main() {
	// setIO("input");  
	scanf("%d%d", &n, &h);  
	for(int i = 1; i <= n ; ++ i) {
		scanf("%d", &a[i]);  
		a[i] = h - a[i]; 
		if(a[i] < 0) {
			printf("0"); 
			return 0; 
		}
	}
	for(int i = 1; i <= n ; ++ i)
		d[i] = a[i] - a[i - 1];   
	ll ans = 1; 
	int det = 0;  
	for(int i = 1; i <= n ; ++ i) {
		if(abs(d[i]) > 1) {
			printf("0"); 
			return 0; 
		}
		if(d[i] == 1) {
			// 加一个 -1   
			det -= 1;                
		}
		if(d[i] == -1) {
			// 加一个 +1
			if(det >= 0) {
				printf("0"); 
				return 0; 
			}
			ans = (ll)ans * abs(det) % mod;   
			det += 1;   
		}
		if(d[i] == 0) {      
			if(det < 0) {
				// +1, -1 
				(ans += (ll)ans % mod * abs(det) % mod) %= mod;      
			}
		}
	}
	if(det == 0 || det == -1) printf("%lld", ans); 
	else printf("0");  
	return 0; 
}

Pencils and Boxes

来源：CF985E, 2100 

把所有数字从小到大排序，那么每次一定是连续的一段放到一起.  

这样的话就可以从左到右进行 $\mathrm{DP}$ 了，每次枚举最靠右选几个. 

然后这个可选择的数量也是一段区间，直接用前缀数组判断这个区间内有无合法状态即可. 

#include  
#define N  500009 
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r", stdin) 
using namespace std; 
int n, K, D, a[N], sum[N], dp[N];  
int S(int l, int r) {
	if(l == 0) return sum[r]; 
	else return sum[r] - sum[l - 1];   
}
int main() {
	// setIO("input"); 
	scanf("%d%d%d", &n, &K, &D); 
	for(int i = 1; i <= n; ++ i) {
		scanf("%d", &a[i]); 
	}
	sort(a + 1, a + 1 + n);
	dp[0] = sum[0] = 1;          
	for(int i = 1; i <= n ; ++ i) {
		int R = i - K + 1, L = lower_bound(a + 1, a + 1 + n, a[i] - D) - a;    
		// L: 第一个大于等于的.      
		// 则 [L, R] 是当前段的左端点可行处.   
		if(L <= R) {
			dp[i] = S(L - 1, R - 1) ? 1 : 0;  
		}
		sum[i] = sum[i - 1] + dp[i]; 
	}              
	printf("%s", dp[n] ? "YES" : "NO");  	
	return 0; 
}

Anton and Tree

来源：CF734E, 2100   

把颜色相同的连通块缩点，然后考虑如何进行染色.     

对于一跳链来说，答案就是从链的中间开始染色，每次会向两侧拓展一次.  

树的情况答案肯定不会小于链的情况，也肯定不会小于直径的情况.  

直接从直径的中心开始拓展即可取到答案的下界，所以在缩点的树上求一个树的直径即可. 

#include 
#include 
#include 
#include 
#define N  200009 
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int ans; 
int col[N], n, p[N], f[N], se[N];    
vectorG[N], V[N];    
int find(int x) {
	return p[x] == x ? x : p[x] = find(p[x]); 
}
void init() {
	for(int i = 0; i < N ; ++ i) p[i] = i; 
}
void merge(int x, int y) {
	x = find(x), y = find(y); 
	if(x == y) return ;
	p[x] = y; 
}
void dfs(int x, int ff) {
	if(ff && col[x] != col[ff]) { 
		V[find(ff)].pb(find(x));     
	}
	for(int i = 0; i < G[x].size() ; ++ i) {
		if(G[x][i] != ff) dfs(G[x][i], x); 
	}
}
void dfs2(int x) {
	f[x] = 1; 
	for(int i = 0; i < V[x].size() ; ++ i) {
		int v = V[x][i]; 
		dfs2(v);	
		ans = max(ans, f[x] + f[v]);   
		f[x] = max(f[x], f[v] + 1);  
	}
}
int main() {
	// setIO("input"); 
	init(); 
	scanf("%d", &n); 
	for(int i = 1; i <= n ; ++ i) scanf("%d", &col[i]); 
	for(int i = 1; i < n ; ++ i) {
		int x, y; 
		scanf("%d%d", &x, &y); 
		G[x].pb(y); 
		G[y].pb(x); 
		if(col[x] == col[y]) {
			merge(x, y); 
		}
	}
	dfs(1, 0);     
	dfs2(find(1)); 
	printf("%d\n", ans / 2);   
	return 0; 
}

OpenStreetMap

来源：CF1195E, 2100  

二维 $\mathrm{RMQ}$ 来做，不妨先对每一个列求一次，然后放到一个二维数组里.

最后再对行求一遍 $\mathrm{RMQ}$ 即可.  

#include  
#define N  3004 
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
int Lg[N]; 
ll  ans; 
int n, m, x0, Y0, mod, A, B, g[N * N], mi[N][N], f[N][20];    
void init() {
	for(int i = 1; i <= n * m ; ++ i) {
		g[i] = (ll)((ll)g[i - 1] * x0 % mod + Y0) % mod;    
	}
	Lg[1] = 0; 
	for(int i = 2; i < N ; ++ i) Lg[i] = Lg[i >> 1] + 1; 
}
// 空间并不够大.
int Query(int l, int r) {
	int p = Lg[r - l + 1]; 
	return min(f[l][p], f[r - (1 << p) + 1][p]);   
}
void solve(int c) {
	// c 为指定的列.        
	for(int i = 1; i <= n ; ++ i) f[i][0] = g[(i - 1) * m + c - 1];    
	for(int j = 1; (1 << j) <= n ; ++ j) {
		for(int i = 1; i + (1 << j) - 1 <= n ; ++ i) {
			f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);    
		}
	}
	for(int i = 1; i + A - 1 <= n ; ++ i) {
		mi[i][c] = Query(i, i + A - 1);     
	}
}     
void calc(int r) {
	// 第 r 行.  
	for(int i = 1; i <= m ; ++ i) f[i][0] = mi[r][i];     
	for(int j = 1; (1 << j) <= m ; ++ j) {
		for(int i = 1; i + (1 << j) - 1 <= m ; ++ i) {
			f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);   
		}
	}
	for(int i = B; i <= m ; ++ i) {
		// printf("%d %lld\n", Query(i - B + 1, i), ans); 
		ans += Query(i - B + 1, i);     
	}
}
int main() {
	// setIO("input"); 
	scanf("%d%d%d%d", &n, &m, &A, &B); 
	scanf("%d%d%d%d", &g[0], &x0, &Y0, &mod); 
	init();   
	for(int i = 1; i <= m ; ++ i) solve(i); 
	// 把每一列的都处理完毕.  
	for(int i = 1; i + A - 1 <= n ; ++ i) {
		calc(i); 
	}	
	printf("%lld", ans); 
	return 0; 
}

Mishka and Interesting sum

来源：CF703D, 2100  

区间异或和就是出现次数奇数次的数的异或和.  

那么偶数次就是所有不同的数异或上奇数次，求不同的数字就用离线树状数组即可.

#include 
#define N  1000009 
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin)  
using namespace std;
maplst;
int C[N], n, a[N], m ;  
struct Query {
	int l, r, id; 
}q[N]; 
bool cmp(Query i, Query j) {
	return i.r < j.r; 
}
int lowbit(int x) {
	return x & (-x); 
}
void upd(int x, int v) {
	while(x < N) {
		C[x] ^= v; 
		x += lowbit(x); 
	}
}
int query(int x) {
	int tmp = 0; 
	while(x > 0) {
		tmp ^= C[x];
		x -= lowbit(x); 
	}
	return tmp; 
}
int ans[N], pre[N]; 
int main() {
	// setIO("input"); 
	scanf("%d", &n); 
	for(int i = 1; i <= n ; ++ i) {
		scanf("%d", &a[i]);
		pre[i] = pre[i - 1] ^ a[i];   
	}
	scanf("%d", &m); 
	for(int i = 1; i <= m ; ++ i) {
		scanf("%d%d", &q[i].l, &q[i].r); 
		q[i].id = i;  
	}
	sort(q + 1, q + 1 + m, cmp); 
	for(int i = 1, j = 1; i <= m ; ++ i) {
		while(j <= q[i].r) {    
			if(lst[a[j]]) {
				upd(lst[a[j]], a[j]);   
			}
			lst[a[j]] = j;  
			upd(j, a[j]); 
			++ j; 
		}
		ans[q[i].id] = pre[q[i].r] ^ pre[q[i].l - 1] ^ query(q[i].r) ^ query(q[i].l - 1); 
	}
	for(int i = 1; i <= m ; ++ i) {
		printf("%d\n", ans[i]); 
	}
	return 0;
}

Duff in the Army

来源：CF587C, 2200  

直接上树链剖分维护每个区间内前 10 小的编号即可. 

#include 
#define N  100009 
#define ll long long 
#define pb push_back
#define ls now << 1 
#define rs now << 1 | 1  
#define setIO(s) freopen(s".in","r",stdin)  
using namespace std;   
vectorG[N], ID[N];   
int n , m, Q, dfn[N], bu[N], fa[N], dep[N], top[N], size[N], son[N], scc;  
struct data {
	vectorid;
	data() { id.clear(); }  
	data operator+(const data b) const {
		data c;     
		for(int i = 0; i < id.size() ; ++ i) c.id.pb(id[i]); 
		for(int i = 0; i < b.id.size() ; ++ i) c.id.pb(b.id[i]); 
		sort(c.id.begin(), c.id.end());   
		while(c.id.size() > 10) c.id.pop_back(); 
		return c; 
	}  
}s[N << 2]; 
void dfs1(int x, int ff) {
	size[x] = 1, fa[x] = ff, dep[x] = dep[ff] + 1; 
	for(int i = 0; i < G[x].size() ; ++ i) {
		int v = G[x][i]; 
		if(v == ff) continue;  
		dfs1(v, x); 
		size[x] += size[v]; 
		if(size[v] > size[son[x]]) son[x] = v; 
	}
}
void dfs2(int x, int tp) {
	top[x] = tp; 
	dfn[x] = ++ scc, bu[dfn[x]] = x; 
	if(son[x]) dfs2(son[x],tp); 
	for(int i = 0; i < G[x].size() ; ++ i) {
		int v = G[x][i]; 
		if(v == fa[x] || v == son[x]) continue;  
		dfs2(v, v); 
	}
}              
void update(int l, int r, int now, int p, data g) {   
	if(l == r) {
		s[now] = s[now] + g;
		return ; 
	}
	int mid = (l + r) >> 1;      
	if(p <= mid) update(l, mid, ls, p, g); 
	else update(mid + 1, r, rs, p, g); 
	s[now] = s[ls] + s[rs];  
}
data query(int l, int r, int now, int L, int R) {
	if(l >= L && r <= R) return s[now]; 
	int mid = (l + r) >> 1; 
	if(L <= mid && R > mid) return query(l, mid, ls, L, R) + query(mid + 1, r, rs, L, R); 
	else if(L <= mid) return query(l, mid, ls, L, R); 
	else return query(mid + 1, r, rs, L, R); 
}
void solve(int x, int y, int z) {
	data fin;  
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);  
		// 每次跳 x   
		fin = fin + query(1, n, 1, dfn[top[x]], dfn[x]);   
		x = fa[top[x]]; 
	}
	if(dep[x] > dep[y]) swap(x, y); 
	fin = fin + query(1, n, 1, dfn[x], dfn[y]);      
	z = min(z, (int)fin.id.size());          
	printf("%d ", z);
	sort(fin.id.begin(), fin.id.end());           
	for(int i = 0; i < z; ++ i) printf("%d ", fin.id[i]); 
	printf("\n");   
}
int main() {
	//setIO("input");     
	scanf("%d%d%d", &n, &m, &Q); 
	for(int i = 1; i < n ; ++ i) {
		int x, y; 
		scanf("%d%d", &x, &y); 
		G[x].pb(y); 
		G[y].pb(x); 
	}
	dfs1(1, 0); 
	dfs2(1, 1);     
	for(int i = 1; i <= m ; ++ i) {
		int p; 
		data c; 
		scanf("%d", &p),c.id.pb(i); 
		update(1, n, 1, dfn[p], c);    
	}   
	for(int i = 1; i <= Q; ++ i) {
		int x, y, z; 
		scanf("%d%d%d", &x, &y, &z); 
		solve(x, y, z); 
	}
	return 0; 
}

Magic Gems

来源：CF1117D, 2100 

直接做用组合数不太能做，不妨考虑递推.  

令 $\mathrm{f[i]}$ 表示凑满 $\mathrm{i}$ 个的方案数，然后考虑最后一个如何选择. 

1. 最后一个只贡献 1

2. 最后一个贡献 $\mathrm{m}$ 

然后这个递推就可以用矩阵乘法来做了. 

#include    
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin)  
using namespace std;
const int mod = (int)1e9 + 7;  
ll n; 
int m; 
struct M {
	int len, C[102][102];  
	M(int tp = 0) { 
		len = tp; 
		memset(C, 0, sizeof(C)); 
	}   
	void I() {
		for(int i = 1; i <= len ; ++ i) 
			C[i][i] = 1; 
	}
	M operator*(const M b) const {
		M c;
		c.len = len;  
		for(int k = 1; k <= len ; ++ k) {
			for(int i = 1; i <= len ; ++ i) {
				for(int j = 1; j <= len ; ++ j) {
					(c.C[i][j] += (ll)C[i][k] * b.C[k][j] % mod) %= mod; 
				}
			}
		}
		return c; 
	} 
};   
M operator^(M a, ll b) {
	M c; 
	c.len = a.len;  
	c.I();  
	while(b) {
		if(b & 1) c = c * a;   
		b >>= 1, a = a * a;   
	}
	return c; 
}
int main() {
	// setIO("input"); 
	scanf("%lld%d", &n, &m); 
	M tp; 
	tp.len = m;     
	for(int i = 1; i < m ; ++ i) 
		tp.C[i + 1][i] = 1;  
	tp.C[1][m] = tp.C[m][m] = 1;  
	M ans = tp ^ n;     
	ll fin = 0; 
	for(int i = 1; i <= m ; ++ i) 
		fin = (ll)(fin + ans.C[i][1]) % mod; 
	printf("%lld", fin); 
	return 0; 	
}

Array Partition

来源：CF1454F, 2100  

可以枚举前缀，然后合法的后缀是一段区间，然后二分找到最小值等于前缀的中间段即可.   

#include 
#define N  200009 
#define pb push_back 
#define ll long long  
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
setse[N];  
int L[N], R[N]; 
int a[N], A[N], mi[N][20], ma[N][20], Lg[N], n;  
void init() {
	Lg[1] = 0; 
	for(int i = 2; i <= n ; ++ i) Lg[i] = Lg[i >> 1] + 1; 
	for(int i = 1; i <= n ; ++ i) mi[i][0] = ma[i][0] = a[i]; 
	for(int j = 1; (1 << j) <= n ; ++ j) {
		for(int i = 1; i + (1 << j) - 1 <= n ; ++ i) {
			mi[i][j] = min(mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]); 
			ma[i][j] = max(ma[i][j - 1], ma[i + (1 << (j - 1))][j - 1]); 
		}
	}
}
int qmin(int l, int r) {
	int p = Lg[r - l + 1]; 
	return min(mi[l][p], mi[r - (1 << p) + 1][p]);   
}
int qmax(int l, int r) {
	int p = Lg[r - l + 1]; 
	return max(ma[l][p], ma[r - (1 << p) + 1][p]);   
}
void solve() {
	scanf("%d", &n); 
	for(int i = 1; i <= n ; ++ i) {
		scanf("%d", &a[i]); 
		A[i] = a[i]; 
	}
	sort(A + 1, A + 1 + n); 
	for(int i = 1; i <= n ; ++ i) {
		a[i] = lower_bound(A + 1, A + 1 + n, a[i]) - A;    
	} 
	init();   
	for(int i = n, v = 0;  i >= 1 ; -- i) {
		if(a[i] > v) {
			R[a[i]] = i, v = a[i]; 
		}
		L[v] = i;     
	}
	int ok = 0; 
	for(int i = 1, v = 0;  i <= n ; ++ i) {
		v = max(v, a[i]);    
		// printf("%d %d\n", L[v], R[v]); 
		// 前缀 v 搞好了.  
		if(!L[v] || !R[v]) continue;    
		if(R[v] > i + 1) {
			// [i + 1, R[v])   
			int l = max(i + 1, L[v] - 1), r = R[v] - 1, ans = 0;   
			// printf("%d %d\n", l, r); 
			if(l > r) continue;   
			while(l <= r) {
				int mid = (l + r) >> 1;              
				if(qmin(i + 1, mid) <= v) {
					ans = mid, r = mid - 1; 
				}
				else l = mid + 1; 
			}   
			if(!ans) continue;  
			if(qmin(i + 1, ans) == v) {
				printf("YES\n"); 
				printf("%d %d %d\n", i, ans - (i + 1) + 1, n - ans);      
				ok = 1; 
				break; 
			}
		}
	}
	if(!ok) printf("NO\n"); 
	for(int i = 0; i <= n + 2; ++ i) 
		L[i] = R[i] = 0; 
}	
int main() {
	// ssetIO("input"); 
	int T; 
	scanf("%d", &T); 
	while(T -- ) solve(); 
	return 0; 
}