题目链接：http://codeforces.com/contest/1028/problem/C

这道题的题目大意是：给你n个矩形（左上角的坐标，右下角坐标），让你输出一个点，让至少n-1个矩形包含这个点，因为题目保证至少存在一个这样的点，所要我们排除一个矩形，再求剩下n-1个矩形的的相交矩形，在输出其中一个点就行了。我们可以枚举要排除的矩形，再求剩下（n-1）的矩形的相交矩形，但是复杂度为O(n^2),会超时。那我们有没有办法排除一个矩形时，快速求解剩下（n-1）的矩形的相交矩形呢？

我们先来看两个矩形相交的情况

从图中就可以看出相交矩形的左上角和右下角坐标的求法如下：

//左上角坐标(i, j), 右下角坐标(x, y)
 
//矩形1(i1, j1)(x1, y1), 矩形2(i2, j2)(x2, y2)
相交矩形的坐标
i =  max(i1, i2);
j =  max(j1, j2);
x =  min(x1, x2);
y =  min(y1, y2);

如果两个矩形不相交，那么i， j， x， y会出现什么情况，简单模拟一下就知道了。

if(i<x||j<y)
	printf("不相交\n");
else if(i==x&&j==y)
	printf("相交与一点\n");
else if(i==x||j==y)
	printf("相交与一条直线\n");
else
	printf("存在相交矩形\n");

如果有3个矩形，4个矩形,…,n个矩形怎么办？

只要把相交矩形再与第3个矩形在求相交矩形，在与第4个矩形求相交矩形，…，在与第n个矩形求相交矩形就行了。

我们学会了解决n个相交矩形的问题，那么我们把问题改一下：给你n个矩形，并进行n次操作，每次操作输入m, i, j, x, y把第m个矩形的坐标修改（修改会保存）为（i， j），（x, y）。在让在修改后都求这n个矩形的相交矩形，如果每次修改后，我们都重新开始第1个矩形相交一直到第n个矩形相交求一遍，时间复杂度为O（n^n）, 如果n数据为10^5,或者更大，那么这道题肯定超时。

我们再看看刚才求两个矩形相交的求法：

//左上角坐标(i, j), 右下角坐标(x, y)
 
//矩形1(i1, j1)(x1, y1), 矩形2(i2, j2)(x2, y2)
相交矩形的坐标
i =  max(i1, i2);
j =  max(j1, j2);
x =  min(x1, x2);
y =  min(y1, y2);

如果求n个，只要把相交矩形当做第一个矩形，进行n-1次循环就行了，在这n次循环中

//相交矩形的坐标
i =  max(i1, i2, i3, ... , in);
j =  max(j1, j2, j3, ... , jn);
x =  min(x1, x2, x3, ... , xn);
y =  min(y1, y2, y3, ... , yn);

看到这就应该有思路了
相交矩形的 i， j， x, y 之间没有任何关系。那么修改一个矩形我们只有修改i， j, x, y中的一个元素再求 i， j, x, y; 那么我们只要把n个矩形的i， j, x, y分开保存在4个数组就就行了。每次修改后，我们只要修改i[m], j[m], x[m], yu[m], 在求相应最大最小值就行了。当时求最大最小值的复杂度也为n，那么复杂度没有变。

看到，可能有的人有疑问，这个每次修改后，只要把修改的值与之前的最值进行比较就行了。复杂度为O(1), 听着好像没有问题， 但是如果修改的就是之前的最值，那么就要重新找一次最值

当然我们可以用快速排序把查找最值复杂度降O(log n)，我们也可以用STL中的平衡二叉树容器pultiset 复杂度也为O(log n)。这道题完美的理论AC。

我们再来看文章开始的问题那么这道题也已经理论AC了， 为了熟悉STL模板我就用pultiset了。

思考：我这篇博客是看了https://blog.csdn.net/xianpingping/article/details/82193032的博客写的，这位大佬写得太简略了，代码只有17行，看不到他的思路。自己看看画画，又在纸上调试了一个小时，才明白这道题的思路。

AC代码如下：

#include<bits/stdc++.h>
using namespace std;

#define N 150000
int a[N][4];
multiset<int> s[4];

int main()
{
    int n;
    scanf("%d",&n);

    for(int i=0;i<n;i++)//读入矩形
    {
        for(int j=0;j<4;j++)
        {
            scanf("%d",&a[i][j]);
            s[j].insert(a[i][j]);
        }
    }

    for(int i=0;i<n;i++)//枚举删除的矩形
    {
        for(int j=0;j<4;j++)//删除矩形
        {
            //不用s[j].erase(a[i][j])
            //会删除所有的a[i][j]
            s[j].erase(s[j].find(a[i][j]));
        }

        //满足i<=x&&j<=y,则n-1个矩形至少交于一点
        if(*s[0].rbegin()<=*s[2].begin()&&*s[1].rbegin()<=*s[3].begin())
        {
            cout<<*s[0].rbegin()<<' '<<*s[1].rbegin()<<endl;
            break;
        }

        //如果删除这个矩形不满足
        //则恢复这个矩形，枚举下一个删除的矩形
        for(int j=0;j<4;j++)
        {
            s[j].insert(a[i][j]);
        }

    }

    return 0;
}