題面很長，可往往真正有用的題意卻沒有這么長，例如說這么一句：

• 床單放在上面，使它們之間角或邊不會互相接觸， 邊也不會相交，但他可能把較小的床單放在大的上面，或者一個完全覆蓋另個。

從這句話中，我們可以看出，矩形是不會相交的，且只有包含關(guān)系。所以，我們僅需記錄一個矩形的父親為包含它的所有矩形中最小的那個，原圖可由此化為一棵森林。

那么，我們怎么構(gòu)造一個森林呢？我們這里有兩種方法：

• 用掃描線，線段樹處理y軸，每次找到一個矩形之后判斷這個矩形的下邊界是否合法，如不合法就倍增往其父親走，直到合法。
• 對于y軸，我們建一棵標記永久化的線段樹。掃到左邊界時，直接把標記打到相應(yīng)區(qū)間，直接覆蓋。

構(gòu)造出森林過后，我們就可以在此森林上進行線段樹合并或者是set啟發(fā)式合并即可。

?

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<set> #include<queue> #include<ctime> #define MAXN 200005 #define ll long long #define maxn 15 #define maxs 1000005 #define inf 1e9 #define eps 1e-9 using namespace std; inline char gc() {static char now[1<<16],*S,*T;if (T==S) {T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}return *S++; } inline ll readlong() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x*=10;x+=ch-'0';ch=getchar();}return x*f; } inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x*=10;x+=ch-'0';ch=getchar();}return x*f; } void putint(long long t) {int ans[40]= {0};for(; t; t/=10)ans[++ans[0]]=t%10;for(; ans[0]; ans[0]--)putchar('0'+ans[ans[0]]);putchar('\n'); } const int N=500005; int n,m; struct edge{int to,nxt; }e[N]; int h[N],cnt; void add(int x,int y){ // cout<<x<<' '<<y;e[++cnt]=(edge){y,h[x]};h[x]=cnt; } int pre[N],_k[N],_y[N],rt[N]; int ans[N]; int dx,dy,dv; int g[N<<5]; int col[N<<5],f[N<<5][2]; int cntt,cnty,cnts; int tot; struct bed{int x,y,k,i;bool operator <(const bed &a)const{if(x==a.x){return i>a.i;}return x<a.x;} }mp[N<<2]; int query(int x,int l,int r){if(g[x]>=0||l==r){return g[x];}if(!x){return 0;}int mid=(l+r)>>1;if(dx<=mid){return query(x<<1,l,mid);}else{return query(x<<1|1,mid+1,r);} } void push(int x){if(g[x]<0){return ;}g[x<<1]=g[x<<1|1]=g[x];g[x]=-1; } void modify(int x,int l,int r){ // cout<<"Asdf"<<endl;if(dx<=l&&dy>=r){g[x]=dv;return ;}push(x);int mid=(l+r)>>1;if(dx<=mid){modify(x<<1,l,mid);}if(dy>mid){modify(x<<1|1,mid+1,r);} } void add_cor(int &x,int l,int r){if(!x){x=++tot;}if(l==r){col[x]=1;return;}int mid=(l+r)>>1;if(dx<=mid){add_cor(f[x][0],l,mid);}else{add_cor(f[x][1],mid+1,r);}col[x]=col[f[x][0]]+col[f[x][1]]; } int merge(int a,int b,int l,int r){if(!a|!b){return a^b;}if(l==r){return a;}int mid=(l+r)>>1;f[a][0]=merge(f[a][0],f[b][0],l,mid);f[a][1]=merge(f[a][1],f[b][1],mid+1,r);col[a]=col[f[a][0]]+col[f[a][1]];return a; } void dfs(int x){for(int i=h[x];i;i=e[i].nxt){int y=e[i].to;if(y!=pre[x]){dfs(y);rt[x]=merge(rt[x],rt[y],1,cnts);}}ans[x]=col[rt[x]]; } int main(){memset(g,-1,sizeof(g));n=read();m=read();for(int i=1;i<=n;i++){int a=read();int b=read();int c=read();int d=read();mp[++cntt]=(bed){a,b,d,i};_y[++cnty]=b;mp[++cntt]=(bed){c,b,d,-i};_y[++cnty]=d;}for(int i=1;i<=m;i++){int x=read();int y=read();int k=read();mp[++cntt]=(bed){x,y,k,0};_y[++cnty]=y;_k[++cnts]=k;}sort(_y+1,_y+1+cnty);cnty=unique(_y+1,_y+1+cnty)-_y-1;sort(_k+1,_k+1+cnts);cnts=unique(_k+1,_k+1+cnts)-_k-1;sort(mp+1,mp+cntt+1);for(int i=1;i<=cntt;i++){mp[i].y=lower_bound(_y+1,_y+1+cnty,mp[i].y)-_y;if(mp[i].i){mp[i].k=lower_bound(_y+1,_y+1+cnty,mp[i].k)-_y;if(mp[i].i>0){dx=mp[i].y;dy=mp[i].k;dv=mp[i].i;if((pre[dv]=query(1,1,cnty))>0){add(pre[dv],dv);}modify(1,1,cnty);continue;}dx=mp[i].y;dy=mp[i].k;dv=max(pre[-mp[i].i],0);modify(1,1,cnty);continue;}mp[i].k=lower_bound(_k+1,_k+cnts+1,mp[i].k)-_k;dx=mp[i].y;int tmp=query(1,1,cnty);if(tmp>0){dx=mp[i].k;add_cor(rt[tmp],1,cnts);}}for(int i=1;i<=n;i++){if(pre[i]<=0){dfs(i);}}for(int i=1;i<=n;i++){printf("%d\n",ans[i]);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/LHbz/p/9720950.html

總結(jié)

以上是生活随笔為你收集整理的[COCI2017-2018#1] Plahte的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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