bzoj 2743 (트 리 배열)

전송 문 문제 풀이: 구간 에 기여 하 는 수 는 왼쪽 끝 점 에서 뒤로 두 번 째 로 나타 나 는 수 입 니 다.처음에는 두 번 째 로 나타 나 는 위 치 를 트 리 배열 에 삽입 한 다음 에 구간 을 x 순 으로 왼쪽 에서 오른쪽으로 쓸 고 점 i 를 삭제 할 때마다 nxt [i] (i 위치의 다음 에 나타 나 는 위치) 를 트 리 배열 에서 삭제 한 다음 nxt [nxt [i] 를 추가 하여 각 구간 에 오른쪽 점 으로 트 리 배열 에 있 는 query 를 왼쪽 끝 점 의 query 를 빼 면 됩 니 다.(그러나 Po 할 아버 지 는 감법 을 하지 않 아 도 지나 가 셨 습 니 다. 본 건 33951 ° 33979 ° 는 이미 질문 을 보 내 '공식 적 인' 해석 을 기다 리 고 있 습 니 다...)

#include
using namespace std;
const int MAXN=1e6+2;
int n,waste,m;
int a[MAXN],pre[MAXN],nxt[MAXN],c[MAXN],ans[MAXN];
struct Q {
    int x,y,id;
    friend bool operator return a.xx;
    }
}q[MAXN];
bool vis[MAXN];
inline int read() {
    int x=0;char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x;
}
inline void modify(int pos,int val) {
    for (int i=pos;i<=n;i+=(i&-i)) c[i]+=val;
}
inline int query(int pos) {
    int ret=0;
    for (int i=pos;i;i-=(i&-i)) ret+=c[i];
    return ret;
}
int main() {
//  freopen("bzoj 2743.in","r",stdin);
    memset(vis,false,sizeof(vis));
    memset(pre,0,sizeof(pre));
    n=read(),waste=read(),m=read();
    for (register int i=1;i<=n;++i) a[i]=read();
    for (register int i=1;i<=n;++i) {
        if (pre[a[i]]) nxt[pre[a[i]]]=i;
        else vis[i]=true;
        pre[a[i]]=i;
    }
    for (register int i=1;i<=n;++i)
        if (vis[i]&&nxt[i]) modify(nxt[i],1);
    for (register int i=1;i<=m;++i) q[i].x=read(),q[i].y=read(),q[i].id=i;
    sort(q+1,q+m+1);
    int now=1;
    for (register int i=1;i<=m;++i) {
        while (now<q[i].x) {
            if (nxt[now]) {
                modify(nxt[now],-1);
                if (nxt[nxt[now]])
                    modify(nxt[nxt[now]],1);
            }
            ++now;
        }
        ans[q[i].id]=query(q[i].y)-query(q[i].x);
    }
    for (register int i=1;i<=m;++i) printf("%d
",ans[i]);
    return 0;
}