M_sea

洛谷2879 区间统计Tallest Cow
Luogu分析若两头$a$,$b$互相可见,那么它们中间的所有牛都比它们矮。要使可能的身高最高,显然矮1是最好的。...
扫描右侧二维码阅读全文
28
2018/11

洛谷2879 区间统计Tallest Cow

Luogu

分析

若两头$a$,$b$互相可见,那么它们中间的所有牛都比它们矮。

要使可能的身高最高,显然矮1是最好的。

那么把$(a+1,b-1)$这一段减去1即可,最后得出的这个数组再加上最高的身高。

区间减,无查询,可以用差分搞。

代码

#include <bits/stdc++.h>
#define re register
#define mp make_pair
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=10000+10;

int d[MAXN];
map<pair<int,int>,int> S;

int main() {
    int n=read(),p=read(),h=read(),m=read();
    for (re int i=1,l,r,tmp;i<=m;++i) {
        l=read(),r=read();
        if (l>r) tmp=l,l=r,r=tmp;
        if (S[mp(l,r)]) continue;
        S[mp(l,r)]=1,--d[l+1],++d[r];
    }
    for (re int i=1;i<=n;++i) printf("%d\n",h+(d[i]+=d[i-1]));
    return 0;
}
最后修改:2018 年 12 月 02 日 09 : 22 PM

发表评论