Post 66

Veröffentlicht am

二等奖三个名额唉，为了稳一点，要不要停课呢？

emmm….再也不能掉以轻心了，只有一次机会了。

CF893F Subtree Minimum Query

题意翻译

题目大意：

给你一颗有根树，点有权值，m次询问，每次问你某个点的子树中距离其不超过k的点的权值的最小值。（边权均为1，点权有可能重复，k值每次询问有可能不同，强制在线）

真实询问计算方法：

x=(x′+lans)modn+1;

k=(k′+lans)modn;

数据范围： n<=100000,ai<=10^9,m<=1000000

题目描述

You are given a rooted tree consisting of nn vertices. Each vertex has a number written on it; number a_{i}a**iis written on vertex ii .

Let’s denote d(i,j)d(i,j) as the distance between vertices ii and jj in the tree (that is, the number of edges in the shortest path from ii to jj ). Also let’s denote the kk -blocked subtree of vertex xx as the set of vertices yy such that both these conditions are met:

  • xx is an ancestor of yy (every vertex is an ancestor of itself);
  • d(x,y)<=kd(x,y)<=k .

You are given mm queries to the tree. ii -th query is represented by two numbers x{i}x**i and k{i}k**i , and the answer to this query is the minimum value of a{j}a**j among such vertices jj such that jj belongs to k{i}k**i -blocked subtree of x_{i}x**i .

Write a program that would process these queries quickly!

Note that the queries are given in a modified way.

输入输出格式

输入格式：

The first line contains two integers $n$and $r$( $1<=r<=n<=100000$ ) — the number of vertices in the tree and the index of the root, respectively.

The second line contains $n$integers $a{1},a{2},…,a{n}$ ( $1<=a{i}<=10^{9}$) — the numbers written on the vertices.

Then n-1n−1 lines follow, each containing two integers $x$ and $y$ ( $1<=x,y<=n$) and representing an edge between vertices $x$and$ y$ . It is guaranteed that these edges form a tree.

Next line contains one integer $m$( $1<=m<=10^{6}$ ) — the number of queries to process.

Then mm lines follow, ii -th line containing two numbers $p{i}$ and $q{i}$ , which can be used to restore $i$ -th query ( $1<=p{i},q{i}<=n$ ).

$i$-th query can be restored as follows:

Let $last$ be the answer for previous query (or 0 if$ i=1$ ). Then$x{i}=((p{i}+last)modn)+1$ , and $k{i}=(q{i}+last)modn$

输出格式：

Print mm integers. ii -th of them has to be equal to the answer to ii -th query.

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
5 2
1 3 2 3 5
2 3
5 1
3 4
4 1
2
1 2
2 3

输出样例#1：

1
2
2
5

题解

发现前几天的题解口胡错了。。。
回去就删了。
这道题绝对是主席树的好题。一定要利用主席树的各个维度的特点。

说说我的思路历程。。
先想到按照BFS序建权值线段树，思考一下发现没法算DFS序区间，又想建DFS区间树，但是那样建又没法满足深度时间轴。
然后想到既能有深度时间轴又能按DFS序的方法：线段树的下标$i$表示$dfn_i$即可。
这样一来最关键的一点就解决了，维护一个前缀深度可持久化线段树，进行区间查询。
然后写着写着发现不大对：这颗按深度建主席树没法减（这是最致命的，树状数组++）。
然后发现只需要保证深度的上限就可以了，因为我们查的区间$[dfn_x,dfn_x+sz_x)$里不会有深度小于$dep_x$的需要减掉。

然后就为他写了Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define maxn 100005
#define maxm 1000005
#define nlogn 3200005
int a[maxn] , n , la , dfn[maxn] , sz[maxn] , m , r , rt[maxn] , ct , cnt[maxn] , dep[maxn] , maxdep , cur; 
std::queue<int> q;

