sgu Kalevich Strikes Back

这道题就是求一个大矩形被n个矩形划分成n+1个部分的面积,这些矩形之间不会相交,可能包含。。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <vector>
  4 #include <algorithm>
  5 #define maxn 120100
  6 using namespace std;
  7
  8 long long s[maxn];
  9 vector<int>g[maxn];
 10 int pre[maxn];
 11 int X[maxn];
 12 int n,m,w,h,x1,y1,x2,y2;
 13 struct node
 14 {
 15     int l,r;
 16     int ll,rr;
 17     int cover;
 18 }tree[maxn*4];
 19
 20 struct line
 21 {
 22     int y,x1,x2,lr;
 23     bool operator <(const line &a)const
 24     {
 25         return y<a.y;
 26     }
 27 }p[maxn];
 28
 29 void build(int i,int l,int r)
 30 {
 31     tree[i].l=l;
 32     tree[i].r=r;
 33     tree[i].ll=X[l];
 34     tree[i].rr=X[r];
 35     tree[i].cover=0;
 36     if(r-l==1) return ;
 37     int mid=(l+r)>>1;
 38     build(i<<1,l,mid);
 39     build(i<<1|1,mid,r);
 40 }
 41 void down(int i)
 42 {
 43     if(tree[i].l+1==tree[i].r) return;
 44     if(tree[i].cover!=-1)
 45     {
 46         tree[i<<1].cover=tree[i<<1|1].cover=tree[i].cover;
 47         tree[i].cover=-1;
 48     }
 49 }
 50 void update(int i, line a)
 51 {
 52     if(tree[i].ll==a.x1&&tree[i].rr==a.x2)
 53     {
 54         if(a.lr>0)
 55             tree[i].cover=a.lr;
 56         else
 57             tree[i].cover=pre[-a.lr];
 58         return ;
 59     }
 60     down(i);
 61     if(a.x2<=tree[i<<1].rr) update(i<<1,a);
 62     else if(a.x1>=tree[i<<1|1].ll) update(i<<1|1,a);
 63     else
 64     {
 65         line tmp=a;
 66         tmp.x2=tree[i<<1].rr;
 67         update(i<<1,tmp);
 68         tmp=a;
 69         tmp.x1=tree[i<<1|1].ll;
 70         update(i<<1|1,tmp);
 71     }
 72 }
 73
 74 int search1(int i,line m)
 75 {
 76     if(tree[i].cover!=-1)
 77     {
 78         return tree[i].cover;
 79     }
 80     if(m.x2<=tree[i<<1].rr) return search1(i<<1,m);
 81     else if(m.x1>=tree[i<<1|1].ll) return search1(i<<1|1,m);
 82     else
 83     {
 84         line tmp;
 85         tmp=m;
 86         tmp.x2=tree[i<<1].rr;
 87         return search1(i<<1,tmp);
 88     }
 89 }
 90 void dfs(int u)
 91 {
 92     for(int i=0; i<(int)g[u].size(); i++)
 93     {
 94         int v=g[u][i];
 95         s[u]-=s[v];
 96         dfs(v);
 97     }
 98 }
 99
100 int main()
101 {
102     while(scanf("%d",&n)!=EOF)
103     {
104         for(int i=0; i<=n; i++)
105         {
106             g[i].clear();
107         }
108         scanf("%d%d",&w,&h);
109         s[0]=(long long)w*h;
110         int t1=0;
111         for(int i=1; i<=n; i++)
112         {
113             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
114             if(x1>x2)swap(x1,x2);
115             if(y1>y2)swap(y1,y2);
116             s[i]=(long long)(x2-x1)*(y2-y1);
117             p[t1].y=y1;
118             p[t1].x1=x1;
119             p[t1].x2=x2;
120             p[t1].lr=i;
121             X[t1++]=x1;
122             p[t1].y=y2;
123             p[t1].x1=x1;
124             p[t1].x2=x2;
125             p[t1].lr=-i;
126             X[t1++]=x2;
127         }
128         sort(X,X+t1);
129         t1=unique(X,X+t1)-X;
130         build(1,0,t1-1);
131         sort(p,p+2*n);
132         for(int i=0; i<2*n; i++)
133         {
134             if(p[i].lr>0)
135             {
136                 pre[p[i].lr]=search1(1,p[i]);
137                 g[pre[p[i].lr]].push_back(p[i].lr);
138             }
139             update(1,p[i]);
140         }
141         dfs(0);
142         sort(s,s+n+1);
143         for(int i=0; i<=n; i++)
144         {
145             if(i==n) printf("%I64d\n",s[i]);
146             else printf("%I64d ",s[i]);
147         }
148     }
149     return 0;
150 }

