当前位置：CGaZn的博客 > OI > 正文

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

2019-07-21 分类：OI / 题解阅读(182) 评论(0)

根据贪心的思路, 两头牛a,b能相互看见, 一定有区间[a+1,b-1]内的牛比它们至少小1. 因此建立一个初值全为0的数组d, 每读入一对关系a,b, 就把区间d[a+1,b-1]全部减一. 当所有关系读入完毕, 数组d内就是牛之间的相对高度差. 用已知的最高牛i的身高h加上这个高差, 就可以得到每头牛的最大身高.

问题是区间内数值逐个修改复杂度太高, 有$latex O(NM)$, 所以这里引入差分的概念(~~用线段树可以水过~~).设差分数组$latex c[i]=d[i]-d[i-1]$, 则有$latex c[i]=\sum_{j=1}^{i}d[j]$. 当区间[x,y]都加上或减去同一个数时, c[x+1]~c[y]都不变,只要修改c[x]和c[y+1]即可.这样就成功的把对一个区间的修改转化为了对两端点的修改.

注意关系可能重复给出, 要用map判重.

展开代码

#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;
}

赞(0)

标签：差分树状数组模拟贪心

相关推荐

评论抢沙发