codeforces 19 D. Points (离散化+树套树（线段树+set）)

2016-09-04 · 3 min read · set 树套树 离散化 线段树

题目链接

题意：

在二维坐标平面内进行_n_ (1 ≤ _n_ ≤ 2·105) 次操作。一共有三种类型操作。

1.add x,y 将点(x,y)加进坐标系。

2.remove x,y 将点(x,y)移除.

3.find x,y 找到点(x,y)右上角的点(xp>x,yp>y)。如果有多个输出x最小的。还是有多个输出y最小的。

x,y均为非负数。以上操作均合法。

思路：没有思路。。。不会啊。。。以为要二维线段树什么的。。。。总之是不会做。。。

大概从中午开始看题解。。。8个小时。。。。终于完全搞懂了orz

很巧妙得把二维问题转化成了一维问题。。。

我来说一下大概做法，具体的细节见代码注释：

在x轴方向维护一课线段树，线段树的数组tree[i]存储的信息是以i节点为根节点的子树所对应的区间能达到的最大的y值。线段树的叶子节点上是一个set，set[i]是横坐标为i时的纵坐标集合，也就是所谓的树套树。

由于x很大，但是n比较小，所以我们这里采用了stl+去重的办法离散化离散化的三种办法

对于添加和删除点的操作，我们更新完对应的set把相应的x（离散化后的）在线段树中更新就好（因为线段树的update操作是和set有关的）

对于find操作，我们首先从线段树中找到（下标大于x且最小且集合中存在大于y的元素的集合）的下标

这样我们确定了x，再upper_bound一下找到对应的集合中最小的y.

初始化由于没有插入y,所以tree可以初始化为-1，不用建树。。。（反正建了也都是-1）

  1/* ***********************************************
  2Author :111qqz
  3Created Time :Sun 04 Sep 2016 07:19:05 PM CST
  4File Name :code/cf/problem/19D.cpp
  5************************************************ */
  6#include <cstdio>
  7#include <cstring>
  8#include <iostream>
  9#include <algorithm>
 10#include <vector>
 11#include <queue>
 12#include <set>
 13#include <map>
 14#include <string>
 15#include <cmath>
 16#include <cstdlib>
 17#include <ctime>
 18#define fst first
 19#define sec second
 20#define lson l,m,rt<<1
 21#define rson m+1,r,rt<<1|1
 22#define ms(a,x) memset(a,x,sizeof(a))
 23typedef long long LL;
 24#define pi pair < int ,int >
 25#define MP make_pair
 26using namespace std;
 27const double eps = 1E-8;
 28const int dx4[4]={1,0,0,-1};
 29const int dy4[4]={0,-1,1,0};
 30const int inf = 0x3f3f3f3f;
 31const int N=2E5+7;
 32int n,m;
 33int tree[N<<2]; //记录线段树的信息，tree[i]表示的是以i节点为根节点的子树所代表的区间中的点的最大的y值。
 34set<int>se[N];//集合se[i]是横坐标为x的点的纵坐标的集合。
 35struct node   //线段树套平衡树，在x轴的方向上建一棵线段树，线段树的每个叶子节点是一个set。
 36{
 37    int x,y;
 38    char cmd[15];
 39    void input()
 40    {
 41	scanf("%s%d%d",cmd,&x,&y);
 42    }
 43}q[N];
 44int H[N];
 45void PushUp(int rt)
 46{
 47    tree[rt] = max(tree[rt<<1],tree[rt<<1|1]);
 48}
 49void update( int p,int l,int r,int rt)
 50{
 51    if (l==r)
 52    {
 53	if (se[l].size())
 54	    tree[rt] =*(--se[l].end()); //se.end()是指向最后一个元素之后的， *(--se[l].end())只是取了se[l]集合的最后一个元素而已
 55	else tree[rt] = -1;
 56	return ;
 57    }
 58    int m = (l+r)>>1;
 59    if (p<=m)
 60	update(p,lson);
 61    else update(p,rson);
 62    PushUp(rt);
 63}
 64int query(int L,int R,int val,int l,int r,int rt)//返回集合中存在大于val(y)的集合中标号最小的集合的标号（x)
 65{
 66    if (tree[rt]<=val||L>R) return -1;//由于题目要求严格大于，因此查询区间是从h+1到m，当h恰好等于m的时候，L>R，记得判断。
 67    if (l==r) return l;
 68    int m = (l+r)>>1;
 69    int ret = -1;
 70    if (L<=m)
 71	ret = query(L,R,val,lson);
 72    if (ret!=-1)
 73	return ret;
 74    if (R>=m+1)
 75	return query(L,R,val,rson);
 76}
 77int Hash( int x)
 78{
 79    return lower_bound(H,H+m,x)-H;
 80}
 81int main()
 82{
 83	#ifndef  ONLINE_JUDGE 
 84	freopen("code/in.txt","r",stdin);
 85  #endif
 86	cin>>n;
 87	m = n;
 88	for ( int i = 0 ; i < n ; i++) q[i].input(),H[i] = q[i].x;
 89	sort(H,H+m); // 离散化
 90	m = unique(H,H+m)-H;//离散化
 91	ms(tree,-1);//初始化最大值。
 92	for ( int i = 0 ; i <  n;  i++)
 93	{
 94	    int h = Hash(q[i].x)+1;//离散化
 95	    if (q[i].cmd[0]=='a')
 96		se[h].insert(q[i].y),update(h,1,m,1);
 97	    else if (q[i].cmd[0]=='r')
 98		se[h].erase(q[i].y),update(h,1,m,1);
 99	    else 
100	    {
101		int p = query(h+1,m,q[i].y,1,m,1);//x已经是升序了，从h+1开始的区间寻找可以保证x严格大于，此时只需要在[h+1,m]区间找一个严格大于y的点。
102	        if (p==-1)
103		    puts("-1");
104		else printf("%d %d\n",H[p-1],*se[p].upper_bound(q[i].y)); //由于当x相同时要找y最小的那个，因此最后还要upper_bound找到第一个比q[i].y大的y。
105		//下标问题。。只是因为H的下标是从0开始的。。set的下标是从1开始的。。。H下标从0开始离散化会看着舒服一点。。。
106	    }
107	}
108  #ifndef ONLINE_JUDGE  
109  fclose(stdin);
110  #endif
111    return 0;
112}