博客

马不停蹄，马不停蹄，才写完上一部分，没有时间休息，又要开始下一部分了。这部分主要是线段树区间更新的难题和区间合并的一些题目，最后最困难的扫描线算法应该会出现在第三部分。

第一题

ZOJ 1610

分析：首先声明一点这道题我没有AC，当然不是因为我不会，而是因为坑人的ZOJ又爆炸了，交不了代码。所以万一我的代码出了问题，你们不准打我，思路是肯定没有问题的。

其实这道题不算难题啦，只是因为我的失误，错把它分到第二部分了，唉，就当热身。

给你N个气球，在区间端上刷颜色，最后让你求每个颜色的段数。那么还是老套路，区间更新+最后查询一次。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          8000+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------

int col[maxn<<2];
int vis[maxn];
int anw[maxn];
void build(int l,int r,int rt){
    col[rt]=-1;
    if(l==r){
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}
void pushdown(int rt){
    if(col[rt]!=-1){
        col[rt<<1]=col[rt<<1|1]=col[rt];
        col[rt]=-1;
    }
}
void update(int l,int r,int rt,int L,int R,int p){
    if(L<=l&&r<=R){
        col[rt]=p;
        return;
    }
    pushdown(rt);
    int m=(l+r)>>1;
    if(L<=m)update(lson,L,R,p);
    if(R>m) update(rson,L,R,p);
}
void query(int l,int r,int rt){
    if(col[rt]!=-1){
        for(int i=l;i<=r;i++)
            anw[i]=col[rt];
        return ;
    }
    if(l==r){
        anw[l]=-1;
        return ;
    }
    pushdown(rt);
    int m=(l+r)>>1;
    query(lson);
    query(rson);
}
int main(){
    //freopen("d:\\acm\\in.in","r",stdin);
    int n;
    while(~scanf("%d",&n)){
        build(1,8000,1);
        while(n--){
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            a++;
            update(1,8000,1,a,b,c);
        }
        query(1,8000,1);
        clr(vis,0);
        if(anw[1]!=-1)vis[anw[1]]++;
        for(int i=2;i<=8000;i++)
            if(anw[i]!=-1&&anw[i]!=anw[i-1])
                vis[anw[i]]++;
        for(int i=0;i<=8000;i++)
            if(vis[i])
                printf("%d %d\n",i,vis[i]);
        puts("");
    }
    return 0;
}

第二题

POJ 3264

分析：第二题也不难。是求区间最大值与最小值的差+区间更新。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          50000+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------

int minn[maxn<<2];
int maxx[maxn<<2];
void pushup(int rt){
    minn[rt]=min(minn[rt<<1],minn[rt<<1