題目鏈接：點(diǎn)擊查看

題目大意：給定一個(gè)長(zhǎng)度為1e7的墻，然后給出n張海報(bào)，每張海報(bào)都會(huì)占據(jù)墻上的一部分寬度，問(wèn)按照給出的次序往墻上貼海報(bào)，

最后有幾張海報(bào)能露出來(lái)（露出部分也算）

題目分析：線(xiàn)段樹(shù)的區(qū)間更新，因?yàn)閿?shù)據(jù)過(guò)大，必須先用離散化預(yù)處理一下給出的海報(bào)，不過(guò)這個(gè)題目需要注意，使用傳統(tǒng)的離散

化會(huì)有bug，例如一組樣例：1,10、1,4、6,10正確答案應(yīng)該是3，而用錯(cuò)誤的離散化得到的結(jié)果卻是2，但因?yàn)閜oj的數(shù)據(jù)超水，所以

第一次用錯(cuò)誤的方法離散化后交上AC后并沒(méi)有發(fā)現(xiàn)什么不對(duì)勁的地方，后來(lái)看了大佬mmh的博客后才恍然大悟。

由于傳統(tǒng)的離散化只會(huì)保留端點(diǎn)，其他的地方都會(huì)被壓縮掉，而這個(gè)樣例中的5這個(gè)點(diǎn)理論上是應(yīng)該露在外面的，可是卻被壓縮掉

了，所以會(huì)導(dǎo)致結(jié)果不正確。

為了解決這個(gè)問(wèn)題其實(shí)可以改一下離散化的思路，令原本相鄰的點(diǎn)離散化后繼續(xù)相鄰，原本不相鄰（即間隔大于1）的點(diǎn)離散化后

中間可以隔上一個(gè)點(diǎn)，這樣就能解決上述問(wèn)題了。

另外這個(gè)題不知道為什么開(kāi)1e4+100會(huì)RE，一氣之下開(kāi)到1e5+100一下就莽過(guò)去了-.-

PS：還是得多做離散化的題啊，把線(xiàn)段樹(shù)和離散化的基礎(chǔ)打好以后才能靈活運(yùn)用

上代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;struct Node {int l,r,sum; }tree[N<<2];int x[N],y[N];int a[N];bool book[N];void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].sum=0;if(l==r)return;int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r); }void pushdown(int k) {tree[k<<1].sum=tree[k<<1|1].sum=tree[k].sum;tree[k].sum=0;return; }void update(int k,int l,int r,int val) {if(tree[k].l>r||tree[k].r<l)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].sum=val; // cout<<tree[k].l<<' '<<tree[k].r<<' '<<tree[k].sum<<endl;return;}if(tree[k].sum)pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val); }void query(int k,int l,int r) {if(tree[k].l==tree[k].r&&!tree[k].sum)return;if(tree[k].sum){book[tree[k].sum]=true;return;}query(k<<1,l,r);query(k<<1|1,l,r); }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){int n;scanf("%d",&n);vector<int>v;for(int i=1;i<=n;i++)//離散化 {scanf("%d%d",x+i,y+i);v.push_back(x[i]);v.push_back(y[i]);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());memset(a,0,sizeof(a));int cnt=1;a[0]=1;for(int i=1;i<v.size();i++){if(v[i]-v[i-1]==1)cnt++;elsecnt+=2;a[i]=cnt;}for(int i=1;i<=n;i++){x[i]=a[lower_bound(v.begin(),v.end(),x[i])-v.begin()];y[i]=a[lower_bound(v.begin(),v.end(),y[i])-v.begin()];}memset(book,false,sizeof(book));build(1,1,cnt);for(int i=1;i<=n;i++)update(1,x[i],y[i],i); // update(1,x[1],y[1],1);query(1,1,cnt);int ans=0;for(int i=1;i<=n;i++)if(book[i])ans++;cout<<ans<<endl; /* for(int i=1;i<2*v.size();i++)cout<<tree[i].l<<' '<<tree[i].r<<' '<<tree[i].sum<<endl;*/}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ - 2528 Mayor's posters(线段数+离散化)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。