题目描述 For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far. 输入 The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by an odd decimal integer M, (1 ≤ M ≤ 9999), giving the total number of signed integers to be processed. The remaining line(s) in the dataset consists of the values, 10 per line, separated by a single space. The last line in the dataset may contain less than 10 values. 输出 For each data set the first line of output contains the data set number, a single space and the number of medians output (which should be one-half the number of input values plus one). The output medians will be on the following lines, 10 per line separated by a single space. The last line may have less than 10 elements, but at least 1 element. There should be no blank lines in the output. 样例输入 Copy 3 1 9 1 2 3 4 5 6 7 8 9 2 9 9 8 7 6 5 4 3 2 1 3 23 23 41 13 22 -3 24 -31 -11 -8 -7 3 5 103 211 -311 -45 -67 -73 -81 -99 -33 24 56 样例输出 Copy 1 5 1 2 3 4 5 2 5 9 8 7 6 5 3 12 23 23 22 22 13 3 5 5 3 -3 -7 -3 提示 来源：Greater New York Regional 2009
问题传送门
这道题与洛谷P1168类似但输出有点***，对于题目描述，可知这道题让我们做一个维护区间序列 a a a的中位数，注意需要排序（对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，通常取最中间的两个数值的平均数作为中位数。 --选自百度百科).
首先，注意序列个数达到奇数个时，要输出询问答案。
对于每次询问，做一遍查询，排序，输出 a n s k / 2 + 1 ans_{k / 2 + 1} ansk/2+1这个数即可。
分析时间复杂度为 O ( n 2 log n ) O(n^2 \log n) O(n2logn),此时过不了这道题，但可以拿到 40 % 40 \% 40%的好成绩.
用堆来维护，然后二分， 分析时间复杂度为 O ( n log n ) . O(n \log n). O(nlogn).可以过，但这不是重点。
这道题用链表维护也可以。
我们考虑用平衡树来维护这个序列，对于每次询问，只需要询问 [ 1 , i ] [1,i] [1,i]区间即可，查找区间这段排名 ( k t h ) (kth) (kth)为 ( i / 2 + 1 ) (i / 2 + 1) (i/2+1)的数字。其他情况只需要插入 ( i n s e r t ) (insert) (insert),然后一个平衡树板子就好了。
分析时间复杂度：对于平衡树查询有 O ( log n ) O(\log n) O(logn)的复杂度， 然后询问存在大概 n / 2 + 1 n / 2 + 1 n/2+1次， 所以时间复杂度约为 O ( n ) O(n) O(n) 综合一下，这道题用平衡树来维护的时间复杂度为 O ( n log n ) O(n \log n) O(nlogn). 可以过了。
以 Splay \text{Splay} Splay 为例(这里无需排序，因为 Splay \text{Splay} Splay 本质已经排过序了,该代码复杂度为 O ( n log n ) O(n \log n) O(nlogn))：
#include<cstdio> #include<cstring> #define re register using namespace std; const int maxn = 1e5 + 7; int root,ncnt; struct node { int ch[2],val,cnt,fa,size; } tr[maxn]; inline void pushup(re int x) { tr[x].size=tr[tr[x].ch[0]].size+tr[tr[x].ch[1]].size+tr[x].cnt; } inline void rotate(re int x) { re int y=tr[x].fa,z=tr[y].fa,k=tr[y].ch[1]==x,w=tr[x].ch[k^1]; tr[y].ch[k]=w; tr[w].fa=y; tr[z].ch[tr[z].ch[1]==y]=x; tr[x].fa=z; tr[x].ch[k^1]=y; tr[y].fa=x; pushup(y),pushup(x); } inline void splay(re int x,re int rt) { while(tr[x].fa != rt) { re int y=tr[x].fa,z=tr[y].fa; if(z!=rt)(tr[z].ch[0]==y)^(tr[y].ch[0]==x)?rotate(x):rotate(y); rotate(x); } if(!rt)root=x; } inline void insert(re int x) { re int cur=root,p=0; while(cur&&tr[cur].val!=x)p=cur,cur=tr[cur].ch[x>tr[cur].val]; if(cur)tr[cur].cnt++; else { cur=++ncnt; if(p)tr[p].ch[x>tr[p].val]=cur; tr[cur].ch[0]=tr[cur].ch[1]=0; tr[cur].fa=p; tr[cur].val=x; tr[cur].cnt=tr[cur].size=1; } splay(cur,0); } inline void find(re int x) { if(!root)return; int cur=root; while(tr[cur].ch[x>tr[cur].val]&&x!=tr[cur].val)cur=tr[cur].ch[x>tr[cur].val]; splay(cur,0); } inline int kth(re int k) { re int cur=root; if(tr[cur].size<k)return 0; while(1) if(tr[cur].ch[0]&&k<=tr[tr[cur].ch[0]].size)cur=tr[cur].ch[0]; else if(k>tr[tr[cur].ch[0]].size+tr[cur].cnt) { k -= tr[tr[cur].ch[0]].size+tr[cur].cnt,cur=tr[cur].ch[1]; } else { splay(cur,0); return cur; } } int t,cnt,n,m,x; int main() { // freopen("1.txt","w",stdout); scanf("%d",&t); while(t--) { scanf("%d%d",&cnt,&n); printf("%d %d\n",cnt,(n+1) >> 1); memset(tr,0,sizeof(tr)); for(re int i=1; i<=n; i++) { scanf("%d",&x); insert(x); if(i & 1){ printf("%d ",tr[kth((i / 2 + 1))].val); if(((i+1)/2)%10 == 0)puts(""); else if((n%2==1&&i==n)||(n%2==0&&i==n-1))puts(""); } } } return 0; }又用平衡树水过一道题。
题目描述 为了促进奶牛的智力发展， Farmer John 在牛棚的墙上放置了一幅很大的美国地图。在奶牛们花费 很多时间研究地图后，他们注意到一个奇特的现象。例如，有这样两个城市：弗林特(Flint)，其州代 码为 MI，和迈阿密(Miami)，州代码为 FL，他们之间存在一个特殊的关系： “弗林特”(Flint)的前两个 字母刚好是迈阿密的州代码(FL)，同时迈阿密(Miami)前两个字母也刚好是弗林特的州代码(MI)。如果 两个来自不同州的城市满足这一属性，那我们就说这两个城市是特殊的一对。奶牛们想知道有多少对这 样的城市存在。请帮助他们解决这个有趣的地理难题！ 输入 第 1 行输入地图上城市的个数 N； 接下去的 N 行，每行分别输入两个字符串。第一个表示城市名称(字符串由大写英文字母组成， 最少两 个，最多不能超过 10 个)，第二个表示该城市的州代码(两个大写字母)。多个城市的名称允许相同，但 他们必须属于不同的州。 输出 输出共一行一个整数，满足条件的特殊城市对数。 样例输入 Copy 6 MIAMI FL DALLAS TX FLINT MI CLEMSON SC BOSTON MA ORLANDO FL 样例输出 Copy 1 提示 对于 20%的数据： 1≤N≤2,000； 对于 50%的数据： 1≤N≤25,000； 对于 100%的数据： 1≤N≤200,000；
对于这道题，我们不妨考虑用 map \text{map} map来乱搞，因为数据范围只有 2e5 \text{2e5} 2e5. 输入再模拟题目过程即可。 注意，如果相同则跳过，否则更新答案；
题目描述 Farmer John 有 N 头奶牛，他们想组建一个紧急的“传递信息”系统，以便相互之间传递重要的信 息。 他们决定使用对讲机来作为装备，而不是通过相互间的哞哞叫，每头牛配有一只对讲机。这些对讲 机都有自己的有限传输半径，如果有限传输半径是 P 的话，也就是说该对讲机能将信息传送到与之距离 不超过 P 的对讲机（请注意，奶牛 A 可能把信息传递给奶牛 B，但奶牛 B 却没办法把信息传递回去，因 为奶牛 A 的有限传输半径大于奶牛 B 的有限传输半径）。幸运的是,奶牛可以通过其他奶牛传递信息，所 以没必要每头牛都能直接传送到其他牛。 由于对讲机的这种不对等的性质，其中的一些奶牛传播效果可能比其他奶牛更有效，因为它们能传 递到更多的接收者（相互之间产生直接联系）。请帮助奶牛确定：如果源于一头牛，最多能将信息传递 到多少头牛？ 输入 第 1 行输入奶牛的个数 N； 第 2 到 N+1 行，第 i+1 行代表第 i 头奶牛的 Xi 和 Yi 坐标，以及其对应对讲机的最大传输半径 Pi。 输出 输出共一行一个整数，源于一头牛，最多能将信息传递到多少头牛？原始的这头牛也包含在内。 样例输入 Copy 4 1 3 5 5 4 3 7 2 1 6 1 1 样例输出 Copy 3 提示 对于 50%的数据： 1≤N≤100； 对于 100%的数据： 1≤N≤200； 0≤Xi,Yi,Pi≤30,000；
看到这个数据范围，就会想到所有暴力都可以碾过去。 这道题需要注意一点： A A A到 B B B并不能保证 B B B也到 A A A. 所以就不能并查集了。
如果下一个点可以被到达，且之前没有到过，则搜索下去，并标记。 然后搜索完再统计答案。
直接数学公式即可 d i s i , j = ( a 1 i − a 2 i ) 2 + ( a 1 j − a 2 j ) 2 dis_{i,j} = \sqrt{(a_{1_i} - a_{2_i})^2 + (a_{1_j}-a_{2_j})^2} disi,j=(a1i−a2i)2+(a1j−a2j)2
