Description：

有很多线段以 $1\ m/s$ 的速度向左移动，每次可以沿 $y$ 轴向正方向开枪，两次开枪时间差不得小于 $k$ ，问最多能打到几个线段。

$1\leqslant n \leqslant10^5$

Solution1:

首先肯定是 $DP$ ，但直接计算会算重，考虑正难则反，计算在这个位置最后一次开枪会失去几条线段，那么如果到了一个线段的右端点，那么所有从这个线段左端点之前转移过来的状态都会失去这条线段，这个可以用线段树区间加，区间求最小值实现，最后发现每个位置最终的结果就是在这个位置打最后一枪的答案， $DFS$ 整棵线段树取一个最大值即可。

Code1：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,k;

#define MAXN 100010

struct bird

{

	int l,r;

}s[MAXN];

bool cmp_r(bird a,bird b){return (a.r < b.r);}

int tot = 0;

#define MAXX 500010

int f[MAXX];

struct node

{

	int lc,rc;

	int minv,tag;

	node(){minv = tag = 0;}

}t[MAXX << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) / 2)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void pushdown(int rt)

{

	if(t[rt].tag == 0)return;

	t[t[rt].lc].tag += t[rt].tag;t[t[rt].lc].minv += t[rt].tag;

	t[t[rt].rc].tag += t[rt].tag;t[t[rt].rc].minv += t[rt].tag;

	t[rt].tag = 0;

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(L > R)return;

	if(L <= l && r <= R)

	{

		t[rt].minv += k;

		t[rt].tag += k;

		return;

	}

	pushdown(rt);

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].minv = min(t[t[rt].lc].minv,t[t[rt].rc].minv);

	return;

}

int query(int rt,int L,int R,int l,int r)

{

	if(L > R)return 0;

	if(L <= l && r <= R)return t[rt].minv;

	pushdown(rt);

	int res = 0x3f3f3f3f;

	if(L <= mid)res = min(res,query(t[rt].lc,L,R,l,mid));

	if(R > mid)res = min(res,query(t[rt].rc,L,R,mid + 1,r));

	return res;

}

int ans = 0;

void pt(int rt,int l,int r)

{

	if(l == r)

	{

		ans = max(ans,n - t[rt].minv);

		return;

	}

	pushdown(rt);

	pt(t[rt].lc,l,mid);

	pt(t[rt].rc,mid + 1,r);

	return;

}

int main()

{

	freopen("bird.in","r",stdin);

	freopen("bird.out","w",stdout);

	scanf("%d%d",&n,&k);

	int x1,x2;

	int maxr = 0;

	for(int i = 1;i <= n;++i)

	{

		x1 = read();x2 = read();

		if(x2 < 0)continue;

		++tot;s[tot].l = max(x1,0);s[tot].r = x2;

		maxr = max(maxr,s[tot].r);

	}

	++maxr;

	n = tot;

	sort(s + 1,s + 1 + n,cmp_r);

	build(root,0,maxr);

	memset(f,0x3f,sizeof(f));

	f[0] = 0;

	int cnt = 0;

	for(int i = 0,j = 1;i <= maxr;++i)

	{

		for(;j <= n && s[j].r < i;++j)

		{

			++cnt;

			add(root,0,s[j].l - 1,1,0,maxr);

		}

		if(i >= k)f[i] = query(root,0,i - k,0,maxr);

		else f[i] = cnt;

		add(root,i,i,f[i],0,maxr);

	}

	pt(root,0,maxr);

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}

Solution2：

既然会算重那就消除掉重复的影响，即如果扫到了一个位置，那么不把还没有到终点的线段的贡献加上，如果扫到了一个线段的终点，就做一次区间加操作，相当于每只鸟只在最后一次被打中时被记入，这样就不会有任何重复了。

Code2：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 100010

struct line

{

	int l,r;

}l[MAXN];

int tot = 0;

bool cmp_r(line a,line b){return a.r < b.r;}

#define MAXP 500010

struct node

{

	int lc,rc;

	int maxv,tag;

}t[MAXP << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void pushdown(int rt)

{

	if(t[rt].tag == 0)return;

	t[t[rt].lc].maxv += t[rt].tag;t[t[rt].lc].tag += t[rt].tag;

	t[t[rt].rc].maxv += t[rt].tag;t[t[rt].rc].tag += t[rt].tag;

	t[rt].tag = 0;

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].maxv += k;

		t[rt].tag += k;

		return;

	}

	pushdown(rt);

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].maxv = max(t[t[rt].lc].maxv,t[t[rt].rc].maxv);

	return;

}

int query(int rt,int L,int R,int l,int r)

{

	if(L > R)return 0;

	if(L <= l && r <= R)return t[rt].maxv;

	int res = 0;

	pushdown(rt);

	if(L <= mid)res = max(res,query(t[rt].lc,L,R,l,mid));

	if(R > mid)res = max(res,query(t[rt].rc,L,R,mid + 1,r));

	return res;

}

int f[MAXP];

int ans = 0;

void pt(int rt,int l,int r)

{

	if(l == r)

	{

		ans = max(ans,t[rt].maxv);

		return;

	}

	pushdown(rt);

	pt(t[rt].lc,l,mid);

	pt(t[rt].rc,mid + 1,r);

	return;

}

int main()

{

	freopen("bird.in","r",stdin);

	freopen("bird.out","w",stdout);

	scanf("%d%d",&n,&k);

	int a,b;

	int maxr = 0;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d",&a,&b);

		if(b < 0)continue;

		a = max(a,0);

		++tot;l[tot].l = a;l[tot].r = b;

		maxr = max(maxr,b);

	}

	++maxr;

	n = tot;

	build(root,0,maxr);

	sort(l + 1,l + 1 + n,cmp_r);

	for(int i = 0,j = 1;i <= maxr;++i)

	{

		f[i] = query(root,0,i - k,0,maxr);

		for(;j <= n && l[j].r == i;++j)add(root,l[j].l,l[j].r,1,0,maxr);

		add(root,i,i,f[i],0,maxr);

	}

	pt(root,0,maxr);

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}