第一次听到离散化是今年省赛的时候，一道矩形并的题，很水，就两个矩形...
今天再去做线段树已经发现离散化忘得差不多了...水逼的悲哀啊...
先看简单点的hdu 1698
http://acm.hdu.edu.cn/showproblem.php?pid=1698
先做这个水题，在做poj 2528，当然poj 2528也很水
一、建树
把hook作为线段建树，近乎直接套线段树的模板。
二、计算结果
void cal(int i)
{
if(node[i].v)
{
tot+=(node[i].r-node[i].l+1)*node[i].v;
}
else
{
cal(i*2);
cal(i*2+1);
}
}
//poj 2528算的时候也是这样，近乎模板啊
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define N 100005
struct Node{
int l,r,m,v;
};
Node node[N*3];
int tot;
void build(int i,int left,int right)
{
Node &tmp=node[i];
tmp.l=left;
tmp.r=right;
tmp.m=(left+right)>>1;
tmp.v=1;
if(left<right)
{
build(i*2,left,tmp.m);
build(i*2+1,tmp.m+1,right);
}
}
void update(int i,int left,int right,int v)
{
Node &tmp=node[i];
if(tmp.l==left&&tmp.r==right)
{
tmp.v=v;
return ;
}
if(tmp.v==v)return ;/*有这一句可以省一些时间*/
if(node[i].v>0)
{
node[i*2].v=node[i*2+1].v=node[i].v;/*存储父亲节点的值*/
node[i].v=0;
}
/*downside >= or <= think about m,m+1*/
if(right<=tmp.m)
update(i*2,left,right,v);
else
if(tmp.m<left)
update(i*2+1,left,right,v);
else
{
update(i*2,left,tmp.m,v);
update(i*2+1,tmp.m+1,right,v);
}
}
void cal(int i)
{
if(node[i].v)
{
tot+=(node[i].r-node[i].l+1)*node[i].v;
}
else
{
cal(i*2);
cal(i*2+1);
}
}
int main()
{
int ncase,k,n,q,i,l,r,v;
//freopen("hdu 1698.in","r",stdin);
scanf("%d",&ncase);
for(k=1;k<=ncase;k++)
{
scanf("%d%d",&n,&q);
build(1,1,n);
for(i=0;i<q;i++)
{
scanf("%d%d%d",&l,&r,&v);
update(1,l,r,v);
}
tot=0;
cal(1);
printf("Case %d: The total value of the hook is %d.\n",k,tot);
}
return 0;
}
再看poj 2528
谈谈离散化，举个例子，1-5,3-9,11-18三条线段，此题根本不需要线段长度，
所以直接当成
1->1
3->2;
5->3;
9->4;
11->5
18->6;
于是原来的线段就转化为 1->3,2->4,5->6.这样建树会节省空间
另外建树的时候有个问题，tree[N*3]会RE,要tree[N*4]
其他跟poj 2528 一样的，关于离散化的具体做法，我在注释里写清楚吧，下面贴代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> using namespace std; #define N 20002 struct node{ int l,r,c; }; node tree[N*4]; struct line{ int s,id; }; line seg[N]; int des[N][2],ans,numc[N]; bool cmp(line a,line b) { return a.s<b.s; } void build(int i,int left,int right) { tree[i].l=left; tree[i].r=right; tree[i].c=0; if(left!=right) { int mid=(left+right)>>1; build(i*2,left,mid); build(i*2+1,mid+1,right); } } void update(int i,int ll,int rr,int col) { if(tree[i].l==ll&&tree[i].r==rr) { tree[i].c=col; return; } if(tree[i].c==col)return; int mid=(tree[i].l+tree[i].r)>>1; if(tree[i].c>0) { tree[i*2].c=tree[i*2+1].c=tree[i].c; tree[i].c=0; } if(rr<=mid) update(i*2,ll,rr,col); else if(mid<ll) update(i*2+1,ll,rr,col); else { update(i*2,ll,mid,col); update(i*2+1,mid+1,rr,col); } } void cal(int i) { if(tree[i].c>0) { if(!numc[tree[i].c]) { numc[tree[i].c]=1; ans++; } } else { cal(i*2); cal(i*2+1); } } int main() { //freopen("in.txt","r",stdin); int i,j,ncase,n; scanf("%d",&ncase); while(ncase--) { scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d",&des[i][0],&des[i][1]); seg[i*2].s=des[i][0]; seg[i*2].id=-(i+1); seg[i*2+1].s=des[i][1]; seg[i*2+1].id=i+1; /* 这里解释一下，为什么是seg[i*2]，seg[i*2+1]？ des数组起到两个作用： 一是记录原来的线段区间，就是这里的 scanf("%d%d",&des[i][0],&des[i][1]); 二是记录转化后的线段区间，就是下面num记点的个数 */ } sort(seg,seg+n*2,cmp); /*以下为离散化*/ int tmp=seg[0].s,num=1; for(i=0;i<n*2;i++) { if(seg[i].s!=tmp) { num++; tmp=seg[i].s; } if(seg[i].id<0) des[-seg[i].id-1][0]=num; else des[seg[i].id-1][1]=num; } /*建树及更新*/ build(1,1,num); int color=1; for(i=0;i<n;i++) update(1,des[i][0],des[i][1],color++); ans=0; memset(numc,0,sizeof(numc)); cal(1); printf("%d\n",ans); } return 0; }