前三道太水了，第三道一眼二分，就是需要注意要超过一半人就行，我因为检查了好久

D. Robert Hood and Mrs Hood

 

抱歉，我是蒟蒻，我看到区间问题就想到了线段树，我们只需要用线段树去维护每个点药经历多少任务即可

我们用线段树去维护，每个点会覆盖几个任务点即可，我们一个任务，假设开始时间为L，结束时间为R ，因此我们什么时候来能够赶上这个任务呢？很明显是从L-d+1~R这个时间来都能碰到这个任务，因此，我们就需要给这个区间+1

然后最后去查每个点的权值即可，时间复杂度为O(logn)

#include<bits/stdc++.h>  
using namespace std;  
#define int long long
int t;  
int n,d,k;  
int l,r;  
struct node  
{  int l;  int r;  long long sum; long long lz;  
}tree[1000006*4];  void push_down(int i)  
{  if(tree[i].lz != 0)  {  tree[i*2].lz += tree[i].lz;  tree[i*2].sum += tree[i].lz * (tree[i*2].r - tree[i*2].l + 1);  tree[i*2+1].lz += tree[i].lz;  tree[i*2+1].sum += tree[i].lz * (tree[i*2+1].r - tree[i*2+1].l + 1); tree[i].lz = 0; }   
}  void build(int i,int l,int r)  
{  tree[i].lz = 0;  tree[i].l = l;  tree[i].r = r;  if(l == r)  {  tree[i].sum = 0; return;  }  int mid = (l + r) / 2;  build(i*2, l, mid);  build(i*2+1, mid + 1, r);  tree[i].sum = tree[i*2].sum + tree[i*2+1].sum; 
}  void add(int i,int l,int r,int k)  
{  if(l <= tree[i].l && tree[i].r <= r)  {  tree[i].sum += k * (tree[i].r - tree[i].l + 1);  tree[i].lz += k;return;  }  push_down(i);  int mid = (tree[i].l + tree[i].r) / 2;  if(l <= mid)  add(i*2, l, r, k);  if(r > mid)  add(i*2+1, l, r, k);  tree[i].sum = tree[i*2].sum + tree[i*2+1].sum; 
}  long long find(int i,int l,int r)  
{  if(tree[i].l >= l && tree[i].r <= r)  {  return tree[i].sum;  }  push_down(i);  long long ans = 0;  int mid = (tree[i].l + tree[i].r) / 2;  if(l <= mid)  ans += find(i*2, l, r);  if(r > mid)  ans += find(i*2+1, l, r);  return ans;  
}  void solve()  
{  cin >> n >> d >> k;  build(1, 1, n);  for(int i = 1; i <= k; i++)  {  cin >> l >> r;  add(1, max(1, l-d+1), r, 1);  }  int minn = 1, maxn = 1;  long long minnz = find(1, 1, 1);   long long maxnz = find(1, 1, 1);  for(int i = 1; i <= n - d + 1; i++)  {  long long cnt = find(1, i, i);  if(cnt < minnz)  {  minnz = cnt;  minn = i;  }  else if(cnt > maxnz)  {  maxnz = cnt;  maxn = i;  }  }  cout << maxn << " " << minn << '\n';  
}  signed main()  
{  ios_base::sync_with_stdio(0);  cin.tie(0);  cout.tie(0);  cin >> t;  while(t--)  {  solve();  }  return 0;  
}