自动搬运

查看原文

来自洛谷，原作者为

	蹲在丛中笑 qq1939827644

搬运于2025-08-24 21:37:40，当前版本为作者最后更新于2017-11-22 22:49:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

震惊地发现竟然还没有人贴差分的题解。。

没错，就像楼下某位大佬说的，每次输入x和y，于是x的度++，y的度--

然后再扫一遍，累积从0到+的就是左端点，从+到0的就是右端点。

时间复杂度O（1e6）

貌似不是很优越？

总之代码很短很好写

#include<stdio.h>
#define N 1000005
int n,x,y,cnt,a[N],b[N];
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d%d",&x,&y);
        a[x]++; b[y]++;
    }
    for(int i=1;i<N;i++) {
        if(!cnt&&a[i]) printf("%d ",i);
        cnt+=a[i]-b[i];
        if(!cnt&&b[i]) printf("%d\n",i);
    }
}