// File Name: 1823.cpp// Author: darkdream// Created Time: 2014年07月10日 星期四 09时38分05秒#include<vector>#include<list>#include<map>#include<set>#include<deque>#include<stack>#include<bitset>#include<algorithm>#include<functional>#include<numeric>#include<utility>#include<sstream>#include<iostream>#include<iomanip>#include<cstdio>#include<cmath>#include<cstdlib>#include<cstring>#include<ctime>#include<climits>#include<queue>using namespace std;struct ynode{    int ly,ry;     int v;};int L(int x){    return x << 1 ;}int R(int x){    return x * 2  + 1;}struct xnode{    int lx, rx;    struct ynode tt[1014<<2];}tree[112<<2];void build2(int x,int y,int ly ,int ry){    //   printf("%d %d %d\n",y,ly,ry);    tree[x].tt[y].ly = ly;    tree[x].tt[y].ry = ry;    tree[x].tt[y].v = -1;    if(ly == ry)        return ;    int m = (ly + ry )/2;     build2(x,L(y),ly,m);    build2(x,R(y),m+1,ry);}void build(int x,int lx,int rx){    build2(x,1,1,1005);    tree[x].lx = lx;     tree[x].rx = rx;     if(lx == rx)        return ;     int m = (lx + rx)/2;     build(L(x),lx,m);    build(R(x),m+1,rx);}void update2(int x, int y ,int fy,int v){    //    printf("%d %d %d\n",x,y,tree[x].tt[y].v);    int ly = tree[x].tt[y].ly;    int ry = tree[x].tt[y].ry;    if(ly == ry && ly == fy )    {        tree[x].tt[y].v = max(tree[x].tt[y].v,v);        return ;    }    if(ly == ry)        return ;     int m = (ly + ry)/2;     if(fy <= m )        update2(x,L(y),fy,v);    else update2(x,R(y),fy,v);    tree[x].tt[y].v = max(tree[x].tt[L(y)].v,tree[x].tt[R(y)].v);    //    printf("%d %d %d\n",x,y,tree[x].tt[y].v);}void update(int x,int fx ,int fy ,int v){    update2(x,1,fy,v);    if(tree[x].lx == tree[x].rx )    {        return ;     }    int m = (tree[x].lx + tree[x].rx) /2;     if(fx <= m )        update(L(x),fx,fy,v);    else update(R(x),fx,fy,v);}int ans = -1 ; void find2(int x, int y ,int ly,int ry){    if(ly <= tree[x].tt[y].ly && ry >= tree[x].tt[y].ry)    {//        printf("%d\n",tree[x].tt[y].v);        ans = max(ans,tree[x].tt[y].v);        return ;    }    int m = (tree[x].tt[y].ly + tree[x].tt[y].ry)/2;    if(ly <= m)        find2(x,L(y),ly,ry);    if(ry > m)        find2(x,R(y),ly,ry);}void find(int x,int lx,int rx ,int ly ,int ry){    if(lx <= tree[x].lx && rx >= tree[x].rx)    {        find2(x,1,ly,ry);        return;     }    int m = (tree[x].lx + tree[x].rx)/2;    if(lx <= m)        find(L(x),lx,rx,ly,ry);    if(rx > m )        find(R(x),lx,rx,ly,ry);}int main(){    int m ,tx,ty;    double ta,tb;    while(scanf("%d",&m) != EOF,m){        build(1,1,105);        char str[10];        for(int i = 1;i <= m; i++)        {            scanf("%s",str);            if(str[0] == ‘I‘)            {                scanf("%d %lf %lf",&tx,&ta,&tb);                tx = tx - 99 ;                update(1,tx,int((ta + 1e-8)*10+1),int((tb + 1e-8)*10+1));            }else {                ans = -1;                double fx,fy;                scanf("%lf %lf %lf %lf",&fx,&fy,&ta,&tb);                tx = (((fx + 1e-8)*10)+9)/10.0 - 99;                ty = (fy +1e-8) - 99;                if(tx > ty)                {                  int temp =tx;                  tx = ty;                   ty = temp;                }                if(ta > tb)                {                  double temp =ta;                  ta = tb;                   tb = temp;                }                find(1,tx,ty,int((ta+1e-8)*10+1),int((tb+1e-8)*10+1));                if(ans == -1)                    printf("-1\n");                else printf("%.1lf\n",(ans-1)/10.0+1e-8);            }        }    }    return 0;}

  1 struct Sub_Seg_Tree {  2     int left;  3     int right;  4     int val;  5     int mid() {  6         return (left + right) >> 1;  7     }  8 };  9 struct Seg_Tree{ 10     int left; 11     int right; 12     Sub_Seg_Tree tt[1001*4]; 13     int mid() { 14         return (left + right) >> 1; 15     } 16 }tt[101*4]; 17   18 void build2(Sub_Seg_Tree tt[],int l,int r,int idx) { 19     tt[idx].left = l; 20     tt[idx].right = r; 21     tt[idx].val = -1; 22     if(l == r)    return ; 23     int mid = tt[idx].mid(); 24     build2(tt,l,mid,LL(idx)); 25     build2(tt,mid+1,r,RR(idx)); 26 } 27   28 void build(int l,int r,int idx) { 29     build2(tt[idx].tt,0,1000,1); 30     tt[idx].left = l; 31     tt[idx].right = r; 32     if(l == r) return ; 33     int mid = tt[idx].mid(); 34     build(l,mid,LL(idx)); 35     build(mid+1,r,RR(idx)); 36 } 37   38 void update2(Sub_Seg_Tree tt[],int b,int val,int idx) { 39     if(tt[idx].left == tt[idx].right) { 40         checkmax(tt[idx].val,val); 41         return ; 42     } 43     if(b <= tt[idx].mid()) { 44         update2(tt,b,val,LL(idx)); 45     } else { 46         update2(tt,b,val,RR(idx)); 47     } 48     tt[idx].val = max(tt[LL(idx)].val,tt[RR(idx)].val); 49 } 50   51 void update(int a,int b,int val,int idx) { 52     update2(tt[idx].tt,b,val,1); 53     if(tt[idx].left == tt[idx].right) return ; 54     if(a <= tt[idx].mid()) { 55         update(a,b,val,LL(idx)); 56     } else { 57         update(a,b,val,RR(idx)); 58     } 59 } 60   61 int query2(Sub_Seg_Tree tt[],int l,int r,int idx) { 62     if(l <= tt[idx].left && r >= tt[idx].right) { 63         return tt[idx].val; 64     } 65     int mid = tt[idx].mid(); 66     int ret = -1; 67     if(l <= mid) checkmax(ret,query2(tt,l,r,LL(idx))); 68     if(mid < r) checkmax(ret,query2(tt,l,r,RR(idx))); 69     return ret; 70 } 71   72 int query(int l,int r,int l2,int r2,int idx) { 73     if(l <= tt[idx].left && r >= tt[idx].right) { 74         return query2(tt[idx].tt,l2,r2,1); 75     } 76     int mid = tt[idx].mid(); 77     int ret = -1; 78     if(l <= mid) checkmax(ret,query(l,r,l2,r2,LL(idx))); 79     if(mid < r) checkmax(ret,query(l,r,l2,r2,RR(idx))); 80     return ret; 81 } 82   83 int main() { 84     int T; 85     while(scanf("%d",&T) == 1) { 86         if(T == 0)    break; 87         build(100,200,1); 88         while(T --) { 89             char op; 90             while(!isalpha(op = getchar())); 91             if(op == ‘I‘) { 92                 int a; 93                 double b,c; 94                 scanf("%d%lf%lf",&a,&b,&c); 95                 update(a,int(b*10),int(c*10),1); 96             } else { 97                 int l1,r1; 98                 double l2,r2; 99                 scanf("%d%d%lf%lf",&l1,&r1,&l2,&r2);100                 if(l1 > r1) swap(l1,r1);101                 if(l2 > r2) swap(l2,r2);102                 int ret = query(l1,r1,int(l2*10),int(r2*10),1);103                 if(ret < 0) {104                     puts("-1");105                 } else {106                     printf("%.1lf\n",ret/10.0);107                 }108             }109         }110     }111     return 0;112 }

  1 /*  2 题意：  3     给定一个n*n(n <= 300)的矩阵，然后是(T <= 10^6)次询问，每次询问某个子矩  4 阵中的最小值。  5   6 解法：  7 二维线段树 或者 二维RMQ  8   9 思路： 10     一维线段树是一颗完全二叉树，那么二维线段树无疑就是一颗完全四叉树，换言 11 之，每个结点有四个儿子，这里为了空间不浪费，将所有结点记录在一个一维数组中 12 ，每个结点的四个儿子采用编号的方式存储，在建树之前将每个结点的信息全部初始 13 化，初始化的时候需要注意的是每次将当前结点的四个儿子清空，然后判断它本身是 14 否是叶子结点，可以通过x和y区间端点是否重合来判断，最后再来生成四个儿子编号 15 ，然后往下递归，递归结束后根据四个儿子的最小值更新当前的最小值。再来看询问 16 ，和一维的情况类似，一维是对区间交，而二维则是对矩形交，如果询问的二维区间 17 和当前结点管理的二维区间没有交集，显然不可能有最小值，直接返回inf，否则如果 18 询问的二维区间完全包含了当前结点管理的二维区间，那么返回结点最小值。否则递 19 归当前结点的四个儿子，取最小值，回归到根节点就得到了询问区间的最值了。 20     需要注意的是在建树的时候不要在叶子结点生成多余的儿子结点，这样内存会多 21 一倍，如果开得不够大有可能下标越界，开得太大有可能超内存。还有就是在二维线 22 段树的结点上信息会多了不少，能节省空间尽量节省，比如每个结点管理的区间端点 23 不可能很大，所以不需要int，short就足够了。 24 */ 25  26 #include <iostream> 27 #include <cstring> 28 #include <cstdio> 29  30 using namespace std; 31  32 #define maxn 310 33 #define inf  (1<<30)-1 34  35 struct Tree { 36     int Min;           // 当前结点区间最小值 37     int son[4];        // 四个儿子在数组中的编号 38     short x[2], y[2];  // 当前结点管理的二维区间 39 }T[maxn*maxn*5]; 40  41 int Tree_Id; 42  43 int n; 44 int mat[maxn][maxn]; 45  46 void Build(int fat, int x0, int x1, int y0, int y1) { 47     int i; 48     for(i = 0; i < 4; i++) { 49         T[fat].son[i] = 0; 50     } 51     T[fat].x[0] = x0;  T[fat].x[1] = x1; 52     T[fat].y[0] = y0;  T[fat].y[1] = y1; 53  54     if(x0 == x1 && y0 == y1) { 55         T[fat].Min = mat[x0][y0]; 56         return ; 57     } 58     for(i = 0; i < 4; i++) { 59         T[fat].son[i] = Tree_Id++; 60     } 61  62     int xmid = (x0 + x1) >> 1; 63     int ymid = (y0 + y1) >> 1; 64     Build(T[fat].son[0], x0, xmid,   y0, ymid); 65     Build(T[fat].son[1], x0, xmid,   (ymid<y1) ? ymid+1 : ymid, y1); 66     Build(T[fat].son[2], (xmid<x1) ? xmid+1 : xmid, x1, y0, ymid); 67     Build(T[fat].son[3], (xmid<x1) ? xmid+1 : xmid, x1, (ymid<y1) ? ymid+1 : ymid, y1); 68  69     T[fat].Min = T[T[fat].son[0]].Min; 70     for(i = 1; i < 4; i++) { 71         if(T[T[fat].son[i]].Min < T[fat].Min) 72             T[fat].Min = T[T[fat].son[i]].Min; 73     } 74 } 75  76 int Query(int fat, int x0, int x1, int y0, int y1) { 77     if(x0 > T[fat].x[1] || x1 < T[fat].x[0] 78     || y0 > T[fat].y[1] || y1 < T[fat].y[0]) { 79         return inf; 80     } 81  82     if(x0 <= T[fat].x[0] && T[fat].x[1] <= x1 83         && y0 <= T[fat].y[0] && T[fat].y[1] <= y1) { 84         return T[fat].Min; 85     } 86     int i; 87     int Min = inf; 88     for(i = 0; i < 4; i++) { 89         int v = Query(T[fat].son[i], x0, x1, y0, y1); 90         if(v < Min) 91             Min = v; 92     } 93     return Min; 94 } 95  96 int main() { 97     int t; 98     int i, j; 99 100     scanf("%d", &t);101     while(t--) {102         scanf("%d", &n);103         Tree_Id = 0;104         for(i = 1; i <= n; i++) {105             for(j = 1; j <= n; j++) {106                 scanf("%d", &mat[i][j]);107             }108         }109         Tree_Id = 2;110         Build(1, 1, n, 1, n);111 112         int m;113         scanf("%d", &m);114 115         while(m--) {116             int r[2], c[2];117             scanf("%d %d %d %d", &r[0], &c[0], &r[1], &c[1]);118             printf("%d\n", Query(1, r[0], r[1], c[0], c[1]));119         }120     }121     return 0;122 }