hdu 5919 Sequence II 主席树

Sequence II

题意：给出原数列。每次询问一个区间时，把各个数字在这个区间中第一次出现的位置记作 $p_{1},p_{2},\cdots, p_{k}$ ，满足 $p_{1} < p_{2} < \cdots < p_{k}$ ，求 $p_{\lceil \frac{k}{2}\rceil}$ 。询问强制在线。

题解：camp 的题解搞得我莫名其妙。。。 $O(Mlog^{2}N)$ 明显过不了吧。。。

因为我重现赛的时候就是强行套了一个二分变成了这个复杂度。。。
本来我学主席树就是因为长春比完有人说要用到主席树。。。结果我还是没做出来= =
其实只要做过 SPOJ DQUERY 的应该都知道吧。。。然而我没做过
反正就是反着插进去插过的先删除就行了。。。
于是我又犯了一个很傻逼的错误。。。我以为一个一个读插进去和全读了反着插进去是一样的。。。从晚上WA到早上根本想不到是因为这个。。。最近输出很不稳定啊 OTZ

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int,int> PII;

const int N=2e5+5;
const int M=40*N;
int T[N],po[N],a[N];
struct Seg {
    int ls,rs,v;
} tr[M];
int tot,C,n,m;

void read(int &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x=c-'0';
    while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';
}

int build(int l,int r)
{
    int rt=++tot;
    tr[rt].v=0;
    if (l==r) {
        tr[rt].ls=tr[rt].rs=0;
        return rt;
    }
    int m=l+r>>1;
    tr[rt].ls=build(l,m);
    tr[rt].rs=build(m+1,r);
    return rt;
}

int update(int rt,int l,int r,int pos,int d)
{
    int newrt=++tot;
    tr[newrt].v=tr[rt].v+d;
    if (l==r) return newrt;
    int m=l+r>>1;
    if (pos<=m) {
        tr[newrt].rs=tr[rt].rs;
        tr[newrt].ls=update(tr[rt].ls,l,m,pos,d);
    } else {
        tr[newrt].ls=tr[rt].ls;
        tr[newrt].rs=update(tr[rt].rs,m+1,r,pos,d);
    }
    return newrt;
}

int getsum(int rt,int l,int r,int L,int R)
{
    if (L<=l&&r<=R) return tr[rt].v;
    int m=l+r>>1;
    int res=0;
    if (L<=m) res+=getsum(tr[rt].ls,l,m,L,R);
    if (m<R) res+=getsum(tr[rt].rs,m+1,r,L,R);
    return res;
}

int query(int rt,int l,int r,int k)
{
    if (l==r) return l;
    int m=l+r>>1;
    int tmp=tr[tr[rt].ls].v;
    if (k<=tmp) return query(tr[rt].ls,l,m,k);
    else return query(tr[rt].rs,m+1,r,k-tmp);
}

void case_init()
{
    tot=0;
    T[n+1]=build(1,n);
    memset(po,-1,sizeof(po));
}

int main()
{
    read(C);
    for (int t=1; t<=C; t++) {
        read(n);
        read(m);
        for (int i=1;i<=n;i++)
            read(a[i]);
        case_init();
        for (int i=n; i; i--) {
            if (po[a[i]]==-1) {
                T[i]=update(T[i+1],1,n,i,1);
            } else {
                int tmp=update(T[i+1],1,n,po[a[i]],-1);
                T[i]=update(tmp,1,n,i,1);
            }
            po[a[i]]=i;
        }
        printf("Case #%d:",t);
        int ans=0;
        while (m--) {
            int p,q,l,r;
            read(p);
            read(q);
            p=(p+ans)%n+1;
            q=(q+ans)%n+1;
            l=min(p,q);
            r=max(p,q);
            int k=getsum(T[l],1,n,l,r);
            ans=query(T[l],1,n,(k+1)/2);
            printf(" %d",ans);
        }
        puts("");
    }
    return 0;
}