POJ - 2528 区间离散化，线段树区间修改，区间询问
这个题非常有意思的地方是，我们发现区间[1,4]和[5,8]是紧挨着的，因为这个的数代表的是一段区间，原本我们对于普通的离散，
a[1]=1,a[2]=5,a[3]=6,a[4]=8;数组下标就是重新离散的位置，但是a[2]和a[3]明显不重叠，为此我们需要重新考虑离散的内容，其实不妨这样，如果区间的间隔大于1，那么我们插入一个数a[i]+1，这样就强行把a[i]和a[i+1]分开，因为
如三张海报为：1~10 1~4 6~10
离散化时 X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 6, X[ 4 ] = 10
第一张海报时：墙的1~4被染为1；
第二张海报时：墙的1~2被染为2，3~4仍为1；
第三张海报时：墙的3~4被染为3，1~2仍为2。
最终，第一张海报就显示被完全覆盖了，于是输出2，但实际上明显不是这样，正确输出为3。
新的离散方法为：在相差大于1的数间加一个数，例如在上面1 4 6 10中间加5（算法中实际上1，4之间，6，10之间都新增了数的）
为什么会这样呢？我们这样考虑，如果a[1]=3,a[2]=4那么他们两个是相邻的，这样其实离散后他们还是相邻的（因为1,2在题目的意义是相邻的），但是如果是a[1]=3,a[2]=5哈希后其实是(1,2) 它是相邻的(实际上3,5不相邻)，于是我们想到这样，既然我们中间有一段（没有数那一段）是我们所忽略的，我们可以新加一个数4,如
a[1]=3 a[2]=4 a[3]=5; 这样哈希后是1,2,3,我们认为3->1而5->3，(1,3)其实是不相邻的。这道题也就没什么问题了，最后区间查询+区间修改。
#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; const int maxn = 10005; int sum[maxn<<4]; int vis[maxn<<3]; int li[maxn*2]; int ri[maxn*2]; int lsh[maxn<<2]; void pushdown(int root){//把节点信息传给儿子节点 sum[root<<1]=sum[root];//相应这个节点如果最后被修改成这个结果，那么他的儿子节点也应该修改 sum[root<<1|1]=sum[root]; sum[root]=-1;//清空laze标记 } int ans; void update(int root,int L,int R,int C,int l,int r){ if (L<=l && r<=R)//如果被修改区间完全盖过当前区间 { sum[root]=C;//更新 return; } if (sum[root]!=-1) pushdown(root);//如果不满足上述条件，我们需要把节点的信息更新， int m=(l+r)>>1; if (m>=R)update(root<<1,L,R,C,l,m);//信息完全在左子树 else if(L>m)update(root<<1|1,L,R,C,m+1,r);//完全在右子树 else update(root<<1,L,m,C,l,m),update(root<<1|1,m+1,R,C,m+1,r); } void query(int root,int l,int r){ // cout<<root<<endl; if (sum[root]!=-1 && !vis[sum[root]])//如果当前节点的信息已经能包含所有的节点信息，并且这个节点的信息是第一次访问到 { ans++; vis[sum[root]]=1; return; } if (l==r) { return; } if (sum[root]!=-1) pushdown(root);//更新标记 int m=(l+r)/2; query(root<<1,l,m); query(root<<1|1,m+1,r); } int main(){ int t; int n; scanf("%d",&t); while(t--){ scanf("%d",&n); memset(sum,-1,sizeof(sum)); memset(vis,0,sizeof(vis)); int tot=0; for (int i=0;i<n;i++) { scanf("%d%d",&li[i],&ri[i]); lsh[tot++]=li[i]; lsh[tot++]=ri[i]; } sort(lsh,lsh+tot); int mm=unique(lsh,lsh+tot)-lsh; int tt=mm; for (int i=1;i<tt;i++) { if (lsh[i]-lsh[i-1]>1) lsh[mm++]=lsh[i-1]+1; } sort(lsh,lsh+mm);//排序 按照数组下标进行离散 for (int i=0;i<n;i++){ int x=lower_bound(lsh,lsh+mm,li[i])-lsh;//查找左边的离散后的号码 int y=lower_bound(lsh,lsh+mm,ri[i])-lsh;//查找右边的离散后的号码 update(1,x,y,i,0,mm-1);//更新 } ans=0; query(1,0,mm-1); printf("%d\n",ans); } return 0; }
查看18道真题和解析
