POJ - 2155: Matrix (2 차원 트 리 또는 2 차원 트 리 배열)

제목 링크: 클릭 하여 링크 열기
제목 의 대의:
2 차원 표를 드 리 겠 습 니 다. 두 가지 조작 을 수행 하 겠 습 니 다. 첫 번 째 는 왼쪽 상단 과 오른쪽 하단 의 좌 표를 드 리 겠 습 니 다. 이 사각형 안의 수 를 뒤 집 으 면 0 이 1 이 되 고 1 이 0 이 됩 니 다.두 번 째 조작 은 어떤 점 의 현재 값 을 조회 하 는 것 이다.
문제 풀이 방향:
이 문 제 는 2 차원 나무 모양 의 배열 과 2 차원 선분 나무 두 가지 방법 이 있다.다음은 각각 설명 하 겠 습 니 다.
트 리 배열:
2 차원 트 리 모양 의 배열 은 이해 하기 쉽 고 코드 도 간단 하 며 마지막 에 시간 이 많이 걸 리 지 않 는 것 같 습 니 다.간단 한 조작 으로 문제 의 요 구 를 실현 할 수 있다.
제목 이 p1, q1 p2, q2 를 업데이트 하 라 고 가정 하면 p1, q1, 뒤의 점 을 모두 1 을 추가 한 다음 에 제목 요구 에 부합 되 지 않 는 구역 을 1, 즉 p2 + 1, q1 로 줄 일 수 있 습 니 다. 화해시키다 p1, q2 + 1. 그러나 이렇게 되면 오른쪽 아래 부분 이 두 번 중복 감 소 됩 니 다. 따라서 오른쪽 아래 부분 + 1, 즉 p2 + 1, q2 + 1 을 뒤에 1 을 추가 합 니 다. 조회 할 때 직접 조회 하면 됩 니 다.아래 에 트 리 배열 의 코드 를 붙 입 니 다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
int n,m;
char c;
int d[1005][1005];
void add(int i,int j,int x)     //        ,     
{
    while(i<=n)
    {
        int jj=j;
        while(jj<=n)
        {
            d[i][jj]+=x;
            jj += jj&-jj;
        }
        i += i&-i;
    }
}
int sum(int i,int j)
{
    int s=0;
    while(i>0)
    {
        int jj=j;
        while(jj>0)
        {
            s=s+d[i][jj];
            jj -= jj&-jj;
        }
        i -= i&-i;
    }
    return s;
}
int main()
{
    int QAQ;
    scanf("%d",&QAQ);
    while(QAQ--)
    {
        int p1,q1,p2,q2;
        scanf("%d%d",&n,&m);
        memset(d,0,sizeof(d));    //     
        for(int i=0;i

선분 트 리 부분:
선분 트 리 는 2 차원 선분 트 리 를 사용 해 야 하 며, 내 가 처음으로 쓴 2 차원 선분 트 리 이기 도 하 다.처음 엔 진짜 로 어떻게 쓰 는 지 몰랐어 요.어차피 4 분 의 나 무 를 마구 썼 는데 뭐 가 틀 렸 는 지 모 르 겠 어. 미 친 RE. 그리고 나중에 인터넷 에 가서 찾 아 봤 어.
2 차원 선분 수 는 두 가지 가 있 는 것 같 습 니 다. 하 나 는 방금 말 한 4 분 수 입 니 다. 그러나 4 분 수 는 어떤 경우 에는 시간 복잡 도가 매우 높 습 니 다.그리고 내 가 미 쳐 서 RE 도 왜 그런 지 모 르 겠 어.나중에 다른 나무 로 나 무 를 묶 는 방법 을 배 웠 다.즉, x 에 대응 하 는 모든 노드 에 도 하나의 라인 트 리 가 있 는데 처음에 도 유지 하려 고 했 던 문제 가 있 었 다. 나중에 인터넷 에 접속 하여 다른 사람의 블 로 그 를 보고 나 서 야 이렇게 하지 않 아 도 되 고 업데이트 와 조회 방법 이 비교적 기묘 하 다 는 것 을 알 게 되 었 다.
업데이트 하면 요구 에 부 합 된 x 의 대응 구간 을 먼저 찾 은 다음 에 해당 하 는 y 라인 트 리 를 업데이트 하 는 것 입 니 다.그러나 이렇게 하면 검색 할 때 문제 가 생 길 수 있다. 예 를 들 어 첫 번 째 업데이트 1, 1. 10,10 。그러면 현재 구간 이 1 에서 10 이 라 고 가정 하면 현재 노드 의 y 라인 트 리 를 업데이트 합 니 다.근 데 다음 에 업데이트 되면 1, 1. 5,5 업 데 이 트 된 것 은 바로 이전 노드 의 하위 노드 의 y 라인 트 리 입 니 다. y 라인 트 리 역시 이런 문제 가 있 기 때문에 조회 할 때 주의해 야 합 니 다. 함부로 돌아 갈 수 없습니다. 그러면 이런 문 제 를 해결 하려 면 매번 의 x 노드 에서 y 라인 트 리 를 조회 하면 됩 니 다. y 라인 트 리 도 모든 노드 의 값 을 추가 합 니 다.이렇게 하면 당신 이 조회 한 값 이 빠 지지 않 았 음 을 보증 합 니 다.
사다
전체적으로 보면 이 문 제 는 간단 한 편 이 고 실현 하기 가 그리 번 거 롭 지 않 지만 나무 모양 의 배열 보다 시간 이 많이 걸 렸 습 니 다. 그리고 예전 에 선분 나 무 를 쓰 는 습관 이 구조 체 로 쓰 였 습 니 다. 이런 선분 나 무 는 갑자기 구조 체 로 쓰 지 않 았 습 니 다. 마지막 으로 wa 를 초기 화 하 는 것 을 잊 었 습 니 다. 제 코드 가 너무 못 생 긴 원인 일 수 있 습 니 다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define xlson xl,xmid,xt<<1
#define xrson xmid+1,xr,xt<<1|1
#define ylson yl,ymid,xt,yt<<1
#define yrson ymid+1,yr,xt,yt<<1|1
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
const int maxn=1010;
int n,m,ans;
int tree[maxn<<2][maxn<<2];
void update_y(int q1,int q2,int yl,int yr,int xt,int yt)    //  y   
{
    if(q1<=yl&&yr<=q2)
    {
        tree[xt][yt]++;
        return ;
    }
    int ymid=(yl+yr)>>1;
    if(q1<=ymid)
        update_y(q1,q2,ylson);
    if(q2>ymid)
        update_y(q1,q2,yrson);
}
void update_x(int p1,int q1,int p2,int q2,int xl,int xr,int xt)     //         
{
    if(p1<=xl&&xr<=p2)      //          y   
    {
        update_y(q1,q2,1,n,xt,1);
        return ;
    }
    int xmid=(xl+xr)>>1;
    if(p1<=xmid)
        update_x(p1,q1,p2,q2,xlson);
    if(p2>xmid)
        update_x(p1,q1,p2,q2,xrson);
}
void query_y(int y,int yl,int yr,int xt,int yt)     //  y      
{
    ans=ans+tree[xt][yt];       //           
    if(yl==yr) return ;
    int ymid=(yl+yr)>>1;
    if(y<=ymid)
        query_y(y,ylson);
    if(y>ymid)
        query_y(y,yrson);
}
void query_x(int x,int y,int xl,int xr,int xt)      //     x   
{
    query_y(y,1,n,xt,1);        //  x     y   
    if(xl==xr) return ;
    int xmid=(xl+xr)>>1;
    if(x<=xmid)
        query_x(x,y,xlson);
    if(x>xmid)
        query_x(x,y,xrson);
}
int main()
{
    int QAQ;
    scanf("%d",&QAQ);
    while(QAQ--)
    {
        memset(tree,0,sizeof(tree));    //     
        scanf("%d%d",&n,&m);
        char q;
        int p1,q1,p2,q2;
        for(int i=0;i

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

hunnu 11460 - 구간 최대 값 구하 기 (선분 트 리 템 플 릿)

Problem 11460 : No special judgement 길이 가 N 인 배열 을 지정 하고 q 개의 질문 이 있 습 니 다. 모든 질문 은 배열 의 한 구간 에서 그 요소 의 인자 의 개수 가 가장 큽 니...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

POJ - 2155: Matrix (2 차원 트 리 또는 2 차원 트 리 배열)

좋은 웹페이지 즐겨찾기