hdu 5454 흥 분 된 데이터베이스 (선분 트 리)

hdu5454 Excited Database
선분 트 리 구간 업데이트 관건 은 생각 하고 어떻게 쓰 느 냐 하 는 것 이다.
경 기 는 2 차원 트 리 같은 거. 어떻게 업 데 이 트 를 해 야 할 지 몰라 서 버 렸 어 요.
문제 풀이 에서 말 한 유지보수 a [i] * i a [i] 와 사실은 이렇다.
만약 에 우리 가 4 * 3 의 행렬 이 있다 고 가정 하면 이 사각형 의 각 칸 의 X + Y 값 에 대해
2 3 4
3 4 5
4 5 6
5 6 7
우 리 는 이 행렬 의 모든 칸 을 분류 합 니 다.
x+y
2
3
4
5
6
7
개수
1
2
3
3
2
1
점차 증가 하 다
1
2
3
4
 
 
점차 줄다
 
 
4
3
2
1
화해시키다
1
2
7
7
2
1
원 하 는 개수
0
0
4
4
0
0
이렇게 하면 우 리 는 1, 2 조작 과 3 조작 의 관 계 를 찾 을 수 있다.
화차
몇 개 만 더 가 져 오 면 관 계 를 맺 을 수 있어 요.
그래서 2 차원 라인 트 리 가 아 닌 두 개의 라인 트 리 를 유지 합 니 다.
유지 보수 a [i], a [i] * i, a [i] * (n - i) 
유지 보수 a [i] * i  바로 ((l + r) * (r - l + 1) / 2) * x  이것 은 비교적 상용 된다.

#include 
#define lson num<<1
#define rson num<<1|1
#define gl l,m,lson
#define gr m+1,r,rson
#define PARA int l=1,int r=n,int num=1
using namespace std;
const int MAXN = 2e5+100;

template 
inline bool scan_d(T &ret) {
   char c; int sgn;
   if(c=getchar(),c==EOF) return 0; //EOF
   while(c!='-'&&(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;
}

int n;
struct SegTree
{
    struct Node
    {
        long long v,vl,vr;
        int add;
        void mark(long long l,long long r,long long x)
        {
            add+=x;
            v+=(r-l+1)*x;
            vl+=(((l+r)*(r-l+1))/2)*x;
            r=n-r+1;
            l=n-l+1;
            swap(l,r);
            vr+=(((l+r)*(r-l+1))/2)*x;
        }
    }st[MAXN<<3];

    void init()
    {
        memset(st,0,sizeof(st));
    }

    void pushUp(int num)
    {
        st[num].v=st[lson].v+st[rson].v;
        st[num].vl=st[lson].vl+st[rson].vl;
        st[num].vr=st[lson].vr+st[rson].vr;
    }

    void pushDown(int l,int r,int num)
    {
        int &v=st[num].add;
        int m=l+r>>1;
        if(l!=r)
        {
            st[lson].mark(l,m,v);
            st[rson].mark(m+1,r,v);
            pushUp(num);
        }
        v=0;
    }
    void update(int a,int b,PARA)
    {
        int m=l+r>>1;
        pushDown(l,r,num);
        if(a<=l&&r<=b)
            st[num].mark(l,r,1);
        else
        {
            if(b<=m)
                update(a,b,gl);
            else if(a>m)
                update(a,b,gr);
            else
                update(a,b,gl),update(a,b,gr);
            pushUp(num);
        }
    }
    long long ret[3];
    void query(int a,int b,PARA)
    {
        int m=l+r>>1;
        pushDown(l,r,num);
        if(a<=l&&r<=b)
            ret[0]+=st[num].v,ret[1]+=st[num].vl,ret[2]+=st[num].vr;
        else
        {
            if(b<=m)
                query(a,b,gl);
            else if(a>m)
                query(a,b,gr);
            else
                query(a,b,gl),query(a,b,gr);
            pushUp(num);
        }
    }

    long long count(long long d,long long len,long long s)
    {
        /**
             
        */
        long long v=0;
        memset(ret,0,sizeof(ret));
        query(s,s+d);
        v+=ret[1]-ret[0]*(s-1);

        memset(ret,0,sizeof(ret));
        query(s+len-d-1,s+len-1);
        v+=ret[2]-ret[0]*(n-s-len+1);

        memset(ret,0,sizeof(ret))/
        query(s+len-d-1,s+d);
        v-=ret[0]*(d+1);
        return v;
    }
}soul[2];
/**
0: /
1: \
*/

int main()
{
    int T,m,on,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        scan_d(on);
        scan_d(m);
        n=2*on-1;
        soul[0].init();
        soul[1].init();
        printf("Case #%d:
",cas++);
        while(m--)
        {
            int a,x1,x2,y1,y2;
            scan_d(a);
            scan_d(x1);
            scan_d(x2);
            if(a==1)
                soul[0].update(x1-1,x2-1);
            else if(a==2)
                soul[1].update(x1+on,x2+on);
            else
            {
                scan_d(y1);
                scan_d(y2);
                int d=max(x2-x1,y2-y1);
                int len=x2-x1+y2-y1+1;
                printf("%lld
",soul[0].count(d,len,x1+y1-1)+soul[1].count(d,len,x1-y2+on));
            }
        }
    }
    return 0;
}