hdu 3333 선분 트 리 오프라인 작업

이 문 제 는 일반적인 선분 트 리 와 다 릅 니 다. 온라인 알고리즘 을 사용 하면 실패 합 니 다. 제 가 이해 하면 모든 노드 가 저장 해 야 할 정 보 는 앞 에 있 는 데이터 와 관련 이 있 기 때 문 입 니 다.일반적인 선분 트 리 와 는 달리 하위 노드 의 정보 와 만 관련 이 있 습 니 다.
우선 검색 구간 의 오른쪽 값 에 따라 정렬 합 니 다.그 다음 에 데 이 터 를 삽입 하여 모든 수 를 선분 트 리 에 넣 을 때 먼저 판단 한 다음 에 그 가 온라인 트 리 가 있 는 지 없 는 지 판단 하고 있 으 면 삭제 하고 그의 위 치 를 현재 점 으로 업데이트 합 니 다.

#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
#include<map>  
using namespace std;  
typedef __int64 ll;  
#define N 300010  
#define M 100010  
struct   
{  
    int l,r;  
    ll num;  
}root[N*4];  
struct Q  
{  
    int s,t,ind;  
}q[M];  
bool cmp(Q i,Q j)  
{  
    return i.t<j.t;  
}  
inline void build(int t,int x,int y)  
{  
    root[t].l=x;  
    root[t].r=y;  
    root[t].num=0;  
    if(x==y) return;  
    int m=(x+y)>>1;  
    build(t*2,x,m);  
    build(t*2+1,m+1,y);  
}  
inline void Modefiy(int t,int x,ll val)  
{  
    int l=root[t].l;  
    int r=root[t].r;  
    if(l==r)  
    {  
        root[t].num+=val;return;  
    }  
    int m=(l+r)>>1;  
    if(x<=m) Modefiy(t*2,x,val);  
    else Modefiy(t*2+1,x,val);  
    root[t].num=root[t*2].num+root[t*2+1].num;  
}  
inline ll query(int t,int x,int y)  
{  
    int l=root[t].l;  
    int r=root[t].r;  
    if(l==x&&r==y)  
    {  
        return root[t].num;  
    }  
    int m=(l+r)>>1;  
    ll ans=0;  
    if(x<=m) ans+=query(t*2,x,min(m,y));  
    if(y>m) ans+=query(t*2+1,max(m+1,x),y);  
    return ans;  
}  
  
int t,n,qn;  
ll a[N];  
map<ll,int>m;  
ll ans[M];  
int main()  
{  
    scanf("%d",&t);  
    while(t--)  
    {  
        m.clear();  
        scanf("%d",&n);  
        for(int i=1;i<=n;i++) scanf("%I64d",&a[i]);  
        build(1,1,n);  
        scanf("%d",&qn);  
        for(int i=0;i<qn;i++)  
        {  
            scanf("%d%d",&q[i].s,&q[i].t);  
            q[i].ind=i;  
        }  
        sort(q,q+qn,cmp);  
        int k=1;  
        for(int i=0;i<qn;i++)  
        {  
            for(;k<=q[i].t;k++)  
            {  
                if(m[a[k]]!=0) Modefiy(1,m[a[k]],-a[k]);  
                m[a[k]]=k;  
                Modefiy(1,k,a[k]);  
            }  
            ans[q[i].ind]=query(1,q[i].s,q[i].t);  
        }  
        for(int i=0;i<qn;i++) printf("%I64d
",ans[i]);  
    }  
    return 0;  
}