hdu 2888 2 차원 선분 트 리 와 2 차원 ST 모델
20500 단어 데이터 구조
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 500;
struct Nodey
{
int l,r;
int Max,Min;
};
int locy[MAXN],locx[MAXN];
struct Nodex
{
int l,r;
Nodey sty[MAXN*4];
void build(int i,int _l,int _r)
{
sty[i].l = _l;
sty[i].r = _r;
sty[i].Max = -INF;
sty[i].Min = INF;
if(_l == _r)
{
locy[_l] = i;
return;
}
int mid = (_l + _r)/2;
build(i<<1,_l,mid);
build((i<<1)|1,mid+1,_r);
}
int queryMin(int i,int _l,int _r)
{
if(sty[i].l == _l && sty[i].r == _r)
return sty[i].Min;
int mid = (sty[i].l + sty[i].r)/2;
if(_r <= mid)return queryMin(i<<1,_l,_r);
else if(_l > mid)return queryMin((i<<1)|1,_l,_r);
else return min(queryMin(i<<1,_l,mid),queryMin((i<<1)|1,mid+1,_r));
}
int queryMax(int i,int _l,int _r)
{
if(sty[i].l == _l && sty[i].r == _r)
return sty[i].Max;
int mid = (sty[i].l + sty[i].r)/2;
if(_r <= mid)return queryMax(i<<1,_l,_r);
else if(_l > mid)return queryMax((i<<1)|1,_l,_r);
else return max(queryMax(i<<1,_l,mid),queryMax((i<<1)|1,mid+1,_r));
}
}stx[MAXN*4];
int n;
void build(int i,int l,int r)
{
stx[i].l = l;
stx[i].r = r;
stx[i].build(1,1,n);
if(l == r)
{
locx[l] = i;
return;
}
int mid = (l+r)/2;
build(i<<1,l,mid);
build((i<<1)|1,mid+1,r);
}
//
void Modify(int x,int y,int val)
{
int tx = locx[x];
int ty = locy[y];
stx[tx].sty[ty].Min = stx[tx].sty[ty].Max = val;
for(int i = tx;i;i >>= 1)
for(int j = ty;j;j >>= 1)
{
if(i == tx && j == ty)continue;
if(j == ty)
{
stx[i].sty[j].Min = min(stx[i<<1].sty[j].Min,stx[(i<<1)|1].sty[j].Min);
stx[i].sty[j].Max = max(stx[i<<1].sty[j].Max,stx[(i<<1)|1].sty[j].Max);
}
else
{
stx[i].sty[j].Min = min(stx[i].sty[j<<1].Min,stx[i].sty[(j<<1)|1].Min);
stx[i].sty[j].Max = max(stx[i].sty[j<<1].Max,stx[i].sty[(j<<1)|1].Max);
}
}
}
int queryMax(int i,int x1,int x2,int y1,int y2)
{
if(stx[i].l == x1 && stx[i].r == x2)
return stx[i].queryMax(1,y1,y2);
int mid = (stx[i].l + stx[i].r)/2;
if(x2 <= mid)return queryMax(i<<1,x1,x2,y1,y2);
else if(x1 > mid)return queryMax((i<<1)|1,x1,x2,y1,y2);
else return max(queryMax(i<<1,x1,mid,y1,y2),queryMax((i<<1)|1,mid+1,x2,y1,y2));
}
int a[MAXN][MAXN];
int main()
{
int nn, mm;
while (~scanf("%d%d",&nn, &mm)) {
int fn = nn, fm = mm;
n = max(nn, mm);
build(1,1,n);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
{
int b;
if (i <= fn && j <= fm) {
scanf("%d", &b);
Modify(i, j, b);
a[i][j] = b;
}
else
Modify(i, j, 0);
}
int q;
scanf("%d",&q);
while(q--)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d",&x1,&y1,&x2, &y2);
int maxx = queryMax(1, x1, x2, y1, y2);
int flag = 0;
if (a[x1][y1] == maxx)
flag = 1;
else if (a[x2][y1] == maxx)
flag = 1;
else if (a[x1][y2] == maxx)
flag = 1;
else if (a[x2][y2] == maxx)
flag = 1;
if (flag == 1)
printf("%d yes
", maxx);
else
printf("%d no
", maxx);
}
}
return 0;
}
ST
#include
#include
#include
#include
using namespace std;
#define N 305
#define M 11
#define INF 0x3f3f3f3f
int row,col;
int __pow[M];
int dp[N][M][N][M];
int a[N][N];
bool check(int res , int r1 , int c1 , int r2 , int c2)
{
if(res == a[r1][c1] || res == a[r1][c2] || res == a[r2][c1] || res == a[r2][c2]) return true;
return false;
}
inline int max(int aa ,int bb ,int cc ,int dd)
{
int res = -INF;
res = aa > res ? aa : res;
res = bb > res ? bb : res;
res = cc > res ? cc : res;
res = dd > res ? dd : res;
return res;
}
void ST()
{
int KR = (int)(log((double)row) / log(2.0));
int KC = (int)(log((double)col) / log(2.0));
for(int i=1; i<=row; i++) // dp[i][0][j][0]
for(int j=1; j<=col; j++)
dp[i][0][j][0] = a[i][j];
for(int i=1; i<=row; i++) // dp[i][0][j][p]
for(int pc=1; pc<=KC; pc++)
for(int j=1; j+__pow[pc]-1<=col; j++)
{
int kc = j + __pow[pc-1];
int x = dp[i][0][j][pc-1] , y = dp[i][0][kc][pc-1];
dp[i][0][j][pc] = x > y ? x : y;
}
for(int j=1; j<=col; j++) // dp[i][p][j][0]
for(int pr=1; pr<=KR; pr++)
for(int i=1; i+__pow[pr]-1<=row; i++)
{
int kr = i + __pow[pr-1];
int x = dp[i][pr-1][j][0] , y = dp[kr][pr-1][j][0];
dp[i][pr][j][0] = x > y ? x : y;
}
for(int pr=1; pr<=KR; pr++)
for(int pc=1; pc<=KC; pc++)
for(int i=1; i+__pow[pr]-1<=row; i++)
for(int j=1; j+__pow[pc]-1<=col; j++)
{
int kr = i + __pow[pr-1];
int kc = j + __pow[pc-1];
dp[i][pr][j][pc] = max(dp[i][pr-1][j][pc-1] , dp[i][pr-1][kc][pc-1] , dp[kr][pr-1][j][pc-1] , dp[kr][pr-1][kc][pc-1]);
}
}
int RMQ(int r1 , int c1 , int r2 , int c2)
{
int KR = (int)(log((double)(r2-r1+1)) / log(2.0));
int KC = (int)(log((double)(c2-c1+1)) / log(2.0));
int kr = r2 - __pow[KR] + 1;
int kc = c2 - __pow[KC] + 1;
return max(dp[r1][KR][c1][KC] , dp[r1][KR][kc][KC] , dp[kr][KR][c1][KC] , dp[kr][KR][kc][KC]);
}
int main()
{
for(int i=0; i1<while(scanf("%d%d",&row,&col)!=EOF)
{
for(int i=1; i<=row; i++)
for(int j=1; j<=col; j++)
scanf("%d",&a[i][j]);
ST();
int q;
scanf("%d",&q);
while(q--)
{
int ok = 0,r1,c1,r2,c2;
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
int res = RMQ(r1,c1,r2,c2);
printf("%d ",res);
if(check(res ,r1,c1,r2,c2)) printf("yes
");
else printf("no
");
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.