/*
一道很明显的离散化啦
我们来看一下这道题的意思其实就是
对于n个可相交区间
问其中共有多少个元素
一个典型的裸体了叭
x,y可能达到10^9而数据其实最多只有20000个x,y
这样就会很明显想到离散化了
读入区间后对所有区间快排
以左端点为第一关键字  右端点为第二关键字
从小到大一排
再从1-n-1所有的区间
如果当前的某个区间
可以扩展连到下一个区间
即比如[2,8]和[6,10]
有相交部分
那么这段我们就可以不处理
转移叠加到下一段中去
就是a[i+1].x=a[i].x   a[i+1].y=max(a[i].y,a[i+1].y)
就把当前区间融入到下一个区间了
而当当前区间和下一个区间没有交集之时
这个区间就是一个最大的联合区间了
加上它的元素个数
这样的操作进行到n-1
这个时候第n个区间可能已经融合了某个区间
也可能没有融合
我们再将最后一个区间的长度加入即可
水题Orz
然而窝好弱
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=20005;
struct node
{
    int x,y;
}a[MAXN];
int n;
int ans;

inline bool cmp(node a,node b)
{
    return a.x==b.x?a.y<b.y:a.x<b.x;
}

void init()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
}

int main()
{
    init();
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<n;i++)
    {
        if(a[i].y>=a[i+1].x)
        {
            a[i+1].x=a[i].x;
            a[i+1].y=max(a[i].y,a[i+1].y);
        }
        else
            ans+=a[i].y-a[i].x;
    }
    ans+=a[n].y-a[n].x;
    cout<<ans<<endl;
    return 0;
}
     

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
    class itv{
    public:
        int x,y;
    };
    int cmpitv(itv a,itv b)
    {
        return a.x<b.x||(a.x==b.x&&a.y<b.y);
    }
    
    int n,ans;
    itv a[1<<15];
    
    void main()
    {
        scanf("%d",&n);
        for (int i=0;i<n;i++)
            scanf("%d%d",&a[i].x,&a[i].y);
        sort(&a[0],&a[n],cmpitv);
        ans=0;
        for (int i=0;i<n-1;i++)
            if (a[i].y>=a[i+1].x)
            {
                a[i+1].x=a[i].x;
                a[i+1].y=max(a[i].y,a[i+1].y);
            }
            else
                ans+=a[i].y-a[i].x;
        ans+=a[n-1].y-a[n-1].x;
        printf("%d\n",ans);
    }
};

int main()
{
    dts::main();
}

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct no{
    int x,y;
}h[23333];
bool cmp(no a,no b){
    return a.x<b.x;
}
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d %d",&h[i].x,&h[i].y);
    sort(h+1,h+1+n,cmp);
    int x=h[1].x,y=h[1].y;
    int sum=0;
    for(int i=2;i<=n;i++){
        if(h[i].x<y){
            if(h[i].y>y)
                y=h[i].y;
        }
        else{           
            sum+=y-x;
            x=h[i].x;
            y=h[i].y;
        }
    }
    sum+=y-x;
    cout<<sum;
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
long long a[100000],b[100000];
int main()
{
long long n,num=0;
cin>>n;
for (long long i=0;i<n;i++)
{
cin>>a[i]>>b[i];
}
sort (a,a+n);
sort (b,b+n);
a[n]=99999999999;
for (long long i=0;i<n;i++)
{
if (a[i+1]<b[i])
{
num+=a[i+1]-a[i];
}
else num+=b[i]-a[i];
}
cout<<num;
return 0;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 62 ms, mem = 868 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 864 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #5: Accepted, time = 31 ms, mem = 860 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 860 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 864 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 864 KiB, score = 10
Accepted, time = 169 ms, mem = 868 KiB, score = 100
代码
#include<iostream>
#include<algorithm>
const int size = 20010;
int main()
{
using namespace std;
int n;
long long a[size],b[size],sum=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i]>>b[i];
}
sort(a,a+n);sort(b,b+n);
a[n]=111111111111;
for(int i=0;i<=n-1;i++)
{
if(a[i+1]<=b[i])
sum+=(a[i+1]-a[i]);
else sum+=(b[i]-a[i]);

}
cout<<sum;
return 0;
}

留个另类算法，类似差分的思路，不过用一个ln指针维护已经算过的最右面。【用到一堆数学证明就略了】
```c++
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll l[20005], r[20005];
ll a, b, n;
int main()
{
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", &a, &b);
if (b < a) swap(a, b);
l[i] = a, r[i] = b;
}
sort(l+1, l+n+1);
sort(r+1, r+n+1);
ll ln = INT_MIN, ans = 0;
for (int i = 1; i <= n; i++) {
if (r[i] <= ln) continue;
if (l[i] <= ln) {
ans += r[i]-ln;
ln = r[i];
continue;
}
ln = r[i];
//cout << i << " " << r[i] << " " << l[i] << endl;
ans += r[i]-l[i];
}
cout << ans << endl;
return 0;
}
```

区间真是一个有趣的东西2333

sort comp写错还过了7组。。。。

测试数据 #0: Accepted, time = 15 ms, mem = 2372 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2372 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2368 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2372 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 2364 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 2372 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 2368 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 2368 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 2368 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 2368 KiB, score = 10
Accepted, time = 30 ms, mem = 2372 KiB, score = 100
为什么不能0 second？

首先把所有的区间按l为第一关键字，r为第二关键字升序排序
然后从第一个开始，如果这个区间和下一个区间有交集 则合并到下一个区间里去，否则答案加上这个区间的长度
最后加上最后一个区间的长度即可
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=20010;
struct line{int l,r;}s[N];
int n,head,tail;
long long ans;
bool cmp(line a,line b){return a.l==b.l? a.r<b.r:a.l<b.l;}
int main(){
//freopen("1165.in","r",stdin);freopen("1165.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&s[i].l,&s[i].r);
sort(s+1,s+n+1,cmp);
for(int i=1;i<n;i++){
if(s[i].r>=s[i+1].l) s[i+1].l=s[i].l,s[i+1].r=max(s[i].r,s[i+1].r);
else ans+=s[i].r-s[i].l;
}
ans+=s[n].r-s[n].l;
printf("%lld",ans);
return 0;
}

#include<queue>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
struct hehe{
int a,b;
bool operator<(const hehe tmp)const{return a<tmp.a;}
};
int n;
long long num;
hehe x[20005];
void work(){
int l,r;
l=x[1].a;r=x[1].b;
for (int i=2;i<=n;i++){
if (x[i].a<r) x[i].a=r;
else l=x[i].a;
if (x[i].b<r) x[i].b=r;
else r=x[i].b;
}
for (int i=1;i<=n;i++)
num+=x[i].b-x[i].a;
}
int main(){
scanf("%d",&n);
if (n==0){printf("0");return 0;}
for (int i=1;i<=n;i++)
scanf("%d%d",&x[i].a,&x[i].b);
sort(x+1,x+1+n);
work();
printf("%I64d",num);
}
AC的C++代码

program fire;
type
note1=record
a:longint;
b:longint;
end;
var
c:array[1..21000] of note1;
//d:array[1..21000] of note2;
n,i,j,ans,last:longint;
t:note1;
procedure qsort(l,r:longint);
var
i,j,x: longint;
begin
i:=l;
j:=r;
x:=c[(l+r) div 2].a;
repeat
while c[i].a<x do
inc(i);
while x<c[j].a do
dec(j);
if not(i>j) then
begin
t:=c[i];
c[i]:=c[j];
c[j]:=t;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
qsort(l,j);
if i<r then
qsort(i,r);
end;
begin
{assign(input,'fire.in');
assign(output,'fire.out');
reset(input);
rewrite(output);}
readln(n);
ans:=0;
for i:=1 to n do
readln(c[i].a,c[i].b);
qsort(1,n);
ans:=c[1].b-c[1].a;
last:=c[1].b;
for i:=2 to n do
begin
if c[i].a<=last then
begin
if c[i].b>last then
begin
ans:=ans+c[i].b-last;
last:=c[i].b;
end;
end
else begin
ans:=ans+c[i].b-c[i].a;
last:=c[i].b;
end;
end;
writeln(ans);
{close(input);
close(output);}
end.

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <stack>

using namespace std;

int n;
int i , j;

struct line
{
long long l , r;
};

int cmp( line x , line y )
{
if( x.l < y.l )
return 1;
if( x.l > y.l )
return 0;
if( x.r > y.r )
return 0;
return 1;
}

line a[2000000 + 2];
line t;
stack < line > s;
long long ans;

int main()
{
scanf( "%d" , &n );
for( i = 0 ; i < n ; i++ )
{
scanf( "%lld %lld" , &a[i].l , &a[i].r );
if( a[i].l >= a[i].r )
{
i--;
n--;
}
if( i > 0 )
if( a[i].l == a[i - 1].l && a[i].r == a[i - 1].r )
{
i--;
n--;
}
}
sort( a , a + n , cmp );
t.l = a[0].l;
t.r = a[0].r;
j = 0;
for( i = 1 ; i < n ; i++ )
if( a[i].r > a[i].l )
{
if( t.r == -1000000001 )
{
t.l = a[i - 1].l;
t.r = a[i].r;
}
else if( t.r >= a[i].l )
{
t.r = max( a[i].r , t.r );
t.l = min( a[i].l , t.l );
}
else
{
if( t.l != -1000000001 )
s.push( t );
t.l = a[i].l;
t.r = a[i].r;
}
}
if( t.l != -1000000001 )
s.push( t );
ans = 0;
while( !s.empty() )
{
t = s.top();
s.pop();
if( t.r > t.l )
ans += t.r - t.l;
}
cout << ans << endl;
return 0;
}

艹！

纯暴力 过七个点 求优化
var n,ans,maxn:longint;
be,en,data:array[1..20000] of longint;

procedure init;
var i:longint;
begin
fillchar(data,sizeof(data),0);
readln(n);
for i:=1 to n do
readln(be[i],en[i]);
end;

procedure put;
var i,j:longint;
begin
for i:=1 to n do
for j:=be[i] to en[i] do
if (be[i]<>en[i]) then inc(data[j]);
end;

procedure max;
var i:longint;
begin
maxn:=0;
for i:=1 to n do
if en[i]>maxn then maxn:=en[i];
end;

procedure count;
var i:longint;
begin
for i:=1 to maxn do
if (data[i]<>0) then inc(ans);
end;

begin
init;
put;
max;
count;
writeln(ans);
end.

记录信息
评测状态 Runtime Error
题目 P1165 火烧赤壁
递交时间 2013-12-17 23:00:05
代码语言 C
评测机 VijosEx
消耗时间 778 ms
消耗内存 2464 KiB
评测时间 2013-12-17 23:00:06
评测结果
编译成功

测试数据 #0: Accepted, time = 374 ms, mem = 828 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 440 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 432 KiB, score = 10
测试数据 #3: Accepted, time = 31 ms, mem = 532 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 532 KiB, score = 10
测试数据 #5: Accepted, time = 124 ms, mem = 604 KiB, score = 10
测试数据 #6: RuntimeError, time = 31 ms, mem = 2464 KiB, score = 0
测试数据 #7: Accepted, time = 187 ms, mem = 1232 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 484 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 484 KiB, score = 10
RuntimeError, time = 778 ms, mem = 2464 KiB, score = 90
代码
#include <stdio.h>
int main (){
long n,i,j,m;
scanf ("%ld",&n);
double a[n][2],max=-2147400000000000,min=214740000000000,sum=0;
for (i=0;i<n;i++)
{scanf ("%lf%lf",&a[i][0],&a[i][1]);
if (a[i][0]>=a[i][1]) {continue;}
if (a[i][1]>=5000000||a[i][0]>=5000000||a[i][0]<=-5000000||a[i][1]<=-5000000||a[i][0]-a[i][1]>=5000000) {continue;}
if (a[i][0]>max) {max=a[i][0];}
if (a[i][0]<min) {min=a[i][0];}
if (a[i][1]>max) {max=a[i][1];}
if (a[i][1]<min) {min=a[i][1];}
}
if (max<=min)
{printf ("0");return 0;
}
m=(long)(max-min+1);
int zx[m];
for (i=0;i<max-min;i++)
{zx[i]=0;
}
for (i=0;i<n;i++)
{if (a[i][0]>=a[i][1])
{continue;}
if (a[i][0]<min||a[i][1]>max+1)
{continue;}
if (a[i][1]>=5000000||a[i][0]>=5000000||a[i][0]<=-5000000||a[i][1]<=-5000000||a[i][0]-a[i][1]>=5000000)
{sum+=a[i][1]-a[i][0];continue;}
for (j=a[i][0]-min;j<=a[i][1]-min;j++)
{zx[j]=1;
}
}
for (i=0;i<max-min;i++)
{if (zx[i]!=0) {sum++;}
}
printf ("%0.lf",sum);
return 0;
}
为什么？？？

#include <stdio.h>
int main (){
long n,i,j,m;
scanf ("%ld",&n);
double a[n][2],max=-2147400000000000,min=214740000000000,sum=0;
for (i=0;i<n;i++)
{scanf ("%lf%lf",&a[i][0],&a[i][1]);
if (a[i][0]>=a[i][1]) {continue;}
if (a[i][1]>=5000000||a[i][0]>=5000000||a[i][0]<=-5000000||a[i][1]<=-5000000||a[i][0]-a[i][1]>=5000000) {continue;}
if (a[i][0]>max) {max=a[i][0];}
if (a[i][0]<min) {min=a[i][0];}
if (a[i][1]>max) {max=a[i][1];}
if (a[i][1]<min) {min=a[i][1];}
}
if (max<=min)
{printf ("0");return 0;
}
m=(long)(max-min+1);
int zx[m];
for (i=0;i<max-min;i++)
{zx[i]=0;
}
for (i=0;i<n;i++)
{if (a[i][0]>=a[i][1])
{continue;}
if (a[i][0]<min||a[i][1]>max+1)
{continue;}
if (a[i][1]>=5000000||a[i][0]>=5000000||a[i][0]<=-5000000||a[i][1]<=-5000000||a[i][0]-a[i][1]>=5000000)
{sum+=a[i][1]-a[i][0];continue;}
for (j=a[i][0]-min;j<=a[i][1]-min;j++)
{zx[j]=1;
}
}
for (i=0;i<max-min;i++)
{if (zx[i]!=0) {sum++;}
}
printf ("%0.lf",sum);
return 0;
}
评测结果
编译成功

测试数据 #0: Accepted, time = 374 ms, mem = 828 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 440 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 432 KiB, score = 10
测试数据 #3: Accepted, time = 31 ms, mem = 532 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 532 KiB, score = 10
测试数据 #5: Accepted, time = 124 ms, mem = 604 KiB, score = 10
测试数据 #6: RuntimeError, time = 31 ms, mem = 2464 KiB, score = 0
测试数据 #7: Accepted, time = 187 ms, mem = 1232 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 484 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 484 KiB, score = 10
RuntimeError, time = 778 ms, mem = 2464 KiB, score = 90
为什么？？？

跟NOIP2005第2题《校门外的树》差不多。。。

小心第六个点测试点，坑坑坑坑！！！

AC第40题，纪念一下。
先快排
var
a,b:array[0..20000]of longint;
i,j,k,n,s:longint;

procedure qsort(l,r: longint);
var i,j,x,y: longint;
begin
i:=l;j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if i<=j then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
y:=b[i]; b[i]:=b[j]; b[j]:=y;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;

begin
read(n);
for i:=1 to n do read(a[i],b[i]);
qsort(1,n);
b[0]:=-1000000000;
for i:=1 to n do
begin
if b[i-1]>a[i] then a[i]:=b[i-1];
if a[i]>b[i] then b[i]:=a[i];
end;
for i:=1 to n do
s:=s+b[i]-a[i];
writeln(s);
end.

算法：离散优化