[POJ3263][洛谷P2879][USACO07JAN]区间统计Tallest Cow[差分]

#include<cstdio>
#include<map>
#define in inline
#define re register
using namespace std;
in int read()
{
    int s(0),b(0);char ch;
    do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    if(b) return -s;
    return s;
}
int n,h,I,r,c[10005];
map<pair<int,int>,int> book;
in int lowbit(int x){return x&-x;}
in void add(int i,int x)
{
	while(i<=n) c[i]+=x,i+=lowbit(i);
}
in int sum(int i)
{
	int ans=0;
	while(i>0) ans+=c[i],i-=lowbit(i);
	return ans;
}
signed main()
{
    n=read(),I=read(),h=read(),r=read();
    for(re int i=1;i<=r;++i)
    {
    	int a=read(),b=read();
    	if(a>b) a^=b,b^=a,a^=b;
    	if(book.find(make_pair(a,b))!=book.end()) continue;
    	book[make_pair(a,b)]=1;
    	add(a+1,-1);
    	add(b-1+1,1);
    }
    for(re int i=1;i<=n;++i)
    	printf("%d\n",h+sum(i));
    return 0;
}