P2879 [USACO07JAN]区间统计Tallest Cow
差分
对于每个限制$(l,r)$,我们建立一个差分数组$a[i]$
使$a[l+1]--,a[r]++$,表示$(l,r)$区间内的数至少比$l,r$小$1$
最后统计下前缀和,顺便把最大高度加上去。
记得判重。
(逃一节晚自习真chiji)
不写了,放风时间到了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
void swap(int &a,int &b) {a^=b^=a^=b;}
map <pair<int,int>,bool> mp; //bzoj 64mb 用不了bool二维
int n,m,mxi,id,a[],s;
int main(){
scanf("%d%d%d%d",&n,&id,&mxi,&m);
for(int i=,q1,q2;i<=m;++i){
scanf("%d%d",&q1,&q2);
if(q1>q2) swap(q1,q2);
if(!mp[make_pair(q1,q2)])
--a[q1+],++a[q2],mp[make_pair(q1,q2)]=;
}
for(int i=;i<=n;++i)
s+=a[i],printf("%d\n",s+mxi);
return ;
}