组队赛6：线段树离散化+树状数组并哈希

G题：URAL 1987

这题比赛的时候没看懂题目，现在又研究了好久，把题意理解错了，然后看队友交的代码都不懂，大帝一提醒才知道又把题意看错了^_^.因为把以前的线段树模板给放弃了，采取了更加飘逸的数组写法，所以还不是很熟悉……而且代码是看了别人的，代码与上次保存的代码都差不多，就是处理lazy标记的不一样而已，就是这个不一样，苦死我了，现在那个Pushup函数还没看懂怎么意思……唉……过段时间回来看看应该才懂吧……

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define sc(a,b) scanf("%d%d",&a,&b)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 1000005
#define MN 200050
#define INF 1000000009
#define eps 1e-7
using namespace std;
typedef long long ll;
int lazy[MN*8],a[MN/2],b[MN/2],c[MN*8],q[MN/2];
void pushdown(int i) //处理lazy标记
{
    if(lazy[i]!=-1) 
    {
        lazy[i<<1]=lazy[i<<1|1]=lazy[i];
        lazy[i]=-1;  //去除标记
    }
}
void pushup(int i)
{
    if(lazy[i<<1]==lazy[i<<1|1]) lazy[i]=lazy[i<<1]; //不过这句话没看懂
    else lazy[i]=-1;
}
void update(int i,int l,int r,int L,int R,int val)
{
    if(L<=l&&r<=R) {lazy[i]=val;return ;}
    pushdown(i);  //处理lazy标记往下传
    int mid=(l+r)>>1;
    if(L<=mid) update(lson,L,R,val);
    if(R>mid) update(rson,L,R,val);
    pushup(i);
}
int query(int i,int l,int r,int w)
{
    if(l==r) return lazy[i];
    pushdown(i);  //处理lazy标记往下传
    int res,mid=(l+r)>>1;
    if(w<=mid) res=query(lson,w);
    else res=query(rson,w);
    pushup(i);
    return res;
}
int main()
{
    int n,m,i,cnt=0;
    mem(lazy,-1);
    sca(n);
    for(i=1;i<=n;i++)
    {
        sc(a[i],b[i]);
        c[cnt++]=a[i];
        c[cnt++]=b[i];
    }
    sca(m);
    for(i=1;i<=m;i++)
        sca(q[i]),c[cnt++]=q[i];
    sort(c,c+cnt);
    cnt=unique(c,c+cnt)-c;  //去重离散化
    for(i=1;i<=n;i++)
    {
        int L=lower_bound(c,c+cnt,a[i])-c+1;
        int R=lower_bound(c,c+cnt,b[i])-c+1;
        update(1,1,cnt,L,R,i);
    }
    for(i=1;i<=m;i++)
        pri(query(1,1,cnt,lower_bound(c,c+cnt,q[i])-c+1));
    return 0;
}

组队赛6：线段树离散化+树状数组并哈希,布布扣,bubuko.com

组队赛6：线段树离散化+树状数组并哈希

原文：http://blog.csdn.net/u011466175/article/details/23204603