[bzoj4959][乱搞]Visual Python++

本文主要是介绍[bzoj4959][乱搞]Visual Python++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

在最近被提出的Visual Python++编程语言中,一个语句块被表示为一个由字符组成的矩形,其中左上角在r1行c1列,
右下角在r2行c2列。对于r1≤r≤r2,c1≤c≤c2,所有位于(r,c)的字符被认为是属于这个块的内容。在这些位置中,
满足r=r1或r=r2或c=c1或c=c2的位置被称为是边界。语句块可以嵌套 (矩形包含在其他矩形中) 任意层。在语法正
确的程序中,任意两个语句块要么是嵌套的 (一个包含在另一个中) ,要么是不交的 (不重叠) 。在这两种情况中,
他们的边界也不能重叠。编程人员不需要画出经典程序中的所有矩形,这太浪费时间了,而且Visual Python++也不
可能称为下一个ICPC编程语言。因此程序员只需要在左上角位置放一个字符 ‘┌’ ,在右下角位置放一个字符’┘’
。解析器会自动匹配相应的拐角来获取程序的嵌套结构。你的团队刚刚获得了五小时的合同来开发解析器的这一部分。

Input

第一行包含一个整数n(1≤n≤10^5),表示拐角对的数量。
接下来n行,每行包含两个整数r和c(1≤r,c≤10^9),指定r行c列为一个左上角。接下来n行以相同的方式指定了右下角。
所有的拐角位置互不相同。

Output

输出n行,每行包含一个整数。第i行的整数j表示第i个左上角和第j个右下角组成一个矩形。
左上角和右下角均按照他们在输入中的顺序从1到n标号。输出必须是1到n的排列,从而匹配可能嵌套的矩形。
如果存在超过一种合法的匹配,任意一组合法的匹配都是可接受的。如果不存在合法的匹配,输出syntax error。

Sample Input

样例1

2

4 7

9 8

14 17

19 18

样例2

2

4 7

14 17

9 8

19 18

样例3

2

4 8

9 7

14 18

19 17

样例4

3

1 1

4 8

8 4

10 6

6 10

10 10

Sample Output

样例1

2

1

样例2

1

2

样例3

syntax error

样例4

syntax error

题解

这个题他欺骗我感情…
话说回来还是自己菜吧…
首先这题不能想着一步解决…想着这个我就fake不会做了啊qwq
我们按 $x$ 从右往左扫
如果遇到一个右括号，我们把他扔进 $s e t$ 中，如果遇到一个 $y$ 和它相同的，显然是个不合法情况
如果遇到一个左括号，我们在 $s e t$ 中找一个 $y$ 比他大且最小的右括号匹配
如果没有显然又是不合法情况
看到这里可能你会发现，这样构造下去，方案是唯一的啊？
…嗯方案确实是唯一的…
我们考虑一个左括号不匹配第一个 $y$ 比他大的右括号的方案会怎么样
那么显然有 $y_i\leq y_j \leq y_k$ ，其中 $j, k$ 为右括号， $i$ 为左括号
那么不管怎么样，由于剩余的左括号都在左边。总会引出某个一个矩形的上边界或者下边界过了 $(i, j)$ 这个矩形，所以一定会出现有交集的情况
那么这样构造出来之后，剩余的就是再判一次是否有交集了…
再用一个 $s e t$ 维护一下就可以了…
教训就是…很多时候想要一步解决问题都是不可能的…应当还是从小方面入手，然后分析性质。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(int x)
{if(x<0){putchar('-');x=-x;}if(!x){putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x);putchar(' ');}
inline void pr2(int x){write(x);putchar('\n');}
const int MAXN=100005;
set<pii> se;
set<pii>::iterator it;
set<int> se1;
set<int>::iterator it1;
struct line
{int x,l,r,o,id;line(){}line(int _x,int _l,int _r,int _o,int _id){x=_x;l=_l;r=_r;o=_o;id=_id;}
}L[2*MAXN],b[2*MAXN];int ln,ln1;
bool cmp1(line n1,line n2){return n1.x!=n2.x?n1.x<n2.x:n1.o>n2.o;}
struct pt{int x,y,o,id;}w[2*MAXN];
int n,mk[2*MAXN];
bool cmp(pt n1,pt n2){return n1.x!=n2.x?n1.x>n2.x:n1.o>n2.o;}
bool cmp2(line n1,line n2){return n1.l<n2.l;}
bool cmp3(line n1,line n2){return n1.id<n2.id;}
int main()
{n=read();for(int i=1;i<=n;i++){w[i].x=read();w[i].y=read();w[i].o=0;w[i].id=i;}for(int i=1;i<=n;i++){w[i+n].x=read();w[i+n].y=read();w[i+n].o=1;w[i+n].id=i;}sort(w+1,w+1+2*n,cmp);bool tf=true;for(int i=1;i<=2*n;i++){if(w[i].o){it=se.lower_bound(mp(w[i].y,0));if(it!=se.end()){pii temp=*it;if(temp.first==w[i].y){tf=false;break;}}se.insert(mp(w[i].y,i));}else{it=se.lower_bound(mp(w[i].y,0));if(it==se.end()){tf=false;break;}pii temp=*it;se.erase(it);mk[w[i].id]=w[temp.second].id;L[++ln]=line(w[i].x,w[i].y,w[temp.second].y,1,w[i].id);L[++ln]=line(w[temp.second].x,w[i].y,w[temp.second].y,-1,w[i].id);}}if(!tf)return puts("syntax error"),0;sort(L+1,L+1+ln,cmp1);for(int i=1,nxt;i<=ln;i=nxt+1){nxt=i;while(L[nxt+1].x==L[i].x&&nxt<ln)nxt++;ln1=0;for(int j=i;j<=nxt;j++)b[++ln1]=L[j];sort(b+1,b+1+ln1,cmp3);int gg=0;for(int j=1;j<=ln1;j++)if(b[j].id!=b[gg].id)b[++gg]=b[j];ln1=gg;sort(b+1,b+1+ln1,cmp2);int mx=0;for(int j=1;j<=ln1;j++){if(b[j].l<=mx){tf=false;break;}mx=max(mx,b[j].r);}}for(int i=1;i<=ln;i++){if(L[i].o==1){it1=se1.lower_bound(L[i].l);if(it1!=se1.end()){int x=*it1;if(x<=L[i].r){tf=false;break;}}se1.insert(L[i].l);se1.insert(L[i].r);}else {it1=se1.upper_bound(L[i].l);if(it1!=se1.end()){int x=*it1;if(x<L[i].r){tf=false;break;}}se1.erase(L[i].l),se1.erase(L[i].r);}}if(!tf)return puts("syntax error"),0;for(int i=1;i<=n;i++)pr2(mk[i]);return 0;
}