UVA12663 【High bridge, low bridge】

差分

题目大意：一共有n座桥，每个桥都有一个高度，海水每次都会涨落，问被淹次数大于等于k的桥一共有多少座。

对于海水的涨落，可以看成是区间加法（被淹的桥次数加一），暴力搞的话肯定会TLE，所以我们珂以用差分来实现区间加法，从l到r加上x就相当于差分数组里的l处+x，r+1处-x，因为这个题还需要记录上一次海水所在的位置，所以我们珂以这样写：

for(int i=1;i<=m;++i)
{
    scanf("%d%d",&x,&y);
    mp[pre+1]++;
    mp[x+1]--;pre=y;
}

又因为这道题的数据范围比较大，可以离散化来解决，我们还可以使用map来实现（因为我比较懒），直接使用迭代器遍历就珂以啦~差分的时间复杂度为\(O(nlong(n))\)O(能过),可能没有线段树跑的快（毕竟map的常数太大了），但我们还是能开心地A掉这道题啦。

最后献上我丑陋的代码

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<map>
#define IT map<int,int>::iterator 
using namespace std;
const int N=100010;
int n,m,k,my_case,ans,sum,pre,x,y;
int b[N];
map<int,int>mp;
int main()
{
    while(scanf("%d%d%d",&n,&m,&k)==3)
    {
        ans=sum=pre=0;mp.clear();
        for(int i=1;i<=n;++i)scanf("%d",&b[i]);
        for(int i=1;i<=m;++i)
        {
            scanf("%d%d",&x,&y);
            mp[pre+1]++;
            mp[x+1]--;pre=y;
        }
        for(IT it=mp.begin();it!=mp.end();++it)
        {
            sum+=it->second;
            it->second=sum;
        }
        for(int i=1;i<=n;++i)
        {
            IT it=mp.lower_bound(b[i]);
            ans+=(((--it)->second)>=k);
        }
        printf("Case %d: %d\n",++my_case,ans);
    }
    return 0;
}