namespace segtree
{
	int lc[nlogn] , rc[nlogn] , tot , mn[nlogn];
	inline void pushup(int x){
		mn[x] = std::min(mn[lc[x]] , mn[rc[x]]);
	}
	void build(int& p , int l , int r)
	{
		p = ++tot;
		if(l == r) return;
		int mid = l +r >> 1;
		build(lc[p] , l , mid);
		build(rc[p] , mid + 1 , r);
		pushup(p);
	}
	void ins(int& p , int pre , int pos , int l , int r , int val)
	{
		p = ++tot;
		if(l == r){	mn[p] = val ;  return;}
		int mid = l + r >> 1;
		if(pos <= mid) rc[p] = rc[pre] , mn[rc[p]] = mn[rc[pre]] , ins(lc[p] , lc[pre] , pos , l , mid , val);
		else lc[p] = lc[pre] , mn[lc[p]] = mn[lc[pre]] , ins(rc[p] , rc[pre] , pos , mid + 1 , r , val);
		pushup(p);
//		printf("PUSH %d %d\n",p,mn[p]);
	}
	int query(int node , int l , int r , int cl , int cr)
	{
//		printf("Q : %d %d %d %d %d %d\n",node,l,r,cl,cr,mn[node]);
		if(l <= cl && cr <= r) return mn[node];
		int mid = cl + cr >> 1 , ans = 0x7fffffff;
		if(l <= mid) ans = std::min(ans , query(lc[node] , l , r , cl , mid));
		if(r > mid) ans = std::min(ans , query(rc[node] , l , r , mid + 1 , cr));
		return ans;
	}
}
std::vector<int> g[maxn];

void dfs(int x , int fx)
{
	dfn[x] = ++ct;
	sz[x] = 1;
	dep[x] = dep[fx] + 1;
	maxdep = std::max(maxdep , dep[x]);
	for(int i = 0 ; i < (int)g[x].size() ; ++i)
		if(g[x][i] != fx)
			dfs(g[x][i] , x) , sz[x] += sz[g[x][i]];
}

bool vis[maxn];
inline void BFS_BUILD(int r)
{
	q.push(r);
	vis[r] = true;
	for(int k ; (int)q.size() ; q.pop())
	{
		k = q.front();
		for(int i = 0 ; i < (int)g[k].size() ; ++i)
			if(!vis[g[k][i]]) vis[g[k][i]] = true , q.push(g[k][i]);
//		printf("INS! %d\n",k);
		segtree::ins(rt[++cur] , rt[cur] , dfn[k] , 1 , n , a[k]);
	}
}
		
int main()
{
	std::memset(segtree::mn,0x6f,sizeof(segtree::mn));
	scanf("%d%d",&n,&r);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&a[i]);
	for(int i = 1 ; i < n ; ++i)
	{
		int x , y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y) , g[y].push_back(x);
	}
	dfs(r , r);
	for(int i = 1 ; i <= n ; ++i)
		++cnt[dep[i]];
	for(int i = 1 ; i <= maxdep ; ++i)
		cnt[i] += cnt[i-1];
	segtree::build(rt[0] , 1 , n);

	BFS_BUILD(r);

	scanf("%d",&m);
	for(int i = 1 ; i <= m ; ++i)
	{
		int x , k;
		scanf("%d%d",&x,&k);
		x = (x + la) % n + 1 , k = (k + la) % n ;
//		printf("START BUG : %d\n",rt[cnt[std::min(maxdep , dep[x] + k)]]);
		printf("%d\n",la = segtree::query(rt[cnt[std::min(maxdep , dep[x] + k)]] , dfn[x] , dfn[x] + sz[x] - 1 ,1 , n));
	}
}

介绍一个关于底数不变模数不变的快速求幂技巧—幂次数分块。

具体来说就是把幂分成4块然后预处理每一块，注意第二块乘的是第一块最大次幂。

比如16位分一块。

第二块每次应该乘一个$2^{16}$矩阵。

SP11469 SUBSET - Balanced Cow Subsets

给出N（1≤N≤20）个数M(i) (1 <= M(i) <= 100,000,000)，在其中选若干个数，如果这几个数可以分成两个和相等的集合，那么方案数加1。问总方案数。

题解

这题时限是174ms……

本来我秒想一个$T(n) = 2T(n/2) + O(n2^n)$的做法觉得差不多，现在看来似乎不行。

我们还得尽量减小常数。。。

然后好像有个不用递归的meet in the middle的做法！

把这$n$个数随便分成均等的两个集合，然后按子集和排序。

内部统计只需要记录一个相等值连续量$cur$，然后中断的时候$C_{cur}^2$..

这两部分由于值单调双指针贪心即可。

复杂度$O(n2^n)$

上面算法是错误的。。。。

正确做法坚信不难，明天再想想。