最近这道题，一连出现了三次,所以在这儿记录一下

http://codeforces.com/contest/1029/problem/C
题意：给定n条线段，求删除其中一条线段之后这n条线段的共同交集最大是多少。

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+7;
const int inf = 0x3f3f3f3f;
int prl[N],prr[N],sufl[N],sufr[N];
struct node
{
    int l,r;
} p[N];
//所有线段的交集就是最大的左端点到最小的右端点
int main()
{
    int n;
    cin>>n;
    prl[1] = sufl[n+1] = 0;
    //prl[0] = sufl[n] = 0;
    prr[1]= sufr[n+1]  = inf;
    //prr[0]= sufr[n] = inf;
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&p[i].l,&p[i].r);

    }
    //初始化注意pre[1]无用，suf[n+1]无用，所以要特殊初始化，之后算好循环终止即可
    for(int i=1; i<=n-1; i++)
    {
        prl[i+1] = max(p[i].l,prl[i]);
        prr[i+1] = min(prr[i],p[i].r);
    }
    for(int i=n; i>=1; i--)
    {
        sufl[i] = max(p[i].l,sufl[i+1]);
        sufr[i] = min(p[i].r,sufr[i+1]);
    }
    long long ans =0 ;
    for(int i=1; i<=n; i++)
    {
        long long tmp1 = max(prl[i],sufl[i+1]);
        long long tmp2 = min(prr[i],sufr[i+1]);
        ans = max(ans,tmp2-tmp1);
    }
    cout<<ans<<endl;
    return 0;
}

code2：

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+7;
const int inf = 0x3f3f3f3f;
int prl[N],prr[N],sufl[N],sufr[N];
struct node
{
    int l,r;
} p[N];
//所有线段的交集就是最大的左端点到最小的右端点
int main()
{
    int n;
    cin>>n;
    sufl[n+1] = 0;
    prl[1] =0;
    sufr[n+1]  = inf;
    prr[1]= inf;
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&p[i].l,&p[i].r);

    }
    for(int i=2; i<=n; i++)
    {
        prl[i] = max(p[i-1].l,prl[i-1]);
        prr[i] = min(prr[i-1],p[i-1].r);
    }
    for(int i=n; i>=1; i--)
    {
        sufl[i] = max(p[i].l,sufl[i+1]);
        sufr[i] = min(p[i].r,sufr[i+1]);
    }
    long long ans =0 ;
    for(int i=1; i<=n; i++)
    {
        long long tmp1 = max(prl[i],sufl[i+1]);
        long long tmp2 = min(prr[i],sufr[i+1]);
        ans = max(ans,tmp2-tmp1);
    }
    cout<<ans<<endl;
    return 0;
}

线段树版：

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define lson rt<<1
#define rson rt<<1|1
#define MID int m = (l+r)/2;
const int N = 3e6+7;
struct node
{
    int l,r;
  // node(int ll=0,int rr=0):l(ll),r(rr){}

}tree[N], p[N] ;

node mm(node a, node b)
{
    node g;
    g.l = max(a.l,b.l);
    g.r = min(b.r,a.r);
    return g;
}
void push_up(int rt)
{
    tree[rt] = mm(tree[lson],tree[rson]);
}
void build(int rt,int l,int r)
{
    if(l==r)
    {
        tree[rt] = p[l];
        return ;
    }
    MID
    build(lson,l,m);
    build(rson,m+1,r);
    push_up(rt);
}
node query(int rt,int l,int r,int ql,int qr)
{
    node h;
    h.l = 0;
    h.r = 0x3f3f3f3f;
    if(ql<=l&&qr>=r)return tree[rt];
    if(ql>r||qr<l)return  h;

    MID
    return mm(query(lson,l,m,ql,qr),query(rson,m+1,r,ql,qr));

}
int main()
{

    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
       scanf("%d%d",&p[i].l,&p[i].r);
    }
    build(1,1,n);
    int ans= 0;
    for(int i=1;i<=n;i++)
    {
        node tmp1 ;
        if(i==1) {

            tmp1 = query(1,1,n,2,n);
        }
        else if(i==n)
        {
            tmp1 = query(1,1,n,1,n-1);
        }
        else
        {
         tmp1 = query(1,1,n,1,i-1);
        node tmp2 = query(1,1,n,i+1,n);
        tmp1 = mm(tmp1,tmp2);
        }

        ans= max(ans,tmp1.r-tmp1.l);
    }
    cout<<ans<<endl;


    return 0;
}

https://vjudge.net/contest/250168#problem/G
G - Running a penitentiary Gym - 101879G
增加了修改操作

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define lson rt<<1
#define rson rt<<1|1
#define MID int m = (l+r)/2;
const int N = 1e6+7;
struct node
{
    int l,r;
    node(int ll=0,int rr=0):l(ll),r(rr){}

}tree[N], p[N] ,t;

node mm(node a, node b)
{
    node g;
    g.l = max(a.l,b.l);
    g.r = min(b.r,a.r);
    return g;
}
void push_up(int rt)
{
    tree[rt] = mm(tree[lson],tree[rson]);
}
void build(int rt,int l,int r)
{
    if(l==r)
    {
        tree[rt] = p[l];
        return ;
    }
    MID
    build(lson,l,m);
    build(rson,m+1,r);
    push_up(rt);
}
node query(int rt,int l,int r,int ql,int qr)
{
    node h;
    h.l = -0x3f3f3f3f;
    h.r = 0x3f3f3f3f;
    if(ql<=l&&qr>=r)return tree[rt];
    if(ql>r||qr<l)return  h;

    MID
    return mm(query(lson,l,m,ql,qr),query(rson,m+1,r,ql,qr));

}
void update(int rt,int l,int r,int x,node p)
{
    if(x<l||x>r)return ;
    if(l==r)
    {
        tree[rt] = p;
        return;
    }
    MID
    update(lson,l,m,x,p);
    update(rson,m+1,r,x,p);
    push_up(rt);
}
int main()
{

    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
       scanf("%d%d",&p[i].l,&p[i].r);
    }
    build(1,1,n);
    int ans= 0;
    string op;
    for(int i=1;i<=m;i++)
    {

        int ll,rr;
        cin>>op;
        if(op[0]=='?')
        {
            cin>>ll>>rr;
           t = query(1,1,n,ll,rr);
           cout<<max(0,t.r-t.l+1)<<endl;
        }
        else
        {
           int cc;
           cin>>cc>>ll>>rr;
           update(1,1,n,cc,node(ll,rr));

        }

    }
   // cout<<ans<<endl;


    return 0;
}

http://codeforces.com/contest/1028/problem/C

#include <bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;


struct node
{
    int l,r,u,d;
}a[210000],l[210000],r[210000],t;

node f(node a,node b)
{
    node c;
    c.l=max(a.l,b.l);
    c.d=max(a.d,b.d);
    c.u=min(a.u,b.u);
    c.r=min(a.r,b.r);
    return c;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&a[i].d,&a[i].l,&a[i].u,&a[i].r);
    }
    l[0].l=l[0].d=r[n+1].l=r[n+1].d=-1234567890;
    l[0].r=l[0].u=r[n+1].r=r[n+1].u=1234567890;
    for(int i=1;i<=n;i++)
    {
        l[i]=f(l[i-1],a[i]);
    }
    for(int i=n;i>=1;i--)
    {
        r[i]=f(r[i+1],a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        t=f(l[i-1],r[i+1]);
        if(t.r>=t.l&&t.u>=t.d)
        {
            printf("%d %d\n",t.d,t.l);
            break;
        }
    }
    return 0;
}