sgu Kalevich Strikes Back,布布扣,bubuko.com

时间: 08-06

sgu Kalevich Strikes Back的相关文章

SGU 319 Kalevich Strikes Back(线段树扫描线)

题目大意: n个矩形,将一个大矩形分成 n+1 块.矩形之间不重合,可是包括.求这n+1个矩形的面积 思路分析: 用线段树记录他们之间的父子关系.然后dfs 计算面积. 当给出的矩形上边的时候,就要记录到该矩形的父亲去. #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define lson num<<1,s,mid #define rs

【SGU 390】Tickets (数位DP)

Tickets Description Conductor is quite a boring profession, as all you have to do is just to sell tickets to the passengers. So no wonder that once upon a time in a faraway galaxy one conductor decided to diversify this occupation. Now this conductor

ACM: SGU 101 Domino- 欧拉回路-并查集

sgu 101 - Domino Time Limit:250MS     Memory Limit:4096KB     64bit IO Format:%I64d & %I64u Description Dominoes – game played with small, rectangular blocks of wood or other material, each identified by a number of dots, or pips, on its face. The bl

SGU 116 Index of super-prime 数论+完全背包+输出方案

题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=116 题意好晦涩 给你一个不超过一万的数 问它最少可以用多少个“超级素数”来表示 使“超级素数”之和等于它 如果无法这样表示 输出0 否则 按非降序形式输出方案 数论部分就模板的问题 没什么说的 完全背包方面也很常规 说说[输出方案] 背包九讲的伪码给的是二维dp[]的方法 实际上稍加改动就可以用在一维数组上 用一个rec[]记录dp[]的当前状态是从哪个状态转移而来(即上一个状态) 通过

SGU 乱搞日志

SGU 100 A+B :太神不会 SGU 101 Domino: 题目大意:有N张骨牌,两张骨牌有两面有0到6的数字,能相连当且仅当前后数字相同,问能否有将N张骨牌连接的方案?思路:裸的欧拉回路,注意自环,连通 1 //sgu101 2 #include<iostream> 3 #include<cstdio> 4 #include <math.h> 5 #include<algorithm> 6 #include<string.h> 7 #i

SGU 275 To xor or not to xor (高斯消元)

题目地址:SGU 275 首先,贪心的思想,每一二进制位上要尽量是1,而能不能是1用高斯消元来解决.当该位有一个可以使之为1的变元时,就说明这位可以为1,而且令该变元控制该位,然后向低位消元. 代码如下: #include <iostream> #include <string.h> #include <math.h> #include <queue> #include <algorithm> #include <stdlib.h>

SGU 221.Big Bishops(DP)

题意: 给一个n*n(n<=50)的棋盘,放上k个主教(斜走),求能放置的种类总数. Solution : 同SGU 220,加个高精度就好了. code #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> using namespace std; string f[2][250][250], ans;

SGU 193.Chinese Girls&#39; Amusement

/* 实际上就是求一个k,满足k<=n/2,且gcd(n,k)=1 如果n为奇数,k为[n/2] 如果n为偶数,k=n/2-1-(n/2)%2 */ #include <iostream> using namespace std; string s; void div2() { string t; int l = s.size() - 1, tem = s[0] - '0'; if (tem > 1) t += '0' + tem / 2; tem &= 1; for (i

sgu 495 Kids and Prizes

计算出每个人得到礼物的概率,然后加起来即可 1 #include<iostream> 2 #include<string.h> 3 #include<algorithm> 4 #include<stdio.h> 5 using namespace std; 6 double dp[101010]; 7 int main(){ 8 int n,m; 9 while(cin>>n>>m){ 10 dp[1]=1; 11 for(int i