[模板]二维ST表
2024-10-21 16:07:51
考试yy二维ST表失败导致爆零。
其实和一维的ST表很像...
也是设$f[i][j][p][q]$为以$(i, j)$为左上角,长为$2^p$,宽为$2^q$的矩形的最大值。
算法流程是先把每一行都分别求一遍一维的ST表,然后再把行与行之间合并...
查询和一维ST表类似
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define reg register
inline int read() {
int res=;char ch=getchar();bool fu=;
while(!isdigit(ch))fu|=(ch=='-'),ch=getchar();
while(isdigit(ch))res=(res<<)+(res<<)+(ch^),ch=getchar();
return fu?-res:res;
} int n, m;
int a[][];
int st[][][][]; inline int query(int x1, int y1, int x2, int y2)
{
int k1 = log2(x2 - x1 + ), k2 = log2(y2 - y1 + );
return max(st[x1][y1][k1][k2], max(st[x2-(<<k1)+][y1][k1][k2], max(st[x1][y2-(<<k2)+][k1][k2], st[x2-(<<k1)+][y2-(<<k2)+][k1][k2])));
} int main()
{
freopen("yy.in", "r", stdin);
freopen("yy.out", "w", stdout);
n = read(), m = read();
for (reg int i = ; i <= n ; ++i)
for (reg int j = ; j <= m ; ++j)
st[i][j][][] = a[i][j] = read();
for (reg int p = ; p <= ; p ++)
for (reg int q = ; q <= ; q ++)
if (p != or q != )
for (reg int i = ; i + (<<p) - <= n ; i ++)
for (reg int j = ; j + (<<q) - <= m ; j ++)
if (!p) st[i][j][p][q] = max(st[i][j][p][q - ], st[i][j+(<<(q-))][p][q - ]);
else st[i][j][p][q] = max(st[i][j][p-][q], st[i+(<<(p-))][j][p-][q]);
int q = read();
while(q--)
{
int x1=read(),y1=read(),x2=read(),y2=read();
printf("%d\n", query(x1,y1,x2,y2));
}
return ;
}
最新文章
- Python基础篇【第7篇】: 面向对象(1)
- jdbc autoReconnect=true 参数设置导致 slow log 爆表。
- Iphone 英语语言下通讯录排序问题
- 高大上的uGUI正式版发布了
- UML 简单介绍
- 【小月博客】用HTML5的File API做上传图片预览功能
- mysql 错误代码汇总
- 01-03-03【Nhibernate (版本3.3.1.4000) 出入江湖】cascade的测试
- H - 高桥和低桥
- MySQL查询优化处理
- 【Python】Coding the Matrix:Week 5: Dimension Homework 5
- Swift语言iOS8的蓝牙Bluetooth解析
- 悬浮二维码 QQ ToTop
- JedisConnectionException: Unexpected end of stream.
- (cljs/run-at (JSVM. :all) ";一次说白DataType、Record和Protocol";)
- 201521123108 《Java程序设计》第6周学习总结
- javscript eval()的优缺点与web安全防范
- 图片转base64上传,视频同理。
- jupyter Notebook环境搭建
- C#-vs2012学习笔记-惊奇于vs的强大和便利