zoj3299 线段树区间更新，坐标建立线段树的方式

/* 平台和砖块的坐标离散化，边缘坐标转换成单位长度 处理下落信息，sum数组维护区间的砖块数量 把平台按高度从高到低排序，询问平台区间的砖块有多少，询问后将该区域砖块数置0 */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define maxn 100005 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ll long long struct Blocks{ int l,r; }bks[maxn];//砖块信息 struct Boards{ int l,r,h,id; bool operator<(const Boards & a)const{ return h>a.h; } }bds[maxn];//平台信息 ll ans[maxn]; int data[maxn<<3],cnt,tot;//离散化 ll sum[maxn<<2],lazy[maxn],flag[maxn];//flag维护区间是否置零，优先级大于lazy inline void pushup(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } inline void pushdown(int l,int r,int rt){ if(flag[rt]){ sum[rt<<1]=sum[rt<<1|1]=0; flag[rt<<1]=flag[rt<<1|1]=1; flag[rt]=0; } else if(lazy[rt]){ int m=l+r>>1; lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt]; sum[rt<<1]+=lazy[rt]*(data[m]-data[l]+1); sum[rt<<1|1]+=lazy[rt]*(data[r]-data[m]); lazy[rt]=0; } } void setzero(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){ sum[rt]=0; lazy[rt]=0; flag[rt]=1; return; } pushdown(l,r,rt); int m=l+r>>1; if(L<=m) setzero(L,R,lson); if(R>m) setzero(L,R,rson); pushup(rt); } void build(int l,int r,int rt){ sum[rt]=lazy[rt]=flag[rt]=0; if(l==r) return; int m=l+r>>1; build(lson);build(rson); } void update(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){ lazy[rt]++; sum[rt]+=data[r]-data[l]+1; return; } pushdown(l,r,rt); int m=l+r>>1; if(L<=m) update(L,R,lson); if(R>m) update(L,R,rson); pushup(rt); } ll query(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){ return sum[rt]; } pushdown(l,r,rt); int m=l+r>>1; ll ret=0; if(L<=m) ret+=query(L,R,lson); if(R>m) ret+=query(L,R,rson); return ret; } int main(){ int n,m; while(scanf("%d%d",&n,&m)==2){ tot=cnt=0; for(int i=0;i<n;i++){ scanf("%d%d",&bks[i].l,&bks[i].r); bks[i].r--; data[cnt++]=bks[i].l; data[cnt++]=bks[i].r; } for(int i=0;i<m;i++){ scanf("%d%d%d",&bds[i].l,&bds[i].r,&bds[i].h); bds[i].id=i; bds[i].r--; data[cnt++]=bds[i].l; data[cnt++]=bds[i].r; } int tmp=cnt; sort(data,data+cnt); for(int i=1;i<cnt;i++) if(data[i]-data[i-1]>1) data[tmp++]=data[i-1]+1; cnt=tmp; sort(data,data+cnt); tot=unique(data,data+cnt)-data; sort(bds,bds+m); build(0,tot,1); for(int i=0;i<n;i++){ int L=lower_bound(data,data+tot,bks[i].l)-data; int R=lower_bound(data,data+tot,bks[i].r)-data; update(L,R,0,tot,1); } //每次查询后 for(int i=0;i<m;i++){ int L=lower_bound(data,data+tot,bds[i].l)-data; int R=lower_bound(data,data+tot,bds[i].r)-data; ans[bds[i].id]=query(L,R,0,tot,1); setzero(L,R,0,tot,1); } for(int i=0;i<m;i++) printf("%lld\n",ans[i]); } }

 碰到区间更新最头痛的就是坐标的离散化，所以上面的代码挂了

网上看题解，线段树有直接维护坐标的办法，但是维护方式和普通的区间更新略有不同

同时换了种比较容易懂的思路

/* 对于坐标轴上的离散化，与段的离散化有所不同，但也可以直接离散化而不用进行其它修改,其在线段树上的维护方式为[l,m],[m,r],同时分左右子树进行更新时判断条件也相应改变 比较快的做法，给横轴染色，然后再统计掉在每种颜色的砖头有几块 */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> using namespace std; #define maxn 100005 #define ll long long struct board{ int l,r,h,id; }b[maxn]; int n,m,l[maxn],r[maxn]; ll res[maxn]; ll sum[maxn<<4],flag[maxn<<4]; vector<int> a; bool cmp(const board &a,const board &b){ return a.h<b.h; } void pushdown(int k){ if(flag[k]){ flag[k<<1]=flag[k<<1|1]=flag[k]; flag[k]=0; } if(sum[k]){ sum[k<<1]+=sum[k]; sum[k<<1|1]+=sum[k]; sum[k]=0; } } //这个函数染色 void modify1(int k,int left,int right,int l1,int r1,int x){ if(l1<=left && r1>=right){ flag[k]=x; return; } pushdown(k); int mid=left+right>>1; //注意这里不可以等于,因为维护区间[l1,l1]没有任何意义 if(l1<mid) modify1(k<<1,left,mid,l1,r1,x); if(r1>mid) modify1(k<<1|1,mid,right,l1,r1,x); } //这个函数进行累加 void modify2(int k,int left,int right,int l1,int r1){ if(l1<=left && right<=r1){ sum[k]++; return; } pushdown(k); int mid=left+right>>1; if(l1<mid) modify2(k<<1,left,mid,l1,r1); if(r1>mid) modify2(k<<1|1,mid,right,l1,r1); } //统计 void query(int k,int left,int right){ if(flag[k]){ //因为直接维护坐标，所以两坐标直接相减 res[flag[k]]+=(ll)sum[k]*(a[right]-a[left]); return; } if(left+1==right)//判断退出递归并不是通过判断(l==r) return; pushdown(k); int mid=left+right>>1; query(k<<1,left,mid); query(k<<1|1,mid,right); } int main(){ int n,m; while(scanf("%d%d",&n,&m)==2){ a.clear(); //build()=init() memset(sum,0,sizeof sum); memset(flag,0,sizeof flag); memset(res,0,sizeof res); for(int i=1;i<=n;i++){ scanf("%d%d",&l[i],&r[i]); a.push_back(l[i]); a.push_back(r[i]); } for(int i=1;i<=m;i++){ scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].h); b[i].id=i; a.push_back(b[i].l); a.push_back(b[i].r); } sort(a.begin(), a.end()); a.erase(unique(a.begin(),a.end()),a.end()); int cnt=a.size(); sort(b+1,b+1+m,cmp); for(int i=1;i<=m;i++){ int pos1=lower_bound(a.begin(),a.end(),b[i].l)-a.begin(); int pos2=lower_bound(a.begin(),a.end(),b[i].r)-a.begin(); modify1(1,0,cnt-1,pos1,pos2,b[i].id); } for(int i=1;i<=n;i++){ int pos1=lower_bound(a.begin(),a.end(),l[i])-a.begin(); int pos2=lower_bound(a.begin(),a.end(),r[i])-a.begin(); modify2(1,0,cnt-1,pos1,pos2); } query(1,0,cnt-1); for(int i=1;i<=m;i++) printf("%lld\n",res[i]); puts(""); } return 0; }

 

转载于:https://www.cnblogs.com/zsben991126/p/9929694.html