题意是说给出一连串的展板，有10000000块。
然后要贴n (0 最后能看到多少个广告。 我的做法是 先离散化数据，然后构建线段树。然后查询。 不离散化那么 树所需要的空间就太大了。 注意这个样例 3 1 5 1 3 4 5 如果答案是3那么是错的。 因为每个点代表一块板。 而不是算两个数字之间的区间有没有被覆盖。 PS：貌似我的办法有点笨。耗时有点高。 #include #include #include #include #include #include #include #include #include #include #include #include #include #define INF 0x7fffffff #define eps 1e-8 #define LL long long #define PI 3.141592654 #define CLR(a,b) memset(a,b,sizeof(a)) #define FOR(i,a,b) for(int i=a;i=b;i--) #define sf scanf #define pf printf #define all(v) (v).begin(),(v).end() #define acfun std::ios::sync_with_stdio(false) #define SIZE (10000 +1) #define MOD 1000000007 using namespace std; struct post { int pos; int site; }l[SIZE*4]; bool cmp1(post a,post b) { return a.site=0) t[o]+=up[o]*(r-l+1); else if(l=r) up[o]=us; else { if(up[o]>=0) { up[o*2]=up[o*2+1]=up[o]; up[o]=-1; } int m=(l+r)>>1; if(ul<=m)update(l,m,o*2); else cal(l,m,o*2); if(ur>m)update(m+1,r,o*2+1); else cal(m+1,r,o*2+1); } cal(l,r,o); } int ql,qr; int query(int l,int r,int o) { int ans=0; if(up[o]>=0) ans+=up[o]*(min(r,qr)-max(l,ql)+1); else if(ql<=l&&qr>=r) ans+=t[o]; else { int m=(l+r)>>1; if(ql<=m)ans+=query(l,m,o*2); if(qr>m)ans+=query(m+1,r,o*2+1); } return ans; } bool vis[SIZE*8]; mappo; int main() { int tt; sf("%d",&tt); while(tt--) { int m,cnt=1; sf("%d",&m); FOR(i,0,m) { sf("%d%d",&l[i*2].site,&l[i*2+1].site); l[i*2].pos=i*2,l[i*2+1].pos=i*2+1; } sort(l,l+m*2,cmp1); po.clear(); FOR(i,0,m*2) { if(po[l[i*2].site]==0) po[l[i*2].site]=cnt++; l[i*2].site=po[l[i*2].site]; if(po[l[i*2+1].site]==0) po[l[i*2+1].site]=cnt++; l[i*2+1].site=po[l[i*2+1].site]; } sort(l,l+m*2,cmp2); //离散化后还原 CLR(t,0); CLR(up,-1); CLR(vis,0); int ans=0; int color=1; FOR(i,0,m) { ul=l[i*2].site,ur=l[i*2+1].site; us=color++; update(1,cnt-1,1); } FOR(i,1,cnt) { ql=qr=i; int tmp=0; tmp=query(1,cnt-1,1); //pf("%d:%d\n",i,tmp); if(tmp==0)continue; vis[tmp]=1; } FOR(i,0,color) if(vis[i])ans++; pf("%d\n",ans); } }
最后能看到多少个广告。
我的做法是 先离散化数据，然后构建线段树。然后查询。
不离散化那么 树所需要的空间就太大了。
注意这个样例
3
1 5
1 3
4 5
如果答案是3那么是错的。
因为每个点代表一块板。
而不是算两个数字之间的区间有没有被覆盖。
PS：貌似我的办法有点笨。耗时有点高。
#include #include #include #include #include #include #include #include #include #include #include #include #include #define INF 0x7fffffff #define eps 1e-8 #define LL long long #define PI 3.141592654 #define CLR(a,b) memset(a,b,sizeof(a)) #define FOR(i,a,b) for(int i=a;i=b;i--) #define sf scanf #define pf printf #define all(v) (v).begin(),(v).end() #define acfun std::ios::sync_with_stdio(false) #define SIZE (10000 +1) #define MOD 1000000007 using namespace std; struct post { int pos; int site; }l[SIZE*4]; bool cmp1(post a,post b) { return a.site=0) t[o]+=up[o]*(r-l+1); else if(l=r) up[o]=us; else { if(up[o]>=0) { up[o*2]=up[o*2+1]=up[o]; up[o]=-1; } int m=(l+r)>>1; if(ul<=m)update(l,m,o*2); else cal(l,m,o*2); if(ur>m)update(m+1,r,o*2+1); else cal(m+1,r,o*2+1); } cal(l,r,o); } int ql,qr; int query(int l,int r,int o) { int ans=0; if(up[o]>=0) ans+=up[o]*(min(r,qr)-max(l,ql)+1); else if(ql<=l&&qr>=r) ans+=t[o]; else { int m=(l+r)>>1; if(ql<=m)ans+=query(l,m,o*2); if(qr>m)ans+=query(m+1,r,o*2+1); } return ans; } bool vis[SIZE*8]; mappo; int main() { int tt; sf("%d",&tt); while(tt--) { int m,cnt=1; sf("%d",&m); FOR(i,0,m) { sf("%d%d",&l[i*2].site,&l[i*2+1].site); l[i*2].pos=i*2,l[i*2+1].pos=i*2+1; } sort(l,l+m*2,cmp1); po.clear(); FOR(i,0,m*2) { if(po[l[i*2].site]==0) po[l[i*2].site]=cnt++; l[i*2].site=po[l[i*2].site]; if(po[l[i*2+1].site]==0) po[l[i*2+1].site]=cnt++; l[i*2+1].site=po[l[i*2+1].site]; } sort(l,l+m*2,cmp2); //离散化后还原 CLR(t,0); CLR(up,-1); CLR(vis,0); int ans=0; int color=1; FOR(i,0,m) { ul=l[i*2].site,ur=l[i*2+1].site; us=color++; update(1,cnt-1,1); } FOR(i,1,cnt) { ql=qr=i; int tmp=0; tmp=query(1,cnt-1,1); //pf("%d:%d\n",i,tmp); if(tmp==0)continue; vis[tmp]=1; } FOR(i,0,color) if(vis[i])ans++; pf("%d\n",ans); } }
POJ 1528 Mayor&＃39;s posters
京公网安备 11010802041100号