AcWing 101. 最高的牛
原题链接
简单
刚学差分法,这个题做了我一个多小时,记录一下
C++代码
#include<iostream>
using namespace std;
const int N = 5010;
int a[N];
int x[10010],y[10010];
long long h;
long long n,p,h_p,m;
void insert(int l,int r)
{
a[l+1] -= 1;
a[r] += 1;
}
void insert_mid(int l,int r)
{
a[l+1] -= 1;
a[r] += 1;
a[p] +=1;
a[p+1] -=1;
}
int main()
{
int k = 0;
cin >> n >> p >> h_p >> m;
a[1] = h_p;
for(int i = 0; i < m ; i ++)
{
int l,r;
int j = 0;
cin >> l >> r;
if(l>r)
{
swap(l,r);
}
for( ; j < k ; j ++)
{
if(l == x[j] && r == y[j])
{
break;
}
}
if(j>=k)
{
x[k] = l;
y[k++] = r;
if(r<=p) insert(l,r);
else if(l>=p) insert(l,r);
else insert_mid(l,r);
}
}
for(int i = 1; i <= n ; i ++)
{
a[i] += a[i-1];
cout << a[i] << endl;
}
// for(int i = 0; i < k; i ++)
// {
// cout << x[i] << " " << y[i] <<endl;
// }
}