蓝彗星（差分+前缀和）

题目链接

https://ac.nowcoder.com/acm/contest/23479/C

题面

思路

我们知道彗星每次出现的持续时间，以及出现时间，很容易就联想到区间覆盖问题，有的同学可能就直接去写树状数组或者线段树了，其实没必要，我们直接差分处理就好了，关于差分和前缀和的讲解链接：https://acmer.blog.csdn.net/article/details/122371482 现在你应该懂差分和前缀和了吧？那我们现在来看怎么使用差分，因为我们想知道这个时间是否出现过红彗星，那么我们就希望红彗星在进行区间覆盖的时候权值非常的大（也就是影响非常大）例如：-0x3f3f3f3f，而蓝彗星影响就取个1或者其他较小值，这样有什么好处呢，我们知道对差分求前缀和就是获取当前位置的实际影响，如果一个时刻的影响是一个负数那么说明这个时间被红彗星所影响，等于0说明没有彗星，只有大于0才是被蓝彗星影响。

关于兰子姐姐的进阶问题，也就是时间段数据范围变成1e9，我们可以直接使用map或者手写离散化处理

代码

#include
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
//----------------自定义部分----------------
ll t,n,m,q,a[N];
ll pre[N];

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	
	cin>>n>>t;
	string s;
	cin>>s;
	ll ti;
	ll len = 1;
	for(int i = 1;i >ti;
		if(s[i-1] == 'B'){//蓝色彗星
			a[ti]++;
			a[ti + t]--;
		}
		else{
			a[ti] -= INF;
			a[ti + t] += INF;
		}
		len = max(ti + t,len);
	}
	ll res = 0LL;
	ll ans = 0;
	for(int i = 1;i  0) ans++;
	}
	cout