Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 2]

J. Lonely Numbers（线性筛+打表+找规律）
题目意思就是有一种新定义的两个数字之间的叫friend的关系，如果对于两个数字a，b ，有gcd(a,b), a/gcd(a,b), b/gcd(a,b)可以组成一个三角形（即两两之和大于第三边）的话，我们就说a和b是朋友。

现在给你一个数字n，要你输出1-n中有多少个数字没有朋友。

一般这种数据较大的多组样例是肯定要打表的，上来先找了一下规律，发现一个合数和任何数都可以是朋友，所以我们就先找到素数（线性筛打表），然后发现并不是所有的素数都没有朋友，每个素数和这个素数的平方一定是朋友。（对于一个素数k来说，三条边分别是k，1，k。两边之和一定大于第三边。）

所以我们需要找的素数就是从根号n到n的所有的素数的个数，这个操作只能用前缀和数组来实现，因为每次n的范围最大可能到1e6，如果每次都去找从根号n到n有多少个素数的话一定会超时。

最后的结果记得加上1。因为对于1和n来说，三条边分别是1，1，n，所以1跟任何数都不是朋友。

代码：

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

const int N = 1e6 + 10;

int p[N], a[N], idx, pre[N];

void xxs()
{
    int kns = 0;
    for(int i = 2; i <= N; i ++)
    {
        if(!a[i])
        {
            p[ ++ idx] = i;
            kns ++;
        }
        for(int j = 1; j <= idx && i * p[j] <= N; j ++)
        {
            a[i * p[j]] = 1;
            if(i % p[j] == 0) break;
        }
        pre[i] = kns;
    }
}

int main()
{
	xxs();
	int t;
	scanf("%d", &t);
	while(t --)
	{
		int n;
        scanf("%d", &n);
        int k = sqrt(n);
        printf("%d\n", pre[n] - pre[k] + 1);
	}
	return 0;
}

G. Years（差分思想+压缩）
这道题题意很简单。就是给你n个人，然后是每个人的出生年份和死亡年份，要你求出哪一个年活着的人数量最多，输出这个最大数量和这个年份，如果最大数量相同，输出年份较小的一个。

问题就在于这个区间的范围是1e9，这意味着我们不能用线段树来维护区间最大值（线段树需要开4e9）。

既然线段树不能用，自然就想到了差分。当时想的是：差分不也得开数组来维护吗？这不还是1e9的复杂度么，然后就没继续往下想。其实这道题就算差分不开数组也可以判定最大值的大小还有位置。

那具体怎么实现呢？

其实我们可以用两个点来维护差分，如果是左端点就标记为1，右端点就标记为-1(因为右端点指得是死亡年份，所以不用考虑在+1的区间里，实际就是全加1的区间的后一个点)。

可以使用vector+pair来存，然后将vector一遍再从标记值的累加值中找到最大的值并更新下标就可以。（这里是因为端点从小到大遍历能保证差分的性质不改变，如果端点相同的话就按标记的值从小到大排序。这里端点的标记值不按从大到小是因为我们记录的是端点的累加标记值的最大值，而如果先加大的的话会把在这一年死了的人算上，然后之后这个端点的值会减小，实际上的最大值是不考虑在这一年死了的人的，所以需要从小到大排）

代码：

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

vector<pair<int,int> > P;


int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        int a,b;
        scanf("%d%d", &a, &b);
        P.push_back(pair<int,int>(a,1));     //这里注意push＿back的内部结构。（需要pair！）
        P.push_back(pair<int,int>(b, -1));
    }
    sort(P.begin(), P.end()); //pair的sort默认先对第一个元素排序，如果第一个元素相等，则对第二个元素排序。
    int idx = 0;
    int ans = -1;
    int xb = 1;   //这里下标从1开始是为了保证在最大值相等的情况下取更小的。

    for(int i = 0; i < n * 2; i ++)  //这里到 n*2是因为 对每个n我们放入了两个vector。
    {
        idx += P[i].second;      //注意pair可以这样用。
        if(idx > ans)
        {
            ans = idx;
            xb = P[i].first;
        }
    }
    printf("%d %d", xb, ans);
    return 0;
}