D. Robert Hood and Mrs Hood
一开始想的是将[l,r]均+1,但是这样会出现问题,就是比如统计[i,i+d-1]时,如果将其均加起来,那么有可能i中有一个1是工作x加的,j中有一个1也是工作x加的,这样就重复了
实际上,每个区间的长度均是d,所以,区间的起点就能代表整个区间,我们将它看作一个整体,那么工作[l,r]对哪些区间会作出贡献呢?[l-d+1,r],所以我们对[d-l+1,r]均+1,利用差分就可以轻松解决了
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int b[N];
int n,d,k;
void solve() {cin>>n>>d>>k;for(int i=1;i<=n;i++) b[i]=0;for(int i=0;i<k;i++){int l,r;cin>>l>>r;b[max(l-d+1,1ll)]++;b[r+1]--;}for(int i=1;i<=n;i++) b[i]+=b[i-1];int ans1=1,ans2=1;int maxn=0,minn=2e9;for(int i=1;i+d-1<=n;i++){if(maxn<b[i]){maxn=b[i];ans1=i;}if(minn>b[i]){minn=b[i];ans2=i;}}cout<<ans1<<' '<<ans2<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}