UVALive

二维线段树单点修改板子题
  1 #include<bits/stdc++.h>
  2 #define LL long long
  3 #define fi first
  4 #define se second
  5 #define mk make_pair
  6 #define pii pair<int,int>
  7 #define piii pair<int, pair<int,int>>
  8 using namespace std;
  9 
 10 const int N=800+7;
 11 const int M=1e4+7;
 12 const int inf=0x3f3f3f3f;
 13 const LL INF=0x3f3f3f3f3f3f3f3f;
 14 const int mod=1e9 + 7;
 15 
 16 int n, q, ans1, ans2, mx[N << 2][N << 2], mn[N << 2][N << 2], Map[N][N];
 17 
 18 void subBuild(int op, int pos, int l, int r, int rt) {
 19     mx[pos][rt] = -inf;
 20     mn[pos][rt] = inf;
 21     if(l == r) {
 22         if(!op) {
 23             scanf("%d", &mn[pos][rt]);
 24             mx[pos][rt] = mn[pos][rt];
 25         } else {
 26             mn[pos][rt] = min(mn[pos << 1][rt], mn[pos << 1 | 1][rt]);
 27             mx[pos][rt] = max(mx[pos << 1][rt], mx[pos << 1 | 1][rt]);
 28         }
 29         return;
 30     }
 31     int mid = l + r >> 1;
 32     subBuild(op, pos, l, mid, rt << 1);
 33     subBuild(op, pos, mid + 1, r, rt << 1 | 1);
 34     mn[pos][rt] = min(mn[pos][rt << 1], mn[pos][rt << 1 | 1]);
 35     mx[pos][rt] = max(mx[pos][rt << 1], mx[pos][rt << 1 | 1]);
 36 }
 37 void build(int l, int r, int rt) {
 38     if(l == r) {
 39         subBuild(0, rt, 1, n, 1);
 40         return;
 41     }
 42     int mid = l + r >> 1;
 43     build(l, mid, rt << 1);
 44     build(mid + 1, r, rt << 1 | 1);
 45     subBuild(1, rt, 1, n, 1);
 46 }
 47 
 48 void subUpdate(int op, int pos, int y, int v, int l,int r,int rt) {
 49     if(l == r) {
 50         if(!op) mn[pos][rt] = mx[pos][rt] = v;
 51         else {
 52             mn[pos][rt] = min(mn[pos << 1][rt], mn[pos << 1 | 1][rt]);
 53             mx[pos][rt] = max(mx[pos << 1][rt], mx[pos << 1 | 1][rt]);
 54         }
 55         return;
 56     }
 57     int mid = l + r >> 1;
 58     if(y <= mid) subUpdate(op, pos, y, v, l, mid, rt << 1);
 59     else subUpdate(op, pos, y, v, mid + 1,r, rt << 1 | 1);
 60     mn[pos][rt] = min(mn[pos][rt << 1], mn[pos][rt << 1 | 1]);
 61     mx[pos][rt] = max(mx[pos][rt << 1], mx[pos][rt << 1 | 1]);
 62 }
 63 void update(int x, int y, int v, int l, int r, int rt) {
 64     if(l == r) {
 65         subUpdate(0, rt, y, v, 1, n, 1);
 66         return;
 67     }
 68     int mid = l + r >> 1;
 69     if(x <= mid) update(x, y, v, l, mid, rt << 1);
 70     else update(x, y, v, mid + 1, r, rt << 1 | 1);
 71     subUpdate(1, rt, y, v, 1, n, 1);
 72 }
 73 
 74 void subQuery(int L, int R, int pos, int l, int r, int rt) {
 75     if(l >= L && r <= R) {
 76         ans1 = min(ans1, mn[pos][rt]);
 77         ans2 = max(ans2, mx[pos][rt]);
 78         return;
 79     }
 80     int mid = l + r >> 1;
 81     if(L <= mid) subQuery(L, R, pos, l, mid , rt << 1);
 82     if(R > mid) subQuery(L, R, pos, mid + 1, r, rt << 1 | 1);
 83 }
 84 void query(int Lx, int Rx, int Ly, int Ry, int l, int r, int rt) {
 85     if(l >= Lx && r <= Rx) {
 86         subQuery(Ly, Ry, rt, 1, n, 1);
 87         return;
 88     }
 89     int mid = l + r >> 1;
 90     if(Lx <= mid) query(Lx, Rx, Ly, Ry, l, mid, rt << 1);
 91     if(Rx > mid) query(Lx, Rx, Ly, Ry, mid + 1, r, rt << 1 | 1);
 92 }
 93 int main() {
 94     int T; scanf("%d", &T);
 95     for(int cas = 1; cas <= T; cas++) {
 96         printf("Case #%d:
", cas);
 97         scanf("%d", &n);
 98         build(1, n, 1);
 99         scanf("%d", &q);
100         while(q--) {
101             int x, y, w; scanf("%d%d%d", &x, &y, &w);
102             w >>= 1;
103             int r1 = max(1, x - w);
104             int r2 = min(n, x + w);
105             int c1 = max(1, y - w);
106             int c2 = min(n, y + w);
107             ans1 = inf, ans2 = -inf;
108             query(r1, r2, c1, c2, 1, n, 1);
109             printf("%d
", ans1 + ans2 >> 1);
110             update(x, y, ans1 + ans2 >> 1, 1, n, 1);
111         }
112     }
113     return 0;
114 }
115 /*
116 */