牛客手速月赛 48 C(差分都玩不明白了属于是)

不想玩辣!   好久没打牛客了，第二题连wa5发，心态有点炸。天天做天梯赛的题都有点不知道罚时，就硬莽夫，是个坏习惯。罢了，收拾收拾退役了。 题目 题意: 给定n个编号从1到n的区间，给定len，求有多少个区间满足长度为len且与区间相交的数量最多且权重最大。 权重: 所有相交区间的编号和。 思路: 稍微想想就知道，每次只移动一个格子，把信息预处理出来即可。傻了，非得用vector处理。这里和差分非常像的，但是不能在消失的地方–，因为可能区间左端点还在区间中。只需要多开一个数组记录所有给定区间的右端点，在枚举的时候减去即可。 ！注意右端点最大是5e6+5e6 时间复杂度: O(n) 代码:

#include
using namespace std;
const int N = 1e7+10;
typedef long long ll;
int n,m,k,T;
int b[N],bb[N];
ll w[N],ww[N];
ll ans = 0;
ll mx = 0;
ll quan = 0;
void solve()
{
	cin>>n>>m;
	for(int i=1;i>x>>y;
		b[x]++,bb[y]++;
		w[x]+=i,ww[y]+=i;
	}
	ll now;ll sum;
    for(int i=1;iquan))
        {mx = now; quan = sum; ans = 0;}
        if(now==mx&&sum==quan) ans++;
    }
	coutT;
	while(T--)
	solve();
	return 0;
}