E - Gophers
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87794#problem/E
Description
Input
The first line of input contains four integers n, m, d and l (2 ¬ n; m ¬ 500 000, 1 ¬ d ¬ 500 000, 1 ¬ l ¬ 109 ) representing the number of gophers’ holes, the number of Dick’s CD players, the number of days and the range of a CD player, respectively. The second line of input contains n − 1 integers x2; x3; : : : ; xn (0 < x2 < x3 < : : : < xn ¬ 109 ) denoting the distances of the holes 2; 3; : : : ; n from the hole number 1. The third line contains m integers z1; z2; : : : ; zm (0 ¬ z1 < z2 < : : : < zm ¬ 109 ) denoting the distances of the consecutive CD players from the hole number 1. All the CD players are located to the east of this hole. Next, d lines follow. The i-th of these lines contains two integers pi and ri (0 ¬ pi ; ri ¬ 109 , pi 6= ri ) meaning that in the beginning of the i-th day Dick is going to move the CD player located pi meters from the hole number 1 to the point located ri meters to the east from that hole. You may assume that before every such operation there is a CD player at the position pi and there are no CD players at the position ri .
Output
Your program should output d + 1 lines. The line number i (for i = 1; 2; : : : ; d) should contain one integer representing the number of holes in which no gopher would be able to sleep well during the night before the i-th Dick’s operation. The last line should contain this number after the last Dick’s operation.
Sample Input
5 3 4 1 2 5 6 11 2 4 8 2 1 4 10 8 6 1 8
Sample Output
2 3 3 5 3
HINT
题意
给你n个点，m个长度为l的线段
有Q次询问，每次询问就是把x位置的线段挪到y位置，然后问你这些线段覆盖了多少个点
题解：
首先，我们知道每一个线段的长度都是一样的，而且题目给了，没有任何两条线段是在同一个点的，于是我们就可以用set做
对于每一个线段，他覆盖的区域实际上是[max(a[i-1]+l,a[i]-l),min(a[i+1]-l,a[i]+l)]这个区域
然后我们用set去维护就好了
代码：
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 1000001
#define mod 10007
#define eps 1e-9
int Num;
char CH[];
const int inf=0x7fffffff; //нчоч╢С
//const int inf=0x3f3f3f3f;
/* inline void P(int x)
{
Num=0;if(!x){putchar('0');puts("");return;}
while(x>0)CH[++Num]=x%10,x/=10;
while(Num)putchar(CH[Num--]+48);
puts("");
}
*/
//**************************************************************************************
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void P(int x)
{
Num=;if(!x){putchar('');puts("");return;}
while(x>)CH[++Num]=x%,x/=;
while(Num)putchar(CH[Num--]+);
puts("");
}
ll n,m,q,l;
ll aa[maxn];
ll ans=;
ll d[maxn];
ll C(ll l,ll r)
{
if(l>aa[n])
return ;
if(r<aa[])
return ;
if(l>r)
return ;
ll L,R;
if(l<=)
L=;
else
L=lower_bound(aa+,aa+n+,l)-aa;
if(r>=aa[n])
R=n;
else
R=(upper_bound(aa+,aa+n+,r)-aa)-;
return R-L+;
}
set<ll> S;
int main()
{
n=read(),m=read(),q=read(),l=read();
S.insert(-inf);
aa[]=;
for(int i=;i<=n;i++)
aa[i]=read();
S.insert(inf);
ll tmp=;
for(int i=;i<=m;i++)
{
ll x=read();
S.insert(x);
if(i==)
ans+=C(x-l,x+l);
else
ans+=C(max(tmp+l+1LL,x-l),x+l);
tmp=x;
}
printf("%lld\n",ans);
for(int i=;i<=q;i++)
{
ll x=read();
ll c=*++S.lower_bound(x);
ll d=*--S.lower_bound(x);
ans-=C(max(d+l+1LL,x-l),min(c-l-1LL,x+l));
int e=*S.lower_bound(x);
S.erase(e);
x=read();
c=*S.lower_bound(x);
d=*--S.lower_bound(x);
ans+=C(max(d+l+1LL,x-l),min(c-l-1LL,x+l));
printf("%lld\n",ans);
S.insert(x);
}
}