首页 > 代码库 > Uva 11297 Census 二维线段树
Uva 11297 Census 二维线段树
题目链接：点击打开链接
好久没发题解了，
第一维的线段树更新到底，叶子节点建一棵线段树。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<algorithm>
using namespace std;
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if (c = getchar(), c == EOF) return 0;
while (c != '-' && (c<'0' || c>'9')) c = getchar();
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x <0) {
putchar('-');
x = -x;
}
if (x>9) pt(x / 10);
putchar(x % 10 + '0');
}
const int N = 550;
const int inf = 1000 * 1000 * 1000;
int a[N][N];
class Segment_Tree{
public:
class Node{
public:
int l, r, max, min, lazy;
Node(){}
Node(int ll, int rr, int mmax, int mmin){
l = ll; r = rr; max = mmax; min = mmin;
lazy = inf;
}
};
Node t[N << 2];
int pos = 0, Max, Min;
int L(int x){ return x << 1; }
int R(int x){ return x << 1 | 1; }
void up(int id){
t[id].max = max(t[L(id)].max, t[R(id)].max);
t[id].min = min(t[L(id)].min, t[R(id)].min);
t[id].lazy = inf;
}
void down(int id){
if (t[id].lazy != inf){
t[L(id)].max = t[R(id)].max = t[id].lazy;
t[L(id)].min = t[R(id)].min = t[id].lazy;
t[L(id)].lazy = t[R(id)].lazy = t[id].lazy;
t[id].lazy = inf;
}
}
void build(int l, int r, int id){
t[id] = Node(l, r, 0, 0);
if (l == r){
t[id].min = t[id].max = a[pos][l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, L(id)); build(mid + 1, r, R(id));
up(id);
}
void update(int l, int r, int val, int id){
if (l == t[id].l && r == t[id].r){
t[id].max = t[id].min = t[id].lazy = val;
return;
}
down(id);
int mid = (t[id].l + t[id].r) >> 1;
if (r <= mid)
update(l, r, val, L(id));
else if (mid < l)
update(l, r, val, R(id));
else{
update(l, mid, val, L(id));
update(mid + 1, r, val, R(id));
}
up(id);
}
void query(int l, int r, int id){
if (l == t[id].l && r == t[id].r){
Min = min(Min, t[id].min);
Max = max(Max, t[id].max);
return;
}
down(id);
int mid = (t[id].l + t[id].r) >> 1;
if (r <= mid)
query(l, r, L(id));
else if (mid < l)
query(l, r, R(id));
else{
query(l, mid, L(id));
query(mid + 1, r, R(id));
}
}
void Q(int l, int r){
Max = -inf; Min = inf;
query(l, r, 1);
}
void P(int l, int r, int val){
update(l, r, val, 1);
}
};
class Two_Dimension_Segment_Tree{
public:
class Node{
public:
int l, r;
Node(){}
Node(int ll, int rr){
l = ll; r = rr;
}
};
Node t[N << 2];
Segment_Tree T[N];
int Max, Min, M;
int L(int x){ return x << 1; }
int R(int x){ return x << 1 | 1; }
void build(int l, int r, int id){
t[id] = Node(l, r);
if (l == r){
T[l].pos = l;
T[l].build(1, M, 1);
return;
}
int mid = (l + r) >> 1;
build(l, mid, L(id)); build(mid + 1, r, R(id));
}
void update(int l, int r, int x, int y, int val, int id){
if (l == r){
T[l].P(x, y, val);
return;
}
int mid = (t[id].l + t[id].r) >> 1;
if (r <= mid)
update(l, r, x, y, val, L(id));
else if (mid < l)
update(l, r, x, y, val, R(id));
else{
update(l, mid, x, y, val, L(id));
update(mid + 1, r, x, y, val, R(id));
}
}
void query(int l, int r, int x, int y, int id){
if (l == r){
T[l].Q(x, y);
Max = max(Max, T[l].Max);
Min = min(Min, T[l].Min);
return;
}
int mid = (t[id].l + t[id].r) >> 1;
if (r <= mid)
query(l, r, x, y, L(id));
else if (mid < l)
query(l, r, x, y, R(id));
else{
query(l, mid, x, y, L(id));
query(mid + 1, r, x, y, R(id));
}
}
void Q(int l, int r, int x, int y){
Max = -inf; Min = inf;
query(l, r, x, y, 1);
}
void P(int l, int r, int x, int y, int val){
update(l, r, x, y, val, 1);
}
};
int n, m;
Two_Dimension_Segment_Tree tree;
void input(){
rd(n); rd(m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)rd(a[i][j]);
}
int main(){
input();
tree.M = m;
tree.build(1, n, 1);
int q; rd(q);
string s; int l, r, x, y, val;
while (q-- > 0){
cin >> s;
if (s[0] == 'q'){
rd(l); rd(x); rd(r); rd(y);
tree.Q(l, r, x, y);
printf("%d %d\n", tree.Max, tree.Min);
}
else {
rd(x); rd(y); rd(val);
tree.P(x, x, y, y, val);
}
}
return 0;
}java:
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;
public class Main {
static int N = 550;
static int inf = 1000*1000*1000;
int[][] a = new int[N][N];
class Segment_Tree{
class Node{
int l, r, max, min, lazy;
Node(){}
Node(int l, int r, int max, int min){
this.l = l; this.r = r; this.max = max; this.min = min;
lazy = inf;
}
}
public Node[] t = new Node[N<<2];
public int pos = 0, Max, Min;
int L(int x){return x<<1;}
int R(int x){return x<<1|1;}
void up(int id){
t[id].max = max(t[L(id)].max, t[R(id)].max);
t[id].min = min(t[L(id)].min, t[R(id)].min);
t[id].lazy = inf;
}
void down(int id){
if(t[id].lazy != inf){
t[L(id)].max = t[R(id)].max = t[id].lazy;
t[L(id)].min = t[R(id)].min = t[id].lazy;
t[L(id)].lazy = t[R(id)].lazy = t[id].lazy;
t[id].lazy = inf;
}
}
public void build(int l, int r, int id){
t[id] = new Node(l, r, 0, 0);
if(l == r){
t[id].min = t[id].max = a[pos][l];
return ;
}
int mid = (l+r)>>1;
build(l, mid, L(id)); build(mid+1, r, R(id));
up(id);
}
void update(int l, int r, int val, int id){
if(l == t[id].l && r == t[id].r){
t[id].max = t[id].min = t[id].lazy = val;
return ;
}
down(id);
int mid = (t[id].l + t[id].r)>>1;
if(r <= mid)
update(l, r, val, L(id));
else if(mid < l)
update(l, r, val, R(id));
else{
update(l, mid, val, L(id));
update(mid+1, r, val, R(id));
}
up(id);
}
void query(int l, int r, int id){
if(l == t[id].l && r == t[id].r){
Min = min(Min, t[id].min);
Max = max(Max, t[id].max);
return;
}
down(id);
int mid = (t[id].l + t[id].r)>>1;
if(r <= mid)
query(l, r, L(id));
else if(mid < l)
query(l, r, R(id));
else{
query(l, mid, L(id));
query(mid+1, r, R(id));
}
}
public void Q(int l, int r){
Max = -inf; Min = inf;
query(l, r, 1);
}
public void P(int l, int r, int val){
update(l, r, val, 1);
}
}
class Two_Dimension_Segment_Tree{
class Node{
int l, r;
Node(){}
Node(int l, int r){
this.l = l; this.r = r;
}
}
Node[] t = new Node[N<<2];
Segment_Tree[] T = new Segment_Tree[N];
int Max, Min, M;
int L(int x){return x<<1;}
int R(int x){return x<<1|1;}
void build(int l, int r, int id){
t[id] = new Node(l, r);
// System.out.println(l+" "+r);
if(l == r){
T[l] = new Segment_Tree();
T[l].pos = l;
T[l].build(1, M, 1);
return ;
}
int mid = (l+r)>>1;
build(l, mid, L(id)); build(mid+1, r, R(id));
}
void update(int l, int r, int x, int y, int val, int id){
if(l == r){
T[l].P(x, y, val);
return ;
}
int mid = (t[id].l + t[id].r)>>1;
if(r <= mid)
update(l, r, x, y, val, L(id));
else if(mid < l)
update(l, r, x, y, val, R(id));
else{
update(l, mid, x, y, val, L(id));
update(mid+1, r, x, y, val, R(id));
}
}
void query(int l, int r, int x, int y, int id){
if(l == r){
T[l].Q(x, y);
Max = max(Max, T[l].Max);
Min = min(Min, T[l].Min);
return;
}
int mid = (t[id].l + t[id].r)>>1;
if(r <= mid)
query(l, r, x, y, L(id));
else if(mid < l)
query(l, r, x, y, R(id));
else{
query(l, mid, x, y, L(id));
query(mid+1, r, x, y, R(id));
}
}
void Q(int l, int r, int x, int y){
Max = -inf; Min = inf;
query(l, r, x, y, 1);
}
void P(int l, int r, int x, int y, int val){
update(l, r, x, y, val, 1);
}
}
int n, m;
Two_Dimension_Segment_Tree tree = new Two_Dimension_Segment_Tree();
void input(){
n = cin.nextInt(); m = cin.nextInt();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)a[i][j] = cin.nextInt();
}
void work() {
input();
tree.M = m;
tree.build(1, n, 1);
int q; q = cin.nextInt();
String s; int l, r, x, y, val;
while(q-- > 0){
s = cin.next();
if(s.charAt(0) == 'q'){
l = cin.nextInt(); x = cin.nextInt(); r = cin.nextInt(); y =cin.nextInt();
tree.Q(l, r, x, y);
out.println(tree.Max+" "+tree.Min);
}
else {
x = cin.nextInt(); y = cin.nextInt(); val = cin.nextInt();
tree.P(x, x, y, y, val);
}
}
}
Main() {
cin = new Scanner(System.in);
out = new PrintWriter(System.out);
}
public static void main(String[] args) {
Main e = new Main();
e.work();
out.close();
}
public Scanner cin;
public static PrintWriter out;
class Queue {
int[] queue = new int[100000];
int front, rear;
void clear() {
front = rear = 0;
}
boolean empty() {
return front == rear;
}
int size() {
return rear - front;
}
void push(int x) {
queue[rear++] = x;
}
int top() {
return queue[front];
}
void pop() {
front++;
}
}
int max(int x, int y) {
return x > y ? x : y;
}
int min(int x, int y) {
return x < y ? x : y;
}
double max(double x, double y) {
return x > y ? x : y;
}
double min(double x, double y) {
return x < y ? x : y;
}
static double eps = 1e-8;
double abs(double x) {
return x > 0 ? x : -x;
}
boolean zero(double x) {
return abs(x) < eps;
}
}Uva 11297 Census 二维线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。