hdu 3874 / hdu 3333 선분 수 구간 구 화

#include
#include
#include
#include
#define LL long long
using std::sort;

const int nsize=53333;
const int msize=221111;

LL ans[msize];
LL sum[nsize<<2];
int pos[nsize];
int change[nsize];

struct Number
{
    int k;
    int idx;
} num[nsize],tmp[nsize];

struct question
{
    int l,r;
    int idx;
} qu[msize];

bool cmp1(question a1,question a2)
{
    if (a1.r!=a2.r) return a1.r>1;
    build(rt<<1,l,m);
    build(rt<<1|1,m+1,r);
}

void PushUp(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void update(int rt,int l,int r,int p,int v)
{
    if (l==r)
    {
        sum[rt]=v;
        return ;
    }
    int m=(l+r)>>1;
    if (p<=m) update(rt<<1,l,m,p,v);
    else update(rt<<1|1,m+1,r,p,v);
    PushUp(rt);
}

LL query(int rt,int l,int r,int L,int R)
{
    if (L<=l&&r<=R) return sum[rt];
    int m=(l+r)>>1;
    LL cnt=0;
    if (L<=m) cnt+=query(rt<<1,l,m,L,R);
    if (R>m)  cnt+=query(rt<<1|1,m+1,r,L,R);
    return cnt;
}

int main()
{
    int T,i,j,x,n,q;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        for (i=1; i<=n; i++)
        {
            num[i].idx=tmp[i].idx=i;
            scanf("%d",&num[i].k);
            tmp[i].k=num[i].k;
        }
        scanf("%d",&q);
        for (i=1; i<=q; i++)
        {
            qu[i].idx=i;
            scanf("%d %d",&qu[i].l,&qu[i].r);
        }
        build(1,1,n);
        sort(qu+1,qu+q+1,cmp1);
        sort(tmp+1,tmp+n+1,cmp2);
        memset(pos,0,sizeof(pos));
        change[tmp[1].idx]=1;
        for (x=1,i=2; i<=n; i++)
        {
            if (tmp[i].k!=tmp[i-1].k) x++;
            change[tmp[i].idx]=x;
        }
        for (j=i=1; i<=q;)
        {
            while (j<=qu[i].r&&j<=n)
            {
                if (pos[change[num[j].idx]]>0)
                    update(1,1,n,pos[change[num[j].idx]],0);
                pos[change[num[j].idx]]=j;
                update(1,1,n,j,num[j].k);
                j++;
            }
            while (qu[i